- •15.2. Машина Тьюринга. Описание. Примеры машин
- •15.3. Сочетания машин Тьюринга: композиция и объединение. Машины с полулентами, разветвление и итерация машин
- •1. Композиция машин
- •2. Машины с полулентами
- •3. Объединение машин
- •4. Разветвление машин
- •5. Итерация машины
- •15.4. Тьюрингов подход к понятию «алгоритм». Алгоритмически разрешимые и неразрешимые проблемы
- •1. Универсальный алфавит; универсальная кодировка
- •15.5. Универсальная машина Тьюринга
15.3. Сочетания машин Тьюринга: композиция и объединение. Машины с полулентами, разветвление и итерация машин
Перечисленные в заголовке типы сочетаний машин позволяют при конструировании машин использовать стандартные приемы, аналогами которых в реальном программировании являются подпрограммы, циклы, разветвления, модульное программирование.
1. Композиция машин
Композиция машин - последовательное их применение.
Определение 15.7 Пусть Т1 - машина с внешним алфавитом А1 и алфавитом состояний Q1, Т2 - с алфавитами А2 и Q2 соответственно, причем . Композицией Т1 и Т2 называется машина, обозначаемая с внешним алфавитом , алфавитом состояний ( - заключительное состояние Т1) и работающая по правилу:
Теорема 15.4. Композиция машин существует.
Пусть программы машин Т1 и Т2 выглядят следующим образом:
|
……… |
|
|
…….. |
||||
А1
|
|
Т1 |
|
|
А2 |
|
Т2 |
|
Программа композиции приведена в таблице 15.2.
Таблица 15.2.
|
……… |
…….. |
|||||||
А1
|
|
|
|
|
|
|
|
|
|
А2 |
|
|
Т2 |
|
|||||
|
|
|
|
|
Блок получен из блока T1 следующим образом: все клетки вида программы Т1 заменены на клетки вида (что и обеспечивает включение в работу машины Т2 после окончания работы машины Т1.
Пример 15.5. Пусть Т1 - машина, складывающая числа в унарной системе счисления (пример 15.2), Т2 - машина Тьюринга, удваивающая числа, записанные в унарной системе счисления (пример 15.3). Тогда - машина, проводящая вычисления по формуле .
2. Машины с полулентами
Прежде чем перейти к объединению, разветвлению, итерации машин, нам потребуется изучить класс машин Тьюринга с полулентами.
Под машиной с правой (левой) полулентой понимают следующее: в одной из ячеек бесконечной ленты содержится символ ◦ — неподвижный ограничитель, СЗУ машин с правой (левой) полулентой может находиться только на правой (левой) полуленте, состоящей из ячейки, содержащей неподвижный ограничитель, и ячеек, находящихся справа (слева) от этой ячейки.
При выходе СЗУ на ячейку с неподвижным ограничителем мы не имеет права менять ее содержимое. Так как теория машин с левой полулентой - зеркальное отражение теории машин с правой полулентой, мы в дальнейшем будем рассматривать подробно только машины с правыми полулентами.
Теорема 15.5 Пусть ▲T - машина с правой полулентой, тогда существует обычная машина, ей эквивалентная, т. е. для любого слова и над алфавитом А имеет место следующее:
▲Т(▲и) = ▲v → Т(и) = v.
Искомую машину построим в виде композиции трех машин: T2 ◦▲T ◦ T1,
где Т1(и) = ▲и для любого слова и над А, Т2(▲и) = v для любого слова ▲v.
Оказывается, что наряду с этой теоремой справедлива и обратная к ней теорема.
Теорема 15.6. Для любой машины Тьюринга с обычной лентой существует равносильная ей машина с правой (левой) полулентой ▲T (Т▲), т. е. для любого слова и над А справедливо следующее:
Т(и) = v → ▲T(▲u) = ▲v.
(T▲ (u▲) = v▲)
Расширим исходный алфавит двумя символами: ▲ - неподвижный ограничитель, ∆ - подвижный ограничитель. Искомую машину ▲T построим в виде композиции ▲T = T4 ◦◦ T3.
Опишем работу машин T3 и T4. Машина T3 применима к любому слову ▲и и T3 (▲и) = ▲и∆. Ясно, что T3 существует. T4 применима к любому слову w = ▲ΛΛ…Λv∆ и T4 (w) = ▲v. Ясно, что и T4 существует. Участок ленты между ▲ и ∆ назовем рабочей зоной. Машина Т ' строится по машине Т следующим образом: внутри рабочей зоны она работает так же, как машина Т, в случае выхода СЗУ на ∆ она перемещает подвижный ограничитель на одну ячейку вправо, помещая в освободившуюся ячейку Λ, и продолжает работу, возвращаясь на одну ячейку влево в том же состоянии, в котором СЗУ вышло на ∆. Эта возможность расширения рабочей зоны обеспечивается введением для каждого рабочего состояния q машины Т состояния машины Т '.
Хуже обстоит дело в случае, когда СЗУ выходит на ▲, так как неподвижный ограничитель нельзя перемещать. В этот момент работа машины Т ' как машины Т должна прерваться для того, чтобы побуквенно переместить слово на одну ячейку вправо, заполнив освободившуюся ячейку пустым символом Λ; после чего машина Т ' может вернуться к освободившейся ячейке и продолжить работу как машина Т. Сложность такой «модернизации» Т к Т ' состоит в том, что машина Тьюринга не обладает внутренней памятью, а запоминать нужно рабочее состояние, в котором произошел выход СЗУ на неподвижный ограничитель и перекладываемые буквы (какую поместить в ячейку из предыдущей и какую запомнить, чтобы переложить в следующую). Такое расширение рабочей зоны обеспечивается введением для каждого рабочего состояния q машины Т целого шлейфа состояний машины Т ' (длина шлейфа зависит от |А|). Выпишем программу машины Т ' в случае, когда А = (табл. 15.3).
Таблица 15.3.
|
α |
β |
Λ |
▲ |
∆ |
Т |
▲q▲ +1 |
Λ+1 |
|||
… |
|||||
q |
|||||
… |
|||||
q▲ |
Λ qα +1 |
Λ qβ +1 |
Λ qΛ +1 |
|
∆ q∆ +1 |
qα |
α qα +1 |
α qβ +1 |
α qΛ +1 |
|
α q∆ +1 |
qβ |
β qα +1 |
β qβ +1 |
β qΛ +1 |
|
β q∆ +1 |
qΛ |
Λ qα +1 |
Λ qβ +1 |
Λ qΛ +1 |
|
Λ q∆ +1 |
q∆ |
|
|
∆-1 |
|
|
α-1 |
β-1 |
Λ-1 |
▲ q +1 |
|
|
|
|
∆ q -1 |
|
|
Очевидно, построение программы Т ' возможно в случае любого конечного алфавита А.
Доказанные две теоремы означают, что класс машин с полулентами эквивалентен классу обычных машин Тьюринга.