Том 22. Сон разума. Математическая логика и ее парадоксы

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

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

Программа начинает выполнение первой инструкции. Так как считан 0, а инструкция гласит «Если считан 0, записать 1 и перейти к инструкции № 3», достаточно заменить 0 на 1 и посмотреть, как звучит третья инструкция.

Инструкция № 3 состоит из двух частей: первая указывает, что если считан 0, то нужно записать 1 и вернуться к инструкции № 1, однако согласно второй части этой инструкции, если считан символ 1, машина Тьюринга должна остановить работу. Так как в этом случае считан именно символ 1, программа прекращает выполнение. Следовательно, если подать на вход машины Тьюринга ленту, заполненную нулями, Т остановится после того, как запишет 1 в исходной точке.

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

Начнем с первой инструкции: так как считан символ 1, нужно сместиться вправо и перейти к инструкции № 2. Никакой загадки нет.

Теперь, согласно инструкции № 2, если считан 0, машина Тьюринга должна заменить его на 1 и перейти к инструкции № 3. Последуем этой инструкции.

И вновь, согласно инструкции № 3, машина Т должна остановиться, если считан 1, следовательно, программа прекратит выполнение, а результатом ее работы будет лента, на которой записаны две единицы посреди бесконечного множества нулей, при этом устройство чтения-записи будет располагаться рядом с единицей, записанной справа. Если мы вновь запустим эту машину Тьюринга, в результате получим ленту, на которой будет записано три единицы, таким образом Т вычисляет не что иное, как значение функции f(n) = n + 1. В общем случае функция является вычислимой, если существует машина Тьюринга, вычисляющая каждое из ее значений.

Допустим, что натуральное число n закодировано, как мы показали в предыдущем примере, путем ввода бумажной ленты, на которой записано n единиц посреди бесконечного множества нулей справа и слева, при этом устройство чтения-записи расположено на ячейке с последней единицей. Функция f будет вычислимой, если существует такая машина Тьюринга, что при вводе произвольного значения n описанным способом ее выходным значением будет f(n). Мы доказали, что функция «прибавить единицу» является вычислимой на машине Тьюринга. Так как для вычисления функции f(n) = n + 2 достаточно выполнить это же множество инструкций два раза, а для вычисления f(n) = n + 3 — трижды, операция сложения является вычислимой. Вычислимой является и операция умножения, поскольку умножить 3 на 3 означает сложить число 3 с самим собой три раза или сложить число 3 с самим собой пять раз. Мы указали, что функция является вычислимой, если существует машина Тьюринга, вычисляющая каждое из ее значений, но это не означает, что мы всегда можем найти такую машину. Рассмотрим, например, функцию, которая принимает в качестве входных и выходных значений только нули и единицы. Следовательно, достаточно определить значение f(0), которое может равняться 0 или 1, и f(1), которое также будет иметь одно из этих значений.

Читателю несложно убедиться, что существует всего четыре функции с подобными свойствами: та, которая всегда возвращает значение 0; та, значение которой всегда равно 1; та, которая при входном значении 0 принимает значение 0, при входном значении 1–1, и та, которая сопоставляет числу 0–1 и наоборот, числу 1–0.

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

Пусть на множестве чисел от 1 до 9 определена некая функция, которая ставит в соответствие n значение 1, если десятичная запись числа π содержит n последовательных цифр n (например, число 4444 для n = 4), и 0 в противном случае. Согласно этому определению f(1) равно 1, так как десятичная запись π, которая начинается с 3,141592 …, содержит 1 (это первый знак после запятой).

Аналогично f(2) также равно 1, однако чтобы найти первую последовательность цифр 22, нужно просмотреть 135 первых знаков π: …44609550582231725359408.