Тьюринг, Алан

Алан Тьюринг
Научная сфера	математика, логика, криптография, информатика
Место работы	Кембриджский университет Национальная физическая лаборатория Великобритании Правительственная школа кодов и шифров Манчестерский университет
Альма-матер	Королевский колледж (Кембридж) Принстонский университет
Ученики	Робин Ганди
Известен как	изобретатель машины Тьюринга, теста Тьюринга
Награды и премии	член Лондонского королевского общества

А́лан Мэ́тисон Тью́ринг (англ. Alan Mathison Turing; 23 июня 1912, Лондон, Англия — 7 июня 1954, Уилмслоу, Восточный Чешир, Англия.) — английский математик, логик, криптограф, оказавший большое влияние на развитие информатики как науки. Разработал машину «Bombe», которая использовалась для дешифровки кода Enigma, во время Второй мировой войны. Офицер ордена Британской империи (OBE, 1945), с 1951 член Лондонского королевского общества.

Биография

Ранние годы

Тьюринг родился 23 июня 1912 в Лондоне в Великобритании в аристократической семьи. Его отец Джулиус Мэтисон Тьюринг происходил из старого шотландского рода и работал в Индийской гражданской службе, а мать Этель Сара Стоуни была из протестантской ирландской дворянской семьи. Родители жили в городе Чхатрапур. Отпуск отца пришёлся на 1912 год и семейство отплыло в Англию, где и родился младший сын. У Алана был старший брат Джон. Служба отца продолжалась, поэтому уже в 1913 году они с матерью вернулись в Индию, но навещали детей по возможности. Дети оставались на попечении друга семьи — отставного полковника Уорда и его жены.

Способности и интересы Алана проявились уже в раннем детстве: в шесть лет он всего за три недели самостоятельно научился читать по книге «Чтение без слёз», придумал способ найти дикий мёд. В возрасте шести лет Алан Тьюринг начал учиться в школе святого Михаила в Гастингсе, где директор сразу же заметила его талант. В десять лет Алану подарили альманах «Чудеса природы, о которых должен знать каждый ребёнок». После прочтения он изобрёл собственные варианты авторучки и печатную машинку. С детства увлекался химией — придумал новый состав чернил. В 1926 году Тьюринг поступил в престижную частную школу Шерборн в городе Шерборн, Дорсет. Мальчик отличался от сверстников, ему не удавалось влиться в коллектив, поэтому он быстро стал объектом насмешек. Учителя также не одобряли его увлечение математикой, потому что Алан в занимался только тем, что интересовало его и игнорировал остальную учебную программу. Но Алан продолжал свои занятия, так в 1927 году он представил тригонометрические функции в виде десятичного ряда с использованием чисел Бернулли, без использования элементарного дифференциального исчисления, поскольку был с ним ещё не знаком.

В Шерборне Тьюринг близко подружился с Кристофером Моркомом. Алан не знал, что мальчик ещё в детстве заразился туберкулёзом, и поэтому смерть друга в феврале 1930 года, стала для него потрясением.

Учёба в университете и начало карьеры

Окончив школу, юноша поступил в Королевский колледж Кембриджа, поскольку в Тринити-колледже ему не удалось получить стипендию на обучение. В 1931—1934 годах учился под руководством известного математика Годфри Харолда Харди.

В 1928 году немецкий математик Давид Гильберт привлек внимание к проблеме разрешения. В ноябре 1936 года Тьюринг опубликовал статью «On Computable Numbers, with an Application to the Entscheidungsproblem», в которой переосмыслил теорему Гёделя о неполноте — универсальный формальный арифметический язык Гёделя заменил на простые гипотетические устройства. Позднее эти устройства были названы машинами Тьюринга. Он доказал, что машина может выполнять любые математические вычисления, представленные в виде алгоритма. Далее Тьюринг доказал, что проблема остановки для машины Тьюринга неразрешима, тем самым опровергнув теорию Гильберта. Это доказал и Алонзо Чёрч, разработав Лямбда-исчисление, но сам Тьюринг не был знаком с этим. В дальнейшем была сформулирована теория Чёрча-Тьюринга.

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

Тьюринг поступил в Пристонский университет, где с сентября 1936 года по июль 1938 года работал под руководством Чёрча. Помимо математики изучал криптографию, а также конструировал электро-механический бинарный умножитель. В июне 1938 года защитил докторскую диссертацию «Логические системы, основанные на ординалах». В работе представлена идея сведения по Тьюрингу — объединение машины Тьюринга с оракулом. Это позволяло разрешать проблемы, которые невозможно было решить только с применением машины Тьюринга.

Криптоанализ «Энигмы»

Дешифровальная машина «Bombe»

В конце 1930-х Тьюринг начал работать в Блетчли-парке, где в то время находилось главное шифровальное подразделение Великобритании, которое сейчас называется Центром правительственной связи (GCHQ). Алан возглавлял группу Hut 8, ответственную за криптоанализ сообщений военно-морского флота Германии, шифровавшего их при помощи «Энигмы». После того как польское Бюро шифров в июле 1939 года предоставило Великобритании и Франции подробную информацию о соединениях в роторах «Энигмы» и методе расшифровки сообщений, началась работа над более основательным подходом решения проблемы. Метод польских криптографов базировался на недоработках индикаторной процедуры, однако немцы исправили их к маю 1940 года. На основе криптографического анализа алгоритма «Энигмы», проведённого Тьюрингом, в 1940 году была построена дешифровальная машина «Bombe». Он использовал метод перебора последовательностей начального текста.

Помимо «Bombe» Тьюринг определил индикаторную процедуру ВМФ Германии, разработал более действенный способ использования Bombe — «Banburismus», разработал портативный шифратор речи Delilah.

Разработанный Тьюрингом подход в разгадывании шифров имел такую ценность, что его две научные статьи («Доклад о применимости вероятностного подхода в криптоанализе» и «Документ о статистике и повторениях» ) не были переданы из Центра правительственной связи в национальный архив до апреля 2012 года.

Долгие годы оставалось в секрете, что в 1945 году за военную службу король Георг VI наградил Алана Тьюринга орденом Британской империи.

Принцип работы «Bombe»

Работа машины «Bombe» происходила в несколько этапов. Сначала машина, на основе структуры открытого текста, определяла порядок роторов, положение ротора, связи коммутационной панели. Для каждой возможной конфигурации ротора формулировался ряд логических предположений. Затем выявлялся ряд противоречий, отбрасывались определённые параметры и машина переходила к следующим. Благодаря этому, большинство возможных вариантов отбрасывалось, а для более тщательного анализа оставалось несколько вариантов. Машина была запущена 18 марта 1940 года. Вращение механических барабанов при переборе ключей имело характерный звук, напоминающий тиканье часов.

Алан Тьюринг вместе с Гордоном Уэлшманном, Стюартом Милнер-Берри и Конелом Хью О’Донелой Александером на основе материалов польского бюро шифров смогли наладить работу системы, способной к взлому шифра «Энигмы», но из-за нехватки людей и машин, времени на дешифровку всех сообщений не хватало. Немцы постоянно улучшали своё шифрование, и чтобы справиться с этим необходимо было привлечь новых людей и финансирование для постройки новых машин. Сообщение с такой просьбой было направлено Черчиллю. Меры были предприняты и к концу войны в эксплуатацию было запущено более двух сотен машин.

В ноябре 1942 года Тьюринг отправился в США, где совместно с криптоаналитиками ВМФ работал над взломом «Энигмы» и постройкой машин «Bombe» в Вашингтоне. Посетил компьютерную лабораторию в Дайтоне, штат Огайо.

Colossus

«Колосс»

Для шифрования сообщений верховного руководства немцы во время Второй мировой войны использовали «Лоренц», устройство которого был гораздо сложнее «Энигмы». Созданием машины для расшифровки сообщений занималось специальное подразделение в Блечли-Парке, которое возглавлял английский математик Макс Ньюман. В 1943 году сотрудники подразделения вместе с Томми Флауэрсом спроектировали дешифровальную машину — Colossus. Она была построена на основе схем с электронными лампами. В качестве консультанта к команде присоединился Алан Тьюринг.

Ранние компьютеры

После войны Тьюринг жил в Ричмонде и работал в Национальной физической лаборатории над ACE. В 1946 году детально описал принцип работы компьютера с хранимой программной памятью. Постройка ACE была возможна, но из-за секретности задерживалась. В 1947 году Тьюринг вернулся в Кембридж. Во время отпуска усердно работал над «Intelligent Machinery», но работа не была опубликована прижизненно. В это время был построен Pilot ACE и выполнил первую программу 10 мая 1950 года. Полная версия ACE никогда не была построена.

С 1948 года Алан Тьюринг работал в математическом департаменте Манчестерского университета. В 1949 году он стал директором компьютерной лаборатории, где программировался Манчестерский Марк I.

Тест Тьюринга

В октябре 1950 года была опубликована работа «Вычислительные машины и разум», в которой он описал искусственный интеллект и предложил эксперимент, в дальнейшем названный тест Тьюринга. Идея заключалась в следующем: если человек не сможет в процессе взаимодействия отличить компьютер от человека, то компьютер мыслит. На этом принципе основан тест CAPTCHA.

Морфогенез

Тьюринг внёс вклад в теорию морфогенеза, предположив, что некоторые упорядоченные структуры формируются путём самоорганизации на основе реакционно-диффузионного механизма. «Модель Тьюринга», так иначе называется этот механизм, предполагает наличие двух динамически взаимодействующих веществ. Активатор усиливает собственное производство и производство второго вещества — ингибитора. Ингибитор подавляет активность или уменьшает количество активатора и самого себя. Посредством диффузии они проникают из клетки в клетку, но с разной скоростью.

Личная жизнь

В 1941 году Тьюринг делал предложение коллеге Джоан Кларк, но свадьба не состоялась — учёный признался в своей гомосексуальности перед невестой.

В феврале 1952 года квартиру Алана Тьюринга ограбили. Было подано заявление в полицию, однако в ходе следствия выяснилось, что грабителем оказался его любовник — Арнольд Мюррей. Любая гомосексуальная связь между мужчинами в Великобритании тогда являлась незаконной, в соответствии с «поправкой Лабушера» мужчинам предъявили обвинение в непристойном поведении. Тьюрингу был предоставлен выбор между гормональной терапией и тюремным заключением. Он выбрал первое и после этого был отстранён от работы консультанта по криптоанализу в GCHQ.

Смерть

8 июня 1954 года в квартире учёного было обнаружено его мёртвое тело. По результатам вскрытия причиной смерти было отравление цианидом. На прикроватной тумбе было найдено откушенное яблоко, однако экспертиза на наличие цианида в нём никогда не проводилась. По официальной версии, учёный покончил жизнь самоубийством. Тело было кремировано в Крематории Уокинга 12 июня 1954 года, прах был развеян.

Помилование

В 2013 году королева Великобритании Елизавета II формально посмертно помиловала Алана Тьюринга за обвинения в «непристойности». Долгое время помилование Тьюринга было невозможным, потому что приговор учёному был вынесен в соответствии с британским законодательством тех лет. С 31 января 2017 года в Великобритании вступил в силу закон о посмертном помиловании мужчин, осуждённых за гомосексуальность.

Память

В честь Алана Тьюринга были названы: награда Ассоциации вычислительной техники (Премия Тьюринга), астероид (10204) Тьюринг, архитектура видеокарт GeForce 20. Помимо этого, в Манчестере в 2001 году установлен памятник, в 2002 году он был признан «одним из 100 величайших британцев в истории».

В нумизматике:

• В 2021 году банк Англии выпустил банкноту в 50 фунтов с портретом Тьюринга на обратной стороне купюры.
• В июле 2022 Королевский монетный двор выпустил монеты номиналом 50 пенсов, посвященные Алану Тьюрингу.

В кино:

• В 2001 году вышел фильм — «Энигма», режиссёра Майкла Эптида по одноимённому роману Роберта Харриса, в основе которого лежит история криптоанализа «Энигмы». В центре сюжета математик Том Джерико, его возлюбленная Клэр и команда. Все вместе они разгадывают код.
• В 2014 году вышла драма «Игра́ в имита́цию». Сюжет разворачивается вокруг криптографа Алане Тьюринга, взломавшего код немецкой шифровальной машины «Энигма» во время Второй мировой войны и позже привлечённого к уголовной ответственности за свою гомосексуальность. Роль исполняет британский актёр Бенедикт Камбербэтч.

В литературе:

• Тьюринг — основной персонаж романа Нила Стивенсона «Криптономикон».
• Упоминание в романе Апостолоса Доксиадиса «Дядя Петрос и проблема Гольдбаха».
• Эндрю Ходжес: «Вселенная Алана Тьюринга».

Галерея

• 

  Дом Тьюринга

• 

  Офицер ордена Британской империи

• 

  Члены Ratio Club

Ссылки

• Фотографии
• Г. Далидович «Заметки об искусственном интеллекте: маргаритки Тьюринга», «Заметки об искусственном интеллекте: Энигма Тьюринга», «Заметки об искусственном интеллекте: Яблоко Тьюринга»
• Роберт Харрис. Enigma
• Список статей, отчётов и лекций Тьюринга (англ.)
• Тьюринг и Блечли Парк