В 1931 году в девятнадцатилетнем возрасте Тьюринг в качестве математического стипендиата поступил в Королевский колледж Кембриджского университета. Четырьмя годами позже защитил диссертацию «Центральная предельная теорема теории вероятности» (которую он самостоятельно «переоткрыл», не зная об аналогичной предшествующей работе) и был избран членом Королевского научного общества. Именно в 1935 году он впервые начал работать в области математической логике и проводить исследования, которые уже через год привели к выдающимся результатам: решению одной из проблем Д. Гильберта и изобретению умозрительной машины (машины Тьюринга), по своему логическому устройству являющейся прообразом цифровых компьютеров, созданных только спустя десять лет.
Предыстория этого была следующей. В Париже в 1900 году на Международном математическом конгрессе знаменитый математик Давид Гильберт представил список нерешенных проблем. В этом списке второй значилась задача доказательства непротиворечивости системы аксиом обычной арифметики, формулировку которой в дальнейшем Гильберт уточнил как «Ent- scheidungsproblem» (проблема разрешимости). Она заключалась в нахождении общего метода, который позволил бы определить, «выполнимо ли данное высказывание на языке формальной логики, т. е. установить его истинность». Алан Тьюринг впервые услышал об этой проблеме на лекциях Макса Ньюмена в Кембридже (он работал там преподавателем математики с 1924 года) и в течение 1936 года получил ответ: проблема Гильберта оказалась неразрешимой. Результаты работы он описал в своей знаменитой статье в 1936–1937 годах. Но «значение статьи, в которой Тьюринг изложил свой результат, — писал Джон Хопкрофт, — простирается за рамки той задачи, по поводу которой статья была написана. Работая над проблемой Гильберта, Тьюрингу пришлось дать четкое определение самого понятия метода. Отталкиваясь от интуитивного представления о методе как о некоем алгоритме, т. е. процедуре, которая может быть выполнена механически (здесь, по- видимому, Тьюринг воспользовался терминологией М. Ньюмена — „чисто механический процесс“, примененной на лекции, излагающей проблему Гильберта), без творческого вмешательства, он показал, как эту идею можно воплотить в виде подробной модели вычислительного процесса. Полученная модель вычислений, в которой каждый алгоритм разбивался на последовательность простых, элементарных шагов, и была логической конструкцией, названной впоследствии машиной Тьюринга».
Значение работы Тьюринга для теории вычислений велико: «Машина Тьюринга за данный большой, но конечный промежуток времени способна справиться с любым вычислением, которое может выполнить всякий сколь угодно мощный современный компьютер».
Тьюринг стал первым, достигшим понимания универсальной природы вычислительной машины. Он показал, что можно построить универсальную машину, способную работать так же, как любая простая машина Тьюринга, если в нее ввести описание этой простой машины.
В сентябре 1936 года Тьюринг покидает Кембридж и перебирается в Америку в Принстонский университет, где работает куратором. Там в 1938 году он получает степень доктора философии. В то время в Принстонском университете работали такие знаменитости, как Черч, Курант, Эйнштейн, Харди, фон Нейман.
Между Нейманом и Тьюрингом состоялись первые дискуссии по вычислительным и «думающим» машинам. Джон фон Нейман проявил живой интерес к идее универсальной машины и предложил Тьюрингу поработать в Принстоне в должности своего ассистента. Тьюринг не принял это предложение и весной того же года возвратился в Кембридж, где ему подтвердили звание и положение члена Королевского колледжа университета.
Период жизни и деятельности Алана Тьюринга с 1939 по 1945 год долгое время был скрыт завесой секретности. Мать Тьюринга, опубликовавшая в 1959 году воспоминания о сыне, скупо писала, что сразу же после объявления войны Тьюринга приняли на работу в качестве государственного служащего в управление связи Министерства иностранных дел. Вначале его местопребывание сохранялось в тайне, хотя позднее стало известно, что он работал в Блетчли-парке близ Лондона, где проводилась особо секретная работа по криптоанализу.
Электрическая шифровальная машина «Энигма»
Работа в Блетчли-парке велась в рамках засекреченного проекта «Ультра», целью которого был поиск метода расшифровки секретных немецких кодов. Для шифрования секретнейших приказов верховного главнокомандования вермахта, аппарата полиции, СД, СС в Германии использовалась электрическая шифровальная машина «Энигма». Еще до начала Второй мировой войны поляки сумели сделать точную копию «Энигмы» и переправить ее в Англию. Но без ключа и схемы коммутации (немцы меняли их три раза в день), даже имея в качестве приемника еще одну «Энигму», трудно было дешифровать сообщение. Для разгадки секретного шифра в Блетчли-парке собралось любопытное общество выдающихся математиков, шахматистов, любителей кроссвордов, знатоков различных областей знаний и даже двух музыкантов. Среди этих людей, оторванных от внешнего мира, был и Алан Тьюринг, возглавлявший одну из групп, в которой работали двенадцать математиков и четыре лингвиста.
В работу его группы и некоторых других входило создание различных специальных вычислительных машин для целей дешифровки немецких сообщений. Надо сказать, что блестящие идеи умозрительной «машины Тьюринга» воплотились в реальных машинах, созданных в Блетчли-парке. Среди них были «Хит Робинсон», электромеханическая машина, включавшая два фотоэлектрических устройства считывания с перфоленты со скоростью 2000 символов в секунду (подобно бесконечной ленте и считывающей головке «машины Тьюринга»), арифметическое устройство на реле и печатающий блок, «Питер Робинсон», «Супер Робинсон» и т. д. Среди разработчиков, кроме Тьюринга, были Уинн- Уильямс, Флауэрс и др. Эти машины работали по принципу перебора различных комбинаций из символов немецкого кода до получения осмысленного сообщения. В сентябре 1942 года в Блетчли-парк прибыл профессор М. Ньюмен (тот самый, из Кембриджа) и возглавил группу специалистов (Т. Флауэрс, А. Кумбс, С. Броуд-бейт, У. Чандлер, И. Гуд, Д. Мичи) по созданию электронной вычислительной машины для той же цели. В результате в декабре 1943 года была создана первая (не только в Англии, но и в мире) электронная вычислительная машина «Колосс», содержащая 2000 электронных ламп.
В этой машине использовался только один тип лент, как и предлагал А. Тьюринг, — «данные» (в закодированном виде перехваченные за день неприятельские сообщения), скорость считывания с которых достигала 5000 символов в секунду (использовались пять фотосчитывающих устройств). Машина в поисках соответствия сопоставляла зашифрованное сообщение с уже известными кодами «Энигмы», которые хранились в кольцевых регистрах, выполненных на тиратронах. К концу войны было изготовлено около 10 «Колоссов».
Компьютер «Колосс»
Очевидно, непосредственного участия в создании «Колосса» Тьюринг не принимал, он выступал в роли консультанта, но как признался И. Гуд, Ньюмену при создании машины очень помогла работа Тьюринга 1936 года. «Я не хочу сказать, что мы выиграли войну благодаря Тьюрингу, — вспоминал многие годы спустя И. Гуд, — но беру на себя смелость сказать, что без него мы могли бы ее и проиграть». За работу в Министерстве иностранных дел (в Блетчли-парке) во время войны А. Тьюринг был награжден орденом Кавалера Британской империи IV степени.
До сих пор остается невыясненной история встречи во время войны Тьюринга с фон Нейманом. История эта, или, как ее назвали позднее, легенда, состоит в том, что эта встреча двух выдающихся математиков имела решающее значение для развития современной компьютерной техники. Известно, что Тьюринг совершил, по крайней мере, одну поездку в США в 1943 году, хотя некоторые утверждают, что он бывал там и в 1942 году. Кроме фон Неймана, он встречался также с Клодом Шенноном, но они, очевидно, не обсуждали вопросов по поводу вычислительных машин.