Образование
Информатика
Алан Матисон Тьюринг (Alan Turing)
Алан Матисон Тьюринг (англ. Alan Mathison Turing; 23 июня 1912 — 7 июня 1954) — английский математик, логик, криптограф, изобретатель машины Тьюринга.
Маленький Алан обладал очень пытливым умом. Самостоятельно научившись читать в возрасте б лет, он просил у своих воспитателей разрешения читать научно-популярные книги. В 11 лет он ставил вполне грамотные химические опыты, пытаясь извлечь йод из водорослей. Все это доставляло огромное беспокойство его матери, которая боялась, что увлечения сына, идущие вразрез с традиционным воспитанием, помешают ему поступить в Public School (английское закрытое частное учебное заведение для мальчиков, учеба в котором была обязательна для детей аристократов). Но ее опасения оказались напрасны: Алан смог поступить в престижную Шербонскую школу (Sherborne Public School). Впрочем, вскоре ей пришлось опасаться уже того, сможет ли ее талантливый сын окончить эту школу...
...О школьных успехах Алана красноречиво свидетельствует классный журнал - юный Алан Тьюринг ничего не делал на уроках, а в свободное время — изучал "внеклассные" науки. Пятнадцатилетним подростком он самостоятельно изучил теорию относительности: его дневниковые заметки сделали бы и в наше время честь студенту-младшекурснику.
Обстановка и стиль обучения в классической британской школе, воспитывающей добропорядочных и благонадежных подданных Империи, не располагали к дальнейшему росту подобных интересов, которые к тому же Тьюрингу было совсем не с кем разделить. Преподаваемые предметы оставляли его полностью равнодушным, он успевал еле-еле и в конце концов оказался перед реальной перспективой отказа в выдаче школьного аттестата, что в очередной раз привело его мать в ужас.
В 1928 году он получает неожиданный стимул для развития своего интереса к науке: этим стимулом оказывается дружба с новым одноклассником, весьма одаренным учеником по имени Кристофер Морком. В нем Тьюринг нашел долгожданную "родственную душу" и интеллектуального партнера — того, с кем ему, наконец, можно было поделиться своими размышлениями о науке.
Юношеская жажда знаний быстро сблизила Тьюринга и Моркома, они стали неразлучными друзьями. Теперь они на уроках французского языка уже вместе зевали или играли в крестики-нолики, одновременно обсуждая астрономию и математику. После окончания школы они оба собирались поступать в Кембриджский университет, и Алан, избавившийся от многолетнего одиночества, возможно, был почти счастлив...
Первая попытка сдать предварительные экзамены в Кембридж, куда они ездили вместе, была для Алана неудачной. Но он не слишком расстраивался, потому что искренне радовался за Кристофера, который успешно прошел испытания и получил стипендию. Алан надеялся поступить со второй попытки, чтобы учиться вместе со своим другом. 13 февраля 1930 г. его друга вдруг не стало. Внезапная смерть лучшего друга потрясла семнадцатилетнего Тьюринга, повергнув его в глубокую и долгую депрессию. Тем не менее, он, бывший худший ученик в классе, нашел в себе силы поступить в Кембридж. Его поддерживало твердое убеждение в своей обязанности совершить в науке то, что Кристофер уже не мог...
Те годы были периодом бурного становления квантовой физики, и Тьюринг в студенческие годы знакомится с самыми последними работами в этой области. Большое впечатление производит на него книга Дж. фон Неймана "Математические основы квантовой механики", в которой он находит ответы на многие давно интересующие его вопросы. Тогда Тьюринг, наверное, и не предполагал, что через несколько лет фон Нейман предложит ему место в Принстоне — одном из самых известных университетов США. Еще позже фон Нейман, так же как и Тьюринг, будет назван "отцом информатики"... Но тогда, в начале 30-х годов, научные интересы обоих будущих выдающихся ученых были далеки от вычислительных машин — и Тьюринг, и фон Нейман занимаются в основном задачами "чистой" математики. (Отметим здесь математическую работу Тьюринга "Эквивалентность левой и правой почти-периодичности", вышедшую в 1935 году, в которой он упростил одну идею фон Неймана в теории непрерывных групп — фундаментальной области современной математики).[4]
Тьюринг происходил из аристократической семьи, но никогда не был "эстетом": кембриджские политические и литературные кружки были чужды ему. Он предпочитал заниматься своей любимой математикой, а в свободное время — ставить химические опыты, решать шахматные головоломки. Он находил отдых в интенсивных занятиях спортом — греблей и бегом (марафонский бег останется его поистине страстным увлечением до конца жизни).
Студенты Кембриджа шептались о том, что Тьюринг никогда не пользуется сигналами точного времени по радио, а подстраивает будильник, глядя по ночам на звезды и производя только ему одному известные вычисления (по радио же он слушает исключительно детские передачи). Ставя химические опыты, он играл в особую игру "Необитаемый остров", изобретенную им самим. Цель игры заключалась в том, чтобы получать различные "полезные" химические вещества из "подручных средств" — стирального порошка, средства для мытья посуды, чернил и тому подобной "домашней химии"...[4]
Тьюринг блестяще заканчивает четырехлетний (undergraduate) курс обучения. Одна из его работ, посвященная теории вероятностей, удостаивается специальной премии, его избирают в научное общество Кингз-колледжа — fellowship (нечто среднее между аспирантурой и преподавательским корпусом). Казалось, его ждет успешная карьера слегка эксцентричного кембриджского дона, работающего в области "чистой" математики (don — так в Кембридже и Оксфорде по традиции называют преподавателей).
Однако Тьюринг никогда не удерживался в каких-либо "рамках"... Никто не мог предвидеть, какая экзотическая проблема неожиданно увлечет его и какой математически неординарный способ ее решения ему удастся придумать.
В 1935—1936 гг. Тьюринг создает теорию, которая навсегда впишет его имя в науку. Изложение этой теории — теории "логических вычисляющих машин" — позже войдет во все учебники по логике, основаниям математики и теории вычислений. "Машины Тьюринга" станут обязательной частью учебных программ для будущих математиков и "компьютерщиков".
Фундаментальное утверждение для многих областей науки, таких, как теория вычислимости, информатика, теоретическая кибернетика и др. Это утверждение было высказано Алонзо Чёрчем и Аланом Тьюрингом в середине 1930-х годов.
В самой общей форме оно гласит, что любая интуитивно вычислимая функция является частично вычислимой, или, что тоже самое, может быть вычислена некоторой машиной Тьюринга.
Физический тезис Чёрча — Тьюринга гласит: Любая функция, которая может быть вычислена физическим устройством, может быть вычислена машиной Тьюринга.
Тезис Чёрча — Тьюринга невозможно строго доказать или опровергнуть, поскольку он устанавливает «равенство» между строго формализованным понятием частично вычислимой функции и неформальным понятием «интуитивно вычислимой функции».
Это проблема разрешимости, которая может неформально быть поставлена в виде: Даны описание алгоритма и его начальные входные данные, требуется определить, сможет ли выполнение алгоритма с этими данными завершиться когда-либо. Альтернативой этому является то, что он работает всё время без остановки.
Алан Тьюринг доказал в 1936 году, что общий алгоритм для решения проблемы зависания для любых возможных входных данных не может существовать. Мы можем сказать, что проблема зависания неразрешима на машине Тьюринга. Т.е. было обнаружено, что компьютеры всё-таки могут решить не любую математическую задачу.
Машина Тьюринга — абстрактный исполнитель (абстрактная вычислительная машина). Была предложена Аланом Тьюрингом в 1936 году для формализации понятия алгоритма.
Машина Тьюринга является расширением конечного автомата и, согласно тезису Чёрча — Тьюринга, способна имитировать все другие исполнители (с помощью задания правил перехода), каким-либо образом реализующие процесс пошагового вычисления, в котором каждый шаг вычисления достаточно элементарен.
В состав Машины Тьюринга входит бесконечная в обе стороны лента, разделённая на ячейки, и управляющее устройство, способное находиться в одном из множества состояний. Число возможных состояний управляющего устройства конечно и точно задано.
Управляющее устройство может перемещаться влево и вправо по ленте, читать и записывать в ячейки ленты символы некоторого конечного алфавита. Выделяется особый пустой символ, заполняющий все клетки ленты, кроме тех из них (конечного числа), на которых записаны входные данные.
Управляющее устройство работает согласно правилам перехода, которые представляют алгоритм, реализуемый данной Машиной Тьюринга. Каждое правило перехода предписывает машине, в зависимости от текущего состояния и наблюдаемого в текущей клетке символа, записать в эту клетку новый символ, перейти в новое состояние и переместиться на одну клетку влево или вправо. Некоторые состояния Машины Тьюринга могут быть помечены как терминальные, и переход в любое из них означает конец работы, остановку алгоритма.
Машина Тьюринга называется детерминированной, если каждой комбинации состояния и ленточного символа в таблице соответствует не более одного правила, и недетерминированной в противном случае.
Конкретная машина Тьюринга задается перечислением элементов множества букв алфавита A, множества состояний Q и набором правил, по которым работает машина. Они имеют вид: qiaj->qi1aj1dk (если головка находится в состоянии qi, а в обозреваемой ячейке записана буква aj, то головка переходит в состояние qi1, в ячейку вместо aj записывается aj1, головка делает движение dk, которое имеет три варианта: на ячейку влево (L), на ячейку вправо (R), остаться на месте (H)). Для каждой возможной конфигурации <qi, aj> имеется ровно одно правило. Правил нет только для заключительного состояния, попав в которое машина останавливается. Кроме того, необходимо указать конечное и начальное состояния, начальную конфигурацию на ленте и расположение головки машины.
Интуитивное понимание машины Тьюринга таково: имеется бесконечная лента, разделённая на клетки. По клеткам ездит каретка. Прочитав букву, записанную в клетке, каретка движется вправо, влево или остаётся на месте, при этом буква заменяется новой. Некоторые буквы останавливают каретку и завершают работу.
Любая интуитивно вычислимая функция является частично рекурсивной, или, эквивалентно, может быть вычислена с помощью некоторой машины Тьюринга.[3]
В 1939 году британское военное ведомство поставило перед Тьюрингом задачу разгадать секрет "Энигмы" – специального устройства, использовавшегося для шифровки радиограмм в германском военно-морском флоте и в "люфтваффе". Британская разведка раздобыла это устройство, но расшифровывать перехваченные радиограммы немцев не удавалось.
Тьюрингу была предоставлена свобода действий. Он работал в Блечли Парке — британском криптографическом центре, где возглавлял одну из пяти групп, Hut 8, занимавшихся в рамках проекта «Ультра» расшифровкой закодированных немецкой шифровальной машиной «Энигма» сообщений Кригсмарине и Люфтваффе. Вклад Тьюринга в работы по криптографическому анализу алгоритма, реализованного в «Энигме» основывался на более раннем криптоанализе предыдущих версий шифровальной машины, выполненных в 1938 году польским криптоаналитиком Марианом Реевским.
В начале 1940 года он разработал дешифровальную машину «Бомба», позволявшую читать сообщения Люфтваффе. Принцип работы «Бомбы» состоял в переборе возможных вариантов ключа шифра и попыток расшифровки текста, если была известна часть открытого текста или структура расшифровываемого сообщения. Перебор ключей выполнялся за счет вращения механических барабанов, сопровождавшегося звуком, похожим на тиканье часов, из-за чего «Бомба» и получила свое название. Для каждого возможного значения ключа, заданного положениями роторов (количество ключей равнялось примерно 1019 для сухопутной «Энигмы» и 1022 для шифровальных машин, используемых в подводных лодках), «Бомба» выполняла сверку с известным открытым текстом, выполнявшуюся электрически. Первая в Блетчли «Бомба» Тьюринга была запущена 18 марта 1940 года. Дизайн «Бомб» Тьюринга так же был основан на дизайне одноименной машины Реевского.[5]
Через полгода удалось взломать и более стойкий шифр Кригсмарине. Позже, к 1943 году, Тьюринг внес ощутимый вклад в создание более совершенной дешифровальной электронно-вычислительной машины «Колосс», использующейся в тех же целях.[5]
Заслуги Алана Тьюринга были по достоинству оценены: после разгрома Германии он получил орден, был включён в научную группу, занимавшуюся созданием британской электронно-вычислительной машины.
Алан Тьюринг участвовал в послевоенные годы в создании мощного компьютера — машины с хранимыми в памяти программами, ряд свойств которой он взял от своей гипотетической универсальной машины. В 1947 году Тьюринг в Манчестере создал один из первых компьютеров в мире. Опытный образец компьютера ACE (Automatic Computing Engine — автоматическое вычислительное устройство) вступил в эксплуатацию в мае 1950 г. Тьюринг увлекался проблемами машинного интеллекта (он даже придумал тест, который по его мнению позволял выяснить, может ли машина мыслить).
Кроме работы в университете, Тьюринг продолжал сотрудничать и с Департаментом кодов. Только теперь в центре его внимания были уже шифры советской резидентуры в Англии. В 1951 году он был избран членом королевского научного общества.
Тьюринг является основателем теории искусственного интеллекта. Машина Тьюринга является расширением модели конечного автомата и способна имитировать (при наличии соответствующей программы) любую машину, действие которой заключается в переходе от одного дискретного состояния к другому.
Тест Тьюринга — тест, предложенный Аланом Тьюрингом в 1950 г. в статье «Вычислительные машины и разум» (Computing machinery and intelligence) для проверки, является ли компьютер разумным в человеческом смысле слова. Тьюринг предложил тест, чтобы заменить бессмысленный, по его мнению, вопрос «может ли машина мыслить?» на более определенный.
Тест должен проводиться следующим образом. Судья (человек) переписывается на естественном языке с двумя собеседниками, один из которых — человек, другой — компьютер. Если судья не может надежно определить, кто есть кто, считается, что компьютер прошел тест. Предполагается, что каждый из собеседников стремится, чтобы человеком признали его. Чтобы сделать тест простым и универсальным, переписка сводится к обмену текстовыми сообщениями. Переписка должна производиться через контролируемые промежутки времени, чтобы судья не мог делать заключения исходя из скорости ответов. (Во времена Тьюринга компьютеры реагировали медленнее человека. Сейчас это правило необходимо, потому что они реагируют гораздо быстрее, чем человек.) [2]
Тьюринг предсказал, что компьютеры в конечном счёте пройдут его тест. Он считал, что к 2000 году компьютер с памятью 1 миллиард бит (около 119 МБ) в ходе 5-минутного теста сможет обмануть судей в 30 % случаев.[2] Это предсказание не сбылось. Тьюринг также предсказал, что сочетание «мыслящая машина» не будет считаться оксюмороном, а обучение компьютеров будет играть важную роль в создании мощных компьютеров (с чем большинство современных исследователей согласны).
Пока что ни одна программа и близко не подошла к прохождению теста. Ежегодно производится соревнование между разговаривающими программами и наиболее человекоподобной, по мнению судей, присуждается приз Лёбнера (Loebner). Есть также дополнительный приз для программы, которая, по мнению судей, пройдет тест Тьюринга. Этот приз еще не присуждался. Самый лучший результат показала программа A.L.I.C.E. выиграв приз Лёбнера 3 раза (в 2000, 2001 и 2004).
Всё рухнуло буквально в один день. В 1952 году квартиру Тьюринга обокрали. В ходе расследования выяснилось, что это сделал один из друзей его сексуального партнёра. Учёный никогда, в общем-то, не скрывал своей "нетрадиционной сексуальной ориентации", но и вызывающе себя не вёл. Однако скандал с кражей получил широкую огласку, и в результате обвинение в "непристойном поведении" было выдвинуто против самого Тьюринга. 31 марта 1953 года состоялся суд. Приговор предполагал выбор: либо тюремное заключение, либо инъекции женского гормона эстрогена (способ химической кастрации). Он выбрал последнее.[4]
Из Департамента кодов его уволили. Лишили допуска к секретным материалам. Правда, коллектив преподавателей Манчестерского университета взял Тьюринга на поруки, но он и в университете почти не появлялся. 8 июня 1954 года Алан Мэтисон Тьюринг был найден мёртвым в своём доме. Он покончил жизнь самоубийством, отравившись цианистым калием. Раствор цианида Тьюринг впрыснул в яблоко. Надкусив его, он скончался. Тем не менее, его мать считала, что он отравился случайно, так как всегда небрежно работал с химикатами. Есть версия, по которой Тьюринг специально выбрал такой способ, чтобы дать матери возможность не верить в самоубийство.[4]
Говорят, именно этот плод, найденный затем на ночном столике Алана, и стал эмблемой знаменитой компьютерной фирмы "Эппл". Впрочем, яблоко – это еще и библейский символ познания и греха.
Премия Тьюринга (англ. Turing Award) — самая престижная премия в информатике, ежегодно вручаемая Ассоциацией вычислительной техники за выдающийся научно-технический вклад в этой области. Премия спонсируется корпорациями Intel и Google и в настоящий момент сопровождается наградой в 250 000 долларов США. Впервые Премия Тьюринга была присуждена в 1966 году Алану Перлису за развитие технологии создания компиляторов.
