Машина Тьюринга стала грандиозным изобретением, положившим начало эре информационных технологий и предвосхитившим архитектуру современных компьютерных систем. Выдающемуся британскому математику и аналитику Алану Тьюрингу в неполные двадцать четыре года удалось мысленно сконструировать некий абстрактный механизм для решения одной из фундаментальных задач математики, которую сформулировал знаменитый немецкий профессор Давид Гильберт на международном математическом конгрессе, прошедшем в 1900-м году в Париже.
Машина Тьюринга не только стала четким ответом на конкретную вычислительную задачу, но и явилась теоретической основой алгоритмов и научной базой программирования. Кроме того, сам принцип решения сложных математических задач методом конструирования различных абстрактных механизмов и построения алгоритмов, исполняемых электронными устройствами, лег в основу зарождения новой сферы интеллектуальной деятельности – информационных технологий.
Машина Тьюринга снабжена бесконечной лентой, разделенной на ячейки, в каждой из которых содержится некий символ из фиксированного конечного множества. Совокупность всех символов называется алфавитом машины. Один из знаков этого своеобразного алфавита выделяется и носит название «пробела». Машина Тьюринга меняет содержимое ячеек при помощи специальной считывающей и записывающей головки движущейся вдоль ленты. Получая информацию от головки о содержимом каждой ячейки, устройство само решает в зависимости от своего внутреннего состояния, какой символ записать в данной ячейке и куда следует сдвинуть головку после этой операции. При этом внутреннее состояние (память) машины, характеризуемое неким значением от нуля до определенной максимальной величины, также подвергается изменению.
Машина Тьюринга устроена чрезвычайно просто, однако она позволяет выполнять практически любые программы, построенные на четких алгоритмах. Для исполнения различных вычислительных операций существует специальная таблица, в которой записаны определенные правила, представляющие собой набор универсальных инструкций для машины. Руководствуясь этой таблицей, в которой зафиксирован порядок действий для той или иной комбинации различных состояний и символов, устройство определяет, какую вычислительную операцию следует осуществить в каждой конкретной ситуации. По сути, универсальная машина Тьюринга является первым прототипом современных компьютеров.
Гениальное изобретение Алана Тьюринга успешно применялось британским криптоаналитическим бюро во время Второй мировой для взлома немецких секретных кодов. Часто расшифровка секретных сообщений подводных стервятников Деница ложилась на стол Черчилля раньше, чем попадала в рейхсканцелярию. В отличие от немецких криптографов, практиковавших сугубо интуитивный подход и относившихся к криптографии, как к искусству, методика Алана Тьюринга предусматривала алгоритмические способы решения сложнейших задач по расшифровке секретных кодов, что оказалось несравнимо эффективнее.
Недетерминированная машина Тьюринга дала возможность взламывать шифры противника не только гениальным криптографам, но и обычным сотрудникам бюро, превратив интуитивные действия в планомерное целенаправленное движение к цели. Полученные с помощью машины Тьюринга данные в немалой степени повлияли на исход битвы за Англию.
