ТЬЮРИНГ, АЛАН МАТИСОН (Turing, Alan Mathison) (1912–1954), английский математик. Родился в Лондоне 23 июня 1912. Учился в Шерборнской школе, где проявил незурядные способности к математике и химии, затем в Кингз-колледже Кембриджского университета, который окончил в 1934. Непосредственным его учителем, а впоследствии коллегой был математик (тополог) М.Х.А.Ньюмен (1897–1984); Тьюринг слушал его курс по основаниям математики в 1935. В том же году Тьюринг получил стипендию Кингз-колледжа для работы над диссертацией. В 1936–1938 – в Принстонском университете в США, где его научным руковдителем был американский логик А.Чёрч (1903–1995). После получения докторской степени Тьюринг отклонил предложение Дж. фон Неймана остаться в США и вернулся в Кембридж, где получил стипендию Кингз-колледжа для занятий логикой и теорией чисел, посещая одновременно семинары Л.Витгенштейна по философии математики. В это же время началось его конфиденциальное сотрудничество с правительственной Школой кодов и шифров (Government Code and Cypher School) в Блечли-Парке, где он еще до войны участвовал в работах по раскрытию немецких шифров.
После начала Второй мировой войны Тьюринг полностью перешел на работу в Блечли-Парк. Используя более ранние польские наработки, совместно с У.Уэлчманом раскрыл шифры германских ВВС, создав дешифровочную машину «Бомба», а к концу 1939 самостятельно взломал гораздо более сложный шифр, использовавшийся в шифровальных машинах «Энигма», которыми были оснащены германские подводные лодки (см. КРИПТОГРАФИЯ). После первого успеха противостояние с «Энигмой» продолжалось еще несколько лет, но начиная с весны 1943 весь информационный обмен германских ВМС легко расшифровывался союзниками, к этому времени уже использовавшими электронную технику. Тьюринг занимался также разработкой шифров для переписки Черчилля и Рузвельта, проведя период с ноября 1942 по март 1943 в США. Был удостоен звания кавалера Ордена Британской империи 4-й степени.
Павел Паршин
Современным математикам, программистам и компьютерным инженерам имя Алана Тьюринга хорошо знакомо еще со студенческой скамьи: всем им приходилось изучать "машину Тьюринга" - "основу основ" теории алгоритмов. Без "машины Тьюринга" не обходится ни один серьезный учебник по математической логике и теории вычислимости.
Почти за каждым выдающимся научным открытием стоит удивительная история. За "машиной Тьюринга" стоит история жизни научного гения - гения, который лишь через много лет после своей трагической смерти получил достойное признание.
Роль А.Тьюринга в истории информатики отнюдь не исчерпывается одним лишь изобретением "машины Тьюринга", как это может иногда показаться из-за относительной скудости опубликованных (на русском языке) сведений о нем.
Алан Тьюринг может быть причислен к плеяде составляющих гордость человечества величайших математических и философских умов, таких, как Р.Декарт, Г.В. Лейбниц, Б.Рассел, Д.Гильберт, А.Витгенштейн. Удивительно, сколь злую шутку сыграло с Тьюрингом его полное безразличие к борьбе за приоритет в научных открытиях: вплоть до недавнего времени его место в истории развития научных и инженерных идей представлялось очень неполно, если не сказать однобоко (и не в последнюю очередь благодаря некоторым американским историкам науки, тщательно заботившимся об абсолютизации своего национального приоритета в создании компьютеров, да и, пожалуй, в создании всей информатики).
Кстати, именно Алан Тьюринг впервые пустил в обращение сам термин "компьютер" в современном понимании. До этого так называли тех, кто занимался вычислениями, например, банковских служащих, работавших на арифмометре.
Мемориальная доска, установленная на стене одной из лондонских гостиниц, гласит:
"Здесь родился Алан Тьюринг (1912 - 1954), взломщик кодов и пионер информатики ". Действительно, сейчас (но отнюдь не при жизни!) Тьюринг признан одним из основателей информатики и теории искусственного интеллекта, его считают первым теоретиком современного программирования и, наконец, первым в мире хакером. (Между прочим, его "хакерская деятельность" внесла во время второй мировой войны существенный вклад в победу союзных войск над германским флотом, а один из коллег Тьюринга однажды сказал: "Я не берусь утверждать, что мы выиграли войну благодаря Тьюрингу. Однако без него могли бы ее и проиграть".)
Будущие родители Алана Тьюринга - Юлиус Мэтисон Тьюринг и Этель Сара Стоуни познакомились и обвенчались в Индии. Тьюринг служил в английском колониальном ведомстве, а Этель Сара была дочерью главного инженера Мадрасских железных дорог. Это была добропорядочная английская аристократическая семья, принадлежавшая к так называемому "высшему среднему классу" (upper-middle-class) и жившая в соответствии со строгими традициями Империи.
Лучшие дня
Спустя год после родов мать Тьюринга вернулась в Индию, оставив Алана на попечение друга семьи, отставного полковника. Позже мальчика отдали в частный интернат.
Маленький Алан обладал очень пытливым умом. Самостоятельно научившись читать в возрасте б лет, он просил у своих воспитателей разрешения читать научно-популярные книги. В 11 лет он ставил вполне грамотные химические опыты, пытаясь извлечь йод из водорослей. Все это доставляло огромное беспокойство его матери, которая боялась, что увлечения сына, идущие вразрез с традиционным воспитанием, помешают ему поступить в Public School (английское закрытое частное учебное заведение для мальчиков, учеба в котором была обязательна для детей аристократов). Но ее опасения оказались напрасны: Алан смог поступить в престижную Шербонскую школу (Sherborne Public School). Впрочем, вскоре ей пришлось опасаться уже того, сможет ли ее талантливый сын окончить эту школу...
О школьных успехах Алана красноречиво свиде¬тельствует классный журнал -
юный Алан Тьюринг ничего не делал на уроках, а в свободное время - изучал "внеклассные" науки. Пятнадцатилетним подростком он самостоятельно изучил теорию относительности: его дневниковые заметки сделали бы и в наше время честь студенту-младшекурснику.
Обстановка и стиль обучения в классической британской школе, воспитывающей добропорядочных и благонадежных подданных Империи, не располагали к дальнейшему росту подобных интересов, которые к тому же Тьюрингу было совсем не с кем разделить. Преподаваемые предметы оставляли его полностью равнодушным, он успевал еле-еле и в конце концов оказался перед реальной перспективой отказа в выдаче школьного аттестата, что в очередной раз привело его мать в ужас.
Юношеская жажда знаний быстро сблизила Тьюринга и Моркома, они стали неразлучными друзьями. Теперь они на уроках французского языка уже вместе зевали или играли в крестики-нолики, одновременно обсуждая астрономию и математику. После окончания школы они оба собирались поступать в Кембриджский университет, и Алан, избавившийся от многолетнего одиночества, возможно, был почти счастлив...
Первая попытка сдать предварительные экзамены в Кембридж, куда они ездили вместе, была для Алана неудачной. Но он не слишком расстраивался, потому что искренне радовался за Кристофера, который успешно прошел испытания и получил стипендию. Алан надеялся поступить со второй попытки, чтобы учиться вместе со своим другом. 13 февраля 1930 г. его Криса вдруг не стало. Внезапная смерть лучшего друга потрясла семнадцатилетнего Тьюринга, повергнув его в глубокую и долгую депрессию. Тем не менее, он, бывший худший ученик в классе, нашел в себе силы поступить в Кембридж. Его поддерживало твердое убеждение в своей обязанности совершить в науке то, что Кристофер уже не мог... Тьюринг очень не скоро оправится от потрясения: уже будучи студентом Кембриджа, на протяжении нескольких лет он пишет матери Моркома проникнутые душевной болью письма. В этих письмах он постоянно возвращается к размышлениям о том, как человеческий Разум - и, в частности, разум Кристофера - размешается внутри материальной оболочки и каким образом он освобождается от нее в момент физической смерти тела.
В 1932 году, во время одного из посещений семьи Моркомов, он составляет в их доме документ под названием "Природа Духа" - манифест своей веры в существование человеческого Духа после смерти. Основное положение этой работы состоит в том, что детерминизм традиционной физической картины мира и его очевидное противоречие с идеей свободы воли опровергаются новой наукой - квантовой физикой.
Вопрос об устройстве человеческого разума будет волновать его всю жизнь.
В 1939 году британское военное ведомство поставило перед Тьюрингом задачу разгадать секрет "Энигмы" – специального устройства, использовавшегося для шифровки радиограмм в германском военно-морском флоте и в "люфтваффе". Британская разведка раздобыла это устройство, но расшифровывать перехваченные радиограммы немцев не удавалось.
Тьюрингу была предоставлена свобода действий. Он пригласил в свой отдел "Британской школы кодов и шифров" нескольких друзей-шахматистов. У него работал, например, Гарри Голомбек, ставший впоследствии известным судьёй ФИДЕ и судивший финальный матч на звание чемпиона мира между Фишером и Спасским.
27-летнего Тьюринга и его коллег охватил настоящий спортивный азарт. Немцы считали "Энигму" неприступной. Сложность дешифровки усугублялась тем, что в закодированном слове получалось больше букв, чем в оригинале. Тем не менее, Тьюринг уже через полгода разработал устройство, названное им "Бомбой", которое позволяло читать практически все сообщения "люфтваффе". А спустя ещё год был "взломан" и более сложный вариант "Энигмы", использовавшийся нацистскими подводниками. Это во многом предопределило успех британского флота.
Заслуги Алана Тьюринга были по достоинству оценены: после разгрома Германии он получил орден, был включён в научную группу, занимавшуюся созданием британской электронно-вычислительной машины. В 1951 году в Манчестере начал работать один из первых в мире компьютеров. Тьюринг занимался разработкой программного обеспечения для него. Тогда он написал и первую шахматную программу для ЭВМ. Это был только алгоритм, потому что компьютера, способного применить эту программу, ещё не существовало.
Шахматы были не единственным хобби этого человека. Он занимался бегом, кроссом по пересеченной местности. В 1947 году на Всеанглийском марафоне занял почётное пятое место. Кроме работы в университете, Тьюринг продолжал сотрудничать и с Департаментом кодов. Только теперь в центре его внимания были уже шифры советской резидентуры в Англии. В 1951 году он был избран членом королевского научного общества.
Всё рухнуло буквально в один день. В 1952 году квартиру Тьюринга обокрали. В ходе расследования выяснилось, что это сделал один из друзей его сексуального партнёра. Учёный никогда, в общем-то, не скрывал своей "нетрадиционной сексуальной ориентации", но и вызывающе себя не вёл. Однако скандал с кражей получил широкую огласку, и в результате обвинение в "непристойном поведении" было выдвинуто против самого Тьюринга. 31 марта 1953 года состоялся суд. Приговор предполагал выбор: либо тюремное заключение, либо инъекции женского гормона эстрогена (способ химической кастрации). Он выбрал последнее.
Из Департамента кодов его уволили. Лишили допуска к секретным материалам. Правда, коллектив преподавателей Манчестерского университета взял Тьюринга на поруки, но он и в университете почти не появлялся. 8 июня 1954 года Алан Мэтисон Тьюринг был найден мёртвым в своём доме. Он покончил жизнь самоубийством, отравившись цианистым калием.
Раствор цианида Тьюринг впрыснул в яблоко. Надкусив его, он скончался. Говорят, именно этот плод, найденный затем на ночном столике Алана, и стал эмблемой знаменитой компьютерной фирмы "Эппл". Впрочем, яблоко – это еще и библейский символ познания и греха..
В рубрике «Икона эпохи» мы рассказываем о художниках, дизайнерах, режиссёрах, музыкантах и других творческих профессионалах, которым удалось создать узнаваемый стиль и повлиять на современную культуру. Наш герой на этой неделе - основоположник информатики, математик и криптограф Алан Тьюринг, который был посмертно помилован 24 декабря королевой Великобритании.
Алан Мэтисон
Тьюринг
(Alan Mathison Turing)
1912-1954, Великобритания
математик, логик, криптограф
Первые годы и успехи в учёбе
Историю современных компьютеров можно рассказывать по-разному: в «Википедии» она, например, начинается с изобретения счёта в Древнем Вавилоне примерно 6 000 лет назад. Однако наиболее значительный скачок, который привёл к появлению компьютеров, произошёл в первой половине XX века, когда были изобретены первые вычислительные машины. Одной из них была «машина Тьюринга» - гипотетическое устройство, придуманное в 1936 году Аланом Тьюрингом - учёным, которого считают одним из основоположников информатики.
Изобретателю вычислительной машины было всего 24 года - будущий математик и учёный с детства проявлял нетипичные способности и быстро достиг высот в математике. Он поступил в школу в 6 лет, и уже тогда его преподаватели заметили, что он одарённый ребенок. В 13 лет Тьюринг начал учиться в знаменитой независимой школе для мальчиков Sherborne School в Дорсете, которая существует с XVI века: там он добился больших успехов в математике, но его учителя не одобряли этого, потому что считали гуманитарные науки более важными.
В 1928 году Тьюринг познакомился с Кристофером Морком - одарённым мальчиком, который тоже интересовался математикой и новыми технологиями. Два года спустя Морком умер от «бычьего туберкулеза». Тьюринг предчувствовал смерть близкого друга и был поражён тем, что наука не может объяснить такие ощущения. Смерть Моркома очень повлияла на учёного, его философские взгляды и представление о смерти. На протяжении всей своей жизни он пытался найти рациональное объяснение таким событиям, и его размышления на эту тему легли в основу статьи «О вычислимых числах в приложении к проблеме разрешения».
«Машина Тьюринга» и расшифровка сообщений «Энигмы»
В 1931 году будущий учёный поступил в Кембридж, где его учителем был известный математик Годфри Харолд Харди, исследовавший теорию чисел и теорию функций. Закончив колледж в 1934 году, Тьюринг начал посещать лекции учёного Макса Ньюмена, где узнал о проблеме «разрешимости» Гилберта . Размышляя над этой проблемой, Тьюринг придумал устройство, которое могло бы выполнять функции любой другой машины, то есть вычислять всё, что возможно вычислить. Эта концепция была названа «машиной Тьюринга». Кроме того, в своей статье Тьюринг доказал, что проблема остановки такой машины неразрешима, опровергнув теорию Гилберта. Это же доказал и математик и логик Алонзо Чёрч, с которым Тьюринг работал в 1936-1938 гг. в Принстонском университете.
«Бомба»
В конце 1930-х Тьюринг начал работать в Блетчли-парке - особняке в Милтон Кинсе (город неподалёку от Лондона), где то время находилось главное шифровальное подразделение Великобритании, которое сейчас называется Центром правительственной связи (GCHQ). Там Тьюринг вместе с другими учёными пытался дешифровать «Энигму» - портативную машину для шифрования сообщений, которые использовали немецкие военные. На основе криптографического анализа алгоритма «Энигмы», который провёл Тьюринг, в 1940 году была построена дешифровальная машина «Бомба». Она расшифровала множество сообщений немцев: благодаря ей англичане узнали о планах вторжения в СССР и о деятельности немецких подводных лодок во время операции «Битва за Атлантику» .
Блетчли-парк
Последние годы и посмертное признание
Гомосексуализм считался преступлением в Великобритании с конца XVI века: сначала, согласно «Акту о содомии», гомосексуалистов казнили, но в XIX веке это наказание было заменено тюремным заключением. В 1885 году была принята «поправка Лабушера» , по которой был осуждён Оскар Уайльд - она действовала до 1967 года, и именно в соответствии с ней судили и Тьюринга. Он никогда не скрывал свою ориентацию - об этом знали все его друзья и коллеги, в том числе и те, которые работали с ним во время войны.
Однако в 1952 году Тьюринга осудили за связь с 19-летним Арнольдом Мюреем. Молодой человек обокрал дом учёного, Тьюринг заявил в полицию, и ему пришлось рассказать полицейским о связи с Мюреем. Учёного осудили: он должен был выбрать между тюремным заключением и химической кастрацией. Он выбрал последнее. Кроме того, ему было запрещено работать в GCHQ, и это стало трагедией для Тьюринга - в 1954 году он покончил жизнь самоубийством.
В последующие десятилетия, когда «поправка Лабушера» была отменена, Тьюринга признали одним из 100 величайших британцев в истории, а 24 декабря 2013 года он был посмертно помилован королевой Великобритании. Кроме того, Тьюринг стал иконой британского квир-сообщества и кумиром многих математиков - спустя 100 лет после его рождения, в 2012 году, в Великобритании и других странах отмечался «Год Алана Тьюринга» , в рамках которого было организованы научные конференции, выставки и другие события.
Таймлайн
Знакомится с Кристофером Морком
Поступает King’s College в Кембридже
Изобретает «машину Тьюринга», пишет статью
«О вычислимых числах в приложении к проблеме разрешения» и начинает работать в Принстонском университете
Начинает работать в GCHQ
Отправляется в США для строительства «Бомбы» в Вашингтоне
Награждён орденом Британской империи за военную службуне могут его пройти.
Становление информатики как науки
Тьюринг считается одним из основоположников информатики. В своих статьях он формализировал важное для этой науки понятие «алгоритма». Кроме того, учёный фактически изобрел устройство-прототип IBM и всех современных компьютеров - «машину Тьюринга». До нее существовала только механическая вычислительная машина Чарльза Бэббиджа, который построил ее в начале XIX века.
В первой половине XX века, когда были изобретены первые вычислительные машины. Однако наряду с физически осязаемыми машинами появлялись и машины-концепции. Одной из них была «машина Тьюринга» - абстрактное вычислительное устройство, придуманное в 1936 году Аланом Тьюрингом - учёным, которого считают одним из основоположников информатики.
Его кругозор распространялся от квантовой теории и принципа относительности до психологии и неврологии. А в качестве способа познания и передачи своих знаний Тьюринг использовал аппарат математики и логики. Он находил решения, казалось бы, нерешаемых задач, но был сильнее всего увлечен идеей «Универсальной машины», способной вычислить всё, что в принципе вычислимо.
Детство, образование, увлечения
Родители Алана жили в индийском городе Чхатрапур. Отец - Юлиус Мэтисон Тьюринг представитель старого шотландского аристократического рода, работал в Имперской государственной службе. Мать - Сара Этель (урожденная Стони), была родом из Ирландии, из протестантской семьи англо-ирландского дворянства. Когда она ждала ребёнка, супруги решили переехать в Англию, чтобы он рос и воспитывался в Лондоне.Там Алан Тьюринг и родился 23 июня 1912 года. У него был старший брат Джон. Государственная служба Юлиуса Тьюринга продолжалась и родителям Алана приходилось часто путешествовать между Гастингсом и Индией, оставляя двоих своих сыновей на попечение отставной армейской пары. Признаки гениальности проявлялись у Тьюринга с раннего детства.
В детстве Алан и его старший брат Джон довольно редко видели своих родителей - их отец до 1926 года служил в Индии; дети оставались в Англии и жили на попечении в частных домах, получая строгое английское воспитание, соответствующее их положению на социальной лестнице. В рамках такого воспитания изучение основ естественных наук фактически не предусматривалось.
Маленький Алан обладал очень пытливым умом. Самостоятельно научившись читать в возрасте 6 лет, он просил у своих воспитателей разрешения читать научно-популярные книги.
В 11 лет он ставил вполне грамотные химические опыты, пытаясь извлечь йод из водорослей. Все это доставляло огромное беспокойство его матери, которая боялась, что увлечения сына, идущие вразрез с традиционным воспитанием, помешают ему поступить в Public School (английское закрытое частное учебное заведение для мальчиков, учеба в котором была обязательна для детей аристократов). Но её опасения оказались напрасны: Алан смог поступить в престижную Шербонскую школу (Sherborne Public School).
В шесть лет Алан Тьюринг пошёл в школу святого Михаила в Гастингсе, директор которой сразу отметила его одарённость. В 1926 году, в возрасте 13 лет, Тьюринг пошёл в известную частную школу Шерборн в городе Шерборн графства Дорсет. Его первый день в школе совпал со Всеобщей забастовкой 1926 года. Поэтому Тьюрингу пришлось преодолеть расстояние около 100 км от Саутгемптона до Шерборна на велосипеде, по пути он переночевал в гостинице.
Увлечение Тьюринга математикой не нашло особой поддержки среди учителей Шерборнской школы, где уделяли больше внимания гуманитарным наукам. Директор школы писал родителям: «Я надеюсь, что он не будет пытаться усидеть на двух стульях разом. Если он намеревается остаться в частной школе, то он должен стремиться к получению «образования». Если же он собирается быть исключительно «научным специалистом», то частная школа для него - пустая трата времени».
О школьных успехах Алана красноречиво свидетельствует классный журнал, в котором можно найти, например, следующее
Я могу смотреть сквозь пальцы на его сочинения, хотя ничего ужаснее в жизни своей не видывал, я пытаюсь терпеть его непоколебимую небрежность и непристойное прилежание; но вынести потрясающую глупость его высказываний во время вполне здравой дискуссии по Новому Завету я, все же, не могу.
Тем не менее, в областях, интересовавших его, Тьюринг проявлял незаурядные способности.
В 1928 году, в возрасте 16 лет, Тьюринг ознакомился с работой Эйнштейна, в которой ему удалось разобраться до такой степени, что он смог догадаться из текста о сомнениях Эйнштейна относительно выполнимости Законов Ньютона, которые не были высказаны в статье в явном виде.
Университет
Из-за нелюбви к гуманитарным наукам Тьюринг недобрал баллов на экзамене и поэтому после школы поступил в Королевский колледж Кембриджа, хотя намеревался пойти в Тринити-колледж. В Королевском колледже Тьюринг учился с 1931 по 1934 год под руководством известного математика Годфри Харолда Харди.Кембриджский университет, обладавший особыми привилегиями, дарованными английскими монархами, издавна славился либеральными традициями, и в его стенах всегда царил дух свободомыслия. Здесь Тьюринг обретает – пожалуй, впервые – свой настоящий дом, где он смог полностью отдаться науке.
Главное место в жизни заняло увлечённое изучение столь интересующих его наук – математики и квантовой физики. Те годы были периодом бурного становления квантовой физики, и Тьюринг в студенческие годы знакомится с самыми последними работами в этой области. Большое впечатление производит на него книга Джона фон Неймана «Математические основы квантовой механики», в которой он находит ответы на многие давно интересующие его вопросы.
Тогда Тьюринг, наверное, и не предполагал, что через несколько лет фон Нейман предложит ему место в Принстоне – одном из самых известных университетов США. Ещё позже фон Нейман, так же как и Тьюринг, будет назван «отцом информатики». Но тогда, в начале 30-х годов ХХ века, научные интересы обоих будущих выдающихся учёных были далеки от вычислительных машин – и Тьюринг, и фон Нейман занимаются в основном задачами «чистой» математики.
Тьюринг происходил из аристократической семьи, но никогда не был «эстетом»: кембриджские политические и литературные кружки были чужды ему. Он предпочитал заниматься своей любимой математикой, а в свободное время ставить химические опыты, решать шахматные головоломки.
Ставя химические опыты, он играл в особую игру «Необитаемый остров», изобретенную им самим. Цель игры заключалась в том, чтобы получать различные «полезные» химические вещества из «подручных средств» – стирального порошка, средства для мытья посуды, чернил и тому подобной «домашней химии».
Он также находил отдых в интенсивных занятиях спортом – греблей и бегом. Марафонский бег останется его поистине страстным увлечением до конца жизни.
Тьюринг блестяще заканчивает четырёхлетний курс обучения. Одна из его работ, посвященная теории вероятностей, удостаивается специальной премии, его избирают в научное общество Королевского колледжа. В 1935 году Тьюринг публикует работу «Эквивалентность левой и правой почти-периодичности», в которой он упрощает одну идею фон Неймана в теории непрерывных групп – фундаментальной области современной математики. Казалось, его ждет успешная карьера слегка эксцентричного кембриджского преподавателя, работающего в области «чистой» математики.
Однако Тьюринг никогда не удерживался в каких-либо «рамках». Никто не мог предвидеть, какая экзотическая проблема неожиданно увлечет его, и какой математически неординарный способ ее решения ему удастся придумать.
Кроме того, в Кембридже Алан посещал лекции Виттенштейна Людвига. Виттенштейн утверждал теорию о несостоятельности математики. По его словам математика не ищет истину, но сама создаёт её. Алан был с этим не согласен и много спорил с Людвигом. Тьюринг выступал за «формализм» - математическое философское течение, которое не требовало точного перевода слов и ограничивалось примерным смыслом. А Людвиг искал абсолютной точности.
Во время обучения в колледже Алан Тьюринг изучал основы криптографии – то есть расшифровки данных. Это пригодилось ему во время Второй Мировой войны, когда учёный работал над расшифровкой немецких посланий.
Машина Тьюринга
В 1928 году немецкий математик Давид Гильберт привлек внимание мировой общественности к проблеме разрешения (Entscheidungsproblem). В своей работе «On Computable Numbers, with an Application to the Entscheidungsproblem», опубликованной 12 ноября 1936 года. Тьюринг переформулировал теорему Гёделя о неполноте, заменив универсальный формальный арифметический язык Гёделя на простые гипотетические устройства, которые впоследствии стали известны как машины Тьюринга.Он доказал, что подобная машина была бы способна произвести любые математические вычисления, представимые в виде алгоритма. Далее Тьюринг показал, что не существует решения Entscheidungsproblem, сперва доказав, что Проблема остановки для машины Тьюринга неразрешима: в общем случае невозможно алгоритмически определить, остановится ли когда-нибудь данная машина Тьюринга.
Хотя доказательство Тьюринга было обнародовано в скором времени после эквивалентного доказательства Алонзо Чёрча, в котором использовались Лямбда-исчисления, сам Тьюринг был с ним не знаком. Подход Алана Тьюринга принято считать более доступным и интуитивным. Идея «Универсальной Машины», способной выполнять функции любой другой машины, или другими словами, вычислить всё, что можно, в принципе, вычислить, была крайне оригинальной. Фон Нейман признал, что концепция современного компьютера основана на этой работе Алана Тьюринга. Машины Тьюринга по-прежнему являются основным объектом исследования теории алгоритмов.
На вопрос : «Что такое машина Тьюринга и какое отношение она имеет к программированию?» один из пользователей Toster ответил так:
В первую очередь - это формальное определение алгоритма. Задача считается алгоритмически разрешимой тогда и только тогда, когда её решение можно запрограммировать на машине Тьюринга (или каким-нибудь другим эквивалентным способом). Это определение даёт, например, возможность предъявить алгоритмически неразрешимые задачи. Позволяет ввести понятие «Тьюринг-полного» языка - если на языке можно реализовать машину Тьюринга, то на нём можно написать любой алгоритм (препроцессор языка С таким не является, а C# - является).В общем, МТ - способ определить некоторый класс алгоритмов:
Некоторые задачи можно решить конечным автоматом;
- для некоторых потребуется конечный автомат со стековой памятью;
- для других достаточно машины Тьюринга;
- для остальных требуется божественное откровение или другие неалгоритмизируемые методы.
С сентября 1936 года по июль 1938 Тьюринг работал под руководством Чёрча в Принстоне. Кроме занятий математикой, учёный изучал криптографию, а также конструировал электромеханический бинарный умножитель.
В июне 1938 года Тьюринг защитил докторскую диссертацию «Логические системы, основанные на ординалах», в которой была представлена идея сведения по Тьюрингу, заключающаяся в объединении машины Тьюринга с оракулом. Это позволяет исследовать проблемы, которые невозможно решить с помощью лишь машины Тьюринга.
Криптоанализ
Во время Второй мировой войны Алан Тьюринг принимал активное участие во взломе немецких шифров в Блетчли-парке. Историк и ветеран Блетчли-парка Эйза Бригс однажды сказал:«Блетчли-парку был нужен исключительный талант, исключительная гениальность, и гениальность Тьюринга была именно такой».
С сентября 1938 года Тьюринг работал на полставки в GCHQ - британской организации, специализировавшейся на взломе шифров. Совместно с Дилли Ноксом он занимался криптоанализом «Энигмы». Вскоре после встречи в Варшаве в июле 1939 года, на которой польское Бюро шифров предоставило Великобритании и Франции подробные сведения о соединениях в роторах «Энигмы» и методе расшифровки сообщений, Тьюринг и Нокс начали свою работу над более основательным способом решения проблемы.
Польский метод основывался на недоработках индикаторной процедуры, которые немцы исправили к маю 1940 года. Подход Тьюринга был более общим и основан на методе перебора последовательностей исходного текста, для которого он разработал начальную функциональную спецификацию Bombe.
Машина, созданная на основе этой спецификации, искала возможные настройки, использованные для шифрования сообщений (порядок роторов, положение ротора, соединения коммутационной панели), опираясь на известный открытый текст. Для каждой возможной настройки ротора (у которого было 10 ^ 19 состояний или 10 ^ 22 в модификации, использовавшейся на подводных лодках) машина производила ряд логических предположений, основываясь на открытом тексте (его содержании и структуре).
Далее машина определяла противоречие, отбрасывала набор параметров и переходила к следующему. Таким образом, бо́льшая часть возможных наборов отсеивалась и для тщательного анализа оставалось всего несколько вариантов.
Первая машина была запущена в эксплуатацию 18 марта 1940 года. Перебор ключей выполнялся за счёт вращения механических барабанов, сопровождавшегося звуком, похожим на тиканье часов.
Спецификация для «Бомбы» была только первым из пяти важнейших достижений Тьюринга в области военного криптоанализа.
Учёный также определил индикаторную процедуру ВМФ Германии; разработал более эффективный способ использования Bombe, основанный на статистическом анализе и названный «Банбурисмусом»; метод определения параметров колёс машины Лоренца, названный «Тьюринжерией»; ближе к концу войны Тьюринг разработал портативный шифратор речи Delilah.
Статистический подход к оптимизации исследований различных вероятностей в процессе разгадывания шифров, который использовал Тьюринг, был новым словом в науке. Тьюринг написал две работы: «Доклад о применимости вероятностного подхода в криптоанализе» и «Документ о статистике и повторениях», которые представляли для GCCS, а позже и для GCHQ (англ. Government Communications Headquarters) такую ценность, что не были предоставлены национальному архиву вплоть до апреля 2012 года, незадолго до празднования ста лет со дня рождения учёного. Один из сотрудников GCHQ заявил, что этот факт говорит о беспрецедентной важности этих работ.
Тьюринг занимался также разработкой шифров для переписки Черчилля и Рузвельта, проведя период с ноября 1942 года по март 1943 года в США.
В 1945 году Тьюринг был награждён орденом Британской империи королём Георгом VI за свою военную службу, но этот факт оставался в секрете многие годы.
Послевоенные годы
После того как фон Нейман в США предложил план создания компьютера EDVAC, аналогичные работы были развернуты в Великобритании в Национальной физической лаборатории, где Тьюринг проработал с 1945 года. Ученый предложил весьма амбициозный проект АСЕ (Automatic Computing Engine – Автоматическая Вычислительная Машина), который, однако, так и не был реализован.Несмотря на то, что постройка ACE была вполне осуществима, секретность, окружавшая Блэтчли-парк, привела к задержкам в начале работ, что разочаровало Тьюринга.
1947–1948 академический год Тьюринг провел в Кембридже. Пока Алан Тьюринг пребывал в Кембридже, Pilot ACE был построен в его отсутствие.
Franklin ACE 1200
Он выполнил свою первую программу 10 мая 1950 года. Хотя полная версия ACE никогда не была построена, некоторые компьютеры имели с ним много общего, к примеру, DEUCE и Bendix G-15.
В мае 1948 года получил предложение занять пост преподавателя и заместителя директора вычислительной лаборатории Манчестерского университета, занявшего к этому времени лидирующие позиции в разработке вычислительной техники в Великобритании.
В 1948 году Алан совместно со своим бывшим коллегой начал писать шахматную программу для компьютера, который ещё не существовал.
В том же году Тьюринг изобрёл метод LU-разложения, который используется для решения систем линейных уравнений, обращения матриц и вычисления определителя.
Тест Тьюринга
В 1948 году Алан Тьюринг получил звание Reader в математическом департаменте Манчестерского университета. Там в 1949 году он стал директором компьютерной лаборатории, где была сосредоточена работа по программированию Манчестерского Марка I.В то же время Тьюринг продолжал работать над более абстрактными математическими задачами, а в своей работе «Computing Machinery and Intelligence» (журнал «Mind», октябрь 1950) он обратился к проблеме искусственного интеллекта и предложил эксперимент, ставший впоследствии известным как тест Тьюринга.
Его идея заключалась в том, что можно считать, что компьютер «мыслит», если человек, взаимодействующий с ним, не сможет в процессе общения отличить компьютер от другого человека. В этой работе Тьюринг предположил, что вместо того, чтобы пытаться создать программу, симулирующую разум взрослого человека, намного проще было бы начать с разума ребёнка, а затем обучать его. CAPTCHA, основанный на обратном тесте Тьюринга, широко распространён в интернете.
В 1951 году Тьюринг был избран членом Лондонского королевского общества.
В первоначальной формулировке «тест Тьюринга» предполагает ситуацию, в которой два человека, мужчина и женщина, по некоторому каналу, исключающему восприятие голоса, общаются с отделенным от них стеной третьим человеком, который пытается по косвенным вопросам определить пол каждого из своих собеседников; при этом мужчина пытается сбить с толку спрашивающего, а женщина помогает спрашивающему выяснить истину.
Вопрос при этом заключается в том, сможет ли в этой «имитационной игре» вместо мужчины столь же успешно участвовать машина (будет ли при этом спрашивающий ошибаться в своих выводах столь же часто). Впоследствии получила распространение упрощённая форма теста, в которой выясняется, может ли человек, общаясь в аналогичной ситуации с неким собеседником, определить, общается он с другим человеком или же с искусственным устройством.
Данный мысленный эксперимент имел ряд принципиальных следствий. Во-первых, он предложил некоторый операциональный критерий для ответа на вопрос «Может ли машина мыслить?».
Во-вторых, этот критерий оказался лингвистическим: указанный вопрос был явным образом заменен вопрос о том, может ли машина адекватным образом общаться с человеком на естественном языке. Тьюринг прямо писал о замене формулировки и при этом выражал уверенность в том, что «метод вопросов и ответов пригоден для того, чтобы охватить почти любую область человеческой деятельности, какую мы захотим ввести в рассмотрение».
Следствием этого стала та важнейшая роль, которую в дальнейшем развитии искусственного интеллекта, во всяком случае, до 1980-х годов играли исследования по моделированию понимания и производства естественного языка. В 1977 году тогдашний директор лаборатории искусственного интеллекта Массачусетского технологического института П.Уинстон писал, что научить компьютер понимать естественный язык – это все равно, что добиться построения интеллекта вообще.
С развитием компьютерных технологий возрос интерес к личности Алана Тьюринга. Кем был этот человек? Какой оставил след в истории информатики и математики? Почему это имя было долго в забвении?
Кто такой Алан Тьюринг, каковы его заслуги перед наукой? Сегодня найдется немало людей, которые смогли бы уверенно ответить на этот вопрос. А уж тем более в узких профессиональных кругах – без «машины Тьюринга» ни один современный учебник математической логики не обходится. Прекрасно знают учёного и специалисты из области информатики. Правда, у некоторых эти знания немного однобокие. «Тьюринг – первый хакер» – все, что им известно об этом гениальном человеке.
Несмотря на то, что Алана Тьюринга можно поставить в один ряд с известнейшими математиками, например, Декартом или Лейбницем, признание пришло к нему через много лет после смерти. Впрочем, сам Тьюринг сделал все возможное при жизни, чтобы его открытия не получили достойного признания современников. Равнодушие ученого к собственным достижениям сыграло против него же.
Личность Алана Тьюринга очень противоречивая. Да и его жизненный путь не назовешь гладким. Чтобы понять этого человека, надо обратиться к беспристрастным фактам его биографии.
Детство
Как вы думаете, что требуется для появления гения на свет? С точки зрения биологии, должны уникальным образом смешаться гены его родителей. Да и не только родителей, а всех предков до n-ного колена. Природа готовится к появлению гения задолго до даты его рождения.
И вот в 1912 году 23 июня родился маленький Алан. Случилось это в чопорной Англии в одной из лондонских лечебниц. У своих родителей Алан Мэтисон был вторым ребенком. Кстати, отец и мать ученого встретились не в Лондоне, а в далекой Индии (еще одна чудесная случайность, приведшая к появлению гения). Отец еще долго – до 1926 года – служил в этой стране. Братья Алан и Джон оставались на попечении друзей семьи, а затем в лондонском частном интернате, где получали истинно английское строгое воспитание.
Уже с раннего детства мальчик интересовался такими науками, как математика, физика, химия. Научившись читать в шесть лет, Алан начал изучать не сказки как все дети, а научно-популярную литературу. Даже самостоятельно проводил довольно серьезные химические эксперименты: например, получал йод из водорослей. Родители опасались, что эти увлечения помешают ему попасть в престижную английскую школу. Хотя эти опасения были совершенно напрасными.
В возрасте 13 лет младший Тьюринг поступил в знаменитую школу города Шерборн. Эта школа, к сожалению, имела гуманитарный уклон, что не соответствовало увлечениям Алана Мэтисона. Поэтому все годы учебы он слыл плохим учеником, что, согласитесь, для гениев опять же не редкость. Своим поведением он доводил учителей гуманитарных дисциплин до стресса. А как же, позвольте спросить, будет себя вести ребенок на совершенно неинтересных для него занятиях? После уроков вместо подготовки домашних заданий Тьюринг изучал теорию относительности.
Тем не менее, находились преподаватели даже в этой школе, которые смогли заметить необыкновенную одаренность мальчика. Одна из записей в классном журнале гласит, что такие ученики рождаются один раз в два столетия, и он зря теряет время в Шерборнской школе. Однако над Тьюрингом нависла нешуточная угроза остаться без аттестата.
Так бы и пришлось провести свои последние школьные годы в унынии и разочаровании, если бы не случилась чудесная встреча: Алан подружился с Кристофером Моркомом. Для Тьюринга эта дружба стала настоящим спасением. Одноклассников отпугивал его эксцентричный вид, необычные прически, манера говорить. А с Крисом они оказались родными по духу: вместе бездельничали на занятиях, вместе изучали астрономию с математикой, вместе мечтали о Кембридже. Внезапная смерть Криса стала первым жизненным ударом для Тьюринга. Он еще больше уверовал в бессмертие человеческого Духа. С течением времени эта вера сильно пошатнулась, но человеческий разум интересовал Тьюринга всю жизнь.
Первые шаги в науку
В 1931 году Алан Мэтисон, худший ученик школы, поступил в кембриджский Кингз-колледж. Здесь он смог по-настоящему заняться любимой наукой. Особенно его увлекли математика и квантовая физика. Эти дисциплины отвечали на многие интересовавшие его вопросы. По-прежнему эксцентричное поведение Тьюринга отталкивало от него «правильных» студентов. Тем не менее, Алан с блеском закончил учебное заведение спустя четыре года. А с 1936 года около двух лет он работал в Принстоне под началом А.Черча. В 1938 году, защитив докторскую диссертацию, Тьюринг вернулся в Англию, где продолжал изучение теории чисел и логики. Одновременно он посещал семинары по философии математики Л.Витгенштейна, с которым вступал в спор по различным позициям.
Машина Тьюринга
В 1934 году Тьюринг слушал лекции известного М.Ньюмана. На них он впервые столкнулся с проблемой алгоритмов. Ранее эта проблема была поднята Д.Гильбертом еще в 1900 году. Её так и назвали «десятой проблемой Гильберта». Возможно ли с применением алгоритмов решить математическую задачу? Понятия «алгоритма» тогда просто не было. Тьюринг же предположил существование некой машины, которая смогла бы сама изучать мир вокруг себя. Эта машина не физический, а абстрактный объект. Однако через множество лет идеи были применены в практической деятельности.
Взломщик кодов
Еще до начала Второй мировой войны Тьюринг увлекся криптографией и начал работать в Блетчли-Парке. Уже тогда он участвовал в разгадке немецких шифров. А с началом войны Тьюринг полностью перешел в эту организацию. Блетчли-Парку нужен был гениальный сотрудник, и он его получил.
В 1939 году военное ведомство Британии поручило ученому рассекретить «Энигму» – шифровальное устройство. Немецкие радиограммы не поддавались никаким дешифраторам. Все считали «Энигму» совершенной. Сложность шифра была в том, что в нем содержалось больше букв, чем в исходном тексте. Тьюринг вместе с друзьями-шахматистами изобрел достойный ответ «Энигме» – «Бомбу». Это была настоящая бомба для немцев: устройство моментально расшифровывало радиограммы. В дальнейшем друзья совершенствовали свою «Бомбу» с улучшением «Энигмы».
Также Тьюринг кодировал переписку Рузвельта и Черчилля. За свои достижения он был удостоен Ордена Британской империи.
Тест Тьюринга
После войны Тьюринг занимался различной деятельностью, включая криптологию. Также не бросал своего увлечения спортом: шахматами и бегом. Многие не знают, что в кроссе у Тьюринга были мировые результаты. В одном из соревнований он показал время лучше серебряного призера Олимпиады 1948 года. Кстати, первую компьютерную программу для шахмат также разработал Тьюринг. Недаром говорят, что талантливый человек талантлив во всем!
Но более значительные достижения в послевоенное время ученый показал в области создания искусственного интеллекта. Тьюрингу было поручено разработать программное обеспечение для первой «мыслящей машины». Ученого очень интересовал вопрос о возможности замены человека машиной. В журнале «Мind» был предложен знаменитый тест. Суть этого эксперимента заключается в создании ситуации, в которой происходит оценка способности машины думать. Сможет ли человек выявить, кто его собеседник – искусственное устройство или другой человек. И сегодня эта тема является предметом острых споров в науке.
Несмотря на успехи в научной деятельности, в личной жизни Тьюринга пошла череда неудач. Поездка в Грецию и зарубежные контакты создали проблему со службой безопасности. Началась черная полоса в жизни Тьюринга, вызвавшая тяжелейшую депрессию. Восьмого июня 1954 года величайшего гения своего времени Алана Мэтисона Тьюринга нашли мертвым в собственном доме. Он отравился цианидом калия. Юношеское увлечение химией сыграло роковую роль. Тьюринг сам получил отравляющее вещество и впрыснул его в яблоко. Через много лет яблоко стало символом известной компьютерной корпорация «Apple». Прожил гениальный ученый всего лишь 41 год.
За особые заслуги в области информатики ежегодно присуждается премия, названная именем Тьюринга. А в 2002 году он вошел в сотню величайших людей Великобритании.