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

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

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

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

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

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

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

Таблица 15.2.

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

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

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