И вновь, согласно инструкции № 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.
Следующая таблица была составлена с помощью программы для подобных экспериментов, которая находится на сайте http://www.angio.net/pi/bigpi.cgi.
Из таблицы видно, что наша функция принимает значение 1 для первых восьми натуральных чисел, так как запись числа π содержит последовательности цифр 333, 4444, 55555, 666666, 7777777 и 88888888. Чтобы вычислить значение f(9), можно написать программу, которая будет обходить все знаки π, пока не будет найдена искомая последовательность из девяти девяток подряд. Если такая последовательность в записи π действительно существует, то программа обязательно обнаружит ее, и функция примет значение 1. Время выполнения программы в данном случае не имеет значения, поскольку, как мы неоднократно указывали, речь идет об идеальной машине, не имеющей физических ограничений, свойственных компьютерам. Однако если последовательность из девяти девяток подряд в записи π отсутствует, программа никогда не остановится, и мы не сможем определить значение f(9). Следовательно, мы никогда не сможем узнать, является ли функция f вычислимой, если только не докажем, что в записи числа π присутствует последовательность из девяти девяток подряд. Однако в этом случае программа будет бесполезной, так как из нашего доказательства будет следовать, что f(9) равно 1. Эта функция является вычислимой, хотя на первый взгляд может показаться, что это не так.
* * *
А ЧТО, ЕСЛИ ВСЕ ЕСТЬ ЧИСЛО?
В своем рассказе «Вавилонская библиотека» аргентинский писатель Хорхе Луис Борхес предполагает, что вся информация во вселенной может содержаться в единственной книге, которая «содержит бесконечное число бесконечно тонких страниц». Но зачем хранить информацию в этом громадном томе, если, возможно, она поместится в одно число? Одна из самых таинственных гипотез современной математики заключается в том, что в десятичной записи числа π, равного отношению длины окружности к ее диаметру, рано или поздно встречается любая числовая последовательность. Если это в самом деле так, то в записи этого числа содержится не только последовательность 999999999, но и числовая последовательность, кодирующая любое сообщение прошлого, настоящего и будущего.
* * *
Чтобы доказать это, нужно рассуждать точно так же, как мы рассуждали выше: так как число функций, определенных для чисел от 1 до 9 и принимающих значения 0 и 1, является конечным (в нашем случае таких функций 512 — управиться с ними будет несколько труднее, чем с функциями, определенными только для 0 и 1 и принимающими значения 0 и 1), существует машина Тьюринга, вычисляющая значение каждой из них. Это пример вычислимой функции, машину Тьюринга для которой мы не можем описать в явном виде.
Другим классом вычислимых функций являются рекурсивные функции, то есть такие функции, в которых значение f(n) можно вычислить на основе значений, которые принимает эта функция для других чисел, меньших n. Большинство функций, постоянно используемых в математике, являются рекурсивными, но все ли они вычислимы? Алан Тьюринг моментально дал отрицательный ответ на этот вопрос: существует множество функций, значение которых не сможет вычислить ни одна машина Тьюринга, более того, если выбрать функцию произвольным образом, то она почти наверняка не будет вычислимой. В то же время по другую сторону Атлантики логик Алонзо Чёрч (1903–1995) из Принстонского университета пришел к тем же выводам, разработав формальную систему, которую он назвал лямбда-исчислением. Обе эти идеи были столь новаторскими, что единственным, кого смогли найти редакторы журнала Proceedings of the London Mathematical Society для рецензирования статьи Тьюринга, оказался именно Чёрч. Так началось их плодотворное сотрудничество, прервавшееся на время войны, результатом которого стал принцип, сегодня известный под названием «тезис Чёрча — Тьюринга». Возможны и другие определения вычислимой функции, но если принять этот тезис, то все они будут эквивалентны существованию машины Тьюринга, вычисляющей значения функции.
Алонзо Чёрч, коллега Тьюринга и создатель лямбда-исчисления.
Чтобы доказать, что почти никакие функции не являются вычислимыми, Алан Тьюринг использовал хитроумный вариант диагонального метода Кантора, рассмотренный в главе 2. В ней мы рассказали, что не существует способа упорядочить список последовательностей, состоящих из нулей и единиц. Когда мы предполагали, что можем расположить одну последовательность после другой, изменяя значения элементов по диагонали, нам удалось сформировать последовательность из нулей и единиц, которая не совпадала ни с одной последовательностью в списке. Аналогичным образом можно показать, что множество функций не является счетным.
Мы указали, что функция — это отображение, сопоставляющее 0 и f(0), 1 и f(1), 2 и f(2) и т. д. до бесконечности. Следовательно, вся информация f содержится в последовательности чисел f(0), f(1), f(2), f(3)… Для простоты будем рассматривать только функции, которые принимают значения 0 и 1, например функцию f, значение которой равно 0 для четных чисел и 1 — для нечетных. В этом случае вся информация f содержится в последовательности 0101010101…, так как если мы хотим найти отображение n, достаточно перейти к n-му члену этой последовательности. Надеемся, мы убедили читателя, что функции, которые принимают только значения 0 и 1, эквивалентны бесконечным последовательностям нулей и единиц. Следовательно, множество функций не является счетным!
