Теорія Машина Тьюринга та алгоритми Маркова
Московський державний університет ім. М.В. Ломоносова
Факультет обчислювальної математики та кібернетики
В.М. Пильщиков, В.Г. Абрамов, А.А. Виліток, І.В. Гаряча
Машина Тьюринга та алгоритми Маркова. Вирішення задач
УДК 681.325.5 ББК 22.18
Пильщиков В.М., Абрамов В.Г., Виліток А.А., Гаряча І.В. Машина Тьюринга та алгоритми Маркова. Вирішення задач. посібник) - М.: МДУ, 2006. - 47 с.
Видавничий відділ факультету ВМК МДУ (ліцензія ЛР №040777 від 23.07.96)
Посібник присвячений розв'язанню задач на тему «Вступ до теорії алгоритмів», що вивчається на першому курсі факультету ВМК МДУ в рамках дисципліни «Алгоритми та алгоритмічні мови». Це завдання складання алгоритмів як машини Тьюринга і нормальних алгоритмів Маркова, і навіть завдання теоретичного характеру.
У посібнику наводяться необхідні відомості з теорії алгоритмів, докладно пояснюються типові прийоми розв'язання задач та пропонується великий набір задач для самостійного розв'язання.
Посібник розрахований на студентів першого курсу факультету ВМК МДУ та викладачів, які ведуть семінарські заняття з програмування.
доцент Баула В.Г. доцент Корухова Л.С.
Друкується за рішенням ради факультету обчислювальної математики та кібернетики МДУ ім. М.В. Ломоносова.
МДУ ім. М.В. Ломоносова, 2006
1. Машина Тьюринга
У розділі розглядаються завдання складання алгоритмів для машини Тьюринга. Наводиться короткий опис цієї машини, на прикладах пояснюються основні прийоми складання таких алгоритмів та пропонуються завдання для самостійного вирішення.
1.1 Короткий опис машини Тюрінга
Структура машини Тюрінга
Машина Тьюринга (МТ) складається з двох частин – стрічки та автомата (див.зліва):
Стрічка використовується для зберігання інформації. Вона нескінченна в обидві сторони і розбита на клітини, які не нумеруються і називаються. У кожній клітині може бути записано один символ або нічого не записано. Вміст клітини може змінюватися - в неї можна записати інший символ або стерти символ, що знаходиться там.
Домовимося порожній вміст клітини називати символом «порожньо» і позначати знаком Λ («лямбда»). У зв'язку з цим зображення стрічки, показане на малюнку праворуч, таке саме, як і малюнку зліва. Ця угода зручна тим, що операцію стирання символу в деякій клітці можна розглядати як запис в цю клітину символу Λ, тому замість довгої фрази «записати символ у клітку або стерти символ, що там знаходиться» можна говорити просто «записати символ у клітку».
Автомат – це активна частина МТ. У кожний момент він розміщується під однією з клітин стрічки та бачить її вміст; це видима клітина, а символ, що знаходиться в ній, – видимий символ; вміст сусідніх та інших клітин автомат не бачить. Крім того, в кожний момент автомат знаходиться в одному з станів, які позначатимемо літерою q з номерами: q1, q2 і т.п. Перебуваючи в деякому стані, автомат виконує певну операцію (наприклад, переміщається направо по стрічці, замінюючи всі символи b на a), перебуваючи в іншому стані - іншу операцію.
Пару з видимого символу ( S ) та поточного стану автомата ( q ) називатимемо конфігурацією і позначатим S , q >.
Автомат може виконувати три елементарні дії: 1) записувати у видиму клітинку новий символ (міняти вміст інших клітин автомат не може); 2) зрушуватися на одну клітинку вліво або вправо («перестрибувати» відразу через кілька клітин автомат не може); 3) переходити у новий стан.Нічого іншого робити автомат не вміє, тому все складніші операції так чи інакше повинні бути зведені до цих трьох елементарних дій.
Такт роботи машини Тюрінга
МТ працює тактами, які виконуються один за одним. На кожному такті автомат МТ виконує три наступні дії, причому обов'язково у вказаному порядку:
1) записує деякий символ S′ у видиму клітину (зокрема, може бути записаний той самий символ, що й був у ній, тоді вміст цієї клітини не змінюється);
2) зсувається однією клітину вліво (позначення – L , від left ), або одну клітину вправо (позначення – R , від right ), або залишається нерухомим (позначення – N ).
3) переходить у деякий стан q′ (зокрема, може залишитися у колишньому стані).
Формально дії одного такту записуватимемо у вигляді трійки:
S ', [L, R, N], q'
де конструкція з квадратними дужками означає можливість запису тут будь-якої з літер L , R чи N . Наприклад, такт *, L , q8 означає запис символу * у видиму клітину, зрушення однією клітину вліво і перехід у стан q8 .
Програма для машини Тюрінга
Сама собою МТ нічого не робить. Для того, щоб змусити її працювати, треба написати для неї програму. Ця програма записується у вигляді наступної таблиці: