Технология и формат 1936 г.

Абстрактная машина Тьюринга и дешифровка «Бомбой»

Математическая модель алгоритма 1936 года и созданный на практике в Блетчли-парке электромеханический дешифратор шифров «Энигмы»

Краткая справка

В статье 1936 года «О вычислимых числах» Алан Тьюринг описал абстрактную машину с бесконечной лентой и таблицей правил, формализовав понятие алгоритма, определив универсальный компьютер и доказав неразрешимость проблемы Гильберта. В годы Второй мировой войны практический гений Тьюринга, Гордона Уэлчмана и инженера Гарольда Кина воплотился в электромеханических дешифраторах «Бомба» в Блетчли-парке, которые при поддержке Черчилля взломали радиосвязь Германии.

Схема абстрактной машины Тьюринга с ячейками ленты, головкой считывания-записи и конечным автоматом состояний
Диаграмма абстрактной машины Тьюринга (бесконечная лента, головка чтения-записи и блок состояний). Автор: Schadel / Alessio Damato, общественное достояние. Иллюстрация: Schadel ( http://turing.izt.uam.mx ), Public domain

Кризис оснований математики 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 года с военным триумфом электромеханического криптоанализа.

Цепочка влияния: причины и последствия

Исторический «эффект домино» — какие предпосылки вызвали это событие или явление и к каким переменам оно привело.

Что привело к этому (истоки и предпосылки)

Технология и формат1918–1945 гг.Историческая причина и предпосылка

Роторная шифровальная машина «Энигма»

Усложнение роторов и коммутационной панели «Энигмы» вынудило Тьюринга, Уэлчмана и Кина создать электромеханическую дешифровальную машину «Бомба».

Технология и формат1945–1953 гг.Преемственность

Электронные лампы, ЭНИАК и советские БЭСМ / МЭСМ

Теоретическая идея универсального вычислителя 1936 года воплотилась на практике в архитектуре фон Неймана (EDVAC) и первых ламповых ЭВМ с хранимой программой — МЭСМ и БЭСМ.

К чему это привело дальше (последствия)

Технология и формат1945 г.Историческая причина и предпосылка

Архитектура ЭВМ фон Неймана

Статья Алана Тьюринга 1936 года о единой ленте для правил и данных сформировала логико-математическую базу концепции хранимой программы.

Технология и формат1945–1953 гг.Технологический катализатор

Электронные лампы, ЭНИАК и советские БЭСМ / МЭСМ

Концепция универсальной машины 1936 года и военный опыт автоматизированной дешифровки ускорили переход к электронным ЭВМ с хранимой программой в 1945–1953 годах.

Государства и ключевые связи в графе

Связанные личности, технологии, места и понятия

Личность Алан Тьюринг 1912 — 1954 — Изобретатель / конструктор
Технология и формат Роторная шифровальная машина «Энигма» 1918–1945 гг. — Следствие и политический итог
Технология и формат Роторная шифровальная машина «Энигма» 1918–1945 гг. — Историческая причина и предпосылка
Технология и формат Электронные лампы, ЭНИАК и советские БЭСМ / МЭСМ 1945–1953 гг. — Преемственность
Технология и формат Архитектура ЭВМ фон Неймана 1945 г. — Историческая причина и предпосылка
Технология и формат Электронные лампы, ЭНИАК и советские БЭСМ / МЭСМ 1945–1953 гг. — Технологический катализатор

Частые вопросы и ответы

Является ли машина Тьюринга 1936 года реальным железным устройством?
Нет, предложенная Аланом Тьюрингом в 1936 году модель — это мысленный математический аппарат с бесконечной лентой и таблицей правил, созданный для строгого определения понятия «алгоритм» и доказательства неразрешимости проблемы Гильберта.
Что такое универсальная машина Тьюринга и полнота по Тьюрингу?
Универсальная машина Тьюринга — это модель, способная считать с ленты описание любой другой машины и выполнить её алгоритм. Вычислительная система или язык программирования называются полными по Тьюрингу, если на них можно смоделировать работу любой машины Тьюринга (без учёта конечности памяти).
Чем британская «Бомба» Тьюринга — Уэлчмана отличалась от польской «бомбы» 1938 года?
Польская машина Мариана Реевского искала повторы трёхбуквенных ключей в заголовке, которые немцы отменили в 1940 году. Британская «Бомба» искала логические противоречия на вероятных открытых текстах («крибах»), а диагональная доска Гордона Уэлчмана мгновенно отсекала ложные варианты штекерной панели.
Почему для масштабирования «Бомб» потребовалось вмешательство Уинстона Черчилля?
Осенью 1941 года Блетчли-парк задыхался от нехватки персонала и деталей из-за армейской волокиты. После прямого обращения Тьюринга и его коллег Черчилль наложил визу «Action This Day», обеспечив заводу BTM высший приоритет, что позволило построить 211 машин.
Почему реальные компьютеры не строят буквально по схеме ленты Тьюринга?
Последовательная перемотка одной ленты делает чтение удалённых данных крайне медленным. Практические ЭВМ строятся по модели с произвольным доступом к памяти (RASP) и хранимой программой, сохраняя при этом алгоритмическую эквивалентность универсальной машине Тьюринга.

Научная литература и источники

  1. Машина Тьюринга // Википедия (свободная энциклопедия) [ru.wikipedia.org]
  2. Turing machine // Stanford Encyclopedia of Philosophy [plato.stanford.edu]
  3. Turing A. M. On Computable Numbers, with an Application to the Entscheidungsproblem (1936–1937, PDF) [www.cs.ox.ac.uk]
  4. Bombe // Wikipedia [en.wikipedia.org]
  5. Turing machine // Encyclopaedia Britannica [www.britannica.com]