Структуры данных и модели вычислений

         

Вычислимость и разрешимость


Упорядоченный набор из слов в алфавите

называется -местным набором над . Множество всех -местных наборов над обозначим через . Любое подмножество множества называется -местным словарным отношением.

Любое, возможно частичное, отображение

называется -местной словарной функцией. Область определения функции обозначается через .

Результатом работы программы на входном псевдослове называется псевдослово , которое появляется на ленте в момент остановки программы; если программа работает бесконечно, то результат не определен.

Программу, которая в процессе работы над любым псевдословом

не сдвигает головку левее пробела, расположенного слева от -го слова псевдослова , будем называть -программой.

Словарное -местное отношение называется полуразрешимым, если существует -программа , которая останавливается в точности на всех псевдословах, имеющих вид

где .

Словарное -местное отношение называется разрешимым, если и полуразрешимы (под здесь понимается множество .

Словарная -местная функция называется вычислимой по Тьюрингу, если существует программа такая, что

где и , в противном случае результат не определен.

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



Содержание  Назад  Вперед