Эффективный процесс - NiNa.Az

Пусть задано некоторое множество ${\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}$.

См. также

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