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

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

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

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

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

См. такжеПравить

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