Эффективный процесс
Пусть задано некоторое множество [math]\displaystyle{ M }[/math], часть элементов которого обладает свойством [math]\displaystyle{ U }[/math]. Тогда эффективным процессом (методом, алгоритмом) называется такой процесс, который для любого элемента [math]\displaystyle{ x \in M }[/math]позволяет за конечное число шагов выяснить, обладает ли элемент [math]\displaystyle{ x }[/math] свойством [math]\displaystyle{ U }[/math] или не обладает.
Полуэффективный процесс
Если элемент [math]\displaystyle{ x }[/math] обладает свойством [math]\displaystyle{ U }[/math], полуэффективный процесс позволяет это выявить за конечное число шагов. Если же [math]\displaystyle{ x }[/math] не обладает свойством [math]\displaystyle{ U }[/math], полуэффективный процесс, возможно, не сможет сказать ничего определенного об [math]\displaystyle{ x }[/math] за конечное число шагов.
Таким образом, с помощью полуэффективного процесса мы либо узнаем, что [math]\displaystyle{ x }[/math] обладает свойством [math]\displaystyle{ U }[/math], либо не сможем ничего выяснить в отношении [math]\displaystyle{ x }[/math].
См. также
- Разрешимое множество
- Алгоритмическая разрешимость формальной теории.
 | Для улучшения этой статьи по математике желательно: |