Тест тьюринга что это

Наследие Тьюринга: машина, тест и полнота

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

Что такое машина Тьюринга

Для того, чтобы представить простейшую машину Тьюринга, взглянем на её художественную реализацию:

Это бесконечная лента, не имеющая ни начала, ни конца, поделённая на ячейки. Для работы с ней мы используем некое управляющее устройство (автомат), для визуализации выбрана каретка. В каждый момент времени она имеет состояние qj и считывает содержимое ячейки ai. О том, что происходит в остальной части ленты, каретка не знает, соответственно оперировать она может только текущими данными. Всего возможно три типа действий, зависящий от этой композиции:

• выполнить сдвиг на соседнюю ячейку;
• записать в текущую новое содержимое;
• изменить состояния.

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

Множества A = и Q = являются конечными, a0 – символ пустой ячейки, q1 – начальное состояние, q0 – пассивное состояния, условие выхода машины из цикла.

Создадим таблицу для реализации алгоритма Тьюринга:

Символами _Л, _П, _Н обозначим направление движения автомата – соответственно сдвиг «влево», «вправо» или неподвижное положение.

Пусть наша лента выглядит так:

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

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

Зачем это программисту

Машина Тьюринга позволяет размять мозги и взглянуть на решение задачи иначе. В конечном счёте, с той же целью следует познакомиться с:

• нормальным алгоритмом Маркова;
• лямбда-вычислениями;
• языком программирования Brainfuck.

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

Полнота по Тьюрингу

Ещё один важный вопрос, связанный с именем известного математика. На форумах и в статьях вы неоднократно могли видеть выражение «полный\не полный язык программирования по Тьюрингу». Ответ на вопрос «что это означает?» возвращает нас к описанной выше теории. Как уже было сказано, машина Тьюринга позволяет выполнить любое преобразование, соответственно, вы можете реализовать на ней абсолютно любой алгоритм или функцию. То же самое относится и к языкам. Если с его помощью вы можете реализовать любой заданный алгоритм – он тьюринг-полный. Если в дело вступают ограничения синтаксиса или любые физические – не полный.

Тест по Тьюрингу

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

Такой тест на долгие годы предопределил развитие ИИ – программы вроде Элизы или PARRY строились именно на копировании человеческого поведения машиной. Уже позднее, когда стало понятно, что путь тупиковый, вектор развития был сдвинут в сторону изучения механизмов интеллекта. Однако до сих пор тема «способна ли мыслить машина» лежит в основе многих тестов, романов и кинофильмов.

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

Что такое тест Тьюринга и почему его так сложно пройти?

Что такое тест Тьюринга и почему его так сложно пройти?

Ответ редакции

Статья по теме

Впервые в истории компьютерной программе удалось пройти тест Тьюринга на «человечность» и убедить 33 % судей в том, что с ними общается не машина. Программа «Eugene Goostman» («Евгений Густман»), выдающая себя за тринадцатилетнего мальчика по имени Евгений Густман из Одессы, смогла убедить беседовавших с ней людей в том, что выдаваемые ею ответы принадлежат человеку.

Тест проходил в Лондонском королевском обществе, его проведение организовал Университет Рединга, Великобритания. Авторами программы являются российский инженер Владимир Веселов, проживающий в настоящее время в США, и украинец Евгений Демченко, который живёт сейчас в России.

Что такое тест Тьюринга?

Могут ли машины думать? В 1950 году английский математик Алан Тьюринг предложил тест, который позволил бы оценить уровень искусственного интеллекта относительно человеческого. Он был опубликован в философском журнале «Mind».

Идея проверки предполагала общение человека с другим человеком и с компьютерной программой в течение пяти минут, только в текстовом режиме. Если компьютер сможет обмануть как минимум 30 % собеседников, тест считается пройденным. Эксперты общаются одновременно с живым человеком и роботом, находясь в разных комнатах и не видя друг друга. По окончании теста каждый из них должен сказать, кто из двух его собеседников был человеком, а кто — программой.

Как «Евгений Густман» прошёл тест Тьюринга?

В субботу 7 июня 2014 года суперкомпьютер по имени Eugene попытался воссоздать интеллект тринадцатилетнего подростка — Евгения Густмана.

В тестировании, организованном Школой системной инженерии при Университете Рединга (Великобритания), участвовали пять суперкомпьютеров. Испытание представляло собой серию пятиминутных письменных диалогов.

Разработчикам программы удалось подготовить бота ко всем возможным вопросам и даже обучить его собирать примеры диалогов через Twitter. Кроме того, инженеры наделили героя ярким характером. Притворяясь 13-летним мальчиком, виртуальный «Евгений Густман» не вызывал сомнений у экспертов. Они поверили в то, что мальчик может не знать ответы на многие вопросы, ведь уровень знаний у среднего ребёнка существенно ниже, чем у взрослых. При этом его правильные и точные ответы списывали на необычную эрудицию и начитанность.

В тесте участвовали 25 «скрытых» людей и 5 чат-ботов. Каждый из 30-ти судей провёл по пять чат-сессий, пытаясь определить реальную природу собеседника. Для сравнения, в традиционном ежегодном конкурсе программ искусственного интеллекта на премию Лёбнера* участвует всего 4 программы и 4 скрытых человека.

Впервые программа с «юным одесситом» появилась ещё в 2001 году. Однако лишь в 2012 году она показала действительно серьёзный результат, убедив 29 % судей.

* Премия Лёбнера (англ. Loebner prize) — премия, присуждаемая победителю ежегодного конкурса «AI Loebner» (проводится с 1990 г.), в котором соревнуются программы в прохождении теста Тьюринга. Самой «человечной» программе вручается премия в $2000.

Смотрите также:

• Cлепоглухая писательница и учёный-дефектолог Ольга Скороходова. Справка →
• Что такое «Тотальный диктант» и кто его читает в 2014 году? →
• Профессия недели: химик. 9 фактов из жизни великих учёных →

Что на самом деле проверяет Тест Тьюринга

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

Теперь настал момент устроить разбор полетов, рассказать об устройстве бота и сделать выводы.

Правила игры

Правила игры были перечислены в предыдущей статье, повторю здесь, чтобы вам и мне не бегать по ссылкам.

1. Каждый подключившийся к боту участник может взять на себя роль игрока, отвечающего на вопросы, или судьи, эти вопросы задающего.
2. Если участник решил быть судьей, то бот случайным образом подбирает ему игрока – либо среди людей-игроков, либо подключает робота. То есть в игре отвечающий всегда один, и судья задает вопросы только ему.
3. Если участник решил быть игроком, то бот аналогично ищет ему в пару участника-судью.
4. Игра поделена на туры по 5 вопросов. По окончанию каждого тура судья принимает решение, с кем он общается, с человеком или с машиной — на этом игра заканчивается. Если он не может определиться, то может начать следующий тур или сдаться, прекратив игру.
5. Робот играет роль маленького мальчика Миши пяти лет. Чтобы судье не облегчать задачу, человеку-игроку рекомендуется тоже отвечать от имени Миши.

С момента запуска до момента написания статьи было сыграно 256 игр (немного странно, но факт).

Из них закончились с явным результатом, то есть обе стороны сыграли до конца очередного тура (больше одного тура никто не играл) и судья принял решение — 115 игр

• решение «робот» — 74
• решение «человек»- 41

• решение «робот» (на самом деле человек) — 15
• решение «человек» (на самом деле робот) — 11

В итоге робот правильно определялся в (74-15)/115 = 51% игр, а робота приняли за человека в 11/115 = 9.5% игр, то есть можно уверенно сказать, что Миша-бот тест не прошел.

Для сравнения, на конкурсе в 2012 году в 29% из 150 бесед судьи приняли бота-одессита Женю Густмана за человека, а в 2014-ом — 33% судей по результатам 300 бесед.

Что под капотом

Бот написан на Python и по большому счету состоит из трех модулей:

• собственно бот с движком игры
• диспетчер роботов
• робот

• Начало игры
• Ждём вопроса от судьи
• Ждём ответа от игрока
• Ждём решения от судьи
• Игра закончена

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

Когда бот получает ответ от робота, он передает ее не сразу, а с задержкой времени — это не сразу появилось, я ее добавил по замечанию galqiwi, спасибо.

Каждое изменение состояния сохраняется в БД SQLite, на случай непредвиденных ситуаций — пропадания электросети, перезагрузки операционки или попросту хозяину бота (мне, то бишь) захотелось остановить его и что-то переделать. При новом запуске бот загружает из БД сохраненные игры, и игра продолжается.

Далее, есть две очереди ожидания — судей, ожидающих игроков, и игроков, ожидающих судей. Когда участник начинает новую игру, просматривается соответствующая очередь, есть ли ему партнёр. Если нет, то сам участник ставится в очередь.

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

И, наконец, модуль робота. Но прежде, чем рассказать о внутренностях робота, расскажу о базе вопросов и ответов, с которой он работает.

Сначала я набил такой текстовый файл:

T: Миша T: Меня зовут Миша Q: Как тебя зовут? Q: Как тебя звать? Q: Как вас зовут? Q: Как твое имя? Q: Ты кто? T: Конечно Q: Ты настоящий мальчик? T: Я мальчик T: Конечно Q: Ты человек? Q: Ты настоящий человек? Q: Ты живой человек? T: Я мальчик T: Нет, конечно Q: Ты компьютер? Q: Ты машина?

… ну и так далее. Затем отдельной утилиткой считал их в базу данных — таблица вопросов, таблица ответов, связь между ними многие-ко-многим. Плюс табличка использованных слов с линками на вопросы. Причем слова сохранялись не в оригинальной форме, а в нормальной и с синонимами. Нормальная форма слова определялась по pymorphy2 от kmike, а синонимы к ней искались из словаря YARN, предварительно сконвертированного из XML в SQLite — словарь занял всего 22 мегабайта, а сколько удовольствия…

Метод поиска синонимов к нормальной форме слова:

 def normalSynonyms(self,orig): r = self.morph.parse(orig) res = [] for parse in r: word = parse.normal_form syns = self.yarn.synonyms(word) for g in syns: words = self.yarn.words(syns[g]) res = res + words return res

Теперь собственно робот. Вообще от робота требуется реализация лишь одного метода

getAnswer(self, text)

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

Поиск нужного ответа мой робот делает в два этапа:

1. Проверяет, известен ли ему вопрос. Если известен, то выбирает один из подходящих ответов.
2. Иначе разбивает вопрос на токены-слова, также находит им синонимы в нормальной форме, отбирает среди известных вопросов те, в которых есть найденные слова, и уже из найденных вопросов выбирает наиболее вероятные по количеству совпадений. И выдает подходящий ответ.

Как видите, робот не умеет «думать» над ответом, всё, что он может ответить — это одна из заготовок, подходящая или неподходящая для очередного вопроса. Вы скажете, что это фигня, а я скажу — читайте классиков.

«Словарь Вильяма Шекспира, по подсчёту исследователей, составляет 12000 слов. Словарь негра из людоедского племени «Мумбо-Юмбо» составляет 300 слов. Эллочка Щукина легко и свободно обходилась тридцатью.«

Правда, классики не упомянули, обладала ли Эллочка Щукина интеллектом, пусть даже искусственным. Наверное, и сами не были уверены.

Выбор персонажа

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

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

Было соблазнительно выбрать Людоедку Эллочку — а что, минимум словарного и фразеологического запаса, любой заготовленный ответ годится практически на любой вопрос. Но это было не интересно, хотелось усложнить задачу.

Поэтому выбор пал на роль ребенка. Возраст у ребенка должен быть такой, чтобы позволять ему связно говорить, понимать — это где-то от двух-трех лет. Он должен знать какие-то базовые вещи, но еще плохо работать с абстракциями. Например, я не вкладывал в робот калькулятор, поэтому и робот в роли ребенка не сможет посчитать «один плюс два» — так что отпадает школьный возраст и близкий к нему. Так что я взял средний возраст в пять лет, когда дети достаточно самоуверенны, но толком еще ничего не знают.

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

Железо

Осталось показать тот суперкомпьютер, на котором живет Миша-бот:

Это Raspberry Pi 3. На хвосте к нему висит SSD, прицеплен на всякий случай, если понадобится активная работа с базами данных, но в самом роботе не используется.

Собственно, это всё о роботе Мише.

Размышления о Тесте Тьюринга

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

Итак, то, что мы называем Тестом Тьюринга, было описано Тьюрингом в статье «Может ли машина мыслить?» (первая публикация называлась «Computing Machinery and Intelligence») и названо автором «игрой в имитацию». Если исходить лишь из её названия, можно было полагать, что игроки действительно должны имитировать поведение друг друга — человек притворяется машиной, а машина человеком. Но по замыслу Тьюринга в игре лишь машина должна подражать человеку.

Цитата:
«Можно было бы заметить, что при «игре в имитацию» не исключена возможность того, что простое подражание поведению человека не окажется для машины наилучшей стратегией. Такой случай возможен, но я не думаю, чтобы он привел нас к чему-нибудь существенно новому. Во всяком случае никто не пытался исследовать теорию нашей игры в этом направлении, и мы будем считать, что наилучшая стратегия для машины состоит в том, чтобы давать ответы, которые в соответствующей обстановке дал бы человек.«

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

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

Замечу, что Тьюринг не говорит, что человек не должен имитировать машину. Хотя человек может, если хочет, имитировать машину, другого человека или инопланетянина, вообще заниматься чем угодно, даже игнорировать вопросы или задавать встречные, но цель игры — получить ответ на вопрос «может ли [данная] машина мыслить?», поэтому человек здесь лишь помогает задающему вопросы в достижении цели, а не препятствует ему.

Из ответов бота:
«2018-10-23 13:01:53,385 186 Player2Judge Стал бы человек вести себя как машина, чтобы обмануть другого человека?«

Подытожу — два игрока, машина и человек:

• машина имитирует человека как можно лучше — это ее основная цель в игре
• человек ведет себя естественно

Лучшее качество машины

Разобравшись с правилами, следующим шагом предположим, что мы хотим построить мыслящую машину. Как она должна работать, точнее, как она должна проявлять свои мысленные способности?

Мы можем воспользоваться представлениями о мыслящей машине из кинофантастики. Подходит ли Джарвис из «Железного человека» под это определение? R2-D2 или C-3PO из «Звездных войн»? Дэвид из «A.I.»? Долорес Абернати из «Мира Дикого Запада»? Афина из «Земли будущего»? ВАЛЛ-И из одноименного мультфильма? Вроде про каждого из них интуитивно можно сказать, что это мыслящие машины, потому что они ведут себя осмысленно, и не похоже, что они действуют по какой-то относительно простой программе.

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

Очевидно, сразу отпадут роботы R2-D2 и ВАЛЛ-И, как не умеющие разговаривать на человеческом языке, и их я предлагаю далее не рассматривать.

Также очевидно, что в претендентах на победу окажутся машины, специально сконструированные для такой имитации — из нашего списка это Долорес и Афина. Причем если Долорес (я имею в виду её в статусе «девы в беде» в начале первого сезона) сама считает себя человеком, то Афина, напротив, вполне чётко понимает, что она робот, но может исполнить, при необходимости, имитацию на достаточно высоком уровне.

Что же касается Джарвиса, C-3PO и Дэвида, то они тоже осознают, что они машины, и не имеют ни склонности, ни способности скрывать это от людей. Задающему вопросы не придется подлавливать их на каких-то каверзных вопросах, они и сами во всем признаются.

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

• либо будет считать себя человеком и иметь соответствующие человеку воспоминания, знания и жизненный опыт;
• либо, зная о своем происхождении, будет лгать в ответах на вопросы, имитируя человека.

В защиту Тьюринга надо сказать, что перед ним не стояла задача оценки моральных качеств машины. Он искал даже не ответ, а способ получения ответа на вопрос «может ли машина мыслить?», и это в то время (1950), когда задача создания искусственного интеллекта казалась скорее фантастикой, чем теоретической наукой. На этом фоне «игра в имитацию» была значительным шагом вперёд в понимании, как оценивать искусственный интеллект.

Цитата:
«… нас интересует не то, будут ли все цифровые вычислительные машины хорошо играть в имитацию, и не то, будут ли хорошо играть в эту игру те вычислительные машины, которыми мы располагаем в настоящее время; вопрос заключается в том, существуют ли воображаемые вычислительные машины, которые могли бы играть хорошо.«

• Python
• Машинное обучение

Мысль — материальна: Алан Тьюринг как «универсальный вычислитель»

Источник: geektimes.ru

В первой половине XX века, когда были изобретены первые вычислительные машины. Однако наряду с физически осязаемыми машинами появлялись и машины-концепции. Одной из них была «машина Тьюринга» — абстрактное вычислительное устройство, придуманное в 1936 году Аланом Тьюрингом — учёным, которого считают одним из основоположников информатики.

Его кругозор распространялся от квантовой теории и принципа относительности до психологии и неврологии. А в качестве способа познания и передачи своих знаний Тьюринг использовал аппарат математики и логики. Он находил решения, казалось бы, нерешаемых задач, но был сильнее всего увлечен идеей «Универсальной машины», способной вычислить всё, что в принципе вычислимо.

Детство, образование, увлечения

Родители Алана жили в индийском городе Чхатрапур. Отец — Юлиус Мэтисон Тьюринг представитель старого шотландского аристократического рода, работал в Имперской государственной службе. Мать — Сара Этель (урожденная Стони), была родом из Ирландии, из протестантской семьи англо-ирландского дворянства. Когда она ждала ребёнка, супруги решили переехать в Англию, чтобы он рос и воспитывался в Лондоне.

Там Алан Тьюринг и родился 23 июня 1912 года. У него был старший брат Джон. Государственная служба Юлиуса Тьюринга продолжалась и родителям Алана приходилось часто путешествовать между Гастингсом и Индией, оставляя двоих своих сыновей на попечение отставной армейской пары. Признаки гениальности проявлялись у Тьюринга с раннего детства.

В детстве Алан и его старший брат Джон довольно редко видели своих родителей — их отец до 1926 года служил в Индии; дети оставались в Англии и жили на попечении в частных домах, получая строгое английское воспитание, соответствующее их положению на социальной лестнице. В рамках такого воспитания изучение основ естественных наук фактически не предусматривалось.

Маленький Алан обладал очень пытливым умом. Самостоятельно научившись читать в возрасте 6 лет, он просил у своих воспитателей разрешения читать научно-популярные книги.

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

В шесть лет Алан Тьюринг пошёл в школу святого Михаила в Гастингсе, директор которой сразу отметила его одарённость. В 1926 году, в возрасте 13 лет, Тьюринг пошёл в известную частную школу Шерборн в городе Шерборн графства Дорсет. Его первый день в школе совпал со Всеобщей забастовкой 1926 года. Поэтому Тьюрингу пришлось преодолеть расстояние около 100 км от Саутгемптона до Шерборна на велосипеде, по пути он переночевал в гостинице.

Увлечение Тьюринга математикой не нашло особой поддержки среди учителей Шерборнской школы, где уделяли больше внимания гуманитарным наукам. Директор школы писал родителям: «Я надеюсь, что он не будет пытаться усидеть на двух стульях разом. Если он намеревается остаться в частной школе, то он должен стремиться к получению «образования». Если же он собирается быть исключительно «научным специалистом», то частная школа для него — пустая трата времени».

О школьных успехах Алана красноречиво свидетельствует классный журнал, в котором можно найти, например, следующее

Я могу смотреть сквозь пальцы на его сочинения, хотя ничего ужаснее в жизни своей не видывал, я пытаюсь терпеть его непоколебимую небрежность и непристойное прилежание; но вынести потрясающую глупость его высказываний во время вполне здравой дискуссии по Новому Завету я, все же, не могу.

Тем не менее, в областях, интересовавших его, Тьюринг проявлял незаурядные способности.

В 1928 году, в возрасте 16 лет, Тьюринг ознакомился с работой Эйнштейна, в которой ему удалось разобраться до такой степени, что он смог догадаться из текста о сомнениях Эйнштейна относительно выполнимости Законов Ньютона, которые не были высказаны в статье в явном виде.

Университет

Из-за нелюбви к гуманитарным наукам Тьюринг недобрал баллов на экзамене и поэтому после школы поступил в Королевский колледж Кембриджа, хотя намеревался пойти в Тринити-колледж. В Королевском колледже Тьюринг учился с 1931 по 1934 год под руководством известного математика Годфри Харолда Харди.

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

Главное место в жизни заняло увлечённое изучение столь интересующих его наук – математики и квантовой физики. Те годы были периодом бурного становления квантовой физики, и Тьюринг в студенческие годы знакомится с самыми последними работами в этой области. Большое впечатление производит на него книга Джона фон Неймана «Математические основы квантовой механики», в которой он находит ответы на многие давно интересующие его вопросы.

Тогда Тьюринг, наверное, и не предполагал, что через несколько лет фон Нейман предложит ему место в Принстоне – одном из самых известных университетов США. Ещё позже фон Нейман, так же как и Тьюринг, будет назван «отцом информатики». Но тогда, в начале 30-х годов ХХ века, научные интересы обоих будущих выдающихся учёных были далеки от вычислительных машин – и Тьюринг, и фон Нейман занимаются в основном задачами «чистой» математики.

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

Ставя химические опыты, он играл в особую игру «Необитаемый остров», изобретенную им самим. Цель игры заключалась в том, чтобы получать различные «полезные» химические вещества из «подручных средств» – стирального порошка, средства для мытья посуды, чернил и тому подобной «домашней химии».

Он также находил отдых в интенсивных занятиях спортом – греблей и бегом. Марафонский бег останется его поистине страстным увлечением до конца жизни.

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

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

Кроме того, в Кембридже Алан посещал лекции Виттенштейна Людвига. Виттенштейн утверждал теорию о несостоятельности математики. По его словам математика не ищет истину, но сама создаёт её. Алан был с этим не согласен и много спорил с Людвигом. Тьюринг выступал за «формализм» — математическое философское течение, которое не требовало точного перевода слов и ограничивалось примерным смыслом. А Людвиг искал абсолютной точности.

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

Машина Тьюринга

В 1928 году немецкий математик Давид Гильберт привлек внимание мировой общественности к проблеме разрешения (Entscheidungsproblem). В своей работе «On Computable Numbers, with an Application to the Entscheidungsproblem», опубликованной 12 ноября 1936 года. Тьюринг переформулировал теорему Гёделя о неполноте, заменив универсальный формальный арифметический язык Гёделя на простые гипотетические устройства, которые впоследствии стали известны как машины Тьюринга.

Он доказал, что подобная машина была бы способна произвести любые математические вычисления, представимые в виде алгоритма. Далее Тьюринг показал, что не существует решения Entscheidungsproblem, сперва доказав, что Проблема остановки для машины Тьюринга неразрешима: в общем случае невозможно алгоритмически определить, остановится ли когда-нибудь данная машина Тьюринга.

Хотя доказательство Тьюринга было обнародовано в скором времени после эквивалентного доказательства Алонзо Чёрча, в котором использовались Лямбда-исчисления, сам Тьюринг был с ним не знаком. Подход Алана Тьюринга принято считать более доступным и интуитивным. Идея «Универсальной Машины», способной выполнять функции любой другой машины, или другими словами, вычислить всё, что можно, в принципе, вычислить, была крайне оригинальной. Фон Нейман признал, что концепция современного компьютера основана на этой работе Алана Тьюринга. Машины Тьюринга по-прежнему являются основным объектом исследования теории алгоритмов.

На вопрос: «Что такое машина Тьюринга и какое отношение она имеет к программированию?» один из пользователей Toster ответил так:

В первую очередь — это формальное определение алгоритма. Задача считается алгоритмически разрешимой тогда и только тогда, когда её решение можно запрограммировать на машине Тьюринга (или каким-нибудь другим эквивалентным способом). Это определение даёт, например, возможность предъявить алгоритмически неразрешимые задачи. Позволяет ввести понятие «Тьюринг-полного» языка — если на языке можно реализовать машину Тьюринга, то на нём можно написать любой алгоритм (препроцессор языка С таким не является, а C# — является).

В общем, МТ — способ определить некоторый класс алгоритмов:

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

С сентября 1936 года по июль 1938 Тьюринг работал под руководством Чёрча в Принстоне. Кроме занятий математикой, учёный изучал криптографию, а также конструировал электромеханический бинарный умножитель.

В июне 1938 года Тьюринг защитил докторскую диссертацию «Логические системы, основанные на ординалах», в которой была представлена идея сведения по Тьюрингу, заключающаяся в объединении машины Тьюринга с оракулом. Это позволяет исследовать проблемы, которые невозможно решить с помощью лишь машины Тьюринга.

Криптоанализ

Во время Второй мировой войны Алан Тьюринг принимал активное участие во взломе немецких шифров в Блетчли-парке. Историк и ветеран Блетчли-парка Эйза Бригс однажды сказал:

«Блетчли-парку был нужен исключительный талант, исключительная гениальность, и гениальность Тьюринга была именно такой».

С сентября 1938 года Тьюринг работал на полставки в GCHQ — британской организации, специализировавшейся на взломе шифров. Совместно с Дилли Ноксом он занимался криптоанализом «Энигмы». Вскоре после встречи в Варшаве в июле 1939 года, на которой польское Бюро шифров предоставило Великобритании и Франции подробные сведения о соединениях в роторах «Энигмы» и методе расшифровки сообщений, Тьюринг и Нокс начали свою работу над более основательным способом решения проблемы.

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

Машина, созданная на основе этой спецификации, искала возможные настройки, использованные для шифрования сообщений (порядок роторов, положение ротора, соединения коммутационной панели), опираясь на известный открытый текст. Для каждой возможной настройки ротора (у которого было 10 ^ 19 состояний или 10 ^ 22 в модификации, использовавшейся на подводных лодках) машина производила ряд логических предположений, основываясь на открытом тексте (его содержании и структуре).

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

Спецификация для «Бомбы» была только первым из пяти важнейших достижений Тьюринга в области военного криптоанализа.

Учёный также определил индикаторную процедуру ВМФ Германии; разработал более эффективный способ использования Bombe, основанный на статистическом анализе и названный «Банбурисмусом»; метод определения параметров колёс машины Лоренца, названный «Тьюринжерией»; ближе к концу войны Тьюринг разработал портативный шифратор речи Delilah.

Статистический подход к оптимизации исследований различных вероятностей в процессе разгадывания шифров, который использовал Тьюринг, был новым словом в науке. Тьюринг написал две работы: «Доклад о применимости вероятностного подхода в криптоанализе» и «Документ о статистике и повторениях», которые представляли для GCCS, а позже и для GCHQ (англ. Government Communications Headquarters) такую ценность, что не были предоставлены национальному архиву вплоть до апреля 2012 года, незадолго до празднования ста лет со дня рождения учёного. Один из сотрудников GCHQ заявил, что этот факт говорит о беспрецедентной важности этих работ.

Тьюринг занимался также разработкой шифров для переписки Черчилля и Рузвельта, проведя период с ноября 1942 года по март 1943 года в США.

В 1945 году Тьюринг был награждён орденом Британской империи королём Георгом VI за свою военную службу, но этот факт оставался в секрете многие годы.

Послевоенные годы

После того как фон Нейман в США предложил план создания компьютера EDVAC, аналогичные работы были развернуты в Великобритании в Национальной физической лаборатории, где Тьюринг проработал с 1945 года. Ученый предложил весьма амбициозный проект АСЕ (Automatic Computing Engine – Автоматическая Вычислительная Машина), который, однако, так и не был реализован.

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

1947–1948 академический год Тьюринг провел в Кембридже. Пока Алан Тьюринг пребывал в Кембридже, Pilot ACE был построен в его отсутствие.

Franklin ACE 1200

Он выполнил свою первую программу 10 мая 1950 года. Хотя полная версия ACE никогда не была построена, некоторые компьютеры имели с ним много общего, к примеру, DEUCE и Bendix G-15.

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

В 1948 году Алан совместно со своим бывшим коллегой начал писать шахматную программу для компьютера, который ещё не существовал.

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

Тест Тьюринга

В 1948 году Алан Тьюринг получил звание Reader в математическом департаменте Манчестерского университета. Там в 1949 году он стал директором компьютерной лаборатории, где была сосредоточена работа по программированию Манчестерского Марка I.

В то же время Тьюринг продолжал работать над более абстрактными математическими задачами, а в своей работе «Computing Machinery and Intelligence» (журнал «Mind», октябрь 1950) он обратился к проблеме искусственного интеллекта и предложил эксперимент, ставший впоследствии известным как тест Тьюринга.

Его идея заключалась в том, что можно считать, что компьютер «мыслит», если человек, взаимодействующий с ним, не сможет в процессе общения отличить компьютер от другого человека. В этой работе Тьюринг предположил, что вместо того, чтобы пытаться создать программу, симулирующую разум взрослого человека, намного проще было бы начать с разума ребёнка, а затем обучать его. CAPTCHA, основанный на обратном тесте Тьюринга, широко распространён в интернете.

В 1951 году Тьюринг был избран членом Лондонского королевского общества.

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

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

Данный мысленный эксперимент имел ряд принципиальных следствий. Во-первых, он предложил некоторый операциональный критерий для ответа на вопрос «Может ли машина мыслить?».

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

Следствием этого стала та важнейшая роль, которую в дальнейшем развитии искусственного интеллекта, во всяком случае, до 1980-х годов играли исследования по моделированию понимания и производства естественного языка. В 1977 году тогдашний директор лаборатории искусственного интеллекта Массачусетского технологического института П.Уинстон писал, что научить компьютер понимать естественный язык – это все равно, что добиться построения интеллекта вообще.

Источник: slideshare.net

Память

• именем ученого назван один из астероидов;

• ежегодная награда Ассоциации вычислительной техники называется Премией Тьюринга;

• на главной площади университета Суррея (Англия) есть статуя Тьюринга и одно из зданий факультета инженерных и физических наук названо в его честь;

• одна из аудиторий отдела информатики при Университете Лилль в Северной Франции назван в честь Алана М. Тьюринга;

• Манчестерский университет, Открытый университет, Университет Оксфорд Брукс и Университет Орхус (Дания) имеют корпуса имени Тьюринга и другие;

• в 2001 году в Манчестере был установлен памятник учёному.

• машина тьюринга
• программирование
• алгоритмы
• автоматы
• криптография
• математика
• теория алгоритмов
• искусственный интеллект