Композиція машин т'юринга

Визначення. Нехай задані машини Т'юринга Θ₁ і Θ₂, що мають загальний зовнішній алфавіт {a₀, a₁, …, a_m} і алфавіти внутрішніх станів {q₀, q₁, …, q_n}і відповідно. Композицією (чи множенням) машини Θ₁ на машину Θ₂ називається нова машина Θ з тим же зовнішнім алфавітом {a₀, a₁, …, a_m}, внутрішнім алфавітом {q₀, q₁, …, q_n, q_n+1, …, q_n+t} і програмою, що виходить наступним чином. У всіх командах з Θ₂ що містять символ q₀, залишаємо незмінними, а всі останні стани на , змінюємо відповідно на q_n+i. Сукупність усіх так отриманих команд утворює програму машини-композиції Θ.

Введене поняття є зручним інструментом для конструювання машин Т'юринга. Покажемо це на прикладі.

Приклад6. Сконструюємо машини Т'юринга, правильно обчислюючі функції-проектори .

Розглянемо спочатку конкретний випадок n = 3, m = 2, тобто функцію . Ми повинні переробити слово в слово . Будемо застосовувати до початкової конфігурації послідовно сконструйовані раніше машини Т'юринга Б+, В, Б^-, О:

Таким чином, функція обчислюється слідуючою композицією машинБ⁺ВБ⁺ОБ^-ОБ^- = Б⁺ВБ⁺(ОБ^-)².

Перевірте самостійно, що функція обчислюється композицією Б⁺ВОБ^-.

Т епер ми можемо уявити собі алгоритм побудови композиції машинБ⁺, В, Б^-, О для обчислення будь-якої функції виду . За допомогою правого зрушення Б+, застосувавши його т-1 раз, треба спочатку досягти масиву :

П отім, рухаючись вліво, транспонувати (за допомогою В) масив з кожним сусіднім ліворуч масивом, поки масив не вийде на перше місце:

Тепер треба дійти до крайнього правого масиву за допомогою (n - 1) -кратного застосування правого зрушення Б+:

Нарешті, треба стирати послідовно справа наліво усі масиви одиниць, окрім першого:

Отже, цю функцію (правильно) обчислює наступна машина Т'юринга:(Б⁺)^m-1 (В ∙ Б^-)^m-1(Б⁺)^n-1(О∙ Б^-)^n-1.

При n = 3, m = 2 така машина має вигляд:

Б⁺ВБ^-(Б⁺)²(ОБ^-)²= Б⁺ВБ⁺(ОБ^-)²

тобто співпадає з побудованою вище машиною. При n = 2, m = 2 ця машина має вигляд:Б⁺(ВБ^-)Б⁺(ОБ^-) = Б⁺ВОБ^-, тобто також співпадає з відповідною розглянутою вище машиною Т'юринга.

Приклад7.Побудуйте машину Т'юринга, що переводить слово 01^x01^y01^z0 в слово 01^z01^x01^y0, причому в початковому положенні оглядається комірка з 0 між наборами з у і z одиниць, а в кінцевому положенні оглядається комірка з 0 між наборами з z і х одиниць. (Ця машина називається "Циклічне зрушення" і позначається Ц.)

Рішення. Перевіримо, що таке переведення станеться в результаті послідовного застосування (композиції) раніше побудованих машин В, Б^- і В.

Обчислюємо:

01^x01^yq₁01^z0

В: 01^x01^zq01^y0

Б^-: 01^xq01^z01^y0

B: 01^zq₀01^x01^y0.

Тобто Ц = ВБ^-В

Приклад8.Побудуйте машину Т'юринга, що переробляє слово 01^x01^y в слово 01^x01^y01^x01^y, причому в початковому положенні оглядається найлівіша комірка, а в кінцевому - комірка, в якій записаний 0, який знаходиться між масивами 1^x01^y і 1^x01^y. (Машина називається "копіювання" і позначається К₂.)

Рішення. Перевіримо, що таке переведення станеться в результаті послідовного застосування (композиції) раніше побудованих машин.

q₁01^x01^y 01^xq₀01^y01^x01^y

Обчислюємо:

q₁01^x01^y

Б⁺: 01^xq01^y

Г : 01^xq01^y01^y0

Б^-: q01^x01^y01^y0

Г : q01^x01^x01^y01^y0

Б⁺: 01^xq01^x01^y01^y0

Б⁺: 01^x01^xq01^y01^y0

В : 01^x01^yq01^x01^y0

Б^-: 01^xq01^y01^x01^y0

К₂ = Б⁺ГБ^-Г(Б⁺)²ВБ^-.