Лекція 3 Машини т’юрінга Основні поняття

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

Це було зроблено в 1936-1937 р. Постом і Тьюрінгом незалежно друг від друга й майже одночасно з роботами Черча й Кліні. Основна думка Поста й Тьюрінга полягала в тім, що алгоритмічні процеси-це процеси, які може робити відповідно улаштована «машина». Відповідно до цього ними за допомогою точних математичних термінів були описані досить вузькі класи машин. На цих машинах виявилося можливим здійснити або імітувати всі алгоритмічні процеси, які фактично коли-небудь, описувалися математиками.

Машини, уведені Постом і Тьюрінгом, відрізнялися не дуже істотно й надалі сталі називатися машинами Тьюрінга. Розглянемо алгоритмічні системи, представлені цими машинами.

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

1) інформаційної стрічки, що представляє собою нескінченну (необмежену) пам'ять машини. Як інформаційна стрічка може служити магнітна або паперова нескінченна стрічка, розділена на окремі комірки. У кожному комірку можна помістити лише один символ, у тому числі й нуль;

2. « голівки, щозчитує,» - спеціального чутливого елемента, здатного обслідувати вміст комірок. Уздовж голівки інформаційна стрічка переміщається в обидва боки так, щоб у кожен розглянутий момент часу голівка перебувала в одній певній комірці стрічки;

3. керуючого пристрою, що у кожен розглянутий момент перебуває в деякому «стані». Передбачається, що пристрій керування машини може перебувати в деякому кінцевому числі станів. Стан пристрою керування часто називають внутрішнім станом машини. Один із цих станів називається заключним й у роботі машини відіграє особливу роль, тому що воно управляє закінченням роботи машини.

Схематично машина представлена на мал. 4.

Розглянемо тепер алгоритмічну систему, запропоновану Постом.

В алгоритмічній системі Поста інформація представляється у двійковому алфавіті А = {1,0}.

Таким чином, у кожному комірці інформаційної стрічки можна помістити або 0, або 1. Алгоритм представляється у вигляді кінцевого впорядкованого набору правил, називаемих на казами. Робота алгоритму починається з деякої початкової комірки, що відповідає першому наказу алгоритма. Складаючі алгоритм накази можуть належати до одному з 6 наказів, виконуваних пристроєм керування машини Поста:

1. Записати в розглянутий комірку 1 і перейти до i-го наказу.

2. Записати в розглянутий комірку 0 і перейти до i-го наказу.

3. Зрушити стрічку вправо на одну комірку і приступити до виконання i-го наказу.

4. Зрушити стрічку вліво на одну комірку і перейти до виконання i-го наказу.

5. Якщо в розглянутій комірці записана 1, то перейти до виконання j-го наказу, а якщо записано 0, то перейти до виконання i-го наказу.

6. Закінчення роботи алгоритму, зупинка.

Таким чином, алгоритмічна система Поста являє собою машину з інформаційною стрічкою, що містить у кожній комірці або 0, або 1; зі стрічкою, що переміщається вліво й вправо уздовж голівки; із пристроєм керування, що виконує 6 наказів (із внутрішніми станами).

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

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

Цей список операцій можна розширити. Машина Тьюрінга називається стандартною, якщо вона при зсуві стрічки може попередньо змінювати стан сприймаючої комірці.

Надалі будемо розглядати тільки стандартні машини Тьюрінга.

Нехай алфавіт машини Тьюрінга заданий у вигляді множини А = {s₀, s₁,..., s_n}, де s₀ відповідає порожній комірці, а число станів пристрою керування задано у вигляді множини Q = {q_o, q₁, ..., q_m}_t де q₀ відповідає заключному стану.

Кінцева сукупність символів алфавіту, з якої працює машина, називається зовнішнім алфавітом, кінцева сукупність станів пристрою керування -внутрішнім алфавітом.

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

Конфигурація задаеться у вигляді слова, що описує конкретний стан машини.

Рис.5

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

… s₀s_j1s_j2 … q_is_jk …s_jrs₀ … , (6)

де s₀ — символ, що позначає порожню комірку;

r — число заповнених комірок на стрічці;

Sj₁ — стан першої ліворуч непустої комірці;

Sjk — стан комірці, що переглядається в цей момент часу;

q_i — стан пристрою керування.

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

Якщо стандартна машина Тьюрінга, перебуваючи в стані q_i і сприймаючи записаний на стрічці символ S_k, переходить у новий стан q_j здійснюючи при цьому заміну символу в розглянутій комірці на символ s_m і зсув стрічки вліво на одну комірку, то говорять, що машина виконує команду q_is_k→q_js_mЛ. Якщо заміни символу не відбувається, s_m може бути відсутньою в команді.

При маніпуляціях зі стрічками приймемо наступні позначення:

Л - рух стрічки вліво;

П - рух стрічки вправо;

С - немає руху стрічки.

Звичайно команди стандартної машини Тьюринга задаються набором п'ятірок символів виду q_is_kq_is_m Л, тобто стрілка опускається, або виду

q_is_k→q_js_mЛ (7)

Розглянемо приклад машини Тьюрінга з алфавітами А = {0, 1},

Q = { q₀, q₁ } і командами q₁1q₁1Л, q₁0q₀1C.

Нехай на стрічці є слово 11100. Голівка стоїть над першою ліворуч одиницею. У результаті роботи машини Тьюрінга це слово перетворюється в 11110. По закінченні роботи машини голівка стоїть над крайньою правою одиницею.

Стандартна машина Тьюрінга із зовнішнім алфавітом А = {0, 1} називається нестираючою, якщо вона здатна виконувати лише команди виду

q_α0→q_βa;

(8)

q_α1→q_β1T,

де а = {0, 1}, Т = {З, Л, П}, тобто якщо вона може вписати 1 у порожню комірку, але не може видалити символ 1, якщо він вжевписаний в комірку.

Сукупность всіх команд, які може виконувати машина, називається її програмою.

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

Нехай машина Тьюрінга задана зовнішнім алфавітом А = {s°, а, b, з, d), внутрішнім алфавітом Q = {q₀, q₁, q₂, q₃, q₄, q₅) і сукупністю команд q₀aq₁aЛ, q₀bq₀bЛ, q₂aq₅dП, q₀cq₀cЛ, q₁dq₂cП, q₃aq₄dП, q₄bq₂cП. Порожню комірку позначає символ s⁰, а заключний стан — q₅.

Розглянемо застосування даної машини Тьюрінга для переробки первинного слова bcadc, що дасть нам слово bcdcc. Початкова конфігурація має вигляд q₀bcadc, при цьому машиною буде породжена наступна послідовність конфігурацій:

I крок bq₀cadc результат

виконання

команди (q₀b→q₀bЛ)

2. крок bcq₀adc те ж (q₀c→q₀cЛ)

3. крок bcaq₁dc „ (q₀a→ q₁aЛ)

IV крок bcq₂acc результат

виконання

команди (q₁d→q₂сП)

V крок bq₅cdcc „ (q₂a→q₅dП)

Програма розглянутої машини Тьюрінга може бути представлена у вигляді таблиці відповідності:

Запис алгоритму, реалізованого машиною Тьюрінга, виробляється за допомогою програми роботи цієї машини, що представляє собою сукупність команд. У розглянутому прикладі алгоритм переробки вхідного слова bcadc у слово bcdcc представляється командами q₀bq₀bЛ, q₀cq₀cЛ, q₀aq₁aJI, q₁dq₂cП, q₂aq₅dП.

Алгоритми пишуться стовпчиками. Для контролю проти деяких команд указується слово, у яке переходить спочатку задане слово після виконання всіх попередніх команд, включаючи й команду ліворуч.

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

Початкова конфігурація машини має вигляд q₁0010, кінцева конфігурація машини повинна мати вигляд q₀0100. Таким чином, q₀ — заключний стан машини Тьюрінга. Алгоритм буде мати такий вигляд:

Команди Конфігурації

q₁0q₂Л 0q₂010

q₂0q₃1C 0q₃110

q₃1q₃ Л 01q₃10→011q₃0

q₃0q₄ П 01q₄10

q₄1q₅0C 01q₅00

q₅0q₆ П 0q₆100

q₆1q₆ П q₆0100

q₆0q₀0C q₀0100

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

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

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

Машини Т'юрінга із двома виходами

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

Виявляється, що якщо задані дві машини Т'юрінга T₁ й T₂, які допускають непересічні множини слів X₁ і Х₂ відповідно, то завжди можна побудувати машину Т'юрінга Т₃ із двома виходами, що буде допускати X₁ і забороняти Х₂. Ці машини Т'юрінга будуть нам корисні при розгляді питання про можливість розв'язання.

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