вол, который видит сканер, и его действия, и составляет программу машины. (Типичная строчка такой программы должна была бы выглядеть примерно так: «Если машина в состоянии А сканирует 0, то меняет 0 на 1, сдвигается на один квадрат влево и переходит в состояние В».)
При помощи своих абстрактных устройств, которые вскоре стали называть машинами Тьюринга, ученый проделывал поразительные фокусы. Он показал, что, несмотря на простоту дизайна, такие машины можно заставить выполнять всевозможные сложные математические вычисления. Более того, функционирование каждой машины можно заключить в одно-единственное число (как правило, очень длинное), чтобы заставить одну машину воздействовать на другую, записав номер второй машины на ленту первой в виде последовательности нулей и единиц. Таким образом Тьюринг сумел задействовать нечто вроде парадоксов самоссылаемости («Я лгу») и показать, что определенные разновидности машин Тьюринга не могут существовать. В частности, не существует машины Тьюринга, которая, получив программный номер другой машины, решила бы, завершит эта машина когда-нибудь свои вычисления или же будет работать над ними вечно. (Если бы такая машина существовала, ее можно было бы заставить мыслить по-гамлетовски: «Я остановлюсь, если и только если я никогда не остановлюсь».) Однако проблема остановки, как оказалось, была лишь замаскированной проблемой разрешимости. Тьюринг сумел доказать, что никакая вычислительная машина того вида, какой он себе представлял, не может решить проблему разрешимости. То есть логику невозможно свести к вычислениям.
Однако крушение мечты Лейбница знаменовало собой рождение компьютерной эпохи. Самая смелая идея, выросшая из рассуждений Тьюринга, – это идея универсальной машины Тьюринга, то есть машины, которая, получив номер, описывающий механизм любой конкретной машины Тьюринга, идеально подражала бы ее поведению. В сущности, «железо» компьютера, созданного для конкретной цели, можно преобразовать в «программное обеспечение» и ввести, как данные, в универсальную машину, где программа запустится. Побочным продуктом достижений Тьюринга в логике стало изобретение компьютера с хранимой программой.
Когда Тьюринг решил проблему разрешимости, ему было 23 года. Едва он закончил работу, в Кембридж из-за Атлантического океана дошла огорчительная новость: принстонский логик Алонзо Черч успел решить задачу первым. Однако в отличие от Тьюринга Черч не пришел к идее универсальной вычислительной машины, а задействовал гораздо более сложную конструкцию, так называемое лямбда-исчисление. Тем не менее Тьюринг решил, что ему стоит поучиться у более авторитетного логика. Он отправился в Америку – переплыл Атлантику третьим классом и прибыл в Нью-Йорк, где, как он писал матери, «пришлось пройти обряд посвящения в американцы, состоявший в том, что меня облапошил таксист».
В Принстоне Тьюринг проделал первые шаги к созданию рабочей модели своего воображаемого компьютера и придумал, как воплотить свой логический замысел в виде сети переключателей на основе реле; он даже пробился в механическую мастерскую при физическом факультете и собрал несколько реле самостоятельно. И не только учился у Черча, но и консультировался с самим великим Джоном фон Нейманом, который впоследствии присвоил некоторые идеи компьютерной архитектуры, основоположником которых стал Тьюринг. Что касается социальной жизни, американское прямодушие импонировало Тьюрингу, но не всегда: «Когда их благодаришь за что-то, они отвечают “всегда обращайтесь”. Поначалу мне это нравилось – я считал, что и правда могу к ним обратиться. Но теперь я вижу: это означает, что на самом деле ты им обязан, так что это выражение меня несколько пугает. Еще у них есть привычка издавать звук, который писатели передают как “Ага”. Так они говорят, когда не могут придумать подходящего ответа на ту или иную реплику».
В 1938 году Тьюринг защитил в Принстоне диссертацию по математике и, несмотря на предостережения отца, которого тревожила угроза войны с Германией, решил вернуться в Британию. В Кембридже он стал завсегдатаем семинара Людвига Витгенштейна по основам математики. Тьюринг и Витгенштейн были на удивление похожи – одиночки, аскеты, гомосексуалы, любители фундаментальных вопросов. Однако у них возникли острые разногласия по некоторым философским принципам, например, по вопросу об отношениях логики и повседневной жизни. «От логических противоречий еще никто не умер», – настаивал Витгенштейн. На что Тьюринг возражал: «Беды и правда не будет до тех пор, пока противоречие не найдет практического воплощения, а тогда может рухнуть мост». Вскоре Тьюринг доказал, что от логических противоречий и в самом деле зависят жизнь и смерть.
1 сентября 1939 года нацистские войска вторглись в Польшу. Через три дня Тьюринг получил предписание явиться в Блетчли-парк, викторианскую усадьбу в тюдоровско-готическом стиле, расположенную к северо-западу от Лондона, куда секретно перевели шифровальную службу. Тьюринга и других дешифровщиков привезли в Блетчли как участников «охоты капитана Ридли», что вызвало недовольство окрестных жителей: им не нравилось, что взрослые здоровые мужчины приехали развлекаться, вместо того чтобы идти на войну. Задачу перед ними поставили сложнейшую. С тех пор, как во время Первой мировой войны в военном деле впервые начали применять радиосвязь, в армии остро стоял вопрос об эффективном шифровании – способе посылать частные сообщения через публичное пространство. Нацисты полагали, что их система шифрования, основанная на машине под названием «Энигма», напоминавшей усовершенствованную пишущую машинку, сыграет важнейшую роль в ожидаемой победе.
«Энигма» была изобретена в 1918 году и предназначалась для коммерческого применения, но вскоре ее стали использовать в германской армии. У этой машины была алфавитная клавиатура, а кроме нее – набор из 26 лампочек, по одной на каждую букву. Если нажать какую-то букву на обычной клавиатуре, на ламповой клавиатуре зажигалась другая буква. Например, если набрать на клавиатуре «Энигмы» d-o-g, лампочки высветят r-l-u. Если затем радист передаст сочетание букв r-l-u морзянкой, получатель наберет эти буквы на клавиатуре своей «Энигмы», а лампочки высветят d-o-g при условии, что две машины одинаково настроены.
Тут-то все и принимало интересный оборот. Внутри «Энигмы» был набор вращающихся роторов, определявших соответствие вводимых и зашифрованных букв; каждый раз, когда на клавиатуре нажимали какую-то букву, один из роторов поворачивался и менял настройки (то есть, набирая g-g-g, можно было получить шифрованное сообщение q-d-a). У армейской версии «Энигмы» была еще и коммутационная панель, чтобы еще сильнее запутать соотношения между буквами. Настройки колес и коммутационной панели меняли ежедневно в полночь. После чего добавлялись новые уровни сложности, отчего количество возможных ключей шифрования возрастало чуть ли не до 150 квинтиллионов.
Надежнее всего была защищена связь на немецком военном флоте, где машины «Энигма» применялись особенно хитроумно, а работа с ними была построена необычайно строго. К началу 1941 года растущий немецкий подводный флот сеял смерть и разрушение среди британских кораблей – он топил около 60 кораблей в месяц. Британия, в отличие от Германии, была экономически крайне зависима от морских путей. Нужно было срочно придумать какую-то стратегию противодействия, иначе Британским островам грозил голод, а в итоге и капитуляция. Когда Тьюринг прибыл в Блетчли-парк, никаких работ по взлому военно-морской «Энигмы» не велось, поскольку многие считали, что расшифровать этот код в принципе невозможно. Более того, говорят, что в возможность взлома «Энигмы» верили всего два человека – Фрэнк Бёрч, глава отделения военно-морской разведки в Блетчли, который считал, что ее все равно придется взломать, и Алан Тьюринг, поскольку это была интересная задача.
Тьюринг взялся за изучение военно-морской «Энигмы» и вскоре выявил слабое место. Зашифрованные военно-морские сообщения часто содержали стандартные фрагменты-формулы вроде WETTER FUER DIE NACHT («погода на ночь»), которые можно было обнаружить простой догадкой. Тьюринг понял, что такие «несущие конструкции» можно задействовать, чтобы выявить логические цепочки, каждая из которых соответствовала миллиардам возможных настроек «Энигмы». Если одна такая цепочка приводила к противоречию – внутренней несогласованности гипотезы шифра – миллиарды настроек, которым она соответствовала, можно было сразу вычеркнуть. Так что задача свелась к проверке миллионов логических цепочек – что, конечно, чудовищно трудоемко, но не невозможно. Тьюринг решил разработать машину, которая автоматизировала бы поиски логической непротиворечивости, а противоречивые цепочки исключала бы достаточно быстро, чтобы дешифровщики выявляли сегодняшние настройки «Энигмы» раньше, чем устаревали бы разведданные. Результат получился размером с несколько холодильников с десятками вращающихся барабанов (повторявших роторы «Энигмы») и огромными катушками с цветными проводами, напоминавшими узор на пестром свитере. Когда машина работала, ее шум напоминал звон тысяч вязальных спиц – так щелкали реле, проверяя цепочки одну за другой. Сотрудники Блетчли назвали эту машину «Бомбой» в память о первой дешифровальной машине, созданной в Польше: та издавала зловещее тиканье.
В удачные дни «Бомба» получала ключ к сегодняшнему шифру «Энигмы» меньше чем за час, и к 1941 году заработали уже восемнадцать «Бомб». Когда переговоры военно-морского флота фашистской Германии перестали быть тайной, британцы получили возможность точно выявлять местоположение подводных лодок, уводить от них караваны судов, а затем переходить в наступление и отправлять эсминцы, чтобы топить вражеские субмарины. Но даже когда расстановка сил в Битве за Атлантику изменилась, верховное командование войск Германии отказывалось верить, что «Энигму» удалось взломать, и подозревало шпионаж и измену.
По мере развития «Энигмы» Тьюринг изобретал новые методы борьбы с ней. В Блетчли его прозвали Профом, и он славился безобидными чудачествами – например, пристегивал свою кружку цепочкой к батарее отопления и надевал противогаз, когда ездил на работу на велосипеде (так он боролся с сенной лихорадкой). Коллеги знали его как приветливого, общительного гения, который всегда был готов объяснить свои соображения, и он особенно подружился с одной своей сотрудницей, с которой они играли, по его словам, в «сонные шахматы» после того, как вместе работали над дешифровкой кодов в ночную смену. Тьюринг убедил себя, что влюблен, сделал предложение, которое было с радостью принято, несмотря на то, что он признался невесте в «гомосексуальных склонностях». Но затем Тьюринг решил, что из этого ничего не выйдет, и разорвал помолвку. По всей видимости, это был единственный раз за всю жизнь, когда он задумался о гетеросексуальных отношениях.