Моделирование /с-ленточной машины на одноленточной

Теорема 4.41. к-лепточные машины Тьюринга эквивалентны одноленгпочнъш.

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

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

План доказательства таков. Пусть имеется 2-ленточная машина М = (A, Q, Qj, 6, qo, А). Одиоленточная машина А/⁷, которая моделирует А/, работает следующим образом. Состояние 2-ленточной машины кодируется на одной ленте так, чтобы в каждой ячейке были записаны данные о соответственных ячейках 2-ленточной машины (можно считать для определённости, что ячейки на лентах перенумерованы). Каждый такт работы двухленточной машины моделируется в два этапа. На первом М' просматривает все используемые ячейки и определяет, в каком состоянии находится моделируемая машина, и какие символы прочитаны её головками. На втором М⁷ меняет содержимое ячеек в соответствии с таблицей перехода машины М. Перед началом этого двухэтапного процесса машина А/⁷ должна привести входные данные к тому вида, который используется при моделировании. После окончания работы М' должна преобразовать полученные данные к слову в алфавите А, отвечающему результату работы.

Опишем устройство А/⁷ подробнее. Алфавит машины М' — это множество.

пустой символ тот же, что и у моделируемой машины, — Л. Неформально нужно понимать это так, что М' использует помимо алфавита А символы, которые являются записями, фиксирующими содержимое двух ячеек машины А/, расположенных на двух лентах одинаковым образом. Помимо собственно содержимого (символа из алфавита А) машине А/⁷ потребуется информация о положении головок на лентах. Поэтому для записи содержимого ячейки используется не множество А, как можно было ожидать, а множество пар

Ax (QUA), где вторая компонента указывает, что над данной ячейкой нет головки (в этом случае вторая компонента равна Л), либо описывает состояние машины А/ (это происходит в той ячейке, над которой расположена головка).

Такое правило задаёт кодировку конфигураций машины М словами в алфавите (А х (QUA)) х (А х (Q U А)).

Моделирующая машина М' является последовательным соединением трёх машин.

Первая машина М подготавливает содержимое ленты к двухэтапному моделированию. Она просматривает ячейки по очереди, заменяя первый символ а на ((сц, q$), (Л, </о)), а каждый следующий символ входа а на ((а, Л), (Л, Л)) (напомним, что в начальном состоянии вторая лента пуста). Обнаружив пустой символ Л, эта машина записывает на его место символ ((Л, Л), (Л, Л)) и начинает двигаться налево до тех пор, пока не встретит символ вида ((а, (/о), (Л, суо)), после чего переходит в финальное состояние.

Задача 4.9. Задайте таблицу переходов для описанной выше машины Mi. Сколько состояний вам потребуется?

Вторая машина М2 используется в цикле. Её работа разбита на итерации. В начале каждой итерации мы потребуем выполнения следующих условий: налейте записана кодировка конфигурации (г/д, 1²) машины А/, а головка М2 находится над самой левой ячейкой этой кодировки. В конце итерации на ленте записана кодировка конфигурации А/, которая получается из (иц, W2) за один такт работы А/, а головка М2 опять находится над самой левой ячейкой.

Множество состояний второй машины М2 имеет вид.

Q' = Ы UQ/U (AxAxQx ({L, R} U 5)).

Неформально первая компонента, состояния, отличного от </о, Q € Q/, хранит данные о содержимом ячейки первой ленты, над которой находится головка, вторая компонента хранит аналогичные данные о второй ленте, а третья — о состоянии 2-ленточной МТ на данном такте её работы. Последняя компонента хранит информацию о направлении движения машины М2.

Финальными для машины М2 являются состояния вида (а, q, L), где q? Q/ — финальное состояние машины М и состояние qj. Поскольку машина М2 используется при соединении в цикле, укажем заранее, что условием повторения является завершение работы в состоянии qj.

В состоянии qo или состоянии вида (a, b, q, R) машина М2 движется направо, пока не находит символ Л. В процессе движения она. меняет состояние по следующему правилу: пусть текущий символ на ленте имеет вид ((а, </), (6, Л)), q ф Ф Л, тогда машина меняет состояние qo на (a. A, q, R), в остальных случаях она изменяет состояние (а', с, q', R) на (1a, c, q, R). Аналогично (с перестановкой компонент) изменяются состояния в случае, когда символ на ленте имеет вид ((6, Л), (a, q))> q ф А. Если машина М2 встречает символ вида ((а, (/), (6, </)), q Ф Л, она изменяет своё состояние на (a, b, q, Я).

Обнаружив символ Л, машина М2 меняет своё состояние (а, b, q, Я) на (а, 6, г/, L).

Описанные выше правила гарантируют, что если машина М-2 начинает работу на кодировке некоторой конфигурации моделируемой машины М, находясь в самой левой ячейке, и переходит в состояние (а, 6, g, L), то в данной конфигурации состояние моделируемой машины М равно су, а под головками на лентах расположены символы а и b соответственно.

В состояниях вида (a, b.q, L), q? Qj, машина М2 движется налево до тех пор, пока не встретит пустой символ Л, после чего она переходит в состояние qj и сдвигается вправо.

Попутно машина М2 меняет содержимое ленты так, чтобы оно кодировало конфигурацию машины М после выполнения такта работы. Для этого она выполняет следующие действия. Если прочитан символ вида (р, (6, q)), машина находится над той ячейкой, над которой расположена головка второй ленты моделируемой машины. Поэтому М2 должна изменить вторые компоненты символов в соответствии с таблицей переходов моделируемой машины М. Аналогичные действия нужно выполнить с первыми компонентами соседних символов, если прочитан символ вида ((a, q), p) —

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

Все эти действия М2 выполняет в состояниях вида (а, 6, </, 5), где s? S. Каждое из них осуществляется за конечное число шагов. Выбирая для каждого из этих шагов и каждого из этих действий своё s, мы можем записать таблицу переходов для М2, хотя и довольно громоздкую.

Если машина М2 завершает работу в состоянии qj, то в соединении машин её работа повторяется циклически.

Если машина М2 завершает работу в финальном состоянии вида (а, Ь. q, L), то моделируемая машина М находится в финальном состоянии, и машина М2 передаёт управление последней машине М3 в соединении. Эта машина переписывает содержимое ленты обратным по отношению к машине М образом. А именно, машина М3 заменяет символ ((a, q),(b, q)) на а, стирая информацию о состоянии и о содержимом второй ленты.

Замечание 4.42. Аналогично одноленточным распознающим МТ можно определить многоленточные распознающие машины. В качестве упражнения читателю предлагается доказать, что классы языков, распознаваемых одноленточными и многоленточными МТ, совпадают.

Использование многоленточных машин Тьюринга

Во многих случаях описание алгоритма с помощью многоленточных машин Тыорипга проще, чем с помощью одно ленточных.

Задача 4.10. Постройте многоленточную машину Тьюринга, которая.

• а) копирует вход (т. е. результатом работы на входе w является слово ш);
• б) переписывает вход в обратном порядке, т. е. результатом работы на. входе ww₂ … w_n является w_nw_n-…
• в) сравнивает числа, заданные в двоичной записи;
• г) выполняет сложение чисел в двоичной системе счисления;
• д) выполняет умножение чисел в двоичной системе счисления;
• е) выполняет целочисленное деление чисел в двоичной системе счисления (т. е. находит частное и остаток при делении с остатком).

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