Описание машин Тьюринга

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

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

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

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

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

Теперь обратим внимание на двойственную роль множества состояний машины Тьюринга. Во-первых, состояние фиксирует инструкцию по дальнейшим действиям. Но состояния можно также использовать для хранения информации, привязанной к управляющей головке МТ. Такую информацию можно использовать в любой момент времени для выбора одного из возможных действий. Поскольку множество состояний МТ конечно, такая «оперативная память» имеет лишь конечную ёмкость. С формальной точки зрения использование «оперативной памяти» МТ означает, что множество состояний МТ Q представлено в виде декартова произведения С х М двух конечных множеств. В состоянии q = (с, 777.) вторая компонента т отвечает за содержимое «оперативной памяти».

Аналогично множеству состояний алфавит машины Тьюринга также можно расширять. Таким способом можно описывать расстановку «пометок» на рабочей ленте. «Пометки» хранят информацию в ячейках ленты.

Приведём пример использования этих приёмов в рассуждениях о машинах Тьюринга.

Пример 4.14 {"чистое" соединение машин Тьюринга). В дальнейшем мы будем использовать последовательное соединение машин Тыоринга для построения машины, вычисляющей композицию вычисляемых МТ функций^[1]). Обратим внимание на одну возникающую здесь трудность. В определении результата работы МТ ничего не говорится о положении головки. С другой стороны, в начальной конфигурации машины мы предполагаем, что головка находится над первым непустым символом. Поэтому описанная выше конструкция соединения машин напрямую непригодна для вычисления композиции функций.

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

Машина М' имеет алфавит А х {0,1}, который состоит из пар (символ алфавита А машины А/, пометка). Неформально пометка 1 означает, что был выполнен такт работы, при котором прочитана, ячейка, в которой находится символ. Пары вида, (а, 0) отождествляются с исходным алфавитом машины. В частности, пустым символом машины является символ (Л, 0), а запись входа машины М целиком состоит из символов машины А/' с нулевой пометкой, так что описанное выше свойство пометок перед началом работы выполняется.

Опишем машину М' как последовательное соединение машин А/], М2 и М3. Машина М моделирует работу А/, меняя первые компоненты символов алфавита точно так же, как это делает машина А/. Во вторых компонентах машина Mj поддерживает указанное выше свойство. Другими словами, её таблица переходов имеет вид.

Финальные состояния у Mi те же, что и у М.

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

Наконец, машина М3 убирает пометки^[2]' и останавливается над первым непустым символом. (Если вся лента пуста, то машина может остановиться в любом месте.) Машина А/з движется направо, меняя символы (Л, 1) на (Л, 0), пока не достигнет первого непустого символа в первой компоненте. Этот символ она не меняет и продолжает движение направо, заменяя пометки на 0, пока не достигнет символа с пометкой 0. В этот момент она начинает двигаться налево до тех пор, пока не обнаружит (уже единственный) символ с пометкой 1. Заменив пометку этого символа на 0, машина Л/з останавливается. Таблица переходов машины Мз задаётся следующим образом (а пробегает множество непустых символов алфавита):

Проверка корректности этой таблицы предоставляется читателю в качестве полезного упражнения.

Замечание 4.15. Иногда бывает желательно не только фиксировать положение головки в конце работы, но и потребовать, чтобы финальное состояние машины М' совпадало с финальным состоянием машины М. Для этого нужно использовать веерное соединение, в котором для каждого финального состояния запускается своя копия машины М-2 из описанной выше конструкции.

Задача 4.2. Постройте машину Тыоринга, результат работы которой по входе it, v € {0,1}*, равен 1, если и

и v задают одно и то же натуральное число, и равен 0 в противном случае.

• [1] Под вычисляемой МТ функцией мы понимаем сейчас частичноотображение входов на результаты работы.
• [2] Напомним, что с символами алфавита, А машины М мы отождествили пары с нулевой пометкой, поэтому данный шаг необходим.