Структуры данных и модели вычислений
Вычислимость и разрешимость
Упорядоченный набор из слов в алфавите
называется -местным набором над . Множество всех -местных наборов над обозначим через . Любое подмножество множества называется -местным словарным отношением.
Любое, возможно частичное, отображение
называется -местной словарной функцией. Область определения функции обозначается через .
Результатом работы программы на входном псевдослове называется псевдослово , которое появляется на ленте в момент остановки программы; если программа работает бесконечно, то результат не определен.
Программу, которая в процессе работы над любым псевдословом
не сдвигает головку левее пробела, расположенного слева от -го слова псевдослова , будем называть -программой.
Словарное -местное отношение называется полуразрешимым, если существует -программа , которая останавливается в точности на всех псевдословах, имеющих вид
где .
Словарное -местное отношение называется разрешимым, если и полуразрешимы (под здесь понимается множество .
Словарная -местная функция называется вычислимой по Тьюрингу, если существует программа такая, что
где и , в противном случае результат не определен.
Вычислимые по Тьюрингу функции уместно было бы назвать полувычислимыми, а полувычислимые с разрешимой областью определения — вычислимыми, но это противоречит установившимся традициям.
