Разветвление машин

Пусть Т₁ и Т₂ - две машины Тьюринга с общим внешним алфавитом А и алфавитами состояний Q₁ и Q₂ () и пусть 0 и 1 не принадлежат А.

Пусть Ф - машина-предикат, т. е. машина с внешним алфавитом {0; 1}, применимая к любому слову и над алфавитом А и Ф(и) при­надлежит множеству {0; 1}.

Определение 15.9Разветвлением машин Т₁, Т₂, управляемым предикатом Ф, называется машина, обозначаемая , которая работает по правилу

()(и)=

Теорема 15.8. Разветвление машин существует.

Построим разветвление в виде композиции трех машин

,

где машина имеет программу, представленную в виде табл. 15.4

Начальным состоянием машины является состояние , а заключительными - заключительные состояния , - машин Т₁ и Т₂соответственно.

Таблица 15.4.

					………			……..
……..					Т1			Т2
▲