Еквівалентність нормальних алгоритмів і машини Тьюринга

Робота алгоритму Маркова.

ЛЕКЦІЯ 4.Нормальний алгоритм Маркова

Визначення 12.11. Нормальний алгоритм Маркова – це кінцевий упорядкований набір підстановок виду P_i ®(.) Q_i, i = 1, 2, …, n... P_i ® Q_i – звичайна підстановка, що означає, що крайнє ліве входження подслова P_i у W заміняється на Q_i., P_i ®. Q_i – кінцева підстановка, тобто після її виконання робота алгоритму завершується.

Вихідне слово W Î А * переробляється за допомогою алгоритму в такий спосіб. Починаючи з першої підстановки, шукається перше ліве входження подслова P_i у слові W. Якщо воно знайдено, то воно заміняється на Q_i, після чого список підстановок проглядається із самого початку. Якщо ж входження P_i не було знайдено, то вибирається наступна підстановка. Якщо була виконана заключна підстановка, то процес переробки слова завершується і тоді говорять, що алгоритм застосуємо до даного слова. Може виявитися, що процес не завершується, тобто жодна з заключних підстановок не застосовувалася в процесі переробки слова. У цьому випадку говорять, що алгоритм не застосуємо до даного слова.

Приклад. Нормальний алгоритм Маркова для додавання двох чисел в унарной системі, тобто алгоритм обчислює функцію f (x, y) = x + y в алфавіті A = {|, *}. Список підстановок складається з двох підстановок.

1. * | ® |*

2. * ® L

Процес переробки слова полягає в наступному (у дужках зазначений номер застосовуваної підстановки):

| | |* | | | | Þ (1) | | | |* | | | Þ (1) | | | | |* | | Þ (1) | | | | | |* | Þ (1) | | | | | | |* Þ (2) | | | | | | |

Приклад. Алгоритм звертання слова в алфавіті A = {a, b, c, …, z}... Наприклад, вихідне слово abc звертається в слово cba. Список підстановок:

1. aa ® b

2. bx ® xb

3. ba ® b

4. b ® L

5. ahx® xah

6. L®a

де x, h Î A, a, b – допоміжні символи. Для даного слова процес роботи алгоритму показаний нижче.

L abc Þ (6) aabc Þ (5)baac Þ (5)bcaa Þ (6) abcaa Þ (5)cabaa Þ (6) acabaa Þ (6) aacabaa Þ (1)bcabaa Þ (2)cbabaa Þ (3)cbbaa Þ (2)cbbaa Þ (3)cbba Þ (2)cbab Þ (4)cba.

Теорема. Нехай M – машина Тьюринга з зовнішнім алфавітом A і внутрішнім алфавітом Q. Тоді існує нормальний алгоритм Маркова з алфавітом А È Q, еквівалентний даній машині Тьюринга.

Доказ. Нехай дана машина Тьюринга M із зовнішнім алфавітом А = { x_i }, де i = 1, 2, …, n, і внутрішнім алфавітом Q = { q_i }, j = 0, 1, …, n... Двовимірну конфігурацію на стрічці можна записати як x₁x₂…q_jx_ix_i+1…x_n,де символ поточного стану q_j коштує перед символом, що обдивляється голівка машини Тьюринга в даний момент часу. Ми одержимо слово в алфавіті А È Q. Тоді можна замінити кожну команду машини Тьюринга на послідовність підстановок у такий спосіб:

1. q_ja ® bqr Û q_ja ® q_rb

2. q_ja ® bq_rП Û q_jax_i ® bq_rx_i, " x_i Î A

3. q_ja ® bq_rЛ Û x_iq_ja ® q_rx_ib " x_i Î A

4. q_j ®. L " q_j Î Q

5. L ® q₀

Таким чином, якщо мається деяка програма для машини Тьюринга, те за допомогою цих п'яти правил її можна перетворити в алгоритм Маркова.

Приклад. Нехай задана програма для машини Тьюринга в алфавіті А = {|, *}.

	q0
|	| q0 П
L	|! H
*	* q0 П

Нормальний алгоритм Маркова, еквівалентний цій машині Тьюринга має вигляд:

1. q₀ | | ® | q₀ |

2. q₀ |* ® | q₀ *

3. q₀ | L ® | q₀ L

4. q₀ L ®. |

5. L ® q₀

Процес переробки слова:

| | * | Þ q₀ | | * | Þ | q₀ | * | Þ | | q₀ * | Þ | | * q₀ | Þ | | * | q₀ L Þ | | * | |

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

Схема доказу.

1. Пошук подслова Р в слові W (необхідно скласти машину Тьюринга, що шукає подслово P у слові W; голівка машини Тьюринга, у результаті, буде стояти на першому символі подслова P).

2. Побудувати машину Тьюринга, що заміняє подслово P на слово Q (для кожної підстановки алгоритму Маркова можна побудувати машину Тьюринга, що виконує неї).

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

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

Доведена теорема показує, що якщо побудовано машину Тьюринга для рішення якої-небудь задачі, тобто, якщо функція вычислима по Тьюрингу, те для неї існує і нормальний алгоритм Марков, тобто вона вычислима по Маркову, і навпаки. Іншими словами, класи функцій, вычислимых по Тьюрингу і по Маркову, збігаються. Розглянемо тепер, який клас функцій обчислимо по Тьюрингу.

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