Машина Тьюринга

Алан Мэтисон Тьюринг – выдающийся английский математик, совершивший грандиозное открытие, которое положило начало компьютерной эре. В свои неполные 24 года он мысленно сконструировал абстрактный механизм, призванный решить одну из фундаментальных проблем математики, поставленную знаменитым немецким профессором Давидом Гильбертом в 1900 г. на парижском Международном конгрессе математиков.

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

Более того, сама идея решения задач путем конструирования абстрактных механизмов, исполняемых на электронных устройствах, стала важнейшей для зарождения новой профессиональной сферы интеллектуальной деятельности – программирования.

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

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

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

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

При этом также меняется внутреннее состояние. Еще надо договориться, с чего начинается и когда кончается работа.

Таким образом, чтобы задать машину Тьюринга, надо указать следующие объекты:

произвольное конечное множество A (алфавит); его элементы называются символами;

некоторый выделенный символ a₀ из A (пробел, или пустой символ);

конечное множество S, называемое множеством состояний;

некоторое выделенное состояние s₀ из S, называемое начальным;

таблицу переходов, которая определяет поведение машины в зависимости от состояния и текущего символа;

некоторое подмножество F, входящее в S, элементы которого называются заключительными состояниями (попав в такое состояние, машина останавливается).

Таблица переходов устроена следующим образом: для каждой пары (текущее состояние, текущий символ) указана тройка (новое состояние, новый символ, сдвиг). Здесь сдвиг одно из чисел –1 (влево), 0 (на месте) и 1 (направо).

Остается описать поведение машины Тьюринга. В каждый момент имеется некоторая конфигурация, складывающаяся из содержимого ленты (формально говоря, содержимое ленты есть произвольное отображение Z → A), текущей позиции головки (некоторое целое число) и текущего состояния машины (элемент S).

Преобразование конфигурации в следующую происходит по естественным правилам: мы смотрим в таблице, что надо делать для данного состояния и для данного символа, то есть, выясняем новое состояние машины, меняем символ на указанный и после этого сдвигаем головку влево, вправо или оставляем на месте.

При этом если новое состояние является одним из заключительных, работа машины заканчивается.

Остается договориться, как мы подаем информацию на вход машины, и что считается результатом ее работы. Будем считать, что алфавит машины, помимо пробела, содержит символы 0 и 1 (а также, возможно, еще какие-то символы).

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

Если машина останавливается, результатом считается двоичное слово, которое можно прочесть, начиная с позиции головки и двигаясь направо (пока не появится символ, отличный от 0 и 1).