13. Машины Тьюринга и Поста

Машиной Тьюринга (МТ) называется упорядоченный набор вида { А, a₀, а, Q, q₁, q₀, Т, τ},где

А — конечное множество, называемое основным алфавитом МТ,

а₀ А и называется пустой буквой алфавита,Q — конечное множество, называемое алфавитом состояний МТ,q₁ Q — начальное состояние МТ,

q₀ Q — заключительное, или состояние останова МТ,

Т = {Л, Н, П} — множество сдвигов МТ,

τ — программа МТ, то есть

.

В каждой машине Тьюринга есть две части:

1. неограниченная в обе стороны лента, разделенная на ячейки;

2. головка для считывания/записи, управляемая программой.

С каждой машиной Тьюринга связаны два конечных алфавита: алфавит входных символов А = {а₀, a₁, …, a_m} и алфавит состояний Q = {q₀, q₁ ,..., q_p } . (С разными машинами Тьюринга могут быть связаны разные алфавиты А и Q.) Состояние q₀ называется заключительным, или состоянием останова. Считается, что если машина попала в это состояние, то она заканчивает свою работу. Состояние q₁ называется начальным. Находясь в этом состоянии, машина начинает свою работу.

Входное слово размещается на ленте по одной букве в расположенных подряд ячейках. Слева и справа от входного слова находятся только пустые ячейки (в алфавит А всегда входит "пустая" буква а₀ — признак того, что ячейка пуста).

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

Автомат каждый раз "видит" только одну ячейку. В зависимости от того, какую букву a₁ он видит, а также в зависимости от своего состояния q_t, автомат может выполнять следующие действия:

• записать новую букву в обозреваемую ячейку;

• выполнить сдвиг по ленте на одну ячейку вправо/влево или остаться неподвижным;

• перейти в новое состояние.

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

Клетка (q_j, a_i) определяется двумя параметрами — символом алфавита и состоянием машины.

Команда представляет собой указание: какой символ записать в текущую ячейку, куда передвинуть головку чтения/записи, в какое состояние перейти машине. Для обозначения направления движения автомата используем одну из трех букв: "Л" (влево), "П" (вправо) или "Н" (неподвижен).

После выполнения очередной команды МТ переходит в состояние q₁ (которое может в частном случае совпадать с прежним состоянием q_j). Следующую команду нужно искать в к-й строке таблицы на пересечении со столбцом, соответствующим букве, которую автомат видит после сдвига. В процессе работы автомат перескакивает из одной клетки программы, записанной в виде таблицы, в другую, пока не дойдет до клетки, в которой записано, что автомат должен перейти в состояние q₀, т.е. остановиться. Будем говорить, что такие клетки содержат команду останова.

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

Тьюрингом был описан универсальный исполнитель — машина Тьюринга, этот исполнитель способен решить любую алгоритмически разрешимую задачу. Почти одновременно с А.Тьюрингом (1937 г.) американский математик Эмиль Пост предложил иную абстрактную машину, характеризующуюся еще большей простотой, чем машина Тьюринга. Это строгое математическое построение было также предложено в качестве уточнения понятия алгоритма.

В машине Поста в ячейках бесконечной ленты можно записывать всего два знака: 0 и 1 (ставить метку в ячейку или стирать метку). Это ограничение не влияет на ее универсальность, так как любой алфавит может быть закодирован двумя знаками. Кроме ленты, в машине Поста имеется каретка (головка чтения/записи), которая:

• умеет двигаться вперед, назад и стоять на месте;

• умеет читать содержимое, стирать и записывать 0 или 1;

• управляется программой.

Как и машина Тьюринга, машина Поста может находиться в различных состояниях, но каждому состоянию соответствует не строка состояния с клетками, а некоторая команда одного из следующих шести типов (все строки в программе пронумерованы):

1. Записать 1 (метку), перейти к i-й строке программы;

2. Записать 0 (стереть метку), перейти к i-й строке программы;

3. Сдвиг влево, перейти к i-й строке программы i;

2. Сдвиг вправо, перейти к i-й строке программы;

3. Останов;

4. Если 0, то перейти к i, иначе перейти к j.

Состояние машины — это состояние ленты и положение головки чтения/записи. Тезис Поста заключается в том, что: "Всякий алгоритм представим в форме машины Поста". Отсюда следует другое формальное определение алгоритма.

Алгоритм (по Посту) — программа для машины Поста, приводящая к решению поставленной задачи. Тезис Поста невозможно строго доказать, так же, как и тезис Тьюринга.