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

Як користуватися емулятором

• Введіть алфавіт для МТ (символ λ вводити не потрібно) і натисніть кнопку "Задати"
• Введіть слово на стрічці (через саму стрічку або використовуючи поле для введення слова)
• Для переміщення головки на певну комірку, двічі клацніть по ній
• Додайте необхідну кількість станів (за необхідності змініть імена станів)
• Задайте параметри переходів (символ для запису, зсув і новий стан)
• Виберіть початковий стан (якщо він відрізняється від q0)
• Натисніть кнопку "Запустити" для виконання МТ до стану зупинки або кнопку "Зробити крок" для виконання одного кроку
• Якщо не вдається розібратися, скористайтеся одним з кількох підготовлених прикладів

Що таке машина Тьюрінга?

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

• нескінченна стрічка, що складається з комірок
• головка для зчитування/запису символів на стрічці
• пристрій керування

Нескінченна стрічка

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

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

Зчитувальна/записувальна головка

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

Пристрій керування

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

Таблиця має розмір |Q|x|A|, де |Q| — кількість станів, а |A| — розмірність алфавіту (включаючи символ λ). У першому (заголовному) рядку написані символи алфавіту. У кожній з комірок таблиці, що відносяться до рядків зі станами, розташовані трійки <char, action, state>, що визначають дію машини, яку вона повинна здійснити, якщо знаходиться в даному стані і на стрічці записаний символ з заголовочної комірки даного стовпця:

• char — символ, який потрібно записати на стрічку
• action — дія, яку потрібно виконати після запису (одна з трьох дій: L — зсув вліво, N — залишитися на місці, R — зсув вправо)
• state — стан, в який потрібно перейти

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

• Якщо потрібно виконати лише зсув, залишившись у тому ж самому стані, то досить записати лише символ зсуву: L, N або R
• Якщо потрібно виконати зупинку, то досить записати !
• Якщо потрібно записати порожній символ (λ), то можна вставити пробіл або кому перед символом зсуву: ,R,q0

Приклади машин Тьюрінга

Приклад 1 (завантажити в емулятор). Додати 1 до двійкового числа. На початку і в кінці головка повинна знаходитися на найстарший біт слова (зліва).

Q \ A	0	1	λ
q0	R	R	λ L q1
q1	1 N q2	0 L q1	1 N !
q2	L	L	λ R !

Оскільки по умові головка МТ знаходиться на найстаршому біті, а збільшувати потрібно молодший, необхідно спочатку перемістити головку на молодший біт, що виконується в стані q0: як тільки стрічка побачить символ λ, вона зсунеться вліво (на молодший біт) і перейде в стан інкрементації (q1).

В стані q1 можливі наступні ситуації:

• молодший біт дорівнює 0, його потрібно замінити на 1 і перемістити головку на старший біт (через стан q2)
• молодший біт дорівнює 1, його потрібно замінити на 0, зсунутися ліворуч і залишитися в цьому самому стані
• під час заміни 1 на 0 досягнуто порожнього символу (було записано число з одних одиниць), замість нього потрібно записати 1 і зупинити МТ

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

Приклад 2 (завантажити в емулятор). У слові з алфавіту {a, b} інвертувати символи. На початковий момент головка знаходиться в початку слова.

Q \ A	a	b	λ
q0	b R q0	a R q0	!

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