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

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

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

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

()(и)=

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

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

,

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

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

Таблица 15.4.

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

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