- •15.2. Машина Тьюринга. Описание. Примеры машин
- •15.3. Сочетания машин Тьюринга: композиция и объединение. Машины с полулентами, разветвление и итерация машин
- •1. Композиция машин
- •2. Машины с полулентами
- •3. Объединение машин
- •4. Разветвление машин
- •5. Итерация машины
- •15.4. Тьюрингов подход к понятию «алгоритм». Алгоритмически разрешимые и неразрешимые проблемы
- •1. Универсальный алфавит; универсальная кодировка
- •15.5. Универсальная машина Тьюринга
3. Объединение машин
Определение 15.8. Пусть Т1 и Т2 - машины Тьюринга с общим или различными внешними алфавитами А1, А2 и пусть ▲ А1А2.
Объединением машин Т1 и Т2 называется машина, обозначаемая , работающая по правилу
(и▲v) =▲.
Теорема 15.7. Объединение машин существует.
Объединение построим в виде композиции четырех машин:
Т+▲ о ▲Т2 о Т▲+ о Т1▲,
гле Т1▲ - аналог машины Т1 на левой полуленте, ▲Т2 - аналог машины Т2 на правой полуленте. машина Т▲+, отправляясь от первой буквы слова w▲z, останавливается на первой букве после символа ▲, оставляя на ленте слово w▲z. Машина Т+▲, отправляясь от первой справа за ▲ буквы слова w▲z, останавливается на первой букве слова w, оставляя на ленте слово w▲z. Очевидно, машины Т▲+ и Т+▲ существуют.
4. Разветвление машин
Пусть Т1 и Т2 - две машины Тьюринга с общим внешним алфавитом А и алфавитами состояний Q1 и Q2 () и пусть 0 и 1 не принадлежат А.
Пусть Ф - машина-предикат, т. е. машина с внешним алфавитом {0; 1}, применимая к любому слову и над алфавитом А и Ф(и) принадлежит множеству {0; 1}.
Определение 15.9 Разветвлением машин Т1, Т2, управляемым предикатом Ф, называется машина, обозначаемая , которая работает по правилу
()(и) =
Теорема 15.8. Разветвление машин существует.
Построим разветвление в виде композиции трех машин
,
где машина имеет программу, представленную в виде табл. 15.4
Начальным состоянием машины является состояние , а заключительными - заключительные состояния , - машин Т1 и Т2 соответственно.
Таблица 15.4.
|
……… |
…….. |
|||||||
|
|
|
|
|
|
|
|
|
|
…….. |
|
|
|
|
Т1 |
|
|
Т2 |
|
|
|
|
|
|
|
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|
0 |
|
|
|
|
|
|
|
|
|
▲ |
|
|
|
|
|
|
|
5. Итерация машины
Пусть Т - машина Тьюринга с внешним алфавитом А и Ф – машина-предикат (см. выше).
Определение 15.10 Итерацией машины Т по предикату Ф называется машина, обозначаемая ТФ, работа которой описывается следующим образом:
1. К слову и применяется предикат Ф, если Ф(и) = 1, то переход к 2, если Ф(и) = 0, то переход к 3.
2. , переход к 1.
3. (ТФ)(и):= и, останов.
Теорема 15.9 Итерация машины Т по предикату Ф существует.
Построим машину . Обозначим через ()' машину, программа которой получается из программы следующей модернизацией: все клетки, содержащие тройки , где - заключительное состояние машины Т, заменяются на клетки, содержащие , где - начальное состояние всего агрегата .
Очевидно, ТФ = ()'.