Тьюринг: математик, логик и криптоаналитик¶

Тьюринг (полное имя — Алан Мэтисон Тьюринг, 23 июня 1912 — 7 июня 1954) — британский математик, логик, криптоаналитик и теоретик информатики, чьи работы заложили основы современной вычислительной техники и искусственного интеллекта. Наиболее известен формализацией понятий «алгоритм» и «вычисление» через абстрактную машину, носящую его имя, а также участием во взломе немецкой шифровальной системы «Энигма» во время Второй мировой войны.

¶Биография и образование

Алан Тьюринг родился в Лондоне в семье чиновника британской колониальной службы в Индии. Учился в школе Шерборн, где проявил незаурядные способности к математике и естественным наукам, затем поступил в Кингс-колледж Кембриджского университета, который окончил в 1934 году с отличием. В 1938 году получил докторскую степень в Принстонском университете (США) под руководством Алонзо Чёрча. С 1936 года работал над проблемами математической логики, а с началом войны был привлечён к секретным криптографическим проектам.

¶Машина Тьюринга и теория вычислений

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

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

¶Криптоанализ и Вторая мировая война

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

Тьюринг усовершенствовал электромеханическую машину «Бомба» (Bombe), позволявшую перебирать возможные конфигурации роторов «Энигмы» и находить ключ дня. Методы, разработанные под его руководством, существенно сократили время дешифровки и, по оценкам историков, повлияли на ход битвы за Атлантику и других операций. Работа в Блетчли-парке оставалась государственной тайной до 1970-х годов.

¶Тест Тьюринга и искусственный интеллект

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

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

¶Послевоенная деятельность и преследование

После войны Тьюринг работал в Национальной физической лаборатории в Лондоне, где проектировал компьютер ACE (Automatic Computing Engine), и в Манчестерском университете, участвуя в создании одного из первых компьютеров с хранимой программой — Manchester Mark 1. Он занимался также математической биологией, в частности моделированием морфогенеза — процесса образования структур в живых организмах.

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

¶Признание и наследие

В 2013 году королева Великобритании Елизавета II посмертно помиловала Тьюринга. В 2017 году в стране был принят «закон Тьюринга», распространивший помилование на других осуждённых по аналогичным статьям. Имя Тьюринга носят премия ACM A. M. Turing Award — одна из высших наград в области информатики, множество объектов, алгоритмов и понятий (в том числе «полнота по Тьюрингу»).

¶Значение

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

Источники: Э. Ходжес, «Алан Тьюринг: Энигма»; статьи А. Тьюринга «О вычислимых числах» и «Вычислительные машины и разум»; материалы Блетчли-парка; публикации ACM о премии Тьюринга.