Багатострічна машина т'юрінга

Схема багатострічної машини Т'юрінга представлена на Рис. 6. Вона складається з деякого кінцевого числа стрічок, розбитих на комірки. У кожній комірці може перебувати один із символів зовнішнього алфавіту А = {s₀, s₁, ..., s_n}. Комірки із символом s₀ будуть уважатися порожніми. Пристрій керування машини в кожен момент часу перебуває в одному з кінцевої множини станів Q = {q₀, q₁, ...,q_m}. Стан q₀ уважається заключним станом машини.

П рипустимо, що в кожен момент часу машина «обдивляється» одну комірку кожної стрічки.

Конфігурація машини вважається заданою, якщо відомо стан пристрою керування q, стану всіх комірок всіх стрічок і зазначені комірки, сприймані машиною. Для k-стрічкової машини конфігурація її в i-й момент часу описується системою k-слів виду:

s_i11 ... s_i1eq_is_i1e+1 ... S_i1t;

……………...... (9)

S_ikl ... S_ikeq_iS_{ike + 1} ... S_ikv.

по одному слову для кожної стрічки перший індекс відповідає моменту часу, другий-номеру стрічки, третій - номеру комірки на стрічці, рахуючи з ліва на право.

Залежно від внутрішнього стану пристрою керування q_i умісту комірок, що оглядаються у даний момент_{, Si}1e+1 ... S_ike+1 машина переходить у наступний стан за допомогою таких дій:

1. стан кожної сприйманої комірки заміняється новим станом (який може збігатися зі старим);

2. кожна стрічка пересувається на одну комірку вправо, уліво або залишається нерухомої;

3. внутрішній стан пристрою керування q_i переводиться в новий стан q_j (який може збігатися зі старим).

Уважається, що якщо пристрій керування в якийсь момент приходить у заключний стан q₀, то машина зупиняється й у наступні моменти часу конфігурація машини не міняється.

Говорять, що машина виконує команду

q_is_α1... s_αk →q_js_β1T₁ … s_βkT_k, Т = {Л, З, П}, (10)

якщо, перебуваючи в стані q_i і сприймаючи комірки із символами s_α1... s_αk, машина переходить у стан q_j, заміняючи вміст комірок відповідно символами s_β1... s_βk. Після цього стрічки відповідно зрушуються в напрямках Т₁ ... T_k.

Задати програму багатострічкової машини Т'юрінга - це значить для кожного слова

q_is_α1... s_ak(i=1, …, m; α1, …, αk=0,1, …, n)

задати яку-небудь команду виду (10). Таким чином, k-стрічкова машина Т'юрінга визначає алгоритм для переробки слів виду (9).

Помітимо, що вичислимість на багатострічковій машині Т'юрінга частково рекурсивних функцій є прямий наслідок вичислимості цих функцій на однострічковій машині.

Універсальна машина т'юрінга

Дотепер ми дотримувалися тієї точки зору, що різні алгоритми здійснюються на різних машинах Т'юрінга, що відрізняються набором команд, внутрішнім і зовнішнім алфавітами. Однак можна побудувати універсальну машину Т'юрінга, здатну у відомому змісті виконувати будь-який алгоритм, а виходить, здатну виконувати роботу будь-якої машини Т'юрінга.

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

Це досягається шляхом кодування конфігурації й програми будь-якої даної машини Т'юрінга в символах вхідного (зовнішнього) алфавіту універсальної машини. Саме кодування повинне виконуватися в такий спосіб:

1. різні букви повинні замінятися різними кодовими групами, але та сама буква повинна замінятися всюди, де б вона не зустрічалася, однієї й тією же кодовою групою;

2. рядки кодових записів повинні однозначним образом розбиватися на окремі кодові групи;

3. повинна мати місце можливість розпізнати, які кодові групи відповідають різним зсувам, тобто кожної з букв Л, П, С окремо, і розрізняти кодові групи, що відповідають буквам внутрішнього алфавіту й буквам зовнішнього алфавіту.

Розглянемо приклад такого кодування для машини Т'юрінга Т, що має зовнішній алфавіт А = {s₁, s₂, ..., S_k} і внутрішній алфавіт Q = {q₁, q₂, ..., q_m}.

Якщо зовнішній алфавіт універсальної машини Т'юрінга складається із символів А = {0, 1}, то ці умови будуть напевно дотримані при наступному способі кодування.

1. В якості кодових групи беруться 3 + k + т різних слів виду 100 ... 01 (між одиницями — суцільно нулі), де k — число символів зовнішнього алфавіту;

т - число станів пристрою керування.

Тоді розбивка рядків на кодові групи провадиться однозначним шляхом виділення послідовностей нулів, укладених між двома одиницями.

2. Зіставлення кодових груп вихідним символам зовнішнього й внутрішнього алфавітів здійснюється відповідно до наступної таблиці кодування:

	Буква	Кодова група
	Л С П	101 1001 10001

Зовнішній алфавіт Парне число нулів, більше чим 2

Зовнішній алфавіт Парне число нулів, більше чим 2

Так, наприклад, для машини Т'юрінга, що переробляє слова bcadc у слово bcdcc, вхідне слово в універсальній машині Т'юрінга з даним кодом буде представлено наступним рядком: 10000001 1000000001 100001 100000000001 1000000001, де 100001 —a, 10000001 — b, 1000000001 — з, 100000000001 — d. Програма ж буде представлена наступними рядками:

1000001 10000001 1000001 10000001 101 (q₀bq₀bЛ)

1000001 1000000001 1000001 1000000001 101 (q₀Cq₀cJl)

1000001 100001 100000001 100001 101 {q₀aq₁aЛ)

100000001 100000000001 10000000001 1000000001 10001 (q₁d₂q₂cП)

10000000001 100001 100000000000001 100000000001 10001 (d₂aq₃dП)

При кодуванні програм, конфігурацій і вхідних слів замість нулів й одиниць можна брати будь-які інші два символи, наприклад а й b.

Таким чином, якщо яка-небудь машина Т'юрінга Т вирішує деяке завдання, то й універсальна машина Т'юрінга здатна вирішити це завдання за умови, що крім кодів початкових даних цього завдання на її стрічку буде поданий код програми машини Т. Задаючи універсальній машині Т'юрінга Т_и зображення програми будь-якої даної машини Т'юрінга Т_п і зображення будь-якого її вхідного слова Хn, одержимо зображення вихідного слова у_п, у яке машина Т_п переводить слово хп.

Якщо ж алгоритм, реалізований машиною Т_п, не застосовний до слова х_п, то алгоритм, реалізований універсальною машиною Т_и, також не застосовний до слова, утвореному із зображення х_п і програми машини Тп.

Таким чином, машина Т'юрінга Т_п може розглядатися як одна із програм для універсальної машини Т_и.

У зв'язку з існуванням універсальної т'юрингової машини таблиці відповідності, що описують різні стани пристрою керування машини, мають двояке призначення:

1)для опису станів пристрою керування спеціальної машини Т'юрінга, що реалізує відповідний алгоритм;

2) для опису програми, що подається на стрічку універсальної машини Т'юрінга, при реалізації відповідного алгоритму.

Сучасні електронні обчислювальні машини будуються як універсальні; у запам'ятовувальний пристрій поряд з вихідними даними поставленого завдання уводиться також і програма її рішення.

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

Для порівняння структур різних машин й оцінки їхньої складності необхідно мати відповідну міру величини або складності машин. Шеннон запропонував розглядати як таку міру добуток числа символів і числа станів. Таким чином, «складність» машини Т'юрінга дорівнює добутку числа символів зовнішнього алфавіту на число внутрішніх станів, відмінних від заключного. Значний інтерес викликало завдання побудови універсальних машин Т'юрінга мінімальної складності.

До початку 1963 р. останніми результатами в цьому напрямку були теорема Ватанабе про існування універсальної машини з 5-ю символами й 6-ю станами, теорема Мінського про існування машини з 4-мя символами й 7-ю станами й теорема Тригера про існування універсальної машини з 4-мя символами й 6-ю станами.