Значение работы Тьюринга для теории вычислений велико: «Машина Тьюринга за данный большой, но конечный промежуток времени способна справиться с любым вычислением, которое может выполнить всякий сколь угодно мощный современный компьютер».

Тьюринг стал первым, достигшим понимания универсальной природы вычислительной машины. Он показал, что можно построить универсальную машину, способную работать так же, как любая простая машина Тьюринга, если в нее ввести описание этой простой машины.

В сентябре 1936 года Тьюринг покидает Кембридж и перебирается в Америку в Принстонский университет, где работает куратором. Там в 1938 году он получает степень доктора философии. В то время в Принстонском университете работали такие знаменитости, как Черч, Курант, Эйнштейн, Харди, фон Нейман.

Между Нейманом и Тьюрингом состоялись первые дискуссии по вычислительным и «думающим» машинам. Джон фон Нейман проявил живой интерес к идее универсальной машины и предложил Тьюрингу поработать в Принстоне в должности своего ассистента. Тьюринг не принял это предложение и весной того же года возвратился в Кембридж, где ему подтвердили звание и положение члена Королевского колледжа университета.

Период жизни и деятельности Алана Тьюринга с 1939 по 1945 год долгое время был скрыт завесой секретности. Мать Тьюринга, опубликовавшая в 1959 году воспоминания о сыне, скупо писала, что сразу же после объявления войны Тьюринга приняли на работу в качестве государственного служащего в управление связи Министерства иностранных дел. Вначале его местопребывание сохранялось в тайне, хотя позднее стало известно, что он работал в Блетчли-парке близ Лондона, где проводилась особо секретная работа по криптоанализу.

Электрическая шифровальная машина «Энигма»

Работа в Блетчли-парке велась в рамках засекреченного проекта «Ультра», целью которого был поиск метода расшифровки секретных немецких кодов. Для шифрования секретнейших приказов верховного главнокомандования вермахта, аппарата полиции, СД, СС в Германии использовалась электрическая шифровальная машина «Энигма». Еще до начала Второй мировой войны поляки сумели сделать точную копию «Энигмы» и переправить ее в Англию. Но без ключа и схемы коммутации (немцы меняли их три раза в день), даже имея в качестве приемника еще одну «Энигму», трудно было дешифровать сообщение. Для разгадки секретного шифра в Блетчли-парке собралось любопытное общество выдающихся математиков, шахматистов, любителей кроссвордов, знатоков различных областей знаний и даже двух музыкантов. Среди этих людей, оторванных от внешнего мира, был и Алан Тьюринг, возглавлявший одну из групп, в которой работали двенадцать математиков и четыре лингвиста.

В работу его группы и некоторых других входило создание различных специальных вычислительных машин для целей дешифровки немецких сообщений. Надо сказать, что блестящие идеи умозрительной «машины Тьюринга» воплотились в реальных машинах, созданных в Блетчли-парке. Среди них были «Хит Робинсон», электромеханическая машина, включавшая два фотоэлектрических устройства считывания с перфоленты со скоростью 2000 символов в секунду (подобно бесконечной ленте и считывающей головке «машины Тьюринга»), арифметическое устройство на реле и печатающий блок, «Питер Робинсон», «Супер Робинсон» и т. д. Среди разработчиков, кроме Тьюринга, были Уинн- Уильямс, Флауэрс и др. Эти машины работали по принципу перебора различных комбинаций из символов немецкого кода до получения осмысленного сообщения. В сентябре 1942 года в Блетчли-парк прибыл профессор М. Ньюмен (тот самый, из Кембриджа) и возглавил группу специалистов (Т. Флауэрс, А. Кумбс, С. Броуд-бейт, У. Чандлер, И. Гуд, Д. Мичи) по созданию электронной вычислительной машины для той же цели. В результате в декабре 1943 года была создана первая (не только в Англии, но и в мире) электронная вычислительная машина «Колосс», содержащая 2000 электронных ламп.

В этой машине использовался только один тип лент, как и предлагал А. Тьюринг, — «данные» (в закодированном виде перехваченные за день неприятельские сообщения), скорость считывания с которых достигала 5000 символов в секунду (использовались пять фотосчитывающих устройств). Машина в поисках соответствия сопоставляла зашифрованное сообщение с уже известными кодами «Энигмы», которые хранились в кольцевых регистрах, выполненных на тиратронах. К концу войны было изготовлено около 10 «Колоссов».

Компьютер «Колосс»

Очевидно, непосредственного участия в создании «Колосса» Тьюринг не принимал, он выступал в роли консультанта, но как признался И. Гуд, Ньюмену при создании машины очень помогла работа Тьюринга 1936 года. «Я не хочу сказать, что мы выиграли войну благодаря Тьюрингу, — вспоминал многие годы спустя И. Гуд, — но беру на себя смелость сказать, что без него мы могли бы ее и проиграть». За работу в Министерстве иностранных дел (в Блетчли-парке) во время войны А. Тьюринг был награжден орденом Кавалера Британской империи IV степени.

До сих пор остается невыясненной история встречи во время войны Тьюринга с фон Нейманом. История эта, или, как ее назвали позднее, легенда, состоит в том, что эта встреча двух выдающихся математиков имела решающее значение для развития современной компьютерной техники. Известно, что Тьюринг совершил, по крайней мере, одну поездку в США в 1943 году, хотя некоторые утверждают, что он бывал там и в 1942 году. Кроме фон Неймана, он встречался также с Клодом Шенноном, но они, очевидно, не обсуждали вопросов по поводу вычислительных машин.

Ситуацию взаимоотношений этих знаменитостей, наверно, лучше всего обрисовал С. Френкель, который писал: «Многие люди провозгласили фон Неймана отцом вычислительных машин (в современном смысле термина), но я уверен, что он никогда не сделал бы подобной ошибки сам. Его (фон Неймана) достоверно можно назвать „повивальной бабкой“, и он настойчиво утверждал мне и другим, что фундаментальная концепция принадлежит Тьюрингу, поскольку подобное не предвидели ни Бэббидж, ни Лавлейс, ни другие».

В 1945 году Алан Тьюринг, отказавшись от лекторской работы в Кембриджском университете, перешел по рекомендации М. Ньюмена в Национальную физическую лабораторию (НФЛ), где организовалась группа по проектированию и созданию вычислительной машины АСЕ (Automatic Computing Engine). В течение трех лет (1945–1948), пока существовала эта группа, он сделал первые наброски АСЕ и внес ряд предложений по ее конструированию. Отчет Тьюринга по АСЕ датирован более поздней датой и ссылается на известный черновой отчет фон Неймана по EDVAC. Но Тьюринг пошел значительно дальше, т. к. его работа содержала много конкретных деталей и имела полную концепцию компьютера с хранимой программой. Многие утверждают, что Тьюринг предложил один из первых проектов такого компьютера — концепцию, которую считают фундаментальной в вычислительном мире и которая была предложена им независимо от Маучли, Эккерта и фон Неймана.

Отчет по АСЕ был передан в исполнительный комитет НФЛ 19 марта 1946 года с сопроводительной запиской Уомерсли, в которой сообщалось, что, хотя отчет основан на проекте EDVAC, последний содержит ряд идей, принадлежащих Тьюрингу. Хотя о работе Тьюринга во время войны многое неизвестно, она, безусловно, значительна, хотя бы по тем моментам, которые обозначены в проекте АСЕ. Машина под названием MOSAIC, основанная на первичном варианте этого проекта, была вскоре построена Чандлером и Кумбсом.

В сентябре 1948 года Тьюринг перешел на работу в Манчестерский университет, номинально заняв должность заместителя директора лаборатории вычислительных машин, хотя в действительности он числился в математическом отделе М. Ньюмена и являлся ответственным за программирование.