Практична робота 

Тема: Структура та правила виконання машини Тьюринга.

Ціль: Вивчити і отримати практичні навики з формального представлення алгоритму у вигляді машини Тьюринга. Час: 2 год.

 1 Виконання роботи

1)    Вивчити теоретичні відомості.

2)    Проробити практичну частину.

2 Теоретичні відомості

Структура  машини Тьюринга.

Машина Тьюринга (МТ) – абстрактна машина, яка складається з двох частин стрічки та пристрою керування (каретки).

Каретка:

Стрічка:  

Рисунок 1 - Машина Тьюринга

Стрічка використовується для збереження інформації. Стрічка нескінченна та складається з секцій однакового розміру. В кожній секції стрічки може бути записаний один символ або нічого не записано. Зміст секції може змінюватися – в неї може бути записаний інший символ або знищений існуючий там символ. Каретка – це активна частина МТ. В кожен момент часу вона розміщується під однією з секцій і бачить її зміст – це оглядова секція, а символ в секції – оглядовий символ, зміст інших секцій каретка не бачить. Крім того в кожний момент часу каретка знаходиться в одному стані, який будемо позначати буквою q з номерами q₁, q₂ і т.д.

Пару з оглядового символу (S) та поточного стану q будемо називати

Машина Тьюринга може виконувати три елементарні дії: 

1)    Записувати в оглядову секцію новий символ;

2)    Зміщуватися       на      одну секцію        ліворуч       або    праворуч

(переміщуватися зразу на декілька секцій неможливо); 3) Переходити у новий стан.

МТ працює тактами, які виконуються один за другим. На кожному такі МТ, виконує наступні три дії в строгій послідовності:

1)    Записує деякий символ S в оглядову секцію (може бути записаний той самий символ, тоді  стан цієї секції не

змінюється);

2)    Зміщується на один символ ліворуч (позначимо), або на один символ праворуч (позначимо  ). 3)Переходить в деякий стан q.

Формально дію одного такту будемо записувати так:   

Приклад: 

Такт  означає запис символу b в оглядову секцію, зміщення ліворуч на одну секцію та перехід в стан q2.

Програма МТ.  Програма записується у вигляді наступної таблиці:

Рисунок 2 - Програма МТ.

 Зверху записуються всі стани, в яких може  знаходитися каретка – зовнішній алфавіт, ліворуч – всі символи (в тому числі 0) – алфавіт внутрішніх станів, які каретка може оглядати на стрічки. На перетині  (в клітинках таблиці) вказують такт, який повинна виконувати каретка, коли вона знаходиться у відповідному стані і оглядає на стрічки відповідний символ. В цілому таблиця визначає дії МТ при всіх можливих конфігураціях.

Описати алгоритм у вигляді МТ – означає пред’явити таку таблицю.

Правила виконання МТ.

Перед виконанням програми потрібно зробити наступні попередні дії:

1)    Записати на стрічку вхідне слово, до якого буде застосована програма.

2)    Встановити каретку в стан q1 (вказано в таблиці першим), і розмістити її над першим символом слова.

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

Коли завершується виконання програми?  Заключний стан – це такт, який нічого не змінює: каретка записує в оглядаємо секцію той самий символ, не зміщується і залишається в цьому ж стані. Потрапив на заключний стан, МТ, зупиняється, завершає свою роботу.

Якщо потрібно записати, що після виконання такту МТ зупиняється, то в другій позиції цього такту будемо писати знак «!».

Приклад:  

3 Практична частина

 Задача 1

Є машина Тьюринга з зовнішнім алфавітом A={0,1}, алфавітом внутрішнього стану Q={q₀,q₁} і програмою: 

Визначити, в яке слово переробляє МТ кожне з наступних слів, якщо воно знаходиться в початковому стані  q₁ і оглядає вказану секцію:

1)    10110011 (оглядає секцію 4, рахуючи з ліва);

2)    11011101 (оглядає секцію 2);

3)    1111011 (оглядає секцію 4);

4)    1101111 (оглядає секцію 3).

Задача 2

Є машина Тьюринга з зовнішнім алфавітом A={0,1,*}, алфавітом внутрішнього стану Q={q₀,q₁} і програмою: 

Визначити, в яке слово переробляє МТ кожне з наступних слів:

1) 111*111;       4) *1111; 2) 1111*11;     5) 111*.

3)1*11;

Задача 3

Сконструювати машину Тьюринга з зовнішнім алфавітом A={a,b,c}, яка переносить перший символ в кінець непорожнього слова.

Для розв’язання цієї задачі запропонуємо виконати наступні дії:

1)    Запам’ятати перший символ слова, а потім його знищити;

2)    Змістити каретку праворуч до першої порожньої секції та записати символ, який запам’ятали.

Але як запам’ятати символ? Треба використати різні стани каретки. Якщо перший символ це – а, то переходимо до стану q1, в якому каретка біжить праворуч та записує у кінці символ а. Якщо перший символ це – b, то переходимо до стану q2, в якому каретка біжить праворуч та записує у кінці символ b. Якщо перший символ це – c, то переходимо до стану q3, в якому каретка біжить праворуч та записує у кінці символ c. 

Задача 4

Сконструювати машину Тьюринга з зовнішнім алфавітом A={a,b,c}, яка порівнює перший і останній символ не порожнього слова, якщо символи однакові, то слова залишається не змінним, а якщо символи різні, то слово знищує.

 Для розв’язання цієї задачі запропонуємо виконати наступні дії:

1)    Запам’ятати перший символ слова та не знищувати його;

2)    Змістити каретку до останнього символу та порівняти його з першим, якщо вони рівні, то зупинитися;

3)    В протилежному випадку знищити слово.

Задача 5

Сконструювати машину Тьюринга з зовнішнім алфавітом A={a,b}, яка видаляє другий символ в слові, якщо він є.

 Задача 6

Сконструювати машину Тьюринга з зовнішнім алфавітом A={a,b}, яка видаляє з слова перше входження a, якщо воно є.

4 Вимоги до оформлення звіту

Звіт повинен містити:

3)    назву та мету роботи;

4)    завдання на виконання задач, порядок виконання;

5)    результати виконаних дій.

5  Контрольні  питання

1)    МТ загальний опис.

2)    З яких елементарних дій складається команда МТ?

3)    Як позначається алфавіт внутрішнього стану?

4)    Що таке функціональна схема машини Тьюринга?

5)    Як описується машина Тьюрінга? Наведіть приклади схем машин Тьюринга.  

6)    Що називається композицією машин Тьюринга?  

7)    У чому полягає зміст теореми Тьюрінга?