8_1 (Мацнев А.П. - Математическая логика и теория алгоритмов - 2004)

Какая именно команда программы будет выполняться в данный момент, определяется двумя параметрами: читаемым голов­кой символом и состоянием машины.

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

Формат команды имеет следующий вид:

a q b r D,

где а — читаемый символ; q — текущее состояние; b — символ за­писываемый в обозреваемую ячейку ленты вместо символа а; r — новое состояние; D — направление движения головки машины от­носительно ленты.

Символы выбираются из конечного алфавита А = {а₁, . . . , a₁}.

В дальнейшем будем использовать трехсимвольный алфавит {е 0, 1}, причем е будет означать «пустой (empty)» символ — отсут­ствие информации в ячейке, а с помощью нуля и единицы будут кодироваться все данные. Иногда используют двухсимвольный алфавит А = {е, 1}. В этом случае числа кодируются только еди­ницами: нуль кодируется одной единицей, число один кодируется двумя единицами, а число х кодируется х + 1 единицами Это — единичная система счисления. Однако она плоха с точки зрения сложности задач (см. гл. 5).

Множество состояний обозначим Q= { q₁, . . . , q_k}. Направ­ление движения D выбирается из множества {L, R, S} где L — движение влево, R — движение вправо, S — отсутствие лви жения.

Таким образом, команда 1 q₃ 0 q₆ L означает: если, находясь в состоянии q₃, машина Тьюринга обозревает ячейку ленты в ко­торой записана 1, то машина должна записать в эту ячейку 0, произвести сдвиг головки относительно ленты влево на одну ячейку и перейти в состояние q₆.

Это описание действия, соответствующего команде говорит о том, что команда может рассматриваться как отображение пар (a, q) в тройки (b, r, D), т. е. отображение

AxQ=> AxQx {L, R, S}.

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

Все действия производятся в дискретном времени. Иначе го­воря, можно рассматривать целочисленные моменты времени t = = 0, 1, 2, 3, ... Любое изменение происходит мгновенно в момент t = i и ничего не меняется между двумя соседними моментами времени.

Работает машина Тьюринга следующим образом. Стартовая конфигурация: на ленте находятся исходные данные — строка символов в алфавите А, состояние внутренней памяти соответст­вует некоторому оговоренному (всегда одному и тому же) нача­льному состоянию, например, q₁. При этом головка машины обо­зревает некоторую ячейку ленты с записанным там символом а. Нормальным считается начальное положение головки напротив самого левого непустого символа, т. е. не совпадающего с е.

Момент старта рассматривается как нулевой момент времени. В момент старта выполняется первая команда, это единственная команда, начинающаяся с пары (a, q₁). В результате выполнения команды машина перейдет в новое состояние, и головка машины прочтет новый символ с ленты. Эта пара (новый символ, новое состояние) станет начальной частью следующей команды и т. д. Машина будет продолжать работать в дискретном времени, шаг за шагом переходя из состояния в состояние, и постепенно изме­няя содержимое ленты. Наконец, для некоторой пары (a, q) не окажется команды в программе. Такая ситуация считается завер­шающей. Машина прекращает функционирование. Оставшаяся запись на ленте считается записью результата.

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

Существует несколько способов представления программы машины Тьюринга (множества команд). Два наиболее употреби­тельных:

1. двумерная таблица (рис. 1.2);

2. диаграмма (нагруженный псевдограф).

В двумерной таблице строки помечаются различными симво­лами алфавита, а столбцы — именами различных состояний ма­шины, т. е. таблица имеет размер Ik. Каждой команде программы

Рис. 1.2. Табличная форма программы машины Тьюринга

соответствует единственная клетка в таблице. Она определяется для команды aqbrD следующим образом: в клетку, находящу­юся на пересечении строки, помеченной символом я, и столбца помеченного состоянием q. вписывается тройка b r D.

Для некоторых пар (а, q) в программе нет команд, следовате­льно, соответствующие клетки таблицы остаются пустыми. При достижении в процессе работы пустой клетки машина Тьюринга останавливается.

В качестве простого примера приведем программу вычисле­ния функции S(x) = x + 1, т. е. увеличение аргумента на единицу (рис. 1.3). Используем алфавит A = {e, 0, 1}, причем x будем коди­ровать последовательностью нулей и единиц так. как это приня­то при двоичном кодировании целых неотрицательных чисел.

предположим также, что в момент старта головка машины Тьюринга находится напротив крайней левой ячейки с символом 1.

Р и с. 1.3. Программа машины Тьюринга для вычисления функции S(x)=x+1

Первая выполняемая команда —1q₁1q₁R оставляет 1 в ячей­ке ленты, оставляет неизменным состояние q₁ и производит сдвиг головки вправо по ленте. В новой читаемой ячейке может оказа­ться любой из трех символов алфавита. Если это 0 или 1, то про­изводится дальнейшее движение вправо до окончания кода числа х. Если же встретится символ е, то это будет означать, что код числа закончился и головка находится справа от младшей цифры кода числа. После этого, собственно, и начинается процесс при­бавления единицы. Если младшая цифра — 0 то достаточно за­менить се на 1 (команда 0 q₂ 1 q₃ L) и начать обратное движение к исходной позиции. Если младшая цифра — 1 то результатом в данной ячейке будет 0 (сложение по mod 2), и единица перейдет в следующий по старшинству разряд (влево). Процесс распростра­нения переноса может закончиться где-то внутри кода числа и тогда необходимо осуществить «прокрутку» ленты так, чтобы машина остановилась на крайней левой единице кода результата (x+1)

Второй пример - программа вычисления функции Z(x) = 0(x) = 0, превращающей запись любого аргумента. x в запись нуля (рис. 1.4). Эта программа стирает с ленты код x, т. е. запол

P 11 с. 1.4. Программа машины Тьюринга для вычисления функции 0(x) = 0

няет клетки символом е и перед остановкой записывает в теку­щую клетку 0.

Более длинная программа получается для вычисления функции Iⁿ_m (x₁,x₂, … , x_n) выбирающей m-й аргумент из последовательно­сти п аргументов, 1  m  n, Iⁿ_m (х₁, х₂, ... ,x_n)=x_m (рис. 1.5).

Представление последовательности п аргументов зададим на ленте в виде записанных один за другим через разделитель — пу­стую клетку е — двоичных кодов х_i. Программа, написанная для конкретного значения т, действует следующим образом. Снача­ла стирается (заменяется на е ...е) первый аргумент, затем стира­ется второй, ..., стирается (т - 1)-й; затем подтверждается т-й аргумент; затем стираются оставшиеся аргументы.

Рис. 1.5. Программа машины Тьюринга для вычисления функции

Iⁿ_m(x₁, x₂, … , x_n)

Другой способ представления программы машины Тьюрин­га — диаграмма (рис. 1.6).

Диаграмма представляет собой геометрический объект, со­стоящий из вершин (обозначаемых точками или окружностями) и дуг (рисуемых в виде направленных отрезков прямой со стрел­кой на одном из концов или в виде отрезков несамопсресекаю-щихся кривых). Каждой вершине приписывается состояние ма­шины Тьюринга: таким образом вершин в диаграмме ровно столько, сколько имеется состояний. Дуге, соединяющей две вер­шины q_i и q_j, приписывается некоторый символ а алфавита А и двойка b D так, что запись a q_i b q_j D образует команду програм­мы машины Тьюринга.

Дуга (стрелка) символизирует переход из состояния q_i в состо­яние q_j при условии, что головка читает символ а. Одновременно с этим символ а заменяется на символ b и совершается движение D. По этой причине диаграмму называют диаграммой (графом) переходов.

Рис. 1.6. Элемент диаграммы. Рис. 1.7. Диаграмма машины