Страницы

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


Алан Мэтисон Тьюринг родился в Лондоне в 1912 году в семье чиновника индийской граждан­ской службы Джулиуса Тьюринга и Сары Тьюринг, урожденной Стоней. Шотландская фамилия Тью­ринг имеет нормандское происхождение. Англо­ирландская семья Стоней йоркширского происхож­дения дала обществу нескольких выдающихся фи­зиков и инженеров.

Интерес к науке, и в частности к математике, у Алана Тьюринга проявился рано, еще в начальной школе и в пансионе, в который он поступил в 1926 году. Некоторые характерные черты, прису­щие зрелому Тьюрингу, были заметны уже тогда. Принимаясь за ту или иную задачу, он начинал ее решение с азов — привычка, которая дает свежесть и независимость его работам, но также, несомненно, делает автора трудно! читаемым.

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

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

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

Результаты работы он описал в своей знаменитой статье в 1936—1937 годах. Но “значение статьи, в которой Тьюринг изложил свой результат, — писал Джон Хопкрофт, — простирается за рамки той задачи, по поводу которой статья была написана.

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

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

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

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

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

Период жизни и деятельности Алана Тьюринга с 1939 по 1945 год долгое время был скрыт завесой секретности.

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

Вначале его местопребывание сохранялось в тайне, хотя позднее стало известно, что он работал в Блетчли-парке близ Лондона, где проводилась особо секретная работа по криптоанализу. Работа в Блетчли-парке велась в рамках засек­реченного проекта “Ультра”, целью которого был поиск метода расшифровки секретных не­мецких кодов.

Для шифрования секретнейших приказов верховного главнокомандования вер­махта, аппарата полиции, СД, СС в Германии использовалась электрическая шифровальная машина “Энигма”.

Еще до начала Второй миро­вой войны поляки сумели сделать точную ко­пию “Энигмы” и переправить ее в Англию. Но без ключа и схемы коммутации (немцы меняли их три раза в день), даже имея в качестве при­емника еще одну “Энигму”, трудно было де­шифровать сообщение.

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

Надо сказать, что блестящие идеи умозрительной “машины Тьюринга” воплотились в реальных машинах, созданных в Блетчли-парке. Среди них были “Хит Робинсон”, электромеха­ническая машина, включавшая два фотоэлектрических устройства считыва­ния с перфоленты со скоростью 2000 символов в секунду (подобно беско­нечной ленте и считывающей головке “машины Тьюринга”), арифметиче­ское устройство на реле и печатающий блок, “Питер Робинсон”, “Супер Робинсон” и т. д. Среди разработчиков, кроме Тьюринга, были Уинн-Уильямс, Флауэрс и др. Эти машины работали по принципу перебора раз­личных комбинаций из символов немецкого кода до получения осмысленного сообщения.

В сентябре 1942 года в Блетчли-парк прибыл профессор М- Ньюмен (тот самый, из Кембриджа) и возглавил группу специалистов (Т. Флауэрс, А. Кумбс, С. Броуд-бейт, У. Чандлер, И. Гуд, Д. Мичи) по соз­данию электронной вычислительной машины для той же цели. В результате в декабре 1943 года была создана первая (не только в Англии, но и в мире) электронная вычислительная машина “Колосс”, содержащая 2000 электрон­ных ламп.

В этой машине использовался только один тип лент, как и предлагал А. Тьюринг, — “данные” (в закодированном виде перехваченные за день неприятельские сообщения), скорость считывания с которых достигала 5000 символов в секунду (использовались пять фотосчитывающих устройств). Машина в поисках соответствия сопоставляла зашифрованное сообщение с уже известными кодами “Энигмы”[/i], которые хранились в кольцевых регист­рах, выполненных на тиратронах. К концу войны было изготовлено около 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 различных зна­ков (28).

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

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

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

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

Но с какими машинами лучше всего начать двигаться к этой цели? Даже на этот вопрос ответить затруднительно.

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

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

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

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

Многие коллеги вспоминают его энтузиазм и волнение, с которыми он брался за любую идею, интересовавшую его, — от “говорящего” зайца до трудной научной проблемы. На него смотрели с большим уважением, т. к. он выделялся своим интеллектом и оригинальностью мышления. Его харак­теризовали как врожденного учителя, способного решить и объяснить лю­бую необычную задачу. Кроме того, “не последнее слово сказано о нем как об инженере”, — говорил У. Чандлер.

Кроме выдающихся успехов, которых он добился в области компьютерной науки и машинного интеллекта, в области “чистой” математики Тьюринг получил ряд результатов в теории аппроксимации групп Ли, конечных групп и в вычислении дзета-функции Римана.

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

Для восстановления здоровья Тьюринг обращался в большинстве случаев к домашним средствам. Он придумал игру под названием “Необитаемый ост­ров”. Правила игры заключались в том, что все химические вещества (в том числе и лекарства) должны быть получены из бытовых продуктов. Так он получил цианистый калий и принял его. Утром 8 июня 1954 года его нашли в постели мертвым. Через несколько дней ему исполнилось бы 42 года.

Заслуги Алана Мэтисона Тьюринга в вычислительном мире велики. И, как свидетельство тому, известнейшая Ассоциация по вычислительной технике — ACM (Association for Computing Machnery, создана в 1947 году) учреди­ла премию его имени. Первым лауреатом премии Тьюринга в 1966 году стал Алан Перлис (один из создателей АЛГОЛа) — первый президент АСМ. В дальнейшем этой премии удостаивались такие виднейшие ученые, как Джон Бэкус (создатель Фортрана), Джон Маккарти (создатель ЛИСПа, пер­вый, кто ввел в практику термин “искусственный интеллект”), Кеннет Ай-версон (создатель АЛЛ), Герберт Саймон и Аллен Ньюэлл (создатели эври­стического программирования) и др.

Многие языки программирования носят имена великих математиков: Евклид, Паскаль, Бэббидж и т. д. В 1982 году ученые университета в Торонто создали более мощный, чем Паскаль, язык программирования и назвали его ТЬЮРИНГ.