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

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

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

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

См. также

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