Хотя мы говорим о машине Тьюринга, название это относится к абстрактной математической модели, представляющей идеализированную машину. Тьюринг называл ее а-машиной, где «а» означает «автоматическая». Машину эту можно представить в виде ленты, разделенной на последовательные ячейки, которые могут либо быть пустыми, либо содержать какой-нибудь символ. Лента – это память машины, она ничем не ограничена, но конечна. Если вы подошли к концу, добавьте еще несколько клеток. Некая головка, размещенная над начальной ячейкой, считывает находящийся в ней символ. Затем она сверяется с таблицей, в которой размещены правила перехода (программа, заданная пользователем), записывает в клетку какой-нибудь символ (заменяя им то, что было там до этого) и сдвигает ленту на одну ячейку вперед. Затем, в зависимости от таблицы и символа, машина либо останавливается, либо выполняет инструкции, которые таблица предписывает для символа в ячейке, на которую она передвинулась.
Вариантов существует множество, но все они эквивалентны между собой в том смысле, что могут вычислять одно и то же. Мало того, эта рудиментарная машина способна, в принципе, вычислять все то же, что и цифровой компьютер, сколь угодно быстрый и продвинутый. К примеру, машина Тьюринга, использующая символы 0–9 и, возможно, еще несколько символов, может быть запрограммирована на вычисление числа π до любого заданного числа десятичных знаков, причем машина запишет их в последовательные ячейки ленты и после этого остановится. Такой уровень общности может показаться удивительным для столь простого устройства, но все тонкости вычислений изначально зашиты в таблице с правилами перехода, которые могут быть очень сложными, – в точности как все действия компьютера зашиты в программном обеспечении, которое на нем работает. Однако простота машины Тьюринга, помимо всего прочего, делает ее очень медленной в том смысле, что даже простое вычисление требует гигантского числа шагов. Она совершенно непрактична, но из-за простоты отлично подходит для разбора теоретических вопросов об ограничениях, связанных с вычислениями.
Первая важная теорема Тьюринга доказывает существование универсальной машины Тьюринга, при помощи которой можно смоделировать любую конкретную машину. Программа конкретной машины зашифрована на ленте универсальной машины еще до начала вычислений. Правила перехода сообщают универсальной машине, как следует переводить эти символы в инструкции и исполнять их. Архитектура универсальной машины – важный шаг по направлению к реальному компьютеру, где программа размещается в памяти. Мы не строим для каждой задачи новый компьютер с жестко, на уровне «железа», заданной программой – ну разве что для каких-то совершенно особых задач.
Вторая его важная теорема – вариация на тему теорем Гёделя; она доказывает, что задача останова для машины Тьюринга неразрешима. В этой задаче требуется найти алгоритм, который мог бы решить, получив на вход программу для машины Тьюринга, остановится ли машина когда-нибудь, получив ответ, или будет работать до бесконечности. Предложенное Тьюрингом доказательство, что такого алгоритма не существует – то есть что задача останова неразрешима, – предполагает его существование, а затем применяет результирующую машину к ее собственной программе. Однако она при этом хитроумно преобразуется таким образом, что модель останавливается в том, и только том случае, если первоначальная машина этого не делает. Это приводит к противоречию: если модель останавливается, то она не останавливается; если она этого не делает, то она это делает. Мы видели, что доказательство Гёделя в конечном итоге кодирует утверждение вида «это утверждение ложно». Доказательство Тьюринга проще и больше напоминает карточку, на двух сторонах которой написано:
Утверждение на другой стороне этой карточки истинно.
Утверждение на другой стороне этой карточки ложно.
Каждое утверждение за два шага приводит к отрицанию самого себя.
Тьюринг представил свою статью в журнал Proceedings of the London Mathematical Society, не зная, что несколькими неделями раньше американский специалист по математической логике Алонзо Чёрч опубликовал статью «Нерешаемая задача в элементарной теории чисел» в American Journal of Mathematics. В ней он предложил еще одну альтернативу Гёделеву доказательству неразрешимости арифметики. Доказательство Чёрча было чрезвычайно сложным, но он опубликовал его первым. Ньюман убедил журнал все же опубликовать статью Тьюринга, поскольку его доказательство было намного проще – и концептуально, и структурно. Тьюринг переработал статью, включив в нее ссылку на статью Чёрча, и в 1937 г. она вышла. У этой истории счастливый конец, поскольку после этого Тьюринг отправился в Принстон готовить докторскую диссертацию под руководством Чёрча. Его диссертация была опубликована в 1939 г. и называлась «Логические системы, основанные на ординалах».
* * *
Не слишком удачный 1939 г. был отмечен началом Второй мировой войны. Понимая, насколько велика вероятность войны, и прекрасно зная, какую серьезную роль в современной войне играет криптография, глава Секретной разведывательной службы (Secret Intelligence Service, SIS, или MI6) приобрел поместье, которое как нельзя лучше подходило для организации шифровальной школы. Блетчли-парк представлял собой особняк, выстроенный в странной смеси архитектурных стилей, на территории в 235 га. Дом был предназначен под снос, на его месте планировалось построить жилой район. Он стоит до сих пор, вместе с хозяйственными постройками и времянками военных лет; сегодня Блетчли-парк – туристический объект с тематической экспозицией, посвященной работе военных дешифровщиков.
Алистер Деннисон – руководитель Правительственной школы кодов и шифров (Government Code and Cypher School, GC&CS) – перевез своих ведущих криптоаналитиков – специалистов по вскрытию шифров – в Блетчли-парк. Среди них были шахматисты, кроссвордисты и лингвисты; один из криптоаналитиков был специалистом по египетским папирусам. Когда возникла необходимость расширить число специалистов, Деннисон начал искать «людей профессорского типа». Войска Оси все чаще использовали для шифрования сообщений специальные машины, основанные на сложных системах вращающихся шестеренок и ежедневной смене шифров путем изменения конфигурации специальных соединительных проводов. Поэтому ясно было, что без специальных знаний тоже не обойтись, а это означало, что нужны математики. В команду их вошло несколько, в том числе Ньюман и Тьюринг. Все работали в строжайшей тайне, включая технический персонал и управленцев. На пике активности, в начале 1945 г., в Блетчли-парке насчитывалось до 10 000 сотрудников.
Державы «оси» в основном пользовались машиной «Энигма» и машиной, реализующей шифр Лоренца. Обе системы шифрования считались невзламываемыми, но в математике алгоритма шифрования было несколько слабых мест. Они усугублялись, когда пользователи нарушали правила, для того чтобы упростить себе работу: к примеру, использовали одни и те же установки на протяжении нескольких дней, отправляли одно и то же сообщение дважды или начинали сообщения стандартными словами и фразами. Тьюринг был ключевой фигурой в группе, которая пыталась взломать шифр «Энигмы»; руководил этой группой Дилли Нокс из GC&CS. В 1939 г. поляки сумели раздобыть машину «Энигма»; они сообщили британцам, как она работает – как в ней соединяются роторы. Кроме того, польские криптоаналитики разработали методы взлома шифра «Энигмы», основанные на привычке немцев ставить перед кодовым сообщением короткий кусок текста, позволяющий оператору проверить машину. К примеру, сообщение, которое представляло собой продолжение предыдущего сообщения, нередко начиналось с FORT (Fortsetzung, «продолжение»); следом ставилось время отправления первого сообщения, причем это время повторялось дважды и завершалось буквой Y. Польские криптоаналитики изобрели машину, которая позволяла ускорить анализ, и назвали ее bomba.
