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

* * *

Чтобы доказать это, нужно рассуждать точно так же, как мы рассуждали выше: так как число функций, определенных для чисел от 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, эквивалентны бесконечным последовательностям нулей и единиц. Следовательно, множество функций не является счетным!

Каждая машина Тьюринга вычисляет значение единственной функции, поэтому утверждать, что все функции являются вычислимыми, можно, лишь доказав, что существует по меньшей мере столько же машин, сколько и функций, значения которых мы хотим вычислить. Однако Тьюринг установил, что бесконечное множество его машин намного меньше. Чтобы показать, что множество функций не является счетным, сначала следовало записать их в виде последовательностей из нулей и единиц. Мы можем записать в виде символов любую машину Тьюринга, поскольку она представляет собой конечную последовательность инструкций, и каждую из них можно записать несколькими символами. Как вы уже увидели, (#1,1, L , #3) означает то же, что и «Инструкция номер 1: если считан символ 1, сместиться влево и перейти к третьей инструкции». Представив машину Тьюринга как последовательность инструкций, читатель сможет найти способ, позволяющий записать все возможные машины Тьюринга в виде списка.