TA_lec2

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

Классический формат записи работы многоленточной машины Тьюринга:
Si{a,b,c}→{a',b',c'}{R,L,H}Sj.
Машина В эквивалентна машине А, если в соответствующие такты их работы лента машины В содержит всю информацию о ленте машины А.
Примечание.
Одна из машин может работать гораздо медленнее другой, т.к. каждый такт она моделирует несколькими тактами, поэтому мы говорим о соответствующих тактах. Если в конце концов А остановится, то В тоже остановится и к этому моменту будет содержать всю информацию о ленте машины А.

Доказательство
Пусть есть k - ленточная машина М и одноленточная машина М*.
Запишем содержимое лент машины М в виде матрицы с 2k строками и бесконечным числом столбцов. В матрице нечетные строки (1, 3, 5 и т.д. до 2k-1 -ой) занимают непосредственно ленты машины М, а четные (2, 4, 6, …, 2k-ая) являются служебными. На каждой из служебных строк записан только один символ «*» и его расположение указывает на положение смотрового окошка управляющего механизма на соответствующей ленте.
Теорема. Всякая k - ленточная машина Тьюринга М может преобразована в эквивалентную машину М* с одной лентой.

На 2-ой строке специальный символ * стоит в той клетке, которая находится непосредственно под клеткой, обозреваемой управляющей головкой на первой ленте.

Построим ленту машины М*. Для этого содержимое матрицы перенесем на ленту одноленточной машины по столбцам: сначала первый столбец, затем второй и т.д. Одна гиперклетка (набор клеток) машины М* равна целому столбцу в таблице
В этом случае работа машины М* будет повторять работу машины М с тем отличием, что для воспроизведения команды машины М потребуется набор передвижений с целью определения истинной конфигурации. Для этого на ленте машины М* поочередно отыскиваются все символы * и считываются находящиеся слева от них символы внешнего алфавита соответствующих лент.
Т.о. определяется текущая конфигурация машины М. Далее по программе машины М определяются необходимые действия и они моделируются исходя из формата записи машины М*.
Например, перемещение управляющего механизма вправо на какой-нибудь из лент имитируется переносом соответствующего символа * на 2k клеток вправо.

Здесь стоит заметить, что в общем случае, не вполне очевидно, как машина М* будет опознавать на какой из лент находится символ, расположенный левее очередной обнаруженной *. В случае, если алфавиты на всех k лентах различны, это трудностей не составляет и будет учтено при составлении программы соответствующим подбором возможных конфигураций.
В случае если алфавиты на некоторых или всех лентах совпадают или имеют непустое пересечение, возникает потребность в различных символах, например r1, r2, r3 и т.д. вместо предложенного выше единого символа *.
Таким образом показано, что k-ленточная машина Тьюринга может быть преобразована в эквивалентную ей одноленточную машину Тьюринга, Q.E.D.
Q.E.D. (аббревиатура от лат. quod erat demonstrandum — «что доказывалось», «что и требовалось доказать»): латинское выражение, обозначающее завершение доказательства
теоремы.

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

Допустим:
А – знак единственного
внутреннего состояния
R – знак движения вправо
H – знак остановки
Х – табличный разделитель
команд
Тогда введем ленточные образы этих знаков:
А – α (альфа)
R – ρ (ро)
H – η (эта)
Х – ξ (кси)
Можно предложить нарочито упрощенный пример программы машины М.
A α → ξ R A // если машина находится в состоянии А (ленточный образ α),
то на это место ставится образ разделителя команд X (ξ).
A ξ → ξ R A // переход через ленточный образ разделителя команд Х (ξ).
A ρ → η H A // если машине предписано двигаться вправо, она меняет
ленточный образ символа R (ρ) на ленточный образ символа
Н (η) и останавливается.
Посмотрим, как будет проистекать самоанализ машины М.
Пример

Тогда на ленте запишем этот же код, заменив знаки ленточными образами (пробелы поставлены для повышения читаемости, на ленте символы реально записаны друг за другом). Машина находится в состоянии А, ее положение на ленте показано графически.
1 шаг: α α ξ ρ α ξ α ξ ξ ρ α ξ α ρ η η α ξ
2 шаг: ξ α ξ ρ α ξ α ξ ξ ρ α ξ α ρ η η α ξ
3 шаг: ξ ξ ξ ρ α ξ α ξ ξ ρ α ξ α ρ η η α ξ
4 шаг: ξ ξ ξ ρ α ξ α ξ ξ ρ α ξ α ρ η η α ξ
5 шаг: ξ ξ ξ η α ξ α ξ ξ ρ α ξ α ρ η η α ξ
А
А
А
А
А
Образы служебных знаков могут совпадать с самими служебными знаками, но в нашем описании рабочего процесса мы должны их различать.
Код программы машины выглядит так:
A α ξ R A Х A ξ ξ R A X A ρ η H A X

Универсальные машины
Универсальная машина (УМТ) – машина Тьюринга, обладающая способностью путём подходящего кодирования выполнить любое вычисление.
Пусть машина А имеет m символов aj и n внутренних состояний Si . Закодируем знаки, используемые при написании программы работы такой машины следующим образом.
aj = 1…1 (a1=1, a2=11, a3=111 и т.д.)
Si = 2…2 (S1=2, S2=22, S3=222 и т.д.)
R = 3
L = 33
H = 333
В этом случае всю программу работы машины можно записать неким числом, причем возможны два варианта записи:
1. С разделителем команд, допустим Х, которые можно закодировать числом 4. В этом случае классическая запись Sold aold → anew R Snew,
2. Без разделителя команд. В этом случае команды следует писать в формате aold Sold anew R Snew, тогда две команды, записанные непосредственно
друг за другом, будут явно различаться элементарным
анализатором.

Программа такой машины выглядит следующим образом (λ-пустой знак):
λ A 0 R B
λ B 0 R C
λ C 1 R A
Закодируем символы и состояния:
λ=1 0=11 1=111 A=2 B=22 C=222
Тогда запись программы машины будет выглядеть так (пробелы поставлены для повышения читаемости, в реальности их нет):
1 2 11 3 22 1 22 11 3 222 1 222 111 3 2
Т.о. каждая машина Тьюринга представлена числом – это дескриптивное (описательное) число машины. Вместе с тем оно является кодом для входного слова.
Пример: Машина Тьюринга, которая на пустой ленте бесконечно много раз печатает последовательность 001.
(Из соображений удобства формат записи aSi → a'{R,L,H}Sj)

Рассмотрим УМТ. Тогда, если цифру 5 использовать для разделения описания машины и описания входного слова, лента выглядит следующим образом
dT – описание машины (алфавит 1, 2, 3)
dW – описание входного слова, в котором каждый символ слова ai записан в виде наборов по несколько 1, разделенных специальным символом 4 (разделитель).
Описание машины – слово, разбитое на команды. УМТ читает описание данной машины, а затем перерабатывает входное слово так, как бы это сделала конкретная МТ. УМТ имеет такой же алфавит, как и у предъявленной ей машины.
Отсюда вытекает необходимость наличия меток для указания положения исходной МТ. Такие метки удобно ставить вместо разделителя, стоящего непосредственно перед группой ячеек, содержащих код рассматриваемого символа. Поскольку цифры {1,2,3,4,5} алфавита уже заняты, будем заменять разделитель 4 перед символом, на котором остановилась исходная МТ, на цифру 6.
Пример построения универсальной машины Тьюринга

Составление таблицы для одноленточной УМТ длительная и малопригодная для понимания в учебных целях процедура. Поэтому для наглядности построим трехленточную машину, которую всегда можно преобразовать в одноленточную по принципу, рассмотренному в предыдущей теореме.
Ленты трехленточной универсальной машины Тьюринга будут иметь следующее назначение:
исходная лента, на которой записан код таблицы исходной МТ,
рабочая лента, на ней записываются внутренние состояния исходной МТ,
выходная лента – закодированная лента исходной МТ.
В начале моделирования каждого такта работы исходной МТ, УМТ занимает на 3-ей ленте первую клетку.
Эта клетка соответствует той клетке на ленте исходной МТ, которую в данный момент воспринимает считывающая головка исходной МТ.
Пример построения универсальной машины Тьюринга

УМТ движется по входной ленте, пока не дойдёт до команды, в которой внутреннее состояние совпадает с записью на 2-ой ленте, а воспринимаемый символ – с тем, который записан на входной ленте, в кодовой ячейке которой изображено положение исходной машины.
Сравнение происходит по разрядам. В итоге УМТ находит на входной ленте нужную для исполнения команду МТ.
Очень важен механизм опознания того факта, что внутреннее состояние совпадает с записью на 2-ой ленте, а воспринимаемый символ – с тем, который записан на входной ленте. Любое запоминание прочитанных символов может производиться только путем изменения внутреннего состояния, однако при программировании УМТ количество состояний должно быть ограничено. В этой связи метод введения все новых и новых состояний типа S1 S11 S111 S1112 S11122 S111222S1112222 и т.д. для запоминания количества «2» на второй ленте и «1» на третьей ленте является неосуществимым. Нам просто не хватит описательных возможностей для перебора всех допустимых состояний. Реально требуется механизм поразрядного сравнения. Способов естественно огромное множество.
Пример построения универсальной машины Тьюринга

По сути, на первой ленте нужно найти некий набор последовательностей «1» и «2», идущих сразу после разделителя команд, который соответствует находящемуся на второй ленте коду состояния исходной машины (последовательность «2») и обозреваемому на третьей ленте коду символа (последовательность «1»). Для оптимизации поэтапного сравнения возможно первоначально стоит проверять совпадение символа (т.е. двигать смотровые окошки на 1-ой и 3-ой ленте) и в случае удачи, продолжить сравнение, двигая окошки на 1-ой и 2-ой ленте.
Вероятны и другие способы поразрядного сравнения (например, копирование текущей конфигурации на 4-ую ленту и поиск соответствия её содержимому на 1-ой ленте), но важным остается сам факт: запоминать слово неопределенной длины целиком невозможно, в рамках наших возможностей только поразрядное сравнение содержимого лент.
Так или иначе, УМТ считывает инструкцию, соответствующую этой команде. Затем эта инструкция выполняется,
при этом совершается три действия.
Пример построения универсальной машины Тьюринга

Изменяется положение исходной МТ. Например, если инструкция гласит «шаг вправо», то на 3-ей ленте делается необходимое количество шагов вправо до ближайшего нового разделителя команд, который заменяется меткой текущего положения (вместо 4 ставится символ 6).
Изменяется внутреннее состояние исходной МТ. На второй ленте вместо старого записывается ее новое состояние.
Изменяется символ, содержащийся в рассматриваемой ячейке. Поскольку разные символы кодируются различным количеством единичек, то в случае замены символа необходимо предусмотреть процедуру сдвига (растягивание или сжимание слова на нужное число клеток).
После этого моделируется следующий такт работы исходной МТ. Для этого снова анализируется содержание второй ленты (это теперь текущее состояние МТ) и символ, записанный справа от указателя текущего положения управляющей головки (специальная метка 6).
Пример построения универсальной машины Тьюринга
1
2
3