Алгоритм как преобразование слов

Словом в алфавите А или в алфавите Q, или в алфавите AUQназывается любая последовательность букв соответствующего алфавита. Под k-й конфигурацией будем понимать изображение ленты машины с информацией, сложившейся на ней к началу k-го шага (или слово в алфавите А, записанное на ленту к началу k-го шага), с указанием того, какая ячейка обозревается в этот шаг и в каком состоянии находится машина. Имеют смысл лишь конечные конфигурации, т. е. такие, в которых все ячейки ленты, за исключением, быть может, конечного числа, пусты. Конфигурация называется заключительной, если состояние, в котором при этом находится машина, заключительное.

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

Будем говорить, что непустое слово а в алфавите А \ {a₀} = {а₁,...,а_п} воспринимается машиной в стандартном положении, если оно записано в последовательных ячейках ленты, все другие ячейки пусты, и машина обозревает крайнюю справа ячейку из тех, в которых записано слово a. Стандартное положение называется начальным (заключительным), если машина, воспринимающая слово в стандартном положении, находится в начальном состоянии q₁ (соответственно в состоянии остановки q₀). Наконец, будем говорить, что слово α перерабатывается машиной в слово b, если от слова a, воспринимаемого в начальном стандартном положении, машина после выполнения конечного числа команд приходит к слову b, воспринимаемому в положении остановки.

Пример. Дана машина Тьюринга с внешним алфавитом А = {0, 1} (здесь 0 — символ пустой ячейки), алфавитом внутренних состояний Q= {q₀, q₁, q ₂}и со следующей функциональной схемой (программой):

Можно показать, что слово 101 будет преобразовано данной машиной в слово 10101.

Имеем стандартное положение

На первом шаге действует команда: q₁1→q₁ 1 П. В результате на машине создается следующая конфигурация:

На втором шаге действует команда: q₁0→q₂0П; и на машине создается конфигурация:

Наконец, третий шаг обусловлен командой: q₂0→q₀1. В результате него создается конфигурация:

Эта конфигурация является заключительной, потому что машина оказалась в состоянии остановки q₀.

Полученную последовательность конфигураций можно записать более коротким способом. Конфигурация (1) записывается в виде следующего слова в алфавите AUQ: 10q₁1 (содержимое обозреваемой ячейки записано справа от состояния, в котором находится в данный момент машина). Далее, конфигурация (2) записывается так: 101q₁0, конфигурация (3) - 1010q₂0 и, наконец, (4) — 1010q₀1. Вся последовательность записывается так:

(Самостоятельно записать последовательность переработки данной машиной слова 11011).