9.2. Машины Тьюринга: определение

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

Машина Тьюринга может менять содержимое ленты с помощью специальной читающей и пишущей головки, ко­торая движется вдоль ленты. В каждый момент головка находится в одной из ячеек. Машина Тьюринга получает от головки информацию о том, какой символ та видит, и в зависимости от этого (и от своего внутреннего состоя­ния) решает, что делать, то есть какой символ записать в текущей ячейке и куда сдвинуться после этого (налево, направо или остаться на месте). При этом также меняет­ся внутреннее состояние машины (мы предполагаем, что машина — не считая ленты — имеет конечную память, то есть конечное число внутренних состояний). Ещё на­до договориться, с чего мы начинаем и когда кончаем работу.

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

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

• некоторый выделенный символ ао £ А (пробел, или пустой символ);

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

• некоторое выделенное состояние во £ 5, называе­мое начальным;

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

• некоторое подмножество Р С 5, элементы кото­рого называются заключительными состояниями (попав в такое состояние, машина останавливает­ся).

Таблица переходов устроена следующим образом: для каждой пары (текущее состояние, текущий символ) ука­зана тройка (новое состояние, новый символ, сдвиг). •Здесь сдвиг — одно из чисел —1 (влево), 0 (на месте) и 1 (направо). Таким образом, таблица переходов есть функция типа БхА—ь-БхАх { —1,0,1}, определённая на тех парах, в которых состояние не является заключи­тельным.

Остаётся описать поведение машины Тьюринга. В ка­ждый момент имеется некоторая конфигурация, склады­вающаяся из содержимого ленты (формально говоря, со­держимое ленты есть произвольное отображение Ж —У —5- А), текущей позиции головки (некоторое целое число) и текущего состояния машины (элемент 5). Преобразо­вание конфигурации в следующую происходит по есте­ственным правилам: мы смотрим в таблице, что надо де­лать для данного состояния и для данного символа, то есть выясняем новое состояние машины, меняем символ на указанный и после этого сдвигаем головку влево, впра­во или оставляем на месте. При этом, если новое состоя­ние является одним из заключительных, работа машины заканчивается. Остаётся договориться, как мы подаём информацию на вход машины и что считается резуль­татом её работы. Будем считать, что алфавит машины, помимо пробела, содержит символы 0 и 1 (а также, воз­можно, ещё какие-то символы). Входом и выходом маши­ны будут конечные последовательности нулей и единиц (двоичные слова). Входное слово записывается на пустой ленте, головка машины ставится в его первую клетку, машина приводится в начальное состояние и запускает­ся. Если машина останавливается, результатом считает­ся двоичное слово, которое можно прочесть, начиная с позиции головки и двигаясь направо (пока не появится символ, отличный от 0 и 1).

Таким образом, любая машина Тьюринга задаёт не­которую частичную функцию на двоичных словах. Все такие функции естественно назвать вычислимыми на ма­шинах Тьюринга.