Кризис оснований математики 1936 года и военный вызов Блетчли-парка
Теоретическая информатика родилась из фундаментального логического спора. В 1928 году Давид Гильберт и Вильгельм Аккерман поставили «проблему разрешимости» (Entscheidungsproblem): существует ли общий механический алгоритм для проверки истинности любого математического утверждения? В мае 1936 года 23-летний кембриджский математик Алан Тьюринг направил в печать статью «О вычислимых числах в применении к проблеме разрешимости», где дал отрицательный ответ и заложил основы вычислительной науки.
Почти одновременно Алонзо Чёрч получил аналогичный результат с помощью лямбда-исчисления; именно он назвал предложенную Тьюрингом «автоматическую машину» (a-machine) «машиной Тьюринга». В отличие от отвлечённого лямбда-формализма, модель Тьюринга наглядно имитировала действия человека-вычислителя с карандашом и лентой клеток, позволяя строго оценивать память и число шагов алгоритма.
Спустя три года чистая теория встретилась с угрозой национальной катастрофы. С началом Второй мировой войны Тьюринг пришёл в Правительственную школу кодов и шифров (GC&CS) в Блетчли-парке. К этому моменту польская «бомба» Мариана Реевского (1938), искавшая повторы ключей сообщений, не справлялась с усложнённой «Энигмой», и Адмиралтейство профинансировало принципиально новый электромеханический дешифратор Тьюринга — Уэлчмана.
Устройство абстрактной модели и диагональная доска «Бомбы»
Теоретическая машина Тьюринга состоит из неограниченной ленты, разбитой на ячейки, головки чтения-записи, конечного алфавита (с пустым символом) и конечного числа внутренних состояний, заменяющих «состояние ума» вычислителя. На каждом шаге по таблице правил (qiaj → qkam L/R/N) головка перезаписывает ячейку, меняет состояние и сдвигается влево, вправо или остаётся на месте до терминальной остановки.
Ключевым открытием стала универсальная машина Тьюринга (УМТ): если закодировать на ленте таблицу переходов любой другой машины M вместе с исходными данными, одна-единственная машина U сможет прочитать описание и в точности воспроизвести её вычисления. Это математически доказало возможность компьютера с хранимой в памяти программой — при неразрешимости проблемы останова (нельзя создать алгоритм, заранее определяющий, остановится ли любая программа или попадёт в бесконечный цикл).
На практике осенью 1939 года Тьюринг построил логику «Бомбы» вокруг поиска логических противоречий на предполагаемых открытых текстах («крибах» вроде метеосводок), используя фундаментальный изъян «Энигмы» — запрет шифрования буквы самой в себя. В 1940 году математик Гордон Уэлчман добавил диагональную доску (diagonal board), использовавшую взаимную симметрию штекерных пар Steckerbrett для мгновенного отсечения ложных срабатываний. Главный инженер компании British Tabulating Machine (BTM) в Летчуэрте Гарольд («Док») Кин воплотил схемы математиков в двухтонных агрегатах, где вращающиеся барабаны заменяли сразу до 36 синхронных установок «Энигмы», перебирая 17 576 роторных позиций за считанные минуты.
«Action This Day», массовая дешифровка и поворот в войне
Первая британская «Бомба» (Victory) заработала в марте 1940 года, а усовершенствованная (Agnus Dei) с диагональной доской — в августе 1940 года. Однако к осени 1941 года выпуск новых машин и набор круглосуточного персонала застряли в ведомственной волоките на фоне лавины немецкого радиоперехвата.
В октябре 1941 года Алан Тьюринг, Гордон Уэлчман, Хью Александер и Стюарт Милнер-Барри обратились через головы начальства напрямую к Уинстону Черчиллю. Премьер-министр наложил на письмо знаменитую визу «Action This Day» («Исполнить сегодня же»), дав Блетчли-парку высший государственный приоритет. Промышленная сборка на заводе BTM довела британский парк до 211 «Бомб», которые обслуживали сотни сотрудниц Женской вспомогательной службы ВМС (WRNS) и ВВС; параллельно в США компания NCR построила скоростные четырёхроторные «Бомбы» для американского флота.
Дешифровка превратилась в поточный разведывательный конвейер Ultra, помогший переломить Битву за Атлантику в 1943 году и обеспечивший союзников данными о передвижении сил вермахта в Африке и перед высадкой в Нормандии. В науке же статья 1936 года закрепила тезис Чёрча — Тьюринга: любой интуитивно мыслимый алгоритм реализуем на машине Тьюринга, а способные её имитировать системы и языки программирования называют полными по Тьюрингу.
От абстрактной ленты к реальным ЭВМ и теории сложности
Хотя машина Тьюринга выражает любые алгоритмы, её последовательный доступ к одной ленте слишком медлителен для реальной практики. Практические компьютеры строятся по модели с произвольным доступом к памяти и хранимой программой (модель RASP), позволяющей мгновенно обращаться к регистрам по адресу и радикально ускоряющей поиск и сортировку; кроме того, реальный компьютер всегда конечен по памяти.
Тем не менее труды Тьюринга прямо ускорили рождение электронной эры. Если британские ламповые комплексы Colossus (1943–1944) построил Томми Флауэрс для взлома телетайпного шифра Лоренца, опираясь на статистические идеи Блетчли-парка, то сам Тьюринг уже в 1945–1946 годах разработал проект электронного компьютера с хранимой программой ACE (Automatic Computing Engine) для Национальной физической лаборатории.
Во второй половине XX века многоленточные, недетерминированные и вероятностные модификации машины Тьюринга стали стандартным инструментом теории сложности алгоритмов (классы P и NP) и теории компиляторов, навсегда соединив строгую математическую логику 1936 года с военным триумфом электромеханического криптоанализа.
