3. Объединение машин

Определение 15.8. Пусть Т₁ и Т₂ - машины Тьюринга с общим или различными внешними алфавитами А₁, А₂ и пусть ▲ А₁А₂.

Объединением машин Т₁ и Т₂ называется машина, обозначаемая , работающая по правилу

(и▲v) =▲.

Теорема 15.7. Объединение машин существует.

Объединение построим в виде композиции четырех машин:

Т_+▲ ^о _▲Т₂ ^о Т_▲+ ^о Т_1▲,

гле Т_1▲ - аналог машины Т₁ на левой полуленте, _▲Т₂ - аналог машины Т₂ на правой полуленте. машина Т_▲+, отправляясь от первой буквы слова w▲z, останавливается на первой букве после символа ▲, оставляя на ленте слово w▲z. Машина Т_+▲, отправляясь от первой справа за ▲ буквы слова w▲z, останавливается на первой букве слова w, оставляя на ленте слово w▲z. Очевидно, машины Т_▲+ и Т_+▲ существуют.

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

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

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

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

()(и) =

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

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

,

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

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

Таблица 15.4.

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

5. Итерация машины

Пусть Т - машина Тьюринга с внешним алфавитом А и Ф – машина-предикат (см. выше).

Определение 15.10 Итерацией машины Т по предикату Ф называется машина, обозначаемая Т_Ф, работа которой описывается следующим образом:

1. К слову и применяется предикат Ф, если Ф(и) = 1, то переход к 2, если Ф(и) = 0, то переход к 3.

2. , переход к 1.

3. (Т_Ф)(и):= и, останов.

Теорема 15.9 Итерация машины Т по предикату Ф существует.

Построим машину . Обозначим через ()' машину, программа которой получается из программы следующей модернизацией: все клетки, содержащие тройки , где - заключительное состояние машины Т, заменяются на клетки, содержащие , где - начальное состояние всего агрегата .

Очевидно, Т_Ф = ()'.