Упражнение

Построить машину Тьюринга, правильно вычисляющую функцию: o(x)  =  0.

Можно построить машины Тьюринга для правильного вычисления функций:

I_mⁿ(x₁,…,x_n), 1    m    n.

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

Теорема 1. Частичная функция правильно вычислима тогда и только тогда, когда она частично рекурсивна.

Тезис Чёрча и алгоритмически неразрешимые проблемы

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

Применим это для доказательства алгоритмической неразрешимости проблемы остановки машины Тьюринга, которая заключается в нахождении алгоритма, определяющего по машине Тьюринга и начальным данным, остановится ли машина через конечное число шагов. Так как машина Тьюринга задается с помощью конечного набора символов и слов, то число машин Тьюринга счетно и может быть выписано в последовательность: T₀, T₁, … .

Теорема (о проблеме остановки). Пусть T₀,T₁, T₂,… последовательность, перечисляющая все машины Тьюринга, h(n,k) – функция, принимающая значение 1, если машина T_n останавливается, начиная работу с машинного слова q₁01^k0, и принимающая значения h(n,k) = 0 в других случаях. Тогда функция h: N²  N не является частично рекурсивной. Иными словами, нет алгоритма, определяющего, остановится ли машина Тьюринга, если на вход ей подать число k.

Доказательство. От противного. Пусть функция h(n,k) частично рекурсивна. Тогда частичная функция:

f(n)  =  My[h(n,n) + y  =  0]

тоже частично рекурсивна. Существует номер m такой, что f правильно вычисляется с помощью машины T_m. Тогда f(m)  =  0, если и только если h(m,m)  =  0. Согласно определению функции h равенство h(m,m) = 0 имеет место тогда и только тогда, когда машина T_m не останавливается, начиная со слова q₁01^m0. Но f правильно вычисляется с момощью T_m , значит, T_m не остановится, начиная с m, если и только если f(m) не определено. Получаем противоречие: f(m)  =  0, если и только если f(m) не определено, Следовательно, h – не частично рекурсивна.