Эффективный процесс

Пусть задано некоторое множество $M$, часть элементов которого обладает свойством $U$. Тогда эффективным процессом (методом, алгоритмом) называется такой процесс, который для любого элемента $x\in M$позволяет за конечное число шагов выяснить, обладает ли элемент $x$ свойством $U$ или не обладает.

Полуэффективный процесс

Если элемент $x$ обладает свойством $U$, полуэффективный процесс позволяет это выявить за конечное число шагов. Если же $x$ не обладает свойством $U$, полуэффективный процесс, возможно, не сможет сказать ничего определенного об $x$ за конечное число шагов.

Таким образом, с помощью полуэффективного процесса мы либо узнаем, что $x$ обладает свойством $U$, либо не сможем ничего выяснить в отношении $x$.

См. также

• Разрешимое множество
• Алгоритмическая разрешимость формальной теории.