Машина Тюрінга.
Введення поняття Машини Т’юрінга було однією з перших вдалих спроб дати точне з математичної точки зору визначення поняття алгоритму. Це поняття було назване на честь математика Т’юрінга, який у 1937 році сформулював дане поняття. Машина Т’юрінга є математичною, уявною машиною, а не фізичною. Машина Т’юрінга це такий самий математичний об’єкт як похідна, інтеграл, функція. Так як і інше математичне поняття, Машина Т’юрінга відображає об’єктивну реальність, моделює деякі реальні процеси. Машина Т’юрінга представляє собою систему, що працює в дискретні моменти часу t = 0,1,2… і складається з наступних частин:
1) Скінченної стрічки, що розбита на скінчену кількість комірок. При цьому в кожний момент часу t в комірках записані букви з деякого алфавіту , що називають зовнішнім алфавітом машини Т’юрінга. Комірка в якій записаний символ 0 називається пустою. В процесі роботи машини кожна комірка може змінювати свій стан, шляхом заміни приписаного до неї символа на інший символ . До існуючої комірки дозволяється прибудовувати необмежене число додаткових комірок, які початково вважаються пустими. Стрічка вважається направленою і її комірки будуть переглядатися зліва направо. Таким чином, якщо в деякий момент часу стрічка має r комірок, то стан стрічки повністю описується словом , де – це стан першої комірки, – стан другої комірки і так далі.
2) Управляюча каретка, що представляю собою пристрій, що переміщується вздовж стрічки так, що в кожен момент часу, що розглядається, вона знаходиться навпроти визначеної комірки і має деякий стан з множини станів Q ={ }. Множина називається множиною внутрішніх станів. Множини А і Q не перетинаються, їх перетин є пустою множиною.
Стан називається заключним, а стан – початковим, даний стан означає початок роботи машини.
3) Програми П, тобто сукупності виразів T(i , j), . Команда T(i , j) з якої будується програма, складається з команд трьох видів:
1)
2)
3)
Команда з початком спрацьовує, якщо машина М знаходиться в стані , а каретка оглядає символ . Тому в програмі повинна бути тільки одна команда з початком . Дії при виконанні вище зазначених команд наступні:
1) при виконанні даної команди машина Т’юрінга переходить до стану , одночасно змінюючи символ, який оглядається на . В командах даного типу символ С – означає, що далі буде оглядатися ця ж комірка.
2) при виконанні даної команди машина Т’юрінга переходить до стану , одночасно змінюючи символ, який оглядається на . В командах даного типу символ R – означає, що каретка переміщується на одну комірку праворуч.
3) при виконанні даної команди машина Т’юрінга переходить до стану , одночасно змінюючи символ, який оглядається на . В командах даного типу символ L – означає, що каретка переміщується на одну комірку ліворуч.
Зауваження: стани , можуть співпадати, і стани також.
Як працює машина Т’юринга?
Знаходячись в момент стану t в стані відмінному від машина здійснює крок, який повністю визначається її поточним станом і символом , який оглядає в даний момент каретка. При цьому зміст кроку регламентований командою : , де Х є {C, L, R}.
Крок полягає в тому, що:
1) Зміст комірки що оглядається в даний момент часу витирається і на його місце записується символ , який може співпадати з .
2) Машина переходить в новий стан , який може співпадати з .
3) Машина переходить до перегляду наступної комірки, що розміщується ліворуч, якщо X=L і до комірки, що розміщується праворуч, якщо X=R, та продовжує оглядати ту саму комірку якщо X=C.
В наступний момент часу t+1, якщо , машина виконує крок, що регламентований командою і т.д. Процедура переходу така ж сама.
Словом в алфавіті А або в алфавіті Q або в об’єднаному алфавіті називається будь-яка послідовність букв відповідного алфавіту. Під
к–ю конфігурацією будемо розуміти зображення стрічки машини з інформацією, що склалася на ній до початку к-го кроку з вказівкою комірки, яка оглядається на даному кроці і вказівкою стану, в якому знаходиться машина. Конфігурація називається заключною або кінцевою, якщо стан, в якому знаходиться машина є заключним. Робота машини Т’юрінга вважається закінченою, якщо досягається кінцева конфігурація, яка і є результом роботи машини.
Будемо вважати, що не пусте слово в алфавіті \ сприймається машиною в стандартному положенні. Якщо дане слово записане у послідовно розміщені комірки стрічки, всі інші комірки пусті і машина оглядає крайню комірку праворуч, в яких записане слово .
Стандартне положення називається початковим (кінцевим), якщо машина сприймає слово в стандартному положенні і знаходиться в початковому стані ( в стані зупинки ).
Приклад 1.
Задана машина Т’юринга із зовнішнім алфавітом (0 – символ пустої комірки), алфавітом внутрішніх станів і з наступною функціональною схемою (програмою):
.
Розглянемо в яке слово перетворює задана машина слово 101.
Робота машини починається з стандартного положення
Положення 1
Крок 1
Положення 2
Крок 2
Положення 3
Крок 3
Положення 4
Дана конфігурація є заключною, так як машина опинилась у стані зупинки .
Таким чином, вхідне слово 101 перероблено машиною в слово 10101.
Отриману послідовність конфігурацій можна записати більш коротким способом. Конфігурація (1) записується у вигляді наступного слова в алфавіті : ( зміст комірки, що оглядається, записується праворуч від стану, в якому знаходиться в даний момент машина).
Аналогічно, конфігурація (2): ; конфігурація (3): ;
конфігурація (4): . Вся послідовність записується наступним чином: .
Приклад 2.
Визначати послідовність команд, що визначає послідовність конфігурацій машини Т’юринга, яка переробляє слово 11011, виходячи з початкового положення, в якому в стані оглядається крайня ліва непуста комірка, в якій розміщений символ даного слова
(1)
(2)
(3)
(4)
(5)
(6)
(7)
Опис машини Т’юринга:
Зовнішній алфавіт (0-символ пустої комірки).
Алфавіт внутрішніх станів .
Програма П:
.
Біль короткий запис послідовності конфігурацій:
.
Приклад 3.
Машина Т’юринга задається зовнішнім алфавітом , (0 – символ пустої комірки). Алфавітом внутрішніх станів і програмою П;
,
.
Програма може бути записана також у вигляді наступної таблиці:
* |
Для того, щоб визначити дії машини в кожний конкретний момент часу, треба знайти в таблиці клітку, що знаходиться на перетині поточного стану машини (стовпчик ) і рядка, в якому міститься значення комірки, що оглядається в поточний момент часу ( ).
Застосуємо дану машину до слова 11*11.Вхідна конфігурація стандартна. Послідовність конфігурацій наступна:
.
Самостійно застосувати машину Т’юринга з прикладу 3 до наступних початкових конфігурацій: .
Дана машина Т’юринга реалізує операцію додавання. В результаті її роботи на стрічці записано послідовно стільки одиниць, скільки їх було записано послідовно по обидві сторони від знака “*” перед початком роботи машини.
Будемо казати, що слово переробляється машиною у слово , якщо від слова , яке сприймається в початковому стандартному положенні машина після виконання скінченного числа команд переходить до слова , що сприймається машиною в положенні зупинки.
Висновок 1:
Машина Т’юринга – це деяке правило (алгоритм) для перетворення слів з алфавіту .
Висновок 2:
Для визначення машини Т’юринга необхідно задати зовнішній та внутрішній алфавіти, програму, і вказати які з символів позначають пусту комірку та кінцевий (заключний) стан.
Дата добавления: 2015-10-13; просмотров: 3169;