Приклади створення програм для МТ

Розглянемо приклади створення програм для МТ, щоб продемонструвати деякі типові прийоми програмування на МТ.

Для скорочення формулювання умов задач введемо наступні позначення:

- буквою Р будемо позначати вхідне слово;

- буквою А будемо  позначати  зовнішній алфавіт,  тобто  набір  тих  символів, тільки з яких може складатись Р, однак, в проміжних і вихідних словах можуть з'являтись також і інші символи;

- будемо вважати, що в початковому положені  каретка вказує на перший зліва символ слова, що переробляється.

Приклад 1 (переміщення каретки, заміна символів)

Постановка задачі:

Нехай задано А={0,1,2,3,4,5,6,7,8,9} і непусте слово Р. Отже, Р - це послідовність із десяткових цифр, тобто запис невід'ємного цілого числа в десятковій системі числення.    Потрібно одержати на стрічці запис числа, яке буде на 1 більше числа Р.

Словесний опис алгоритму:

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

 1. Пересунути каретку під останню цифру числа.

 2. Якщо це цифра від 0 до 8, то замінити її на 1 більшою цифрою і зупинитися, наприклад:

 3. Якщо ж це цифра 9, тоді замінити її на 0 і перемістити каретку до попередньої цифри, після чого таким же способом збільшити на 1 цю передостанню цифру, наприклад:

 4. Особливий випадок: число Р складається тільки з дев'яток (наприклад, 99). Тоді каретка буде пересуватись вліво, замінюючи дев'ятки на нулі, і зрештою опиниться під порожньою коміркою. В цю порожню комірку треба записати 1 і зупинитись (відповіддю буде 100):

Алгоритм у вигляді програми для МТ:

У вигляді програми для МТ наведені вище дії описуються такою таблицею:

Q  A		0	1	2	3	4	5	6	7	8	9
q1
q2

Пояснення:

q₁ - це стан, у якому каретка «біжить» під останню цифру числа. Для цього він весь час рухається вправо, не міняючи цифри і залишаючись в тому ж стані. Але тут є одна особливість: коли каретка опинеться під останньою цифрою, то вона не може знати про це (оскільки вона не бачить, що записано в сусідніх комірках) і може визначити це лише тоді, коли потрапить на наступну порожню комірку. Тому, дійшовши до першої порожньої комірки, каретка має повернутись назад під останню цифру числа і перейти в стан q₂ (вправо рухатись вже не треба).

q₂ - це стан, у якому каретка додає 1 до тієї цифри, яку вона бачить в цей момент. Спочатку це остання цифра числа. Якщо це цифра з діапазону від 0 до 8, то каретка має замінити її на 1 більшою цифрою, і зупинитись. Але, якщо це цифра 9, то каретка має замінити її на 0 і переміститись вліво, залишаючись в стані q2. Тим самим, він буде додавати 1 до попередньої цифри. Якщо і ця цифра дорівнює 9, то каретка замінить її на 0 і переміститься вліво, залишаючись в стані q₂, тому що повинна далі виконувати такі самі дії - збільшувати на 1 видиму цифру. Якщо ж каретка перемістилась вліво, а у видимій комірці немає цифри (а є символ «порожньо»), ті вона має записати в цю комірку 1 і зупинитись.

Відзначимо, що для порожнього вхідного слова задача не визначена, тому на цьому слові МТ може поводитись як завгодно. У цій програмі, наприклад, при порожньому вхідному слові МТ зупиняється і видає відповідь 1.

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

Q       A

0

1

2

3

4

5

6

7

8

9

Пояснення

q1

R

R

R

R

R

R

R

R

R

R

під останню цифру

q2

видима цифра + 1

Саме так і будемо надалі записувати програми.

Приклад 2 (аналіз символів)

Постановка задачі:

А={a,b,c}. Перенести перший символ непустого слова Р у його кінець. Наприклад:

Словесний опис алгоритму:

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

1. Запам'ятати перший символ слова P, а потім стерти цей символ.

2. Перемістити каретку вправо під першу порожню комірку за P і записати в неї символ, який був запам'ятований.

Як «бігати» вправо, було розглянуто в попередньому прикладі. Питання, як запам'ятати перший символ, є складнішим. Адже в МТ немає іншого запам'ятовувального пристрою, крім стрічки, а запам'ятовувати символ у якійсь комірці на стрічці безглуздо, оскільки, як тільки каретка зрушиться вліво або вправо від цієї комірки, вона відразу забуде даний символ. Вихід з цієї ситуації може бути такий: треба використовувати різні стани каретки. Якщо перший символ - це символ a, то треба перейти в стан , у якому каретка переміщюється вправо і записує в кінці слова символ a. Якщо ж першим був символ b, тоді треба перейти в стан , де робиться все те ж саме, тільки в кінці записується символ b. Якщо ж першим був символ c, тоді треба перейти в стан , у якому каретка має дописати за вхідним словом символ c. Отже, те, яким був перший символ, фіксується переведенням каретки в різні стани.

Це типовий прийом запам'ятовування при програмуванні на МТ.

Алгоритм у вигляді програми для МТ:

У вигляді програми для МТ наведені вище дії описуються такою таблицею:

Q A	a0	a	b	c	Пояснення
q1	R				аналіз 1-го символу, видалення його, розгалуження
q2	R	R	R		запис a справа
q3	R	R	R		запис b справа
q4	R	R	R		запис c справа

Розглянемо поводження цієї програми на вхідних словах, що містять не більше одного символу. При порожньому вхідному слові, яке є «поганим» для цієї задачі, програма зациклиться - каретка, перебуваючи в стані q₁ і потрапляючи весь час на порожні комірки, буде нескінченно переміщатись вправо. Звичайно, в цьому випадку програму можна було б зупинити, але в цьому прикладі спеціально зроблено зациклення, щоб продемонструвати таку можливість.

Якщо ж у вхідному слові тільки один символ, тоді каретка зітре цей символ, переміститься на одну комірку вправо і запише в неї цей символ:

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

Приклад 3 (порівняння символів, стирання слова)

Постановка задачі:

А={a,b,c}. Якщо перший і останній символи непорожнього слова Р однакові, то це слово не міняти, інакше замінити його на порожнє слово.

Словесний опис алгоритму:

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

 1. Запам'ятати перший символ вхідного слова, не стираючи його.

 2. Перемістити каретку під останній символ і порівняти його із символом, який запам'ятали.

Якщо вони рівні, то більше нічого не робити.

 3. У противному випадку знищити все вхідне слово.

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

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

Алгоритм у вигляді програми для МТ:

У вигляді програми для МТ наведені вище дії описуються такою таблицею:

Q A	a0	a	b	c	Пояснення
q1					аналіз 1-го символу, розгалуження
q2		R	R	R	йти до останнього символу при 1-му символі a
q3					порівняти останній символ з a, якщо не рівні - на q8
q4		R	R	R	аналогічно при 1-му символі b
q5
q6		R	R	R	аналогічно при 1-му символі c
q7
q8					стерти все слово, рухаючись справа наліво

Приклад 4 (видалення символу зі слова)

Постановка задачі:

А={a,b}. Видалити зі слова Р його другий символ, якщо такий є.

Словесний опис алгоритму:

Для розв'язання цієї задачі потрібно перемістити каретку під комірку із другим символом і потім очистити цю комірку:

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

Алгоритм у вигляді програми для МТ:

У вигляді програми для МТ наведені вище дії описуються такою таблицею:

Q A	a0	a	b	Пояснення
q1				аналіз і видалення 1-го символу, розгалуження
q2				заміна 2-го символу на a
q3				заміна 2-го символу на b

Приклад 5 (стиснення слова)

Постановка задачі:

А={a,b,c}. Видалити зі слова Р перше входження символу a, якщо таке є.

Словесний опис алгоритму:

У попередньому прикладі було перенесено на одну позицію вправо тільки один симвіл. У цьому прикладі потрібно в циклі переносити вправо всі початкові символи b і c вхідного слова, до першого символу a або до порожньої комірки:

Постає питання, як перенести символ x з лівої комірки в чергову комірку, де перебуває деякий символ y, щоб потім цей символ y можна було перенести в праву комірку? Якщо через  позначити стан, у якому в комірку треба записати символ x, який перебував раніше в комірці зліва, тоді цю дію можна зобразити так:

Для цього потрібно виконати такт , у якому об'єднані наступні три дії:

- по-перше, в комірку записується символ x, взятий із комірки зліва;

- по-друге, каретка переміщується вправо (під комірку, в яку потім треба буде записати тільки що замінений символ y);

- по-третє, каретка переходить в стан , у якому вона і буде виконувати цей запис.    

Повторення таких тактів у циклі і приведе до переміщення вправо на одну позицію початкових символів вхідного слова. Цей цикл повинен закінчитись, коли в черговій комірці виявиться символ a або  (y=a або y= ), а на початку циклу можна вважати, що на місце першого символу зліва переноситься символ «порожньо» (x= ).

Алгоритм у вигляді програми для МТ:

У вигляді програми для МТ наведені вище дії описуються такою таблицею:

Q A	a0	a	b	c	Пояснення
q1					: стерти 1-й символ і перенести його вправо
q2			RR		: запис b, перенос символу, що був в цій комірці раніше, вправо
q3				R	: запис с, перенос символу, що був в цій комірці раніше, вправо

В цій програмі варто звернути увагу на такт , що виконується коли першим символом вхідного слова є a. Треба просто стерти цей символ і зупинитися. Однак у цьому такті зазначене ще й переміщення, оскільки, в момент останова каретка повинна перебувати під вихідним словом (під будь-яким його символом), тому і потрібно перемістити каретку з порожньої комірки на комірку з першим символом вихідного слова.

Приклад 6 (вставка символу в слово)

Постановка задачі:

А={a,b,c}. Якщо Р – непорожнє слово, то за його першим символом вставити символ a.

Словесний опис алгоритму:

Між першим і другим символами слова Р треба звільнити комірку для нового символу a. Для цього треба перенести на одну позицію вліво перший символ (на старому місці його можна поки не видаляти), а потім, повернувшись на старе місце, записати символ a:

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

Алгоритм у вигляді програми для МТ:

У вигляді програми для МТ наведені вище дії описуються такою таблицею:

Q A	a0	a	b	c	Пояснення
q1					аналіз 1-го символу для переносу його вліво
q2					записати a зліва
q3					записати b зліва
q4					записати c зліва
q5					замінити колишній 1-й символ на a

Приклад 7 (розсунення слова)

Постановка задачі:

А={a,b,c}. Вставити в слово P символ a за першим входженням символу c, якщо таке є.

Словесний опис алгоритму:

Переглядаємо вхідне слово зліва направо до порожньої комірки або до першого символу c. В першому випадку символ c не входить в слово P, тому нічого не робимо. В іншому випадку треба звільнити місце для символу а, що вставляється. Для цього переміщаємо початок слова P (від знайденого символу c до першого символу) на одну позицію вліво. Крім того, щоб потім не вертатись до позиції, що звільнилась, починаємо це переміщення з запису символу a замість знайденого символу c. Циклічне переміщення вліво реалізується аналогічно циклічному переміщенню вправо із приклада 5.

Алгоритм у вигляді програми для МТ:

У вигляді програми для МТ наведені вище дії описуються такою таблицею:

Q A	a0	a	b	c	Пояснення
q1		RR	RR		вправо до с, вставка a замість c, переміщення c вліво
q2		L			переміщення a
q3			L		переміщення b
q4				L	переміщення c

Приклад 8 (формування слова на новому місці)

Постановка задачі:

А={a,b,c}. Видалити з P всі входження символу a.

Словесний опис алгоритму:

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

Потрібно виконати наступні дії:

 1. Вихідне слово будемо будувати справа від вхідного. Щоб розмежувати ці слова, відокремимо їх деяким допоміжним символом, відмінним від всіх символів алфавіту A, наприклад знаком = (крок 1). Нагадаємо, що на стрічці можуть бути записані не тільки символи з алфавіту вхідного слова, а й, за потребою, інші символи.

 2. Після цього повертаємось до початку вхідного слова (крок 2).

 3. Далі потрібно перенести в циклі всі символи вхідного слова, крім символу a, вправо за знак = , тобто будемо формувати вихідне слово.    

Для цього аналізуємо перший символ вхідного слова. Якщо це символ a, тоді стираємо його і переходимо до наступного символу (крок 3). Якщо ж перший символ - це b або c, тоді стираємо його і «біжимо» вправо до першої порожньої комірки (крок 4), куди й записуємо цей символ (крок 5).

Далі знову повертаємось до того символу, що став першим у вхідному слові, і повторюємо ті ж самі дії, але вже стосовно цього символу (кроки 6-9).

 4. Цей цикл завершиться тоді, коли при поверненні до початкового символу виявиться в якості першого символу знак =. Це ознака того, що повністю переглянуто вхідне слово і перенесені всі його символи, відмінні від a, у вихідне слово. Залишилось стерти знак =, переміститись вправо під вихідне слово і зупинитись (крок 10).

Алгоритм у вигляді програми для МТ:

Нагадаємо, що крім символів a, b і c у процесі розв'язання задачі на стрічці з'явився новий знак =, тому в таблиці повинен бути передбачений стовпець для цього знаку.

У вигляді програми для МТ наведені вище дії описуються такою таблицею:

Q A	a0	a	b	c	=	Пояснення
q1		R	R	R		записати справа знак =
q2		L	L	L	L	переміститись наліво до 1-го символу слова
q3						аналіз і видалення його, розгалуження
q4		R	R	R	R	запис b справа, повернення наліво
q5		R	R	R	R	запис c справа, повернення наліво

Приклад 9 (фіксування місця на стрічці)

Постановка задачі:

А={a,b}. Подвоїти слово P, поставивши між ним і його копією знак =.

Наприклад:

Словесний опис алгоритму:

Ця задача вирішується аналогічно попередньої: в кінець вхідного слова записуємо знак = (крок 1), потім повертаємось до початку слова (крок 2) і у циклі всі його символи (у тому числі і символ a) копіюємо в порожні комірки справа:

Однак є й відмінність: символи вхідного слова, які копіюються, не видаляються. Це призводить до наступної проблеми. Записавши справа копію чергового символу, потрібно повернутись до вхідного слова в позицію цього символу і потім переміститись вправо до наступного символу, щоб скопіювати вже його. Але як довідатись, у яку позицію вхідного слова треба повернутись? Наприклад, звідки мі знати, що після копіювання першого символу a треба повернутись саме до першого символу вхідного слова, а не до другого або третього? В попередній задачі завжди потрібно було повертатись до першого з тих символів, що залишились у вхідному слові, а тепер зберігаються всі символи, тому незрозуміло, які символи вже скопійовані, а які ще ні. Відзначимо також, що в МТ комірки стрічки ніяк не нумеруються, немає в МТ і лічильників, які дозволили б визначити, скільки символів вже скопійовано.

В загальному проблему можна сформулювати так: як зафіксувати на стрічці деяку позицію, у якій ми  вже були і до якої пізніше повинні повернутись? Зазвичай ця проблема вирішується так. Коли ми опиняємось в цій позиції в перший раз, то заміняємо символ, що в ній знаходиться, на його двійника - на новий допоміжний символ, причому різні символи заміняємо на різні двійники, наприклад a на A і b на B. Після цього виконуються якісь дії в інших місцях стрічки. Щоб потім повернутись до потрібної позиції, треба просто відшукати на стрічці ту комірку, де перебуває символ A або B. Потім в цій комірці можна відновити колишній символ, якщо більше не треба фіксувати цю позицію (саме для відновлення колишнього символу і треба було заміняти різні символи на різні двійники).

Скористаємось цим прийомом, виконавши наступні дії:

1. Записуємо знак = за вхідним словом (крок 1 вище).

2. Повертаємось під перший символ вхідного слова (крок 2 вище).

3. Заміняємо символ a на двійника A (крок 3 нижче), «біжимо» вправо до першої вільної комір-ки і записуємо в неї символ a (крок 4). Після цього повертаємось до комірки із двійником A (крок 5), відновлюємо колишній символ a і переміщаємось вправо до наступного символу (крок 6)

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

 4. Коли буде скопійовано останній символ вхідного слова і повернуто до його двійника (після кроку 12), то потім після переміщення на одну позицію вправо потрапимо на знак = (крок 13). Це сигнал про те, що вхідне слово повністю скопійовано, тому роботу МТ треба завершувати.

Алгоритм у вигляді програми для МТ:

У вигляді програми для МТ наведені вище дії описуються такою таблицею:

Q A	a0	a	b	=	A	B	Пояснення
q1	=L	R	R				поставити справа від слова знак =
q2		L	L				переміститись наліво під 1-й символ
q3							аналіз і заміна чергового символу
q4		R	R	R			запис a справа
q5		R	R	R			запис b справа
q6		L	L	L			повернення, відновлення, до наступного символу

Відзначимо, що в цій програмі можна позбутись стану , якщо об'єднати його зі станом , передбачивши в  повернення вліво як до порожньої комірки, так і до символів A та B:

Q A	a0	a	b	=	A	B	Пояснення
			. . .
q2		L	L	L			переміститись наліво до , A або B
			. . .

Емулятор машини Тьюрінга

Емулятор машини Тьюрінга - це навчальна модель універсального виконавця (абстрактної обчислювальної машини).

В пакет включені наступні файли:

turing.exe      - основна програма - емулятор машини Тьюрінга

EXAMPLES - підкаталог із прикладами програм для емулятора

Середовище емулятора має такий вигляд:

Машина Тьюрінга - це автомат, який керується таблицею. Зовні таблиця МТ дещо відрізняється від наведених вище таблиць. Рядки в таблиці відповідають символам обраного алфавіту A, а стовпці — станам Q. У кожній комірці таблиці, що відповідає деякому символу a_i і деякому стану q_j, перебуває запис, що складається із трьох частин:

1. символ з алфавіту A;

2. напрямок переміщення: > (вправо), < (наліво) або . (на місці);

3. новий стан каретки.

На початку роботи машина Тьюрінга перебуває в стані q₁. Стан q₀ — це кінцевий стан: потрапивши в нього, автомат закінчує роботу.

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

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

За допомогою меню Лента можна запам'ятати стан стрічки у внутрішньому буфері і відновити стрічку з буфера.

В полі Алфавит задаються символи обраного алфавіту. Пробіл додається до введених символів автоматично.

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

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

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

Програма може виконуватись безупинно (F9) або по кроках (F8). Команда, яка має виконуватись, підсвічується зеленим кольором. Швидкість виконання регулюється за допомогою меню Скорость.

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