Чтобы сделать это, Тьюринг рассмотрел работу идеализированной вычислительной машины с бесконечной памятью. Он определил для нее четкую систему действий: машина могла работать, лишь осуществляя последовательные элементарные операции, записывая в одну из ячеек хранения данных новый символ. После этого она могла перейти в соседнюю ячейку и провести там еще одну элементарную операцию. При этом она не имела «свободы воли» — вычисления осуществлялись по четкому алгоритму, последовательности простейших шагов, заданных математически оформленными инструкциями. Определенным входящим данным соответствовал только один возможный результат в выходных данных. В итоге один и тот же алгоритм — именно Тьюринг внес крупный вклад в формализацию этого понятия — всегда выдает один и тот же формализованный результат для решения одной и той же задачи.
Внедрение концепции машины, считающей посредством элементарных операций с четко установленными правилами, позволило начать двигать гору сложных вычислений по отдельным песчинкам — простейшим вычислениям.
Раньше казавшая фантастической задача создания мощных вычислительных машин теперь стала вопросом все более быстрого исполнения простых элементарных операций.
Как математик стал героем войны, ни разу не побывав на фронте
Перед войной в Германии были созданы два типа шифровальных машин (примитивных механических компьютеров) — машины «Энигма» и «Лоренц» (последняя — самая сложная, только для сообщений высшего командования). Они записывали данные с помощью нескольких роторов, каждый из которых имел 26 положений — число, близкое к количеству букв в алфавите. «Зная» изначальное положение роторов (ключ секретных сообщений), другая машина того же типа могла получить из каши символов то, что ей хотел передать отправитель с первой «Энигмы».
Оба типа машин быстро совершенствовались, и взлом передаваемых ими сообщений был чрезвычайно сложен. Ранние польские попытки расшифровки работали только против простых версий машин — до 1940 года. Ознакомившись с польскими наработкам, англичане поняли, что для взлома секретных немецких радиосообщений им нужны куда более совершенные средства, чем все, что существовало в этой области раньше.
Тогда Алан Тьюринг и возглавил создание машины, позже названной Turing Bombe (Бомба Тьюринга). Она имела десятки роторов, каждый из которых примерно соответствовал одной «Энигме». Для раскалывания немецких шифров использовалась известная слабость всех военных и секретных служб всех времен: бессмысленное засекречивание того, что вообще-то не нуждается в секретности. Шифром «Энигмы», среди прочего, передавали и метеосводки, тексты которых для тех или иных регионов также передавались гражданскими службами в открытом радиоэфире. Так удавалось получить часть секретных сообщений. Потом «Бомба Тьюринга» перебором пыталась найти куски с метеосводками в радиоперехватах «Энигмы», и, когда это удавалось, фиксировала положение роторов, при которых из «каши символов» получалась та самая метеоосводка. Зная положение роторов, было легко прочесть и неизвестные части сообщений.
В итоге с весны 1940 года англичане успешно читали почти все немецкие радиосообщения. Это дало им неоценимый инструмент ведения войны. Глава программы «Ультра», использовавшей эти перехваты, Уинтерботэм, указывает, как это выглядело на практике. Когда Роммель в Северной Африке готовил скрытный удар на одном фланге, англичане собирали свои силы на противоположном — и начинали там наступление как раз накануне немецкого, ловя самый слабый немецкий фланг в самый подходящий момент. Точно также война велась союзниками во Франции и Италии. Когда группы немецких подлодок обменивались между собой данными о том, где они ищут конвои союзников, те тут же отклоняли маршруты своих конвоев к тем участкам Атлантики, где немецких подлодок не было.
По сути, англичане и американцы были зрячими, ведущими войну против слепых — немцы союзные радиосообщения взломать не могли. В 1944 году англичане точно знали, что немцы ждут высадки союзников у Па-де-Кале — и поэтому высадились в Нормандии, где их не ждали. Поэтому Уинстон Черчилль и заявил британскому королю Георгу VI: «Именно благодаря «Ультра» мы выиграли войну».
