Идеи с границы познания. Эйнштейн, Гёдель и философия науки - Джим Холт

машины можно заставить выполнять всевозможные сложные математические вычисления. Более того, функционирование каждой машины можно заключить в одно-единственное число (как правило, очень длинное), чтобы заставить одну машину воздействовать на другую, записав номер второй машины на ленту первой в виде последовательности нулей и единиц. Таким образом Тьюринг сумел задействовать нечто вроде парадоксов самоссылаемости («Я лгу») и показать, что определенные разновидности машин Тьюринга не могут существовать. В частности, не существует машины Тьюринга, которая, получив программный номер другой машины, решила бы, завершит эта машина когда-нибудь свои вычисления или же будет работать над ними вечно. (Если бы такая машина существовала, ее можно было бы заставить мыслить по-гамлетовски: «Я остановлюсь, если и только если я никогда не остановлюсь».) Однако проблема остановки, как оказалось, была лишь замаскированной проблемой разрешимости. Тьюринг сумел доказать, что никакая вычислительная машина того вида, какой он себе представлял, не может решить проблему разрешимости. То есть логику невозможно свести к вычислениям.

Однако крушение мечты Лейбница знаменовало собой рождение компьютерной эпохи. Самая смелая идея, выросшая из рассуждений Тьюринга, – это идея универсальной машины Тьюринга, то есть машины, которая, получив номер, описывающий механизм любой конкретной машины Тьюринга, идеально подражала бы ее поведению. В сущности, «железо» компьютера, созданного для конкретной цели, можно преобразовать в «программное обеспечение» и ввести, как данные, в универсальную машину, где программа запустится. Побочным продуктом достижений Тьюринга в логике стало изобретение компьютера с хранимой программой.

Когда Тьюринг решил проблему разрешимости, ему было 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 кораблей в месяц. Британия, в отличие от Германии, была экономически крайне зависима от морских путей. Нужно было срочно придумать какую-то стратегию противодействия, иначе Британским островам грозил голод, а в итоге и капитуляция. Когда Тьюринг прибыл в Блетчли-парк, никаких работ по взлому военно-морской «Энигмы» не велось, поскольку многие считали, что расшифровать этот код в принципе невозможно. Более того, говорят, что в возможность взлома «Энигмы» верили всего два человека – Фрэнк Бёрч, глава отделения военно-морской разведки в Блетчли, который считал, что ее все