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

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

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

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

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

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

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

Таблица 15.2.

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

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

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

Дата добавления: 2014-01-13