Alan Turing

Иногда именно те люди, о которых никто не может ничего вообразить, совершают то, что никто не может себе представить.

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

Во время Второй мировой войны Тьюринг работал в Правительственной школе кодов и шифров GC&CS в Блетчли-Парке, центре дешифровки Британии, который производил разведданные Ultra. Некоторое время он возглавлял Хижину 8, отдел, отвечающий за криптоанализ немецких военно-морских кодов. Здесь он разработал ряд методов для ускорения взлома немецких шифров, включая улучшения довоенного польского метода бомбы, электромеханического устройства, которое могло находить настройки машины Enigma.

Тьюринг сыграл решающую роль в расшифровке перехваченных закодированных сообщений, которые позволили союзникам разгромить нацистов во многих критически важных боях, включая Битву за Атлантику, и тем самым помог выиграть войну. Из-за проблем контрфактической истории трудно оценить точное влияние разведданных Ultra на войну, но по верхним оценкам считается, что эта работа сократила войну в Европе более чем на два года и спасла свыше 14 миллионов жизней.

После войны Тьюринг работал в Национальной физической лаборатории, где он разработал Автоматический вычислительный механизм. Автоматический вычислительный механизм был одной из первых разработок компьютера с сохраняемой программой. В 1948 году Тьюринг присоединился к Лаборатории вычислительных машин Max Newman в Манчестерском университете Виктории, где он помогал разрабатывать манчестерские компьютеры и начал интересоваться математической биологией. Он написал статью о химической основе морфогенеза и предсказал колебательные химические реакции, такие как реакция Белоусова–Жаботинского, впервые наблюдаемая в 1960-х годах.

Тьюринг был привлечён к уголовной ответственности в 1952 году за гомосексуальные действия; поправка Лабушера 1885 года предусматривала, что «грубое оскорбление нравственности» является уголовным преступлением в Великобритании. Он согласился на химическую кастрацию с использованием DES в качестве альтернативы тюремному заключению. Тьюринг умер в 1954 году, за 16 дней до своего 42-го дня рождения, от отравления цианидом. Судебное разбирательство установило его смерть как самоубийство, но отмечалось, что известные доказательства также согласуются со случайным отравлением.

В 2009 году, после интернет-кампании, британский премьер-министр Gordon Brown принёс официальное публичное извинение от имени британского правительства за «ужасный способ, которым с ним обращались». Королева Елизавета II посмертно помиловала Тьюринга в 2013 году. «Закон Алана Тьюринга» теперь является неофициальным термином для закона Великобритании 2017 года, который ретроактивно помиловал мужчин, предупреждённых или осуждённых согласно историческому законодательству, которое запрещало гомосексуальные действия.

Ранняя жизнь и образование

Семья

Тьюринг родился в Maida Vale, Лондоне, пока его отец, Julius Mathison Turing 1873–1947, был в отпуске со своей должности в Индийской гражданской службе ICS в Chatrapur, тогда находившемся в президентстве Мадраса и в настоящее время в штате Одиша, в Индии. Отец Тьюринга был сыном священника, преп. John Robert Turing, из шотландской семьи торговцев, базировавшейся в Нидерландах и включавшей баронета. Мать Тьюринга, жена Julius, была Ethel Sara Turing, урождённая Stoney 1881–1976, дочь Edward Waller Stoney, главного инженера железных дорог Мадраса. Stoneys были протестантской англо-ирландской дворянской семьёй из графств Tipperary и Longford, в то время как сама Ethel провела большую часть своего детства в графстве Clare.

Работа Julius в ICS привела семью в Британскую Индию, где его дед был генералом в Бенгальской армии. Однако как Julius, так и Ethel хотели, чтобы их дети воспитывались в Британии, поэтому они переехали в Maida Vale, Лондон, где Алан Тьюринг родился 23 июня 1912 года, как указано на синей табличке снаружи дома его рождения, позже гостиницы Colonnade Hotel. У Тьюринга был старший брат John, отец Sir John Dermot Turing, 12-го баронета из баронетства Turing.

Гражданская служба отца Тьюринга оставалась активной, и в детские годы Тьюринга его родители путешествовали между Hastings в Великобритании и Индией, оставляя своих двух сыновей с вышедшей в отставку армейской четой. В Hastings Тьюринг остановился в Baston Lodge, Upper Maze Hill, St Leonards-on-Sea, теперь отмеченном синей табличкой. Табличка была открыта 23 июня 2012 года, в столетнюю годовщину рождения Тьюринга.

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

Школа

Родители Тьюринга записали его в St Michael's, дневную школу на 20 Charles Road, St Leonards-on-Sea, в возрасте шести лет. Директриса рано признала его талант, как и многие его последующие учителя.

С января 1922 по 1926 год Тьюринг учился в Hazelhurst Preparatory School, независимой школе в деревне Frant в Sussex, теперь East Sussex. В 1926 году, в возрасте 13 лет, он поступил в Sherborne School, интернат независимой школы в рыночном городе Sherborne в Dorset, где он проживал в Westcott House. Первый день занятий совпал с Всеобщей забастовкой 1926 года в Британии, но Тьюринг был настолько полон решимости присутствовать, что проехал на велосипеде без сопровождения 60 миль (97 км) из Southampton в Sherborne, переночевав в гостинице.

Мы можем видеть только на небольшое расстояние вперёд, но мы видим много всего, что нужно сделать.

Естественный склад Тьюринга к математике и естественным наукам не принёс ему уважения от некоторых учителей в Sherborne, чьё определение образования придавало большее значение классике. Его директор написал его родителям: «Я надеюсь, что он не упадёт между двумя стульями. Если ему суждено остаться в государственной школе, он должен стремиться получить образование. Если он хочет быть исключительно научным специалистом, он теряет своё время в государственной школе». Несмотря на это, Тьюринг продолжал проявлять замечательные способности в изучаемых им предметах, решая сложные задачи в 1927 году, не изучив даже элементарного исчисления. В 1928 году, в возрасте 16 лет, Тьюринг познакомился с работами Albert Einstein; он не только понял её, но, возможно, смог вывести возражение Einstein против законов движения Newton из текста, в котором это никогда не было явно сказано.

Christopher Morcom

В Sherborne Тьюринг сформировал значительную дружбу с однокурсником Christopher Collan Morcom (13 июля 1911 – 13 февраля 1930), который был описан как «первая любовь» Тьюринга. Их отношения вдохновили Тьюринга в его будущих начинаниях, но они были прерваны смертью Morcom в феврале 1930 года от осложнений туберкулёза крупного рогатого скота, заражённого после употребления инфицированного коровьего молока несколько лет назад.

Это событие причинило Тьюрингу большую печаль. Он справился со своей скорбью, работая ещё усерднее над темами науки и математики, которыми он делился с Morcom. В письме матери Moromb, Frances Isobel Moromb, урождённой Swan, Тьюринг написал:

Я уверен, что не мог бы найти больше нигде такого товарища, столь блестящего и в то же время столь очаровательного и скромного. Я считал своё увлечение работой и такими вещами, как астрономия (в которую он меня ввёл), чем-то, что нужно было разделить с ним, и я думаю, что он чувствовал то же самое по отношению ко мне ... Я знаю, что должен вложить столько энергии, если не больше интереса, в свою работу, как если бы он был жив, потому что это то, что он хотел бы, чтобы я делал.

Отношения Тьюринга с матерью Moromb продолжались долго после смерти Moromb, она отправляла ему подарки, а он отправлял письма, как правило, на день рождения Moromb. За день до третьей годовщины смерти Moromb (13 февраля 1933 года) он написал миссис Moromb:

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

Некоторые предположили, что смерть Moromb была причиной атеизма и материализма Тьюринга. По-видимому, на этом этапе своей жизни он ещё верил в такие понятия, как дух, независимый от тела и пережившие смерть. В более позднем письме, также написанном матери Moromb, Тьюринг написал:

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

Университет и работа над вычислимостью

После Sherborne Тьюринг учился студентом с 1931 по 1934 год в King's College, Cambridge, где получил первоклассные отличия по математике. В 1935 году, в возрасте 22 лет, он был избран Fellow of King's College на основе диссертации, в которой доказал центральную предельную теорему. Неизвестно комиссии, теорема уже была доказана в 1922 году Jarl Waldemar Lindeberg. Синяя табличка в колледже была открыта в столетнюю годовщину его рождения 23 июня 2012 года и теперь установлена в здании Keynes Building на King's Parade колледжа.

В 1936 году Тьюринг опубликовал свою статью «О вычислимых числах с применением к проблеме Entscheidungsproblem». Она была опубликована в журнале Proceedings of the London Mathematical Society в двух частях, первая 30 ноября и вторая 23 декабря. В этой статье Тьюринг переформулировал результаты Kurt Gödel 1931 года о границах доказательства и вычисления, заменив универсальный арифметический формальный язык Gödel на формальные и простые гипотетические устройства, которые стали известны как машины Тьюринга. Проблема решения Entscheidungsproblem была первоначально поставлена немецким математиком David Hilbert в 1928 году. Тьюринг доказал, что его «универсальная вычислительная машина» была бы способна выполнять любое мыслимое математическое вычисление, если бы оно было представимо в виде алгоритма. Затем он доказал, что не было решения для проблемы решения, сначала показав, что проблема остановки для машин Тьюринга неразрешима: невозможно алгоритмически решить, остановится ли когда-нибудь машина Тьюринга. Эта статья была названа «легко самой влиятельной математической статьёй в истории».

Хотя доказательство Тьюринга было опубликовано вскоре после эквивалентного доказательства Alonzo Church, использующего его лямбда-исчисление, подход Тьюринга значительно более доступен и интуитивен, чем подход Church. Он также включал понятие «универсальной машины», теперь известной как универсальная машина Тьюринга, с идеей, что такая машина могла бы выполнять задачи любой другой вычислительной машины, как и лямбда-исчисление Church. Согласно тезису Church–Turing, машины Тьюринга и лямбда-исчисление способны вычислять всё, что является вычислимым. John von Neumann признал, что центральная концепция современного компьютера принадлежит статье Тьюринга. По сей день машины Тьюринга являются центральным объектом изучения в теории вычислений.

С сентября 1936 по июль 1938 года Тьюринг провёл большую часть своего времени, обучаясь под руководством Church в Princeton University, на втором году в качестве Jane Eliza Procter Visiting Fellow. Помимо своей чисто математической работы, он изучал криптологию и также построил три из четырёх этапов электромеханического двоичного умножителя. В июне 1938 года он получил степень PhD в Департаменте математики Princeton; его диссертация, Systems of Logic Based on Ordinals, представила концепцию порядковой логики и понятие относительного вычисления, в котором машины Тьюринга дополнены так называемыми оракулами, позволяя изучать проблемы, которые не могут быть решены машинами Тьюринга. John von Neumann хотел нанять его в качестве своего постдокторского ассистента, но он вернулся в Великобританию.

Карьера и исследования

Когда Тьюринг вернулся в Cambridge, он посещал лекции, прочитанные в 1939 году Ludwig Wittgenstein об основаниях математики. Лекции были восстановлены дословно, включая замечания Тьюринга и других студентов, из записей студентов. Тьюринг и Wittgenstein спорили и расходились во мнениях, Тьюринг защищал формализм, а Wittgenstein отстаивал свой взгляд, что математика не открывает никаких абсолютных истин, а скорее их изобретает.

Криптоанализ

Во время Второй мировой войны Тьюринг был ведущим участником взлома немецких шифров в Блетчли-Парке. Историк и криптограф военного времени Asa Briggs сказал: «Вам нужны были бывшие