Сон разума. Математическая логика и ее парадоксы
Шрифт:
Глава 5
Машины Тьюринга
На что я могу надеяться?
Иммануил Кант
«Евр…» Бетти нетерпеливо ожидала, когда телеграфный механизм остановится, чтобы прочитать сообщение целиком. «Европа». Прошло больше пяти лет с того дня, как журнал, который она любила читать в часы, свободные от работы прислугой в одной из богатейших лондонских семей, устроил конкурс кроссвордов. «Европа ник…» Каждый день она вспоминала, как удивило ее известие о победе в конкурсе и как она не решалась попросить недельный отпуск. «Европа никогда». Затем она попыталась восстановить в памяти путешествие с другими любителями логических задач, пока очертания Блетчли-парка не стали в ее памяти столь же ясными, как в тот осенний день, когда она впервые увидела его. «Европа никогда не будет».
Она боялась забыть малейшие подробности истории, которую собиралась рассказать всему миру, когда закончится война. Р-у-с-с-к-о-й. Последнее слово появилось с небольшим опозданием, но Бетти могла праздновать
Они не единственными получили умоисступленное сообщение диктатора за две недели до его самоубийства: Гиммлер и не подозревал, что его переписку с Гитлером читало одновременно десять тысяч человек в маленьком поселке в восьмидесяти километрах от Лондона, надежно спрятанном, чтобы избежать бомбардировок. Именно там в 1939 году была создана правительственная школа кодов и шифров, которая занималась расшифровкой сообщений, кодируемых нацистами на машине «Энигма» — самой совершенной шифровальной машине того времени. «Энигму» в 1918 году начал производить инженер Артур Шербиус. Вначале он продавал машину частным лицам, однако потом ее потенциал оценили немецкая армия и флот, и «Энигма» начала широко использоваться военными, службой безопасности и разведкой. Когда войска вермахта вторглись в Польшу в начале сентября 1939 года, методы шифрования «Энигмы» достигли такой сложности, что возможность их взлома даже не рассматривалась.
И лишь совместная работа группы, состоявшей из математиков, физиков, переводчиков и уже упомянутых нами женщин — победительниц конкурса кроссвордов, помогла разгадать загадку дьявольской машины, которая посредством электрических импульсов и системы роторов преобразовывала одну и ту же букву, записанную два раза подряд, в разные символы. Одетые в костюмы пиратов, словно скучающая знать, ищущая развлечений в годы войны, первые дешифровщики в 1939 году разместились в бараках рядом с викторианским поместьем. Ни одна душа в соседнем поселке не должна была заподозрить, какую важную задачу решали обитатели Station X — так назывался центр в сообщениях союзников, отправляемых на передовую. Даже Уинстон Черчилль называл Блетчли-парк «курицей, несущей золотые яйца, которая никогда не кудахчет».
Справа — немецкие военные кодируют сообщения на машине «Энигма», один из экземпляров которой изображен на рисунке слева.
Вверху — зал Блетчли-парка, в котором происходила расшифровка кодов «Энигмы». Внизу — современная фотография поместья.
Поляки заметили одну особенность «Энигмы», делавшую ее уязвимой: каждая буква вне зависимости от положения всегда кодировалась одной и той же буквой. И все равно потребовалось ответить еще на много вопросов, прежде чем за пять дней до высадки союзников в Нормандии обитатели Блетчли-парка смогли отпраздновать расшифровку секретного сообщения Гитлера. В сообщении утверждалось, что американский десант высадится в Кале, почти в трехстах километрах к северо-востоку от пляжа Арроманш. Возможно, высадка союзников вообще не состоялась бы, если бы не была получена информация о местонахождении нацистских подлодок, которую удалось расшифровать в Station X. Это было особенно удивительно, если учесть, что в 1939 году у дешифровщиков не было ни одной машины «Энигма», на которой можно было бы проверять свои гипотезы.
Работая день и ночь сменами по восемь часов, дешифровщики из Блетчли-парка сконструировали прототип машины, идентичной той, что находилась в руках у на цистов, однако успех предприятия был бы невозможен без юного английского математика, которого многие студенты Кембриджа сравнивали с греческим «богом из машины»: он появился словно из ниоткуда, чтобы помочь выиграть войну. Без Алана Тьюринга (1912–1954) было бы нелегко понять, что во всех сообщениях обязательно упоминались дата и время, к которым они относились, и именно с этого следовало начинать их расшифровку.
Статуя Алана Тьюринга из угольного сланца работы британского скульптора Стивена Кеттла рядом с портретом Тьюринга, который хранится в Национальном музее компьютеров в Блетчли-парке
(источник: Джон Каллас).
Тьюринг также предложил сконструировать огромный компьютер «Бомба», который позволял моделировать работу десяти «Энигм» одновременно. Да, Тьюринг видел дальше своих коллег, и происходило это не потому, что он обучался в лаборатории с новейшим оборудованием, а потому, что он долгое время исследовал границы теоремы Гёделя — прекраснейшего, по его мнению, творения человеческого разума.
* * *
ДИАЛОГ ИЗ ФИЛЬМА «ВЗЛОМАТЬ КОД»
(РЕЖИССЕР ХЕРБЕРТ УАЙЗ, АВТОР СЦЕНАРИЯ ХЬЮ УАЙТМОР, 1996)
Дилли Нокс: Я ознакомился с некоторыми подробностями вашей работы, господин Тьюринг, и должен признаться, что многие из них мне непонятны.
Тьюринг: Меня это не слишком удивляет.
Дилли Нокс: Когда я был молод, я был неплохим математиком, но некоторые фразы совершенно сбивают меня с толку. Например, вот эта: «О вычислимых числах в приложении к проблеме разрешения». Можете сказать что-либо по этой теме?
Тьюринг: Что именно?
Дилли Нокс: Не знаю, что-нибудь, несколько слов, объясните в общих чертах.
Тьюринг: Несколько слов?
Дилли Нокс: Да.
Тьюринг: В общих чертах?
Дилли Нокс: Да, если это возможно…
Тьюринг: Хорошо. В общих чертах — речь идет об истинном и ложном. Это техническая статья по математической логике, в которой также рассматривается, как трудно отличить истинное и ложное. Люди, то есть многие люди, думают, что в математике всегда известно, что истинно, а что нет, но это не так! И это никогда не будет так! Это проблема, над которой математики работают уже сорок или пятьдесят лет. Как вам это объяснить? Нужно понять, как отличить истинное отложного, понимаете? […]
Дилли Нокс: На самом деле не совсем, но теперь мне кое-что понятно. Ваши идеи кажутся мне весьма оригинальными, и я убежден, что вы станете ценным членом нашей команды или группы — называйте ее как угодно.
* * *
Постройка «Бомбы», или «Колосса», первого программируемого компьютера, также изготовленного в Блетчли-парке, вписывалась в череду открытий, восходящую как минимум ко второму десятилетию XVII века, когда немецкий астроном Вильгельм Шиккард (1592–1635) создал первые «часы для счета» — хитроумный механизм, способный выполнять сложение, вычитание, умножение и деление.
За Шиккардом следовал Блез Паскаль (1623–1662), в девятнадцать лет начавший работу над своей вычислительной машиной, чтобы облегчить труд отца — сборщика налогов в Руане. Его «Паскалина» произвела фурор в аристократических салонах, вызвав удивление ученых и членов знатных семейств. Там же ее увидел и Готфрид Лейбниц (1646–1716). Он был убежден, что «терять время на вычисления, подобно рабам, недостойно выдающихся людей», поэтому неудивительно, что «Паскалина» вызвала у Лейбница большой энтузиазм и желание немедленно ее усовершенствовать. Ученый мечтал создать машину, способную распознавать все истинные высказывания.
«Паскалина», придуманная французским ученым Блезом Паскалем, стала первой вычислительной машиной в истории.
В начале XIX века вычислительные машины Паскаля и Лейбница вдохновили английского математика Чарльза Бэббиджа (1791–1871) и его ученицу Аду Байрон (1815–1852) на исследования по теории вычислений. Для создания аналитической машины (Analytical Engine) Бэббидж и Байрон выделили обязательные элементы всех процессов в информатике. Во-первых, должна существовать программа, указывающая операции, которые нужно выполнить. Она представляет собой ряд инструкций, которые на основе множества входных данных позволяют вычислить результат, возвращаемый пользователю на выходе программы. Например, на вход программы «умножить» подаются пары чисел вида (2, 3), выводом является их произведение — в этом случае 2·3 = 6. Чтобы программа (далее мы будем называть ее алгоритмом) могла быть исполнена, необходимы процессор, выполняющий инструкции, и память, в которой хранятся входные данные, инструкции и все промежуточные расчеты. В аналитической машине Бэббиджа входные данные вводились с помощью перфорированных карт, которые использовались в ткацком станке Жаккара, предназначенном для автоматического создания узоров.
Ада Байрон была дочерью великого английского поэта лорда Байрона и Анабеллы Милбэнк, которую муж называл «королевой параллелограммов», так как она обучалась алгебре и геометрии у главы кафедры Кембриджа. Лорд Байрон оставил семью после рождения Ады, и Анабелла начала обучать дочь наукам с очень раннего возраста. В семнадцать лет девушка познакомилась с Чарльзом Бэббиджем, произошло это на ужине, организованном ее подругой и наставницей Мэри Сомервилл, которая всегда поощряла занятия Ады математикой. Вскоре Ада объяснила Бэббиджу, как можно вычислить числа Бернулли с помощью перфокарт. Эта задача по своей сложности намного превосходила те, которые к тому времени удалось решить изобретателю аналитической машины. С помощью своего метода, позволявшего «ткать алгебраические задачи», Байрон не только написала первую в истории программу, но и показала, что для решения задачи алгоритмически необязательно начинать с нуля. При решении почти всех задач повторялся определенный набор базовых операций, поэтому часто было достаточно скомбинировать уже имеющиеся перфокарты в правильном порядке. Такие базовые операции современные программисты называют подпрограммами.