23 июня 1912 года родился Алан Мэтисон Тьюринг, - английский математик, логик, криптограф, оказавший существенное влияние на развитие информатики. Кавалер Ордена Британской империи, член Лондонского королевского общества. Разработал ряд методов взлома, в том числе теоретическую базу для Bombe — машины, использованной для взлома немецкого шифратора "Enigma".
Родители Алана жили в индийском городе Чхатрапур. Отец — Юлиус Мэтисон Тьюринг представитель старого шотландского аристократического рода, работал в Индийской гражданской службе. Мать — Сара Этель, была родом из Ирландии, из протестантской семьи англо-ирландского дворянства. Когда она ждала ребёнка, супруги решили переехать в Англию, чтобы он рос и воспитывался в Лондоне. Там Алан Тьюринг и родился. Государственная служба Юлиуса Тьюринга продолжалась, и родителям Алана приходилось часто путешествовать между Гастингсом и Индией, оставляя двоих своих сыновей на попечение отставной армейской пары.
В шесть лет Алан Тьюринг пошёл в школу святого Михаила в Гастингсе, директор которой сразу отметила его одарённость. В 1926 году, в возрасте 13 лет, Тьюринг пошёл в известную частную школу Шерборн в городе Шерборн графства Дорсет. Его первый день в школе совпал со Всеобщей забастовкой 1926 года. Поэтому Тьюрингу пришлось преодолеть расстояние около 100 километров от Саутгемптона до Шерборна на велосипеде, по пути он переночевал в гостинице.
Увлечение Тьюринга математикой не нашло поддержки среди учителей Шерборнской школы, где уделяли больше внимания гуманитарным наукам. Тем не менее в областях, интересовавших его, Тьюринг проявлял незаурядные способности. Он решал сложные математические задачи в 1927 году несмотря на то, что ему не преподавали даже основ математического анализа.
Из-за нелюбви к гуманитарным наукам Тьюринг недобрал баллов на экзамене и поэтому после школы поступил в Королевский колледж Кембриджа, хотя намеревался пойти в Тринити-колледж. В Королевском колледже Тьюринг учился с 1931 по 1934 год под руководством известного математика Годфри Харолда Харди.
В 1928 году немецкий математик Давид Гильберт привлёк внимание мировой общественности к проблеме разрешения (Entscheidungsproblem – нем.). В своей работе "On Computable Numbers, with an Application to the Entscheidungsproblem", опубликованной 12 ноября 1936 года, Тьюринг переформулировал теорему Гёделя о неполноте, заменив универсальный формальный арифметический язык Гёделя на простые гипотетические устройства, которые впоследствии стали известны как машины Тьюринга. Он доказал, что подобная машина была бы способна произвести любые математические вычисления, представимые в виде алгоритма. Далее Тьюринг показал, что не существует решения Entscheidungsproblem, сначала доказав, что Проблема остановки для машины Тьюринга неразрешима: в общем случае невозможно алгоритмически определить, остановится ли когда-нибудь данная машина Тьюринга.
Хотя доказательство Тьюринга было обнародовано в скором времени после эквивалентного доказательства Алонзо Чёрча, в котором использовались Лямбда-исчисления, сам Тьюринг был с ним незнаком. Подход Алана Тьюринга принято считать более доступным и интуитивным. Идея "Универсальной машины", способной выполнять функции любой другой машины, или, другими словами, вычислить всё, что можно в принципе вычислить, была крайне оригинальной. Фон Нейман признал, что концепция современного компьютера основана на этой работе Алана Тьюринга. Машины Тьюринга по-прежнему являются основным объектом исследования теории алгоритмов.
С сентября 1936 года по июль 1938 года Тьюринг работал под руководством Чёрча в Принстоне, Тьюринг поступил туда в качестве приглашённого студента-последипломника и остался, чтобы завершить свой докторат под началом Чёрча. Кроме занятий математикой, он изучал криптографию, а также конструировал электромеханический бинарный умножитель. В июне 1938 года он защитил докторскую диссертацию "Логические системы, основанные на ординалах", в которой была представлена идея сведения по Тьюрингу, заключающаяся в объединении машины Тьюринга с оракулом. Это позволяет исследовать проблемы, которые невозможно решить с помощью лишь машины Тьюринга.
Предложенная им в 1936 году абстрактная вычислительная "Машина Тьюринга", которую можно считать моделью компьютера общего назначения, позволила формализовать понятие алгоритма и до сих пор используется во множестве теоретических и практических исследований. Научные труды А. Тьюринга — общепризнанный вклад в основания информатики (и в частности — теории искусственного интеллекта).
Машина Тьюринга
Машина Тьюринга — это абстрактная вычислительная машина, мысленный эксперимент для решения проблемы математической логики. Она состоит из трёх элементов:
· бесконечной ленты с ячейками;
· автомата или головки для чтения и записи;
· программы.
Историческое значение машины Тьюринга в том, что это первая математическая модель универсальных вычислений. Другими словами, всё, что можно вычислить, описывается как машина Тьюринга. Это не единственная модель вычислений, но, пожалуй, самая известная и популярная. И ещё это описание работы компьютера, которое Тьюринг дал до появления компьютеров.
Также новаторство Тьюринга было в том, что его машина использовала двоичную систему во времена, когда преобладала десятичная. Привычные для нас двоичные числа для большинства читателей в 1936 году были не столь знакомы. Так, компьютер ENIAC (1943–1945) использовал десятичную систему. А слово "бит" (сокращение от binary digit, «двоичная цифра») появилось в публикациях только в 1948 году.
Важность работы Тьюринга была ещё и в том, что он описал универсальный компьютер "общего назначения". Это революционная концепция. В то время компьютеры разрабатывались специально для определённых видов работ. Например, Вэнивар Буш со студентами в 1920-е годы придумал аналоговый компьютер, известный как дифференциальный анализатор. Он решал обыкновенные дифференциальные уравнения — и это было всё, что он делал.
Полнота по Тьюрингу — одно из базовых понятий в информатике. Полный по Тьюрингу язык программирования или компьютер способен имитировать машину Тьюринга. Он теоретически может выразить все задачи, решаемые компьютерами; почти все языки программирования Тьюринг-полные, если не обращать внимания на ограничения памяти.
Алан Тьюринг скончался 8 июня 1954 года оставив громадный след в истории мировой кибернетики. В честь учёного названа Премия Тьюринга — самая престижная в мире награда в области информатики.
Публикация подготовлена по материалам, опубликованным в сети Интернет.