Книга шифров

Рис. 47 Алан Тьюринг.

В 1931 году Тьюринг поступил в Королевский колледж Кембриджа. Он приехал, когда шли жаркие дискуссии о природе математики и логики, и его окружали некоторые из великих людей того времени: Бертран Рассел, Альфред Норт Уайтхед и Людвиг Витгенштейн. В центре споров была статья логика Курта Геделя о неразрешимости. Всегда считалось, что, по крайней мере в теории, на все математические вопросы можно найти ответ. Однако Гедель показал, что могут существовать задачи, которые нельзя решить логическим путем, так называемые неразрешимые задачи. Математики были потрясены новостью, что, оказывается, математика не так уж всесильна, как они всегда считали. Они попытались спасти свою науку, постаравшись отыскать способ выявления неудобных неразрешимых задач с тем, чтобы суметь надежно избавиться от них. Именно эта цель в конце концов вдохновила Тьюринга написать свою самую важную математическую статью «О вычислимых числах», опубликованную в 1937 году. В пьесе «Взлом шифра» Хью Уайтмора о жизни Тьюринга кто-то спросил Алана о значении его статьи. Тот ответил: «Она об истинном и ложном. В общем смысле. Это специальная статья о математической логике, но она также и о сложности отделения истины от ошибочного высказывания. Люди, причем большинство, считают, что в математике мы всегда знаем, что истинно, а что ложно. Это отнюдь не так. Больше не так».

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

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