Композиция машин Тьюринга

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

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

Умножение машин Тьюринга. Пусть заданы две машины Тьюринга: Тх и Тт В начальный момент времени tQ на ленте имеется некоторая конфигурация, которую начинает обрабатывать машина Т{, отправляясь от некоторого начального состояния ql0, причем головка машины в момент t0 находится напротив ячейки с номером /'0 (рис. 14.3).

Умножение машин Тьюринга (работа машины Т)

Рис. 14.3. Умножение машин Тьюринга (работа машины Т{)

Тогда к некоторому моменту t машина Т{ перейдет в состояние qx к, а головка машины остановится напротив ячейки Iхк. В момент времени t машину отключаем, и с этого момента начинает работать машина Т2, отправляясь от своего начального состояния q2Q, причем в момент времени t{ головка будет расположена напротив ячейки Iхк (рис. 14.4).

Умножение машин Тьюринга (работа машины Т)

Рис. 14.4. Умножение машин Тьюринга (работа машины Т2)

В момент времени t2k машина Т2 закончит работу и остановится напротив ячейки г.. Из рис. 14.4 видно, что результатом последующей работы машин Т] и Т2 будет некоторая машина Г, функциональная таблица которой строится по правилу: верхняя часть таблицы описывает работу машины Tv а нижняя часть — работу машины Т2, причем состояние останова машины Т] — qxк отождествляется с начальным состоянием машины Тг

Пример 1. Пусть заданы две машины Т{ и Тт

Тогда композиция машин Т{ и Т2 будет иметь вид:

Если одна из перемножаемых машин имеет несколько состояний останова, указывается, какой из остановов предыдущего сомножителя отождествляется с начальным состоянием последующего. Система команд (таблица или диаграмма) машины Т есть результат объединения системы команд машин 71, и Тт Из этого нетрудно видеть, что машина Т= Т{- Заработает так, как после завершения работы машины Т{ начала бы работать машина Тг Очевидно, что произведение машины Тьюринга некоммутативно, т.е. Т{- Т2фТ2- Ту Если машина Т{ (записываемая в произведении первой) имеет не одно, а два заключительных состояния, то появляется неоднозначность (индетерминизм) в том, с каким из этих состояний отождествлять начальное состояние машины Тт

Пример 2. Пусть машина Т] имеет два состояния останова.

Тогда

Начальное состояние машины Т2 отождествляется с первым состоянием останова машины Ту Таким образом, машина Т будет иметь два заключительных состояния: одно совпадает с состоянием останова машины Т2, другое — со вторым заключительным состоянием машины Ту

Итерация машин Тьюринга. Она заключается в отождествлении г-го состояния останова машин Тьюринга с начальным состоянием. Машина Тможет быть задана следующим образом:

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

Пример 3. Пусть задана машина Тьюринга.

Здесь показано умножение и итерация машин Тьюринга. При этом состояние останова машины Т3 отождествляется с начальным состоянием машины Tv а состояние останова машины Т5 с начальным состоянием машины Тт

КОНТРОЛЬНЫЕ ВОПРОСЫ

  • 1. Какова структура машины Тьюринга?
  • 2. Чем машина Тьюринга отличается от машины Поста?
  • 3. Что такое конфигурация машины?
  • 4. Каким образом записывается система команд (правил)?
  • 5. Что такое внутренняя память и внешняя память машины Тьюринга?
  • 6. В чем заключается особенность построения функциональных таблиц?
  • 7. Какова связь функциональной таблицы с функциональной диаграммой?
  • 8. Что такое композиция машин?
  • 9. В чем смысл умножения машин Тьюринга?
  • 10. Что такое итерация машин Тьюринга?
 
Посмотреть оригинал