Презентация к уроку по теме "Автоматическая обработка информации и алгоритмы. Машина Тьюринга"

Алан Тьюринг (1912 – 1954)

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

Будущие родители Алана Тьюринга — Юлиус Мэтисон Тьюринг и Этель Сара Стоуни познакомились и обвенчались в Индии. Тьюринг служил в английском колониальном ведомстве, а Этель Сара была дочерью главного инженера Мадрасских железных дорог. Это была добропорядочная английская аристократическая семья, принадлежавшая к так называемому "высшему среднему классу" и жившая в соответствии со строгими традициями Империи.

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

Спустя год после родов мать Тьюринга вернулась в Индию, оставив Алана на попечение друга семьи, отставного полковника. Позже мальчика отдали в частный интернат.

Маленький Алан обладал очень пытливым умом. Самостоятельно научившись читать в возрасте б лет, он просил у своих воспитателей разрешения читать научно-популярные книги. В 11 лет он ставил вполне грамотные химические опыты, пытаясь извлечь йод из водорослей. Все это доставляло огромное беспокойство его матери, которая боялась, что увлечения сына, идущие вразрез с традиционным воспитанием, помешают ему поступить в Public School (английское закрытое частное учебное заведение для мальчиков, учеба в котором была обязательна для детей аристократов). Но ее опасения оказались напрасны: Алан смог поступить в престижную Шербонскую школу (Sherborne Public School). Впрочем, вскоре ей пришлось опасаться уже того, сможет ли ее талантливый сын окончить эту школу...

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

В 1928 году он получает неожиданный стимул для развития своего интереса к науке: этим стимулом оказывается дружба с новым одноклассником, весьма одаренным учеником по имени Кристофер Морком. В нем Тьюринг нашел долгожданную "родственную душу" и интеллектуального партнера — того, с кем ему, наконец, можно было поделиться своими размышлениями о науке.

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

13 февраля 1930 г. его Криса вдруг не стало. Внезапная смерть лучшего друга потрясла семнадцатилетнего Тьюринга, повергнув его в глубокую и долгую депрессию. 

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

В 1932 году, во время одного из посещений семьи Моркомов, он составляет в их доме документ под названием "Природа Духа" — манифест своей веры в существование человеческого Духа после смерти. Основное положение этой работы состоит в том, что детерминизм традиционной физической картины мира и его очевидное противоречие с идеей свободы воли опровергаются новой наукой — квантовой физикой.

Вопрос об устройстве человеческого разума будет волновать его всю жизнь.

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

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

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

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

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

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

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

Период жизни и деятельности Алана Тьюринга с  1939  по  1945  год долгое время был скрыт завесой секретности. Мать Тьюринга, опубликовавшая в  1959  году воспоминания о сыне, скупо писала, что сразу же после объявле­ния войны Тьюринга приняли на работу в качестве государственного слу­жащего в управление связи Министерства иностранных дел. Вначале его местопребывание сохранялось в тайне, хотя позднее стало известно, что он работал в Блетчли-парке близ Лондона, где проводилась особо секретная работа по криптоанализу. Работа в Блетчли-парке велась в рамках засек­реченного проекта “Ультра”, целью которого был поиск метода расшифровки секретных не­мецких кодов.

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

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

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

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

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

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

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

В дальнейшем, как известно, символы компьютеров, в том числе и современных персональных, стали за­нимать 8-битный код (байт). Их число может достигать 256 различных зна­ков (28).

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

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

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

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

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

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

Всё рухнуло буквально в один день. В 1952 году квартиру Тьюринга обокрали. В ходе расследования выяснилось, что это сделал один из друзей его сексуального партнёра. Учёный никогда, в общем-то, не скрывал своей "нетрадиционной сексуальной ориентации", но и вызываю ще себя не вёл. Однако скандал с кражей получил широкую огласку, и в результате обвинение в "непристойном поведении" было выдвинуто против самого Тьюринга. 31 марта 1953 года состоялся суд. Приговор предполагал выбор: либо тюремное заключение, либо инъекции женского гормона эстрогена (способ химической кастрации). Он выбрал последнее.

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

Раствор цианида Тьюринг впрыснул в яблоко. Надкусив его, он скончался. Через несколько дней ему исполнилось бы 42 года.

24 декабря 2013 года Тьюринг был посмертно помилован королевой Великобритании Елизаветой II.

Современным математикам, программистам и компьютерным инженерам имя Алана Тьюринга хорошо знакомо еще со студенческой скамьи: всем им приходилось изучать "машину Тьюринга" — "основу основ" теории алгоритмов. Без "машины Тьюринга" не обходится ни один серьезный учебник по математической логике и теории вычислимости.

Почти за каждым выдающимся научным открытием стоит удивительная история. За "машиной Тьюринга" стоит история жизни научного гения — гения, который лишь через много лет после своей трагической смерти получил достойное признание.

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