Алан Мэтисон Тьюринг

Алан Мэтисон Тьюринг

Alan Mathison Turing

(23 июня 1912 — 7 июня 1954)

В 1931 году в девятнадцатилетнем возрасте Тьюринг в качестве математического стипендиата поступил в Королевский колледж Кембриджского университета. Четырьмя годами позже защитил диссертацию “Центральная предельная теорема теории вероятности” (которую он самостоятельно! “переоткрыл”, не зная об аналогичной предшествующей работе) и был избран членом Королевского научного общества.

Именно в 1935 году он впервые начал работать в области математической логике и проводить исследования, которые уже через год привели к выдающимся результатам: решению одной из проблем Д. Гильберта и изобретению умозрительной машины (машины Тьюринга), по своему логическому устройству являющейся прообразом цифровых компьютеров, созданных только спустя десять лет.

Предыстория этого была следующей. В Париже в 1900 году на Международном математическом конгрессе знаменитый математик Давид Гильберт представил список нерешенных проблем. В этом списке второй значилась задача доказательства непротиворечивости системы аксиом обычной арифметики, формулировку которой в дальнейшем Гильберт уточнил как “Entscheidungs problem” (проблема разрешимости). Она заключалась в нахождении общего метода, который позволил бы определить, “выполнимо ли данное высказывание на языке формальной логики, т. е. установить его истинность”.

Алан Тьюринг впервые услышал об этой проблеме на лекциях Макса Ньюмена в Кембридже (он работал там преподавателем математики с 1924 года) и в течение 1936 года получил ответ: проблема Гильберта оказалась неразрешимой. Результаты работы он описал в своей знаменитой статье в 1936—1937 годах. Но “значение статьи, в которой Тьюринг изложил свой результат, — писал Джон Хопкрофт, — простирается за рамки той задачи, по поводу которой статья была написана.

Работая над проблемой Гильберта, Тьюрингу пришлось дать четкое определение самого понятия метода. Отталкиваясь от интуитивного представления о методе как о некоем алгоритме, т. е. процедуре, которая может быть выполнена механически (здесь, по-видимому, Тьюринг воспользовался терминологией М. Ньюмена — “чисто механический процесс”, примененной на лекции, излагающей проблему Гильберта), без творческого вмешательства, он показал, как эту идею можно воплотить в виде подробной модели вычислительного процесса.

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

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

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

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

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

В начале 1937 г. Тьюринг в Принстоне написал работу по лямбда-исчислению (развитие идей Клини) и две работы по теории групп (развитие идей Рейнхольда Баера и решение задачи по аппроксимации непрерывных групп конечными группами). Последняя задача была предложена Тьюрингу польским математиком Станиславом Уламом через Джона фон Неймана.

 Работа Тьюринга (On Computable Numbers, with an Application to the Entscheidungsproblem) увидела свет в январе 1937 г. Рецензию для Journal of Symbolic Logic готовил сам Черч. Именно он и дал изобретению еще не известного миру англичанина название «машина Тьюринга», под которым мы знаем его сейчас. Что интересно, многие просто не поняли сути работы. Тьюринг был сильно разочарован, когда узнал, что запросы на копии пришли всего от двух ученых. Он ожидал реакции от тех, кто вплотную занимался этой проблематикой, прежде всего от Вейля. Но ответом была тишина. Ее не оценили другие, но зато оценил Джон фон Нейман (а также архитекторы первых компьютеров — Конрад Цузе, Джон Атанасов, Джон Эккерт и Джон Мочли). Правда, больше оценили про себя, а не вслух. Как вспоминал С. Улам (ближайший сподвижник Джона фон Неймана по Манхэттенскому проекту создания американской атомной бомбы), в начале 1939 г. фон Нейман неоднократно упоминал в личных беседах имя Тьюринга, причем не скупился на превосходные эпитеты в адрес его работы.

Период жизни и деятельности Алана Тьюринга с 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 года Тьюринг перешел на работу в Манчестерский университет, номинально заняв должность заместителя директора лаборатории вы числительных машин, хотя в действительности он числился в математическом отделе М. Ньюмена и являлся ответственным за программирование.

В Манчестерском университете с конца 1940 года под руководством ф. Уильямса и Т. Килбурна разрабатывалась вычислительная машина “Марк-1″. 21 июля 1948 года на машине была запущена 52-минутная программа, и в настоящее время считается, что “Марк-1″ был первым действующим компьютером с хранимой программой.

При работе над усовершенствованием манчестерской машины М. Ньюмен первым пришел к изобретению индексного регистра, а А. Тьюринг написал первое руководство по программированию. Кроме того, Тьюрингом было придумано еще одно новшество. В машине “Марк-1″ использовался 5-битный код для представления команды, причем каждая команда содержала 4 таких кода, т. е. 20 бит.

С целью облегчения программирования Тьюринг предложил поставить в соответствие каждому 5-битному коду определенный символ из набора 32 знаков (25) — по числу возможных комбинаций. Символы, которые, по Тьюрингу, соответствовали пятизначному двоичному коду, содержали цифры, буквы и знаки препинания, имеющиеся на стандартной клавиатуре телепринтера. Например, символ “/” (косая черта) был обозначен как 00000, буква “R” — 01010 и т. д. В дальнейшем, как известно, символы компьютеров, в том числе и современных персональных, стали занимать 8-битный код (байт). Их число может достигать 256 различных знаков.

В конце 40-х годов Тьюринг занялся проблемой “мыслящих” машин, машинного интеллекта, которая к настоящему времени сформировалась в целое направление под названием “Искусственный интеллект”. Многие ученые (в частности, Дж. Сирл) считают Алана Тьюринга основоположником искусственного интеллекта.

Первая его статья “Intelligent Machinery” в форме отчета Национальной физической лаборатории вышла в 1948 году, а затем в 1950 году в английском журнале “Mind” была опубликована его основополагающая статья “Computing Machinery and Intelligence”. В русском переводе она вышла под названием “Может ли машина мыслить?”. И сегодня анализ этой проблемы Тьюрингом “остался, пожалуй, самым лучшим из всего, что стоит прочитать каждому желающему понять суть дела”.

Я собираюсь рассмотреть вопрос “Могут ли машины мыслить?” — этими словами Тьюринг начинает статью, но вскоре он заменяет исходную постановку вопроса совершенно иной, в которой “мышление” машины рассматривается в технических терминах. В качестве критерия оценки мыслительной деятельности машины Тьюринг предлагает использовать ее действия в процессе “игры в имитацию” (Imitation game). Эта “игра” в дальнейшем получила название теста Тьюринга.

Современном понимании тест Тьюринга интерпретируют следующим образом: если машина способна имитировать поведение, которое эксперт-экзаменатор не сможет отличить от поведения человека, обладающего мыслительными способностями (у Тьюринга испытуемые — человек и машина отделены от эксперта-экзаменатора, задающего вопросы, стенами комнат и общаются посредством телеграфа), то машина также обладает этими способностями.

С 50-х годов было опубликовано много работ по вопросу о том, как программно реализовать тест Тьюринга и что “можно надеяться получить из современного уровня эвристического программирования”. О своих надеждах и прогнозах А. Тьюринг писал в конце статьи: “Мы можем надеяться, что вычислительные машины в конечном счете смогут конкурировать с людьми во всех чисто интеллектуальных сферах деятельности.

Но с какими машинами лучше всего начать двигаться к этой цели? Даже на этот вопрос ответить затруднительно. Многие люди думают, что лучше всего машина может выявить свои возможности в чрезвычайно абстрактной области, подобной игре в шахматы. Можно также утверждать, что лучше всего было бы снабдить машину наилучшими “органами чувств” (датчиками) из числа тех, что можно купить, а затем учить эту машину понимать и говорить по-английски. Этот процесс может быть сходен с обычным обучением ребенка. То есть машине надо указать на тот или иной предмет, назвать его и т. п. Повторяю, что я не знаю, как правильно ответить на этот вопрос, но я думаю, что следует попытаться использовать два этих подхода.

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

Алан Тьюринг и теория чисел

Ю. В. Матиясевич

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

Все опубликованные им работы по теории чисел связаны с одним, но фундаментальным вопросом этой области математики – распределением простых чисел.

Число Скьюза.

В 1931 году Алан Тьюринг поступил в Кембриджский университет в Англии. Стенли Скьюз к тому времени уже окончил этот университет, но ещё там работал.  Алан и Стенли, занимаясь греблей, плавали в одной лодке, и весьма вероятно, что именно там, на реке Кем, Тьюринг узнал о числе Скьюза из первых уст. Тьюринга привлекла идея получить меньшее значение, но как это сделать?

Когда Алан Тьюринг учился в Кембридже, там одним из преподавателей математики (mathematics supervisors) был Альберт Эдвард Ингам (Albert Edward Ingham). В 1932 году вышло в свет первое издание его ставшей затем классической книги «Распределение простых чисел» (книга была переиздана в 1964 и 1990 годах, её переводы на русский язык вышли в 1936 и в 2005 годах). В этой книге Ингам дал новое, более простое доказательство теоремы Литлвуда, состоящее также из рассмотрения двух случаев – справедливости и ложности гипотезы Римана.   Тьюринг много общался с Ингамом и во время обучения, и позднее по переписке. Когда Тьюринг сообщил Ингаму, что хочет уменьшить число Скьюза.

Теория чисел была серьёзным увлечением Алана Тьюринга начиная от студенческих лет и до последних дней жизни, но, похоже, это увлечение никогда не было главным. В 1936 году Тьюринг опубликовал основополагающую работу «On computable numbers, with an application to the Entscheidungsproblem», в которой ввёл свою знаменитую машину. В наши дни машину Тьюринга традиционно описывают как конечное устройство, работающее конечное время с конечным объёмом информации, но интересно отметить, что Тьюринг рассматривал (и это нашло своё отражение в названии) введённые им вычислительные устройства как средство задания вещественных чисел – такие машины должны работать неограниченно долго, выписывая на ленте всё большее и большее количество десятичных знаков задаваемого вещественного числа. Не исключено, что Тьюринга привёл к этому его интерес к теоретико-числовым проблемам.

В 1938 году Тьюринг написал свою диссертацию по математической логике под руководством Алонзо Чёрча (Alonzo Church) в Принстоне, США. Однако возвратившись в том же году в Европу, Тьюринг снова стал заниматься дзета-функцией Римана.

В 1939 году Тьюринг подал заявку на грант Королевского общества (the Royal Society), играющего в Великобритании ту же роль, что академии наук в других странах. В этой заявке Тьюринг просил средства для изготовления аппарата для вычисления значений дзета-функции.

В качестве прототипа были взяты машины для расчётов высоты приливов.

Такие машины использовались начиная с середины 19-го века и вплоть до появления ЭВМ.

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

    Тьюринг получил  грант (запрошенные 40 фунтов стерлингов) и приступил к работе. Ему помогал студент инженерного факультета Дональд Макфейл (Donald C. MacPhail). Удивительно, что они взялись сделать этот достаточно сложный механизм вдвоём.

В заявке на грант Тьюринг указал, что в некоторых случаях потребуется дополнить счёт на аппарате традиционным вычислением. Этому была посвящена работа Тьюринга «A method for the calculation of the zeta-function», поданная в печать в том же мае 1939 года, что и заявка на грант для механического вычисления дзета-функции, но начавшаяся Вторая мировая война прервала работу над аппаратом Тьюринга для вычисления дзета-функции.

Традиционно в описаниях исследований Алана Тьюринга по теории чисел говорится, что его научное наследие состоит из нескольких писем к другим математикам, неопубликованных рукописей, и только двух печатных работ. Это, однако, не совсем так. Есть ещё одна опубликованная Тьюрингом работа, где он изучает гипотезу Римана. По какой-то причине эта работа практически не цитируется специалистами по теории чисел. Возможно, они не ценят полученный там результат, а, возможно, они просто не знают, что в работе, названной «Systems of logic based onordinals» Тьюринг изучает, в частности, гипотезу Римана.