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

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

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

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

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

См. также

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

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.