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

Перейти к навигацииПерейти к поиску

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

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

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

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

См. также