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

Алан Тьюринг
Alan Turing

Памятник в Сэквиль Парке
Имя при рождении:	Алан Матисон Тьюринг
Дата рождения:	23 июня 1912
Место рождения:	Лондон, Англия
Дата смерти:	7 июня 1954
Место смерти:	Вилмслоу, Чешир, Англия

А́лан Матисон Тью́ринг (англ. Alan Mathison Turing; 23 июня 1912 — 7 июня 1954) — английский математик, логик, криптограф, изобретатель машины Тьюринга.

Содержание

1 Краткая биография
2 Проблема остановки
3 Расшифровка кода «Энигмы»
4 Создание одного из первых компьютеров
5 Машина Тьюринга
6 Основатель теории искусственного интеллекта
7 Тест Тьюринга
8 Преследование за гомосексуальность и смерть Тьюринга
9 Память об Алане Тьюринге
10 См. также
11 Ссылки

[править] Краткая биография

Сын британского чиновника в Индии, Алан учился во Франции, Англии и, затем, в США. Тогда многие математики пытались создать алгоритм для определения истинности высказываний. Но Гёделю удалось доказать, что любая полезная математическая система аксиом неполна в смысле, что в ней существует высказывание, истинность которого нельзя ни опровергнуть, ни подтвердить. Это побудило Тьюринга доказать, что нет общего метода определения истинности и, таким образом, математика всегда будет содержать недоказуемые высказывания.

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

Когда Тьюринг из США возвратился в Англию, началась мировая война. Самым мощным и грозным оружием этой войны стали не ракеты Фау-2, и, даже, не созданная в 1945 году США атомная бомба, а ЭВМ «Колосс» по проекту «Ультра», начавшая в 1943 году взламывать сверхсложные шифры немцев. Именно в этом году союзникам удалось сломать хребет армии нацистов. Победа Красной Армии в Курской битве, впрочем, тоже была в значительной мере предопределена работой созданного Тьюрингом «Колосса».

После войны в 1945 Алан возглавил проект создания компьютера «ТУЗ» (ACE, Automatic Computing Engine), а в 1948 Тьюринг стал работать с «МАДАМ» (MADAM, Manchester Automatic DigitAl Machine), компьютером с самой большой памятью в мире в то время. Работы Алана по сооружению первых ЭВМ и развитию методов программирования имели неоценимую важность, дав основу большинству исследований в области искусственного интеллекта. Он полагал, что компьютеры, в конце концов, смогут мыслить как человек, и предложил простую проверку, известную как тест Тьюринга, оценивающую способность машины мыслить: побеседуйте с ЭВМ, и пусть она убедит вас, что она — человек.

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

В наивном но красивом фильме «Энигма» о любви, войне и секретных службах Тьюринг показан как главный герой Том Джерико, которого сыграл Дюгрэй Скотт.

[править] Проблема остановки

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

[править] Расшифровка кода «Энигмы»

Блечли Парк

Во время Второй Мировой войны Тьюринг работал в Блечли Парке — британском криптографическом центре, где возглавлял одну из пяти групп, Hut 8, занимавшихся в рамках проекта «Ультра» расшифровкой закодированных немецкой шифровальной машиной «Энигма» сообщений Кригсмарине и Люфтваффе. Вклад Тьюринга в работы по криптографическому анализу алгоритма, реализованного в «Энигме» основывался на более раннем криптоанализе предыдущих версий шифровальной машины, выполненных в 1938 году польским криптоаналитиком Марианом Реевским.

В начале 1940 года он разработал дешифровальную машину «Бомба», позволявшую читать сообщения Люфтваффе. Принцип работы «Бомбы» состоял в переборе возможных вариантов ключа шифра и попыток расшифровки текста, если была известна часть открытого текста или структура расшифровываемого сообщения. Перебор ключей выполнялся за счет вращения механических барабанов, сопровождавшегося звуком, похожим на тиканье часов, из-за чего «Бомба» и получила свое название. Для каждого возможного значения ключа, заданного положениями роторов (количество ключей равнялось примерно 10¹⁹ для сухопутной «Энигмы» и 10²² для шифровальных машин, используемых в подводных лодках), «Бомба» выполняла сверку с известным открытым текстом, выполнявшуюся электрически. Первая в Блетчли «Бомба» Тьюринга была запущена 18 марта 1940 года. Дизайн «Бомб» Тьюринга так же был основан на дизайне одноименной машины Реевского.

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

Даже читая закодированные немецкие сообщения, в марте 1943 года Великобритания стояла на грани поражения в Битве за Атлантику и во всей Второй мировой войне. Вполне вероятно, что без расшифровки кода «Энигмы» ход этой войны был бы иным.

[править] Создание одного из первых компьютеров

В 1947 году Тьюринг в Манчестере создал один из первых компьютеров в мире.^{[источник?]}

[править] Машина Тьюринга

Основная статья: Машина Тьюринга

Любая интуитивно вычислимая функция является частично рекурсивной, или, эквивалентно, может быть вычислена с помощью некоторой машины Тьюринга.

Алан Тьюринг высказал предположение (известное как тезис Чёрча — Тьюринга), что любой алгоритм в интуитивном смысле этого слова может быть представлен эквивалентной машиной Тьюринга. Уточнение представления о вычислимости на основе понятия машины Тьюринга (и других эквивалентных ей понятий) открыло возможности для строгого доказательства алгоритмической неразрешимости различных массовых проблем (то есть проблем о нахождении единого метода решения некоторого класса задач, условия которых могут варьироваться в известных пределах). Простейшим примером алгоритмически неразрешимой массовой проблемы является так называемая проблема применимости алгоритма (называемая также проблемой остановки). Она состоит в следующем: требуется найти общий метод, который позволял бы для произвольной машины Тьюринга (заданной посредством своей программы) и произвольного начального состояния ленты этой машины определить, завершится ли работа машины за конечное число шагов, или же будет продолжаться неограниченно долго.

[править] Основатель теории искусственного интеллекта

Тьюринг является основателем теории искусственного интеллекта.

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

[править] Тест Тьюринга

Основная статья: Тест Тьюринга

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

[править] Преследование за гомосексуальность и смерть Тьюринга

Квартира Тьюринга в Вилмслоу

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

Через год после вынесения приговора он умер от отравления цианидом, который, видимо, содержался в яблоке, половину которого Тьюринг съел перед смертью. Было признано, что он покончил жизнь самоубийством. Тем не менее, его мать считала, что он отравился случайно, так как всегда небрежно работал с химикатами. Есть версия, по которой Тьюринг специально выбрал такой способ, чтобы дать матери возможность не верить в самоубийство.^{[источник?]}