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

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

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

(и ▲ v) = ▲ .

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

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

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

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

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