Алгоритмічна система ва

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

Нормальні алгорифм U = - клас словникових алгоритмів, тобто алгоритмів (застосовних до слів деякого алфавіту А), елементарними діями яких є підстановки в слова (їх кортеж є схема S).

Будь-яка нормальна алгоритм, будучи алгоритмом в деякому алфавіті А, породжує в ньому детермінований процес переробки слів. Тому будь-яка нормальна алгоритм в фіксованому алфавіті А цілком визначається зазначенням його схеми S - упорядкованого кінцевого списку формул підстановки в А. Кожна така формула по суті являє пару слів в А (тобто ai. i ÎА *). Слово ai називається лівою частиною цієї формули, а i - її правою частиною. Серед формул даної схеми деякі виділяються спеціально і оголошуються заключними. Зазвичай в схемі нормального алгоритму заключна формула записується у вигляді ai ® · i (®, ® ·ÏA), а незаключітельная у вигляді ai ® i. При цьому допустимі формули виду. e® i; ai ®e; e®e; ai ® · e; e®· i ; (E - порожнє слово)

Нормальний алгоритм U в алфавіті А є припис будувати, виходячи з довільного слова P в А (PÎА *), послідовність слів ai.

У світлі викладеного алгоритмічна система «нормальний алгорифм» має вигляд:

Застосуванням нормального алгоритму U до слова a називається процес, який визначається наступним правилом (що представляє собою алгоритм виконання нормального алгоритму):

1. Вважати, що i = 1. Перейти до пункту 2.

2. Перевірити, чи піддається преобразуемое слово i-ой формулі. Якщо так, то перейти до пункту 3, якщо ні - до пункту 5.

4. Якщо i-ой формула є заключною підстановкою, то процес припинити. В іншому випадку перейти до пункту 1.

5. Перевірити, чи має місце рівність i = n. Якщо так, то процес припинити, в іншому випадку перейти до пункту 6.

6. Збільшити значення i на 1 та перейти до пункту 2.

Будь-яке слово P в алфавіті А може служити вихідними даними для нормального алгоритму в алфавіті А. При цьому можливі випадки:

- Процес виконання нормального алгоритму для слова aÎА * закінчується формулою ai ® · bi після кінцевого числа кроків. При цьому говорять, що нормальний алгоритм застосуємо до слова a, і отримане після його виконання слово bÎA * називається результатом.

- Процес виконання нормального алгоритму при вихідному слові aÎА * ніколи не закінчується або відбувається Безрезультативні зупинка (тобто не на формулі ai ® · bi). У цьому випадку говорять, що нормальний алгоритм застосуємо до слова a.

Алгоритм U =<í0, 1ý > «Звертає» будь-яке слово в А, тобто переробляє його в слово, записане в зворотному порядку (його можна записати як Ù100 з тим, щоб використовувати Ù®h).

Так, слово 100 цей нормальний алгоритм послідовно переробляє в слова h10 0, 0h10, 00h1, h00h1, 0h0h1, h0h0h1, hh0h0h1, x0h0h1, 0xh0h1, 0x0h1, 00xh1, 00x1, 001x, 001Ù.

Останній член цієї послідовності вважається результатом застосування алгоритму U до слова a = 100 і позначається символом U (a). При цьому вважається, що U переробляє a = 100 в b = 001, і пишуть U (a) = b (в нашому прикладі U (100) = 001).

Алгоритм U =<ía, bý, реалізує припис: «Взявши якесь слово aÎía, bý * В якості вихідного, (де a = Аh, a = bah, a = aah), роби допустимі переходи до тих пір, поки не вийде слово виду aah, тоді зупинися: слово і є результат ».

Так, взявши слово babaa в якості вихідного даного після першого переходу (тобто застосувавши формулу bah® haba), отримаємо baaaba (тут h = baa), а після другого (тобто застосувавши знову формулу bah® haba) маємо aabaaba (тут h = ааba). Застосувавши формулу aah® · h до слова aabaaba отримаємо результат baaba (тобто U (babaa) = baaba).

Однак, взявши в якості вихідного даного слова a = baaba, отримаємо нескінченну послідовність abaaba, baabab, abababa, bababab, babababa, ... в якій не буде слова aah. Це означає, що алгоритм U не буде застосовано до слова a = baaba.

Якщо ж вихідними даними взяти слово abaab, то отримаємо кінцеву послідовність baabb, abbaba, bbabab, в якій до останнього слова не можна застосувати допустимий перехід, тобто це випадок безрезультативної зупинки (це означає також непридатність заданого алгоритму U до слова abaab).

Вважається, що для будь-якого алгоритму В в алфавіті А може бути побудований нормальний алгоритм U над цим алфавітом, переробний довільне слово aÎА * в той же самий результат, в який переробляє його вихідний алгоритм В. Ця угода відомо в теорії алгоритмів під назвою принципу нормалізації.

В цьому плані уточнення поняття алгоритм алгоритмічними системами А.Маркова, А.Черча і А. Тьюрінг є еквівалентними.

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

Асоціативне обчислення (система ТУЕ) U - формальна система F.S. задає звичайно певні асоціативні системи (напівгрупи) Ku.

Будь-яке асоціативне обчислення U = визначається зазначенням деякого алфавіту A і кінцевого списку # 931; співвідношень в A - пар слів в цьому алфавіті # 945; i ↔ # 946; i. пара # 945; i → # 946; i розуміється як ліва підстановка, а # 946; i → # 945; i - як права постановка в заданий слово # 945;ÎA * = eÈAÈA # 8729; AÈ...ÈA k È... (kÎN; e - порожнє слово).

Допустимим щодо списку # 931; дією над словами в алфавіті A називається будь-яка підстановка однієї з частин якого-небудь співвідношення # 945; i ↔ # 946; i ((# 945; i ↔ # 946; i)Î# 931;) замість входження іншій частині того ж співвідношення.

Асоціативне обчислення U = є дозвіл виробляти, виходячи з будь-якого слова RÎA *. будь-які допустимі щодо списку # 931; дії.

Підстановка ab↔bcb застосовна чотирма способами до слова P1 = abcbcbab: заміна кожного з двох входжень bcb дасть слова aabcbab і abcabab, а заміна кожного з двох входжень ab дає слова bcbcbcbab і abcbcbbcb. У той же час до слова P2 = bacb ця підстановка не може бути застосована, а підстановка вигляду # 945; ↔e означає, що з преутвореного слова Pi ÎA * викидається входження слова # 945 ;, а також що між двома будь-якими буквами перетворюється слова або попереду нього, або за ним вставляється слово # 945; (E-пусте слово, eÎA *. eÏA). Про всі словах Q, які при цьому виходять (в тому числі і про самому початковому слові P), говорять, що вони еквівалентні P в асоціативному обчисленні U = (В символічному записі U: P # 9576; Q).

ставлення # 9576; для будь-якого асоціативного обчислення U рефлексивно, симетрично і транзитивній. Крім цього, з U: P1 # 9576; Q і P2 # 9576; R слід, що U: P1 P2 # 9576; QR. Це дозволяє природним чином зіставити кожному асоціативному обчисленню U деяку звичайно певну асоціативну систему Ku. взявши в якості її елементів класи слів, еквівалентних один одному в U =, а в якості операції множення в Ku - операцію конкатенації слів в алфавіті A.

Так налаштована асоціативна система Ku буде моноїд, тобто матиме нейтральний елемент eÎA *; елементи Ku представлені буквами алфавіту A, становитимуть для Ku систему породжують елементів, а список співвідношень # 931; буде являти собою повну систему співвідношень між згаданими породжують елементами Ku в тому сенсі, що елементи Ku. представлені словами P і Q, тотожні в Ku тоді і тільки тоді, коли P і Q еквівалентні в U =. У цьому плані, розпізнавання тотожності елементів в Ku зводиться розпізнаванню еквівалентності слів в U =.

Звідси зрозуміла важливість дослідження можливості розв'язання алгоритмічної проблеми розпізнавання еквівалентності слів в довільному асоціативному обчисленні. Ця проблема полягає в тому, що для довільного U = потрібно побудувати алгоритм, який для будь-якої пари слів в алфавіті A U = дозволяв би за кінцеве число кроків з'ясувати, еквівалентні чи в U = слова, составляющие эту пару. В алгебраїчній інтерпретації ця проблема є проблема тотожності для напівгрупи Ku.

"Існує асоціативне обчислення, в якому проблема розпізнавання еквівалентності слів алгоритмічно нерозв'язна"

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

Наведемо і наступні дві теореми:

"Для будь-якого рахункового безлічі M існує система підстановок, безліч заключних слів якої збігається з M"

"В асоціативному обчисленні два слова еквівалентні, якщо їм відповідають дві конфігурації машини Тьюринга такі, що за кінцеве число тактів машина переходить з першої конфігурації до другої"

Очевидно, що теорема: "Існує півгрупа задана визначальними співвідношеннями, в якій проблема розпізнавання еквівалентності (рівності) слів алгоритмічно нерозв'язна" є переформулюванням теореми Маркова-Посту.

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

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