Визначення машини Тьюринга

ЛЕКЦІЯ 2. Машина Тьюринга

Проблема еквівалентності слів

Визначення 9. 8. Якщо слово R може бути перетворене в слово S за допомогою однократного застосування припустимої підстановки, то, мабуть, що слово S може бути перетворене в слово R за допомогою застосування зворотної підстановки. Такі слова називаються суміжними словами.

Визначення 10. 9. Послідовність суміжних слів R ₁, R ₂, …, R_n називають дедуктивним ланцюжком від R ₁ до R_n.

Визначення 11. 10. Якщо існує дедуктивний ланцюжок від R до S, те існує і дедуктивний ланцюжок від S до R. Такі два слова називаються еквівалентними словами.

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

Надалі ми покажемо, що проблема еквівалентності слів для будь-якого довільно узятого асоціативного вирахування алгоритмічно нерозв'язна.

Машина Тьюринга була першою алгоритмічною схемою, запропонованої як математичне визначення алгоритму в 1937 році.

Машина Тьюринга є гіпотетичною машиною: Тьюринг не ставив задачі сконструювати цей пристрій. Концепція обчислювальної машини належить фон Нейману, але її основою послужила машина Тьюринга. Машина Тьюринга є знакоперерабатывающим пристроєм. Задача машини Тьюринга – переробляти вхідне слово W Î A* у деяке вихідне слово W * Î A *, де А – зовнішній алфавіт.

Машина Тьюринга складається з трьох частин.

1). Нескінченна в обидва боки стрічка, розбита на осередки, у кожній з яких може знаходитися один (і тільки один) символ зовнішнього алфавіту A = { a, b, g, … }... Інформація записується на стрічці у виді слова в алфавіті A.

2). Голівка, що зчитує, що в один дискретний момент часу обдивляється один осередок і може знаходитися в одному з внутрішніх станів qi ( Q, де Q - алфавіт внутрішніх станів. При цьому вона розпізнає записаний в осередку символ зовнішнього алфавіту, записує замість нього інший символ (можливо, той же самий), переходить в інший стан (можливо – у колишнє), після чого зрушується вправо, вліво або залишається на місці (П, Л, Н) (див. мал. 1).

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

3) Наступна частина машини Тьюринга – це програма, що складається з команд виду:

aq_i ® b q_jx, x Î {Л, П, Н}, q_i, q_j Î Q, a, b Î A.

У результаті виконання цієї команди символ a на стрічці буде замінений символом b, голівка змінить своє положення в залежності від x і внутрішній стан зміниться з q_i на q_j.

Послідовність команд задає алгоритм переробки слова. На вхід машини Тьюринга подається слово вихідне слово W в алфавіті A і задається початковий стан q₀: початкова конфігурація. Робота машини Тьюринга відбувається по тактах, або по кроках. При роботі машини Тьюринга можливе розширення зовнішнього алфавіту A допоміжними символами, що після переробки слова заміняються символами алфавіту A або витираються. У число символів алфавіту A обов'язково входить порожній символ L. Вважається, що споконвічно всі осередки стрічки заповнені порожніми символами.

У процесі роботи можливі ситуації:

1. Машина Тьюринга переробляє вихідне слово P у Q і зупиняється; тоді говорять, що дана машина застосовна до слова P.

2. Машина Тьюринга, починаючи роботу зі слова P, ніколи не зупиниться; тоді говорять, що дана машина Тьюринга не застосовна до слова P.

Розглянемо приклад.

Нехай заданий алфавіт A = {|, *}, вихідне слово, у якому може мати вигляд: P = | | |* | * | |. У початковому стані q₀ машина обдивляється крайній лівий символ. Машина Тьюринга повинна перетворити це слово в порожнє слово, тобто повинна реалізовувати алгоритм обчислення нуль-функції: 0(x) = L. Для цього вона повинна, рухаючи ліворуч праворуч, замінити кожен символ на стрічці на порожній символ і зупинитися, як тільки побачить крайній правий символ.

Програму для машини Тьюринга звичайно записують у виді таблиці.

Це дуже простий алгоритм.

Розглянемо програму для алгоритму додавання символу | до слова в тім же алфавіті. Нехай вихідне слово має вигляд: P = | | |. Це слово можна розглядати як число 3, а додавання символу | – як обчислення функції f(x) = x + 1 в унарной системі числення. Програма для машини Тьюринга насправді дуже проста: голівка машини пропускає всі символи |, рухаючи ліворуч праворуч, і, дійшовши до крайнього правого порожнього символу L, дописує туди ще один символ |, після чого зупиняється у своєму заключному стані (див. табл.).

Очевидно, що точно так само можна скласти програму для додавання будь-якого символу алфавіту A наприкінці слова, тобто такий алгоритм реалізовує вихідну рекурсивну функцію P_z(x) = xz, де z Î A.

Третя вихідна функція: функція проекції U_i^j(x) = x_i, є не що інше, як елементарна дія машини Тьюринга – розпізнавання символу.

Розглянемо тепер обчислення більш складної функції: F(x,y) = x+y, де x, y – слова, задані в унарной системі числення. Нехай вихідна конфігурація на стрічці задана так, що в початковому стані голівка обдивляється крайній лівий символ |, (див. мал.), слово на стрічці являє собою два числа, розділені символом *.

Складемо машину Тьюринга, що працює по наступному алгоритмі. У початковому стані q₀ машина бачить крайню ліву паличку, витирає її і, перейшовши в стан q₁, рухається вправо, поки не побачить крайній праворуч порожній символ. Тоді на місці порожнього символу машина записує паличку, переходить у новий стан q₂ і рухається вліво в тім же стані q₂, пропускаючи всі символи, поки не дійде до крайнього ліворуч порожнього символу. Тоді машина залишає його на місці, зрушується вправо і переходить у стан q₀. Після цього процес повторюється доти, поки в стані q₀ машина не побачить символ *. Це означає, що уже всі палички перенесені ліворуч праворуч, машина може витерти символ * і зупинитися, тобто перейти в заключний стан.

A \ Q	q0	q1	q2
|	L q1 П	| q1 П	| q2 Л
*	L! П	* q1 П	* q2 Л
L	L! Н	| q2 Л	L q0 П

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

f(x, 0) = x,

f(x, y+1) = f(x, y) + 1.

f(2, 3) = f(2, 2) + 1 = (f(2, 1) + 1) + 1 = ((f(2, 0) + 1) + 1) + 1.

На цьому завершується прямий хід рекурсії: складена рекурсивна схема обчислення функції. Тепер зворотний хід рекурсії обчислює її значення:

((2 + 1) + 1) + 1 = (3 + 1) + 1 = 4 + 1 = 5.

Дата добавления: 2014-01-07