15.3. Сочетания машин Тьюринга: композиция и объединение. Машины с полулентами, разветвление и итерация машин

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

1. Композиция машин

Композиция машин - последовательное их применение.

Определение 15.7 Пусть Т₁ - машина с внешним алфавитом А₁ и алфавитом состояний Q₁, Т₂ - с алфавитами А₂ и Q₂ соответственно, причем . Композицией Т₁ и Т₂ называется машина, обозначаемая с внешним алфавитом , алфавитом состояний ( - заключительное состояние Т₁) и работающая по правилу:

Теорема 15.4. Композиция машин существует.

Пусть программы машин Т₁ и Т₂ выглядят следующим образом:

		………					……..
А1		Т1			А2		Т2

Программа композиции приведена в таблице 15.2.

Таблица 15.2.

					………			……..
А1
	А2							Т2

Блок получен из блока T₁ следующим образом: все клетки вида программы Т₁ заменены на клетки вида (что и обеспечивает включение в работу машины Т₂ после окончания работы машины Т₁.

Пример 15.5. Пусть Т₁ - машина, складывающая числа в унарной системе счисления (пример 15.2), Т₂ - машина Тьюринга, удваивающая числа, записанные в унарной системе счисления (пример 15.3). Тогда - машина, проводящая вычисления по формуле .

2. Машины с полулентами

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

Под машиной с правой (левой) полулентой понимают следующее: в одной из ячеек бесконечной ленты содержится символ ◦ — неподвижный ограничитель, СЗУ машин с правой (левой) полулентой может находиться только на правой (левой) полуленте, состоящей из ячейки, содержащей неподвижный ограничитель, и ячеек, находящихся справа (слева) от этой ячейки.

При выходе СЗУ на ячейку с неподвижным ограничителем мы не имеет права менять ее содержимое. Так как теория машин с левой полулентой - зеркальное отражение теории машин с правой полулентой, мы в дальнейшем будем рассматривать подробно только машины с правыми полулентами.

Теорема 15.5 Пусть ▲T - машина с правой полулентой, тогда суще­ствует обычная машина, ей эквивалентная, т. е. для любого слова и над алфавитом А имеет место следующее:

▲Т(▲и) = ▲v → Т(и) = v.

Искомую машину построим в виде композиции трех машин: T₂ ◦▲T ◦ T₁,

где Т₁(и) = ▲и для любого слова и над А, Т₂(▲и) = v для любого слова ▲v.

Оказывается, что наряду с этой теоремой справедлива и обратная к ней теорема.

Теорема 15.6. Для любой машины Тьюринга с обычной лентой существует равносильная ей машина с правой (левой) полулентой ▲T (Т▲), т. е. для любого слова и над А справедливо следующее:

Т(и) = v → ▲T(▲u) = ▲v.

(T▲ (u▲) = v▲)

Расширим исходный алфавит двумя символами: ▲ - неподвижный ограничитель, ∆ - подвижный ограничитель. Искомую машину ▲T построим в виде композиции ▲T = T₄ ◦◦ T₃.

Опишем работу машин T₃ и T₄. Машина T₃ применима к любому слову ▲и и T₃ (▲и) = ▲и∆. Ясно, что T₃ существует. T₄ применима к любому слову w = ▲ΛΛ…Λv∆ и T₄ (w) = ▲v. Ясно, что и T₄ существует. Участок ленты между ▲ и ∆ назовем рабочей зоной. Машина Т ' строится по машине Т следующим образом: внутри рабочей зоны она работает так же, как машина Т, в случае выхода СЗУ на ∆ она перемещает подвижный ограничитель на одну ячейку вправо, помещая в освободившуюся ячейку Λ, и продолжает работу, возвращаясь на одну ячейку влево в том же состоянии, в котором СЗУ вышло на ∆. Эта возможность рас­ширения рабочей зоны обеспечивается введением для каждого рабочего состояния 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

Очевидно, построение программы Т ' возможно в случае любого конечного алфавита А.

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