Алгоритмическая система А.А.Маркова.

 

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

Нормальные алгорифмы U=<A, S> - класс словарных алгоритмов, то есть алгоритмов (применимых к словам некоторого алфавита А), элементарными действиями которых являются подстановки в слова (их кортеж есть схема S).

Всякий нормальный алгоритм, являясь алгоритмом в некотором алфавите А, порождает в нем детерминированный процесс переработки слов. Поэтому любой нормальный алгоритм в фиксированном алфавите А вполне определяется указанием его схемы S - упорядоченного конечного списка формул подстановки в А. Каждая такая формула по существу представляет пару <a_i, _i > слов в А (то есть a_i, _i ÎА^*). Слово a_i называется левой частью этой формулы, а _i – ее правой частью. Среди формул данной схемы некоторые выделяются специально и объявляются заключительными. Обычно в схеме нормального алгоритма заключительная формула записывается в виде a_i ®· _i (®, ®·ÏA), а незаключительная в виде a_i ® _i. При этом допустимы формулы вида: e® _i; a_i ®e; e®e;a_i ®·e; e®· _i; (e – пустое слово)

Нормальный алгоритм U в алфавите А есть предписание строить, исходя из произвольного слова P в А (PÎА^*), последовательность слов a_i.

В свете изложенного алгоритмическая система «нормальный алгорифм» имеет вид:

 

 

 

 

 

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

1. Считать, что i=1. Перейти к пункту 2.

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

3. Первое простое вхождение левой части i-ой формулы в преобразуемом слове заменить правой частью i-ой формулы. Результат считать в дальнейшем преобразуемым словом, перейти к пункту 4.

4. Если i-ой формула является заключительной подстановкой, то процесс прекратить. В противном случае перейти к пункту 1.

5. Проверить, имеет ли место равенство i=n. Если да, то процесс прекратить, в противном случае перейти к пункту 6.

6. Увеличить значение i на 1 и перейти к пункту 2.

 

Любое слово P в алфавите А может служить исходными данными для нормального алгоритма в алфавите А. При этом возможны случаи:

- Процесс выполнения нормального алгоритма для слова aÎА^* заканчивается формулой a_i®· b_i после конечного числа шагов. При этом говорят, что нормальный алгоритм применим к слову a, и полученное после его выполнение слово bÎA^* называется результатом.

- Процесс выполнения нормального алгоритма при исходном слове aÎА^* никогда не заканчивается или происходит безрезультативная остановка (то есть не на формуле a_i®· b_i). В этом случае говорят, что нормальный алгоритм не применим к слову a.

 

Пример:

Алгоритм U=<í0, 1ý <xh®x, x0®0x, x1® 1x, x®·Ù, hh®x, h 0 0®0 h 0, h 0 1®1h 0, h1 0®0 h 1, h11®1h1, Ù®h>> «обращает» любое слово в А, то есть перерабатывает его в слово, записанное в обратном порядке (его можно записать как Ù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ý, <ah® hb; bah®haba, aah®·h> реализует предписание: «Взяв какое-либо слово 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., задающая конечно определенные ассоциативные системы (полугруппы) K_u.

Всякое ассоциативное исчисление U=<A, Σ> определяется указанием некоторого алфавита A и конечного списка Σ соотношений в A – пар слов в этом алфавите α_i↔β_i. Пара α_i→β_i понимается как левая подстановка, а β_i→α_i – как правая постановка в заданное слово αÎA^*=eÈAÈA∙AÈ…ÈA^kÈ…(kÎN; e – пустое слово).

Допустимым относительно списка Σ действием над словами в алфавите A называется любая подстановка одной из частей какого-либо соотношения α_i↔β_i ((α_i↔β_i)ÎΣ) вместо вхождения другой части того же соотношения.

Ассоциативное исчисление U=<A, Σ> представляет собой разрешение производить, исходя из любого слова RÎA^*, любые допустимые относительно списка Σ действия.

 

Пример:

Подстановка ab↔bcb применима четырьмя способами к слову P₁=abcbcbab: замена каждого из двух вхождений bcb даст слова aabcbab и abcabab, а замена каждого из двух вхождений ab дает слова bcbcbcbab и abcbcbbcb. В то же время к слову P₂=bacb эта подстановка не применима, а подстановка вида α↔e означает, что из преобразуемого слова P_iÎA^* выбрасывается вхождение слова α, а также что между двумя какими-либо буквами преобразуемого слова или впереди него, или за ним вставляется слово α (e-пустое слово, eÎA^*, eÏA). Обо всех словах Q, которые при этом получаются (в том числе и о самом исходном слове P), говорят, что они эквивалентны P в ассоциативном исчислении U=<A,Σ> (в символической записи U:P_╨Q).

Отношение _╨ для любого ассоциативного исчисления U рефлексивно, симметрично и транзитивно. Кроме этого, из U:P_1╨Q и P_2╨R следует, что U: P₁P_2╨QR. Это позволяет естественным образом сопоставить всякому ассоциативному исчислению U некоторую конечно определенную ассоциативную систему K_u, взяв в качестве ее элементов классы слов, эквивалентных друг другу в U=<A, Σ>, а в качестве операции умножения в K_u – операцию конкатенации слов в алфавите A.

Так настроенная ассоциативная система K_u будет моноидом, т.е. будет иметь нейтральный элемент eÎA^*; элементы K_u представленные буквами алфавита A, будут составлять для K_u систему порождающих элементов, а список соотношений Σ будет представлять собой полную систему соотношений между упомянутыми порождающими элементами K_u в том смысле, что элементы K_u, представленные словами P и Q, тождественны в K_u тогда и только тогда, когда P и Q эквивалентны в U=<A, Σ>. В этом плане, распознавание тождества элементов в K_u сводится распознаванию эквивалентности слов в U=<A, Σ>.

Отсюда понятна важность исследования разрешимости алгоритмической проблемы распознавания эквивалентности слов в произвольном ассоциативном исчислении. Эта проблема состоит в том, что для произвольного U=<A, Σ> требуется построить алгоритм, который для любой пары слов в алфавите A U=<A, Σ> позволял бы за конечное число шагов выяснить, эквивалентны ли в U=<A, Σ> слова, составляющие эту пару. В алгебраической интерпретации эта проблема есть проблема тождества для полугруппы K_u.

 

Теорема (Маркова-Поста):

“Существует ассоциативное исчисление, в котором проблема распознавания эквивалентности слов алгоритмически неразрешима”

 

Действительно, рассматривая машину Тьюринга как математическую модель алгоритма, можно свести проблему распознавания эквивалентности слов в U=<A, Σ> к проблеме остановки машины Тьюринга (а эта проблема является алгоритмически неразрешимой).

 

Приведем и следующие две теоремы:

“Для любого перечислимого множества M существует система подстановок, множество заключительных слов которой совпадает с M”

“В ассоциативном исчислении два слова эквивалентны, если им соответствуют две конфигурации машины Тьюринга такие, что за конечное число тактов машина переходит из первой конфигурации ко второй”

 

Очевидно, что теорема: “Существует полугруппа заданная определяющими соотношениями, в которой проблема распознавания эквивалентности (равенства) слов алгоритмически неразрешима” является переформулировкой теоремы Маркова-Поста.

Примером ассоциативного исчисления с неразрешимой проблемой равенства является исчисление U=<{a,b,c,d,e},{ac↔ca, ad↔da, bc↔cb, bd↔db, abac↔abace, eca↔ae, edb↔be}>

 

Замечание:

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

 

Так, любую формулу соответствующего языка математики можно рассматривать как слово в известном алфавите. Процесс эквивалентных преобразований или вывод в таком случае есть преобразование слов с привлечением тех или иных подстановок, в качестве которых выступают аксиомы, тождества, законы.