Год Алана Тьюринга в мире и Украине Суть мероприятия Организаторы Статистика Жизненный путь Трагедия личной жизни Признание Современные экспликации теории Тьюринга Варианты интерпретации теста Критика теста Прогнозы Достижения и вклад в науку Криптография Машина Тьюринга Тест Тьюринга
Более 70 университетов мира Более 50 организаций - партнеров проекта Более 80 запланированных мероприятий Международные научные и творческие конкурсы, конкурсы на получение стипендий Экспозиции, посвященные Алану Тьюрингу и его деятельности Циклы кино- и телепоказов Издание целого ряда книг Ряд мероприятий, которые будут проводиться в течение 2012 года во множестве стран мира. Значительная часть событий будет проведена в местах, имевших особое значение в жизни Алана Тьюринга – Кембридже, Манчестере и Блетчли Парке. (The Turing Centenary, The Alan Turing Year)
(Alan Mathison Turing) 23 июня июня 1954 Великобритания Ввёл математическое понятие абстрактного эквивалента алгоритма, или вычислимой функции, получившее затем название «машины Тьюринга». Одним из первых поставил вопрос о способности вычислительной машины мыслить, то есть вопрос об искусственном интеллекте, и первым предложил критерий оценки мыслительных способностей машины. Внес вклад в криптографию, математику, логику и все дальнейшее развитие компьютерных наук. Его часто называют «отцом компьютерной науки», основоположником теории искусственного интеллекта, первым теоретиком современного программирования и даже первым в мире хакером.
Корни семьи Тьюрингов восходят к XIV веку, к старому шотландскому роду баронетов Turins of Foveran из графства Абердиншир. Дед, Джон Роберт Тьюринг: ученая степень по математике в Кембридже. Отец, Джулиус Мэтисон Тьюринг: степень бакалавра по истории и литературе в Оксфорде; изучение индийской истории и языков. Мать, Этель Сара Стоуни: изучала искусство и музыку в Сорбонне. Род Стоуни: известная в научном мире семья, давшая миру известного физика Джорджа Стоуни, члена английского Королевского общества. «Биография человека никогда не начинается с момента его рождения. Тем более биография истинного гения. Ведь для того чтобы возникла телесная и духовная структура, в которой гений проявился бы во всей своей полноте, необходимо необычайно планомерное взаимодействие, смешение генов и хромосом, неизъяснимых сил и материй к тому же на протяжении нескольких поколений» Иштван Барна
Безобразная успеваемость… Безнадежное отставание… Он принадлежит к числу тех учеников, которые создают проблемы для любой школы и всего общества Отзывы школьных учителей Алана Тьюринга Если он останется в школе, то должен поставить перед собой цель – стать образованным. Если же он должен быть только ученым, то напрасно тратит здесь свое время». Книги, которые потрясли: Чудеса природы, о которых должен знать каждый ребенок (Эдвин Брюстер) Природа физического мира (Артур Эддингтон) Алан Тьюринг Алан Тьюринг в возрасте 16 лет
Поворотным пунктом в жизни Тьюринга стало знакомство с Кристофером Моркомом (Christopher Morcom), с которым его объединил, в числе прочего, интерес к математике, астрономии. Кристофер Морком Они мечтали вместе изменить мир. Вместе готовились и сдавали экзамены в Кембридж. Кристофер был принят, а Алан нет. В феврале 1930 года Крису неожиданно стало плохо. Его увезли в больницу, сделали две операции, но это не помогло через неделю его не стало. Причина туберкулез, которым он заразился в детстве. Алан Тьюринг решил, что теперь он должен жить не только за себя, но и за него и должен был совершить в науке то, что не смог Крис. Работы Криса всегда были лучше моих, писал Тьюринг, «он был невероятно одарен».
Королевский колледж, Кембридж Книги, которые потрясли: Математические основы квантовой механики, (Джон фон Нейман) Вернер Гейзенберг, Эрвин Шредингер (труды по квантовой механике) Введение в математическую философию (Бертран Рассел) Основы арифметики (Готлиб Фреге) Магистерская диссертация: Центральная предельная теорема теории вероятности Научный руководитель (и коллега во всей дальнейшей жизни): математик (тополог) Макс Ньюмен (). Maxwell Herman Alexander "Max" Newman
Тезис Чёрча – Тьюринга: доказательство принципиальной неразрешимости «проблемы разрешимости» (доказательства непротиворечивости системы аксиом обычной арифметики) Давида Гильберта. Опровержение надежд Д. Гильберта и его последователей, полагавших, что математику как самую формализованную часть человеческого знания можно представить в виде набора аксиом и теорем. Именно для решения этой задачи Тьюрингом было разработано понятие абстрактной цифровой вычислительной машины. Четкое определение понятия метода как некоего алгоритма, который может быть выполнен механически, без творческого вмешательства. Модель вычислительного процесса: каждый алгоритм разбивается на последовательность простых, элементарных шагов Неэффективность построения специализированных вычислительных машин и идея универсальной электронной вычислительной машины. Эта логическая конструкция и была впоследствии названа «машиной Тьюринга». (история создания)
(принцип работы) Предельно простая и предельно общая условная схема автоматической вычислительной машины. Выводы: Любой вычислительный или логический процесс, для которого существует алгоритм, может быть автоматизирован с помощью такой примитивной машины. И наоборот: все, что можно сделать с помощью этой машины, подчинено алгоритму. Задачи, которые этой машиной не решаются - алгоритмически неразрешимы для любой, даже самой мощной, машины не только сегодняшнего дня, но и будущего. С алгоритмически неразрешимыми задачами способен справиться только мозг человека.
(физическое воплощение идеи вычислительной машины) Принстонский университет, получение степени PhD. Работа с Алонзо Чёрчем, Джоном фон Нейманом, Альбертом Эйншейном и другими выдающимися физиками и математиками. Первые дискуссии по вычислительным и думающим машинам с Джоном фон Нейманом. Снова Кембридж: работа в Национальной физической лаборатории Кембриджа в группе по проектированию и созданию вычислительной машины АСЕ (Automatic Computing Engine). Манчестер: Работа в математическом отделе Макса Ньюмена над созданием вычислительной машины в должности ответственного за программирование. 21 июля 1948 года: запуск первой программы на созданной вычислительной машине Марк-1: первый действующий компьютер с хранимой программой. Написание первого руководства по программированию и первой шахматной программы.
(расшифровка кодов «Энигмы») Шифровальная машина Энигма Работа в Национальном центре кодирования и криптографии (National Codes Centre) в Блечли-Парке в рамках засекреченного проекта Ультра, целью которого был поиск метода расшифровки секретных немецких кодов, созданных с помощью электрической шифровальной машины Энигма. Создание специальных вычислительных машин для дешифровки немецких сообщений («Хит Робинсон», «Питер Робинсон», «Бомба» и других). Участие в создании Колосса - первой (не только в Англии, но и в мире) полностью электронной вычислительной машины (под руководством М. Ньюмена). «Я не хочу сказать, что мы выиграли войну благодаря Тьюрингу, но беру на себя смелость сказать, что без него мы могли бы ее и проиграть. И. Гуд
(постановка вопроса об искусственном интеллекте) Середина XX века: зарождение интереса к искусственному интеллекту как новому научному направлению. Статьи Intelligent Machinery («Мыслящие машины») (1948) и Computing Machinery and Intelligence, впоследствии переизданная под названием "Can the Machine Think?" (Может ли машина мыслить?) (1950). Постановка вопроса: не «может ли машина думать?», а «Может ли машина делать то, что можем делать мы (как мыслящие создания), то есть то, что мы называем «думанием». «Игра в имитацию» как критерий оценки мыслительной деятельности машины. Следствия: Впервые предложен некоторый операциональный критерий для ответа на вопрос «Может ли машина мыслить?». Лингвистический подход: вопрос о мышлении машины сведен к вопросу о том, может ли машина адекватным образом общаться с человеком на естественном языке. (по Тьюрингу, «метод вопросов и ответов пригоден для того, чтобы охватить почти любую область человеческой деятельности, какую мы захотим ввести в рассмотрение»).
Преследования за гомосексуальность, обвинение в «непристойном поведении». 31 марта 1953 года - суд и приговор: тюремное заключение, либо инъекции женского гормона эстрогена (способ химической кастрации). Он выбрал второе. Увольнение из Департамента кодов. 8 июня 1954 года: тело Алана Тьюринга обнаружила домработница. Вердикт следствия: самоубийство путем отравления цианистым калием. 10 сентября 2009 года: Премьер- министр Великобритании Гордон Браун публично принёс извинения за преследования, которым был подвергнут Алан Тьюринг и тысячи других мужчин- геев, осуждённых по гомофобным законам. Яблоко… библейский символ познания и греха, символ трагической любви и смерти самого Тьюринга; намек на яблоко, вдохновившее Исаака Ньютона на создание теории гравитации; знаменитый логотип компании Apple с надкусанным яблоком…
Новая волна популярности Алана Тьюринга начинается в самом конце 20 века, когда он становится известен не только и не столько благодаря своему вкладу в компьютерные науки и математику, сколько как человек, пострадавший из-за своей нестандартности, своего рода культурный герой, символ и надежда всех гонимых и преследуемых. Огромное количество биографический и исследовательской литературы. Упоминания в исторических и фантастических романах Нила Стивенсона, Роберта Харриса, Гарри Гаррисона, Марвина Мински, Уильяма Гибсона. Как минимум две оперы и несколько песен, в том числе, на китайском языке. Постановка в лондонском театре Вест-энда и на Бродвее пьесы «Breaking the Code» («Взламывая код»), получившей целый ряд наград: фильм «Breaking the Code» («Взламывая код»); 2011: фильм "Игра имитатора" (не завершен). 2002: 21 место в списке 100 величайших британцев в истории по результатам опроса ВВС. 1999: журнал Time назвал Тьюринга в числе 100 наиболее значимых людей 20 века.
В 1974 году Ассоциацией по вычислительной технике ACM (Association for Computing Machnery) учреждена премия имени Алана Тьюринга, признанная в мировом компьютерном сообществе высшей наградой. Также именем Алана Тьюринга названы: Памятники и монументы: в Блетчли Парке, на территории Орегонского университета, на территории университета Суррея, в Сэквилль парке в Манчестере. Компьютерные лаборатории целого ряда университетов. Аллея Алана Тьюринга (Alan Turing Road) на территории университета Суррея (Великобритания); Кольцевая дорога вокруг Манчестера - «Путь Тьюринга» (The Turing Way»), а мост, по которому она проходит, назван «Мостом Алана Тьюринга». (The Alan Turing Bridge). Учебные корпуса в университетах Манчестера, Оксфорд Брукс, University of Manchester, the Open University, Oxford Brookes University and Aarhus University (Дани), Международной школы информационных наук (Франция) и др. Ежегодные конференции и конкурсы в целом ряде городов мира. Язык программирования, созданный в 1982 году учеными университета в Торонто. Памятник Алану Тьюрингу на территории университета Суррея (Великобритания)
Сегодня, более, чем через 50 лет после публикации Тьюрингом первых результатов своей работы в области искусственного интеллекта, поставленные им вопросы не утрачивают актуальности и, более того, порождают новые интерпретации. Среди них: Минимальный интеллектуальный Signal-тест (MIST). Предложен Крисом Мак-Кинстри. Разрешены лишь два типа ответов «да» и «нет». Используется для сбора статистической информации для измерения производительности программ, реализующих искусственный интеллект. Тест бессмертия. Определяет, качественно ли передан характер человека, а именно возможно ли отличить скопированный характер от характера человека, послужившего его источником. Мета-тест Тьюринга. Субъект (в частности, компьютер) считают разумным, если он создал нечто, что он сам хочет проверить на разумность. Обратный тест Тьюринга. Модификация теста Тьюринга, в которой цель или одну или более ролей машины и человека поменяли местами. Задача компьютера - определить с кем он беседовал: с человеком или же с другим компьютером. CAPTCHA (от англ. Completely Automated Public Turing test to tell Computers and Humans Apart). Разновидность обратного теста. Цель предотвратить атаки автоматических систем на сайт.
Чрезмерный антропоморфизм: проверяется только способность машины походить на человека, а не разумность машины вообще. Тест не учитывает следующие возможности: Иногда поведение человека не поддается разумному толкованию. Некоторое разумное поведение не присуще человеку. Тест Тьюринга подвергается критике по нескольким критериям: Непрактичность: антропоморфизм теста приводит к тому, что он не может быть по-настоящему полезным при разработке разумных машин. Например, в авиационном проектировании мы вовсе не стремимся к созданию разумной машины, допускающей свойственные человеку ошибки. Возможность имитации интеллекта: тест Тьюринга явно бихевиористичен или функционалистичен: он лишь проверяет, как действует субъект. Машина, проходящая тест, может имитировать поведение человека в разговоре, просто «неинтеллектуально» следуя механическим правилам (известный пример: мысленный эксперимент американского философа Джона Роджерса Сёрля «Китайская комната»).
В статье «Is the Brains Mind a Computer Program?» («Является ли мозговое мышление компьютерной программой?»), опубликованной в 1990 году, Сёрль описывает доказывает, что при проведении теста Тьюринга не существует никакой возможности отличить действительно мыслительную деятельность программы от механического исполнения правильно подготовленным инструкциям. («Китайская комната» Дж. Р. Сёрля)
Тьюринг прогнозировал, что машины, в конце концов, будут способны пройти разработанный им тест. Он даже называл конкретные даты: к 2000 году, машины с объемом памяти около 125 МБ) будут способны обманывать 30% судей. На сегодняшний день еще ни одна программа пройти тест не смогла. Премия Лёбнера (англ. Loebner prize) премия размером в 100 тысяч долларов, учрежденная в 1990 году американским ученым и филантропом Хью Лебнером и присуждаемая победителю ежегодного конкурса, в котором компьютерные программы соревнуются в прохождении теста Тьюринга. Элиза (ELIZA) (названа в честь Элизы Дулитл из пьесы «Пигмалион» Бернарда Шоу) - одна из первых программ, принявших участие в конкурсе Лёбнера; создана немецко-американским ученым Джозефом Вейценбаумом в 1966 году. A.L.I.C.E. (аббревиатура от англ. Artificial Linguistic Internet Computer Entity, что дословно можно перевести как «Искусственное лингвистическое интернет-компьютерное существо») – лидер в своем роде программ, которая три раза (в 2000, 2001, 2004 годах) становилась победителем премии Лёбнера. Программа-собеседник A.L.I.C.E.
Итак, очевидно, следует признать, что на сегодняшний день прогнозы Алана Тьюринга в отношении искусственного интеллекта не сбылись, а потому вопрос «может ли машина мыслить?» по-прежнему остается открытым. Как и вопросы: должна ли машина мыслить? должна ли машина мыслить именно так, как это делает человек? так ли уж важен вопрос о достижении виртуальным разумом неотличимости от человеческого? И многие другие…
100 лет со дня рождения Алана Тьюринга Юлия Киселева Магистрант специальности «религиоведение», Донецкий национальный технический университет Материалы презентации доступны на сайте Ассоциации философов и религиоведов:
Определение машины Тьюринга
Машина Тьюринга – абстрактный исполнитель, осуществляющий алгоритмический процесс, созданный для уточнения понятия алгоритма. Это математический объект, а не физическая машина. Предложена Аланом Тьюрингом в 1936 году Машина Тьюринга – это строгое математическое построение, математический аппарат, созданный для решения определённых задач.
Структура и описание машины Тьюринга Машина Тьюринга состоит из: бесконечной ленты, разделенной на ячейки; каретки (читающей и записывающей головки); программируемого автомата (программа в виде таблицы). Автомат каждый раз “видит” только одну ячейку. В зависимости от того, какую букву он видит, а также в зависимости от своего состояния q автомат может выполнять следующие действия: записать новую букву в обозреваемую ячейку; выполнить сдвиг по ленте на одну ячейку вправо/влево или остаться неподвижным; перейти в новое состояние.
1) Внешний алфавит А = { a 0 , a 1 , …, a n } Элемент a 0 называется пустой символ или пустая буква (признак того, что ячейка пуста). В этом алфавите в виде слова кодируется исходный набор данных и результат работы алгоритма. Устройство машины Тьюринга
2) Внутренний алфавит Q = { q 0 , q 1 , …, q m }, { П, Л, Н! } В любой момент времени машина Тьюринга находится в одном из состояний q 0 , q 1 , …, q m При этом: q 1 - начальное состояние (машина начинает работу) q 0 - заключительное состояние (машина закончила работу) Символы { П, Л, Н! } – символы сдвига (вправо, влево, на месте) Устройство машины Тьюринга
Виды команд машины Тьюринга Написать новую букву в обозреваемую ячейку Выполнить сдвиг по ленте на одну ячейку вправо/влево или остаться на месте (П, Л, Н) Перейти в новое состояние. а 0 а 1 … а i … а j q 0 q 1 … a k { ЛПН } q m q i … q j 1 1 1 * 1 1 Указание о смене символа Указание о сдвиге каретки Указание о смене внутреннего состояния
3) Внешняя память (лента) Машина имеет ленту, разбитую на ячейки, в каждую из которых может быть записана только одна буква Устройство машины Тьюринга
3) Внешняя память (лента) Устройство машины Тьюринга Пустая клетка содержит a 0 . В каждый момент времени на ленте записано конечное число непустых букв Лента является конечной, но дополняется в любой момент ячейками слева и справа для записи новых непустых символов. Это соответствует принципу абстракции потенциальной осуществимости
4) Каретка (управляющая головка) Каретка машины располагается над некоторой ячейкой ленты – воспринимает символ, записанный в ячейке В одном такте работы каретка сдвигается на одну ячейку (вправо, влево) или остается на месте Устройство машины Тьюринга
5) Функциональная схема (программа) Программа машины состоит из команд: Устройство машины Тьюринга Для каждой пары (q i , a j) программа машины должна содержать одну команду (детерминированная машина Тьюринга)
К началу работы машины на ленту подается исходный набор данных в виде слова Описание работы машины Тьюринга Будем говорить, что непустое слово в алфавите А\ {a 0 } воспринимается машиной в стандартном положении, если: - оно задано в последовательных ячейках ленты, - все другие ячейки пусты, - машина обозревает крайнюю правую ячейку из тех, в которых записано слово
Описание работы машины Тьюринга Стандартное положение называется начальным (заключительным), если машина, воспринимающая слово в стандартном положении, находится в начальном состоянии q 1 (стоп-состоянии q 0)
Находясь в не заключительном состоянии, машина совершает шаг, который определяется текущим состоянием q i и обозреваемым символом a j Описание работы машины Тьюринга
Описание работы машины Тьюринга В соответствии с командой q i a j q k a l Х выполняются следующие действия: 1) Содержимое обозреваемой ячейки a j стирается и в нее записывается символ a l (который может совпадать с a j) 2) Машина переходит в новое состояние q k (оно может совпадать с состоянием q i) 3) Каретка перемещается в соответствии с управляемым символом Х { П, Л, Н! }
При переходе машины в заключительное состояние q 0 ее работа прекращается На ленте записан результат работы алгоритма – слово в алфавите А\ {a 0 } Описание работы машины Тьюринга
Машинным словом (конфигурацией) машины Тьюринга называется слово вида 1 q k a l 2 , где 1 и 2 - слова в алфавите А.
Конфигурация 1 q k a l 2 интерпретируется следующим образом: - машина находится в состоянии q k - каретка обозревает на ленте символ a l - 1 и 2 – это содержимое ленты до и после символа a l
Ситуации неприменимости машины Тьюринга Считается, что машина Тьюринга неприменима к данному входному слову, если в программе нет клеток останова или машина в процессе работы на них не попадает. Например: Машина Тьюринга применима к данному входному слову, если, начав работу над этим входным словом, она рано или поздно дойдёт до одной из клеток останова. Как изменилась программа в примере? а 0 0 1 q 1 1П q 1 0П q 1 1П q 1 а 0 0 1 q 1 1Н q 0 0П q 1 1П q 1
Пример машин Тьюринга Требуется построить машину Тьюринга для решения следующей задачи: во входном слове все буквы «а» заменить на буквы «б» и наоборот. а 0 а б в … я q 1 а 0 Н! б Л q 1 а Л q 1 в Л q 1 … я Л q 1 у у б а а б р р у б а р а б а б б а а б б а
Реализуйте предложенный алгоритм Машина Тьюринга прибавляет единицу к числу на ленте. Входное слово состоит из цифр целого десятичного числа, записанного в последовательные ячейки на ленте. В начальный момент машина находится против самой правой цифры числа. а 0 0 1 2 3 4 … 7 8 9 q 1 1Н q 0 1Н q 0 2Н q 0 3Н q 0 4Н q 0 5Н q 0 … 8Н q 0 9Н q 0 0Л q 1
Реализуйте предложенный алгоритм На ленте машины Тьюринга содержится последовательность символов «+». Машина Тьюринга каждый второй символ «+» заменяет на «–». Замена начинается с правого конца последовательности. Автомат в состоянии q 1 обозревает один из символов указанной последовательности. а 0 + – q 1 а 0 Л q 2 + П q 1 q 2 а 0 Н! + Л q 3 q 3 а 0 Н! – Л q 2 q 1 – машина ищет правый конец числа; q 2 – пропускает знак «+», при достижении конца последовательности – останов; q 3 – знак «+» заменяет на « – ».
Пример Дана машина Тьюринга с внешним алфавитом А = { a 0 , 1, * } , алфавитом внутренних состояний Q = { q 0 , q 1 , q 2 , q 3 }, и следующей функциональной схемой: Применить машину Тьюринга к слову =11*1, начиная со стандартного начального положения
Решение 1) Заменяем содержимое обозреваемой ячейки 1 на а 0
Решение 2) Машина переходит в новое состояние q 2
Решение 3) Каретка перемещается влево
Решение Полное подробное решение
Решение Полное подробное решение
Решение Решение, записанное с помощью конфигураций (в строчку)
= 1*11 Ответ: = 111
Литература Игошин В.И. Математическая логика и теория алгоритмов. – М.: Академия, 2008. - 448 с. Лихтарников Л.М., Сукачева Т.Г. Математическая логика. Курс лекций. Задачник-практикум и решения. – СПб.: Лань, 1999. - 288 с. Ильиных А.П. Теория алгоритмов. Учебное пособие. – Екатеринбург, 2006. - 149 с.
Люди могут вести себя по-разному в одинаковых ситуациях, и этим они принципиально отличаются от машин.
Алан Тьюринг (1912 – 1954)
Будущие родители Алана Тьюринга - Юлиус Мэтисон Тьюринг и Этель Сара Стоуни познакомились и обвенчались в Индии. Тьюринг служил в английском колониальном ведомстве, а Этель Сара была дочерью главного инженера Мадрасских железных дорог. Это была добропорядочная английская аристократическая семья, принадлежавшая к так называемому "высшему среднему классу" и жившая в соответствии со строгими традициями Империи.
Алан Мэтисон Тьюринг родился в Лондоне в 1912 году. Шотландская фамилия Тьюринг имеет нормандское происхождение. Англоирландская семья Стоуни йоркширского происхождения дала обществу нескольких выдающихся физиков и инженеров.
Спустя год после родов мать Тьюринга вернулась в Индию, оставив Алана на попечение друга семьи, отставного полковника. Позже мальчика отдали в частный интернат.
Маленький Алан обладал очень пытливым умом. Самостоятельно научившись читать в возрасте б лет, он просил у своих воспитателей разрешения читать научно-популярные книги. В 11 лет он ставил вполне грамотные химические опыты, пытаясь извлечь йод из водорослей. Все это доставляло огромное беспокойство его матери, которая боялась, что увлечения сына, идущие вразрез с традиционным воспитанием, помешают ему поступить в Public School (английское закрытое частное учебное заведение для мальчиков, учеба в котором была обязательна для детей аристократов). Но ее опасения оказались напрасны: Алан смог поступить в престижную Шербонскую школу (Sherborne Public School). Впрочем, вскоре ей пришлось опасаться уже того, сможет ли ее талантливый сын окончить эту школу...
Интерес к науке, и в частности к математике, у Алана Тьюринга проявился рано, еще в начальной школе и в пансионе, в который он поступил в 1926 году. Некоторые характерные черты, присущие зрелому Тьюрингу, были заметны уже тогда. Принимаясь за ту или иную задачу, он начинал ее решение с азов - привычка, которая дает свежесть и независимость его работам, но также, несомненно, делает автора трудно! читаемым.
Юношеская жажда знаний быстро сблизила Тьюринга и Моркома, они стали неразлучными друзьями. Теперь они на уроках французского языка уже вместе зевали или играли в крестики-нолики, одновременно обсуждая астрономию и математику. После окончания школы они оба собирались поступать в Кембриджский университет, и Алан, избавившийся от многолетнего одиночества, возможно, был почти счастлив...
13 февраля 1930 г. его Криса вдруг не стало. Внезапная смерть лучшего друга потрясла семнадцатилетнего Тьюринга, повергнув его в глубокую и долгую депрессию.
В 1931 году в девятнадцатилетнем возрасте Тьюринг в качестве математического стипендиата поступил в Королевский колледж Кембриджского университета. Четырьмя годами позже защитил диссертацию “Центральная предельная теорема теории вероятности” (которую он самостоятельно! “переоткрыл”, не зная об аналогичной предшествующей работе) и был избран членом Королевского научного общества.
В 1932 году, во время одного из посещений семьи Моркомов, он составляет в их доме документ под названием "Природа Духа" - манифест своей веры в существование человеческого Духа после смерти. Основное положение этой работы состоит в том, что детерминизм традиционной физической картины мира и его очевидное противоречие с идеей свободы воли опровергаются новой наукой - квантовой физикой.
Вопрос об устройстве человеческого разума будет волновать его всю жизнь.
В сентябре 1936 года Тьюринг покидает Кембридж и перебирается в Америку в Принстонский университет, где работает куратором. Там в 1938 году он получает степень доктора философии. В то время в Принстонском университете работали такие знаменитости, как Черч, Курант, Эйнштейн, Харди, фон Нейман.
Именно в 1935 году он впервые начал работать в области математической логики и проводить исследования, которые уже через год привели к выдающимся результатам: решению одной из проблем Д. Гильберта и изобретению умозрительной машины (машины Тьюринга), по своему логическому устройству являющейся прообразом цифровых компьютеров, созданных только спустя десять лет.
Предыстория этого была следующей. В Париже в 1900 году на Международном математическом конгрессе знаменитый математик Давид Гильберт представил список нерешенных проблем. В этом списке второй значилась задача доказательства непротиворечивости системы аксиом обычной арифметики, формулировку которой в дальнейшем Гильберт уточнил как “Entscheidungs problem” (проблема разрешимости). Она заключалась в нахождении общего метода, который позволил бы определить, “выполнимо ли данное высказывание на языке формальной логики, т. е. установить его истинность”.
Алан Тьюринг впервые услышал об этой проблеме на лекциях Макса Ньюмена в Кембридже (он работал там преподавателем математики с 1924 года) и в течение 1936 года получил ответ: проблема Гильберта оказалась неразрешимой. Результаты работы он описал в своей знаменитой статье в 1936 - 1937 годах. Но “значение статьи, в которой Тьюринг изложил свой результат, - писал Джон Хопкрофт, - простирается за рамки той задачи, по поводу которой статья была написана.
Работая над проблемой Гильберта, Тьюрингу пришлось дать четкое определение самого понятия метода. Отталкиваясь от интуитивного представления о методе как о некоем алгоритме, т. е. процедуре, которая может быть выполнена механически (здесь, по-видимому, Тьюринг воспользовался терминологией М. Ньюмена - “чисто механический процесс”, примененной на лекции, излагающей проблему Гильберта), без творческого вмешательства, он показал, как эту идею можно воплотить в виде подробной модели вычислительного процесса.
Полученная модель вычислений, в которой каждый алгоритм разбивался на последовательность простых, элементарных шагов, и была логической конструкцией, названной впоследствии машиной Тьюринга”.
Значение работы Тьюринга для теории вычислений велико : “Машина Тьюринга за данный большой, но конечный промежуток времени способна справиться с любым вычислением, которое может выполнить всякий сколь угодно мощный современный, компьютер”.
Период жизни и деятельности Алана Тьюринга с 1939 по 1945 год долгое время был скрыт завесой секретности. Мать Тьюринга, опубликовавшая в 1959 году воспоминания о сыне, скупо писала, что сразу же после объявления войны Тьюринга приняли на работу в качестве государственного служащего в управление связи Министерства иностранных дел. Вначале его местопребывание сохранялось в тайне, хотя позднее стало известно, что он работал в Блетчли-парке близ Лондона, где проводилась особо секретная работа по криптоанализу. Работа в Блетчли-парке велась в рамках засекреченного проекта “Ультра”, целью которого был поиск метода расшифровки секретных немецких кодов.
В 1939 году британское военное ведомство поставило перед Тьюрингом задачу разгадать секрет "Энигмы" – специального устройства, использовавшегося для шифровки радиограмм в германском военно-морском флоте и в "люфтваффе". Британская разведка раздобыла это устройство, но расшифровывать перехваченные радиограммы немцев не удавалось.
Для шифрования секретнейших приказов верховного главнокомандования вермахта, аппарата полиции, СД, СС в Германии использовалась электрическая шифровальная машина “Энигма”. Еще до начала Второй мировой войны поляки сумели сделать точную копию “Энигмы” и переправить ее в Англию. Но без ключа и схемы коммутации (немцы меняли их три раза в день), даже имея в качестве приемника еще одну “Энигму”, трудно было дешифровать сообщение. Для разгадки секретного шифра в Блетчли-парке собралось любопытное общество выдающихся математиков, шахматистов, любителей кроссвордов, знатоков различных областей знаний и даже двух музыкантов. Среди этих людей, оторванных от внешнего мира, был и Алан Тьюринг, возглавлявший одну из групп, в которой работали двенадцать математиков и четыре лингвиста.
27-летнего Тьюринга и его коллег охватил настоящий спортивный азарт. Немцы считали "Энигму" неприступной. Сложность дешифровки усугублялась тем, что в закодированном слове получалось больше букв, чем в оригинале. Тем не менее, Тьюринг уже через полгода разработал устройство, названное им "Бомбой", которое позволяло читать практически все сообщения "люфтваффе". А спустя ещё год был "взломан" и более сложный вариант "Энигмы", использовавшийся нацистскими подводниками. Это во многом предопределило успех британского флота.
В Манчестерском университете с конца 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 года.
Современным математикам, программистам и компьютерным инженерам имя Алана Тьюринга хорошо знакомо еще со студенческой скамьи: всем им приходилось изучать "машину Тьюринга" - "основу основ" теории алгоритмов. Без "машины Тьюринга" не обходится ни один серьезный учебник по математической логике и теории вычислимости.
Почти за каждым выдающимся научным открытием стоит удивительная история. За "машиной Тьюринга" стоит история жизни научного гения - гения, который лишь через много лет после своей трагической смерти получил достойное признание.
Роль А.Тьюринга в истории информатики отнюдь не исчерпывается одним лишь изобретением "машины Тьюринга", как это может иногда показаться из-за относительной скудости опубликованных (на русском языке) сведений о нем.
Методическая разработка урока , о котором пойдет речь в данной публикации , предназначена для изучения в 10 классе при рассмотрении тематического блока «Алгоритм. Исполнители алгоритма ».
На уроке по теме «» в сопровождении мультимедийной презентации ребята познакомятся с ее устройством, изучат принцип работы и научаться строить программу для машины Тьюринга. Материал урока позволяет развивать алгоритмическое мышление учащихся старших классов, способности к формализации.
По типу данное занятие является комбинированным, на котором изучение нового материала закрепляется в процессе решения задач по теме. Автор разработки предлагает использовать частично-поисковый метод обучения, когда процесс мышления становится продуктивным при последовательном направлении и контроле учителя.
Описание хода занятия о машине Тьюринга
На этапе организации класса учитель настраивает ребят на рабочую , формулирует тему занятия и рассказывает об английском Алане Тьюринге, существенно повлиявшем на развитие информатики, как науки.
В качестве разминки на следующем этапе урока школьники решают логическую задачу с последующей проверкой у доски. Важно обратить внимание на умение составлять алгоритм рассуждений.
Разобравшись с задачей на разминке, актуализируем пройденный ранее теоретический материал об алгоритме и исполнителях алгоритмов. Для этого автор разработки предлагает провести фронтальный опрос по следующим вопросам:
Что называют алгоритмом и кому он предназначается?
Какими свойствами обладает алгоритм?
Кто способен предстать в качестве исполнителя алгоритма?
Назовите основные понятия машины Тьюринга.
Продемонстрируйте главные свойства алгоритмов, ориентируясь на пример машины Тьюринга.
Примеры машин Тьюринга – теоретическая часть
Прежде чем приступить к решению задач по теме, в теоретической части приводим описание машины Тьюринга. Обращаем внимание класса на две составные части любой из таких машин:
1) лента неограниченная и разделенная на ячейки;
2) управляемая программой головка, которая считывает информацию и именуемая автоматом.
Заменить содержащуюся в обозримой ячейке памяти одну букву алфавита на другую;
Осуществить сдвиг вправо либо влево с интервалом в одну ячейку либо оставаться на том же месте;
Сменить собственное внутреннее состояние.
Решение задач с помощью машин Тьюринга
Следующий этап занятия предполагает погружение в практическую часть урока и решение задач по теме. Учитель сообщает, что при помощи машины Тьюринга необходимо попытаться сымитировать устройство, подобное калькулятору. Всего предлагаются две задачи, разбор которых происходит в сопровождении слайдов презентации:
Задача 1.
Лента машины Тьюринга содержит некоторое десятичное число. Необходимо прибавить к этому числу 1 (единицу
). Автомат в данном случае обозревает некую цифру, соответствующую входному числу.
КТО? Машина Тьюринга – математическая (воображаемая) машина, а не машина физическая. Она такой же математический объект, как функция, производная, интеграл и т.д. ЧТО? А́лан Ма́тисон Тью́ринг английский математик, логик, криптограф. В 1937 году предложил уточнение понятия алгоритма как процесса, который может совершаться специальной машиной, названной в дальнейшем машиной Тьюринга. Понятие «машина Тьюринга» было сформулировано за 9 лет до появления первой ЭВМ.
Устройство машины Тьюринга Лента Читающая головка Внутреннее состояние Считываемый символ Лента: Потенциально бесконечная; В одной ячейке – один символ; Пустая ячейка заполнена символом a 0. Головка: В каждый момент времени находится только в одном внутреннем состоянии; Начальное состояние – q 1 ; Конечное состояние – q 0.
Пример машины Тьюринга QA QA q1q1 q2q2 q3q3 0q 1 0Lq 3 1Rq 1 0L 1q 2 0Lq 2 1Lq 3 1R q00q00q 2 Lq 3 R Рассмотрим работы машины Тьюринга, имеющую следующую программу: q q q q q q q q q q q q q q q q q q q q … … … T f(a,b) = a + b
Зачем? Тезис Тьюринга: Для нахождения значений функции тогда и только тогда существует какой-нибудь алгоритм когда существует машина Тьюринга, вычисляющая данную функцию. Данный тезис не может быть строго доказан методами математики, однако до сих пор не удалось придумать вычислимую функцию, которую нельзя было бы запрограммировать в виде машины Тьюринга. Выводы: Машина Тьюринга – математически строгий аналог понятия «алгоритм». Принцип работы машины Тьюринга лежит в основе всех современных ЭВМ.
