WikiSort.ru - Не сортированное

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

См. также

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

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