Определение. Нормальные алгорифмы Маркова

Нормальные алгорифмы Маркова

Нормальные алгорифмы Маркова. 1

Определение. 1

Эквивалентность алгорифмов. 7

Теорема о переводе. 8

Теоремы сочетания. 10

Объединение. 14

Разветвление. 15

Повторение. 16

Определение

Подобно понятию машины Тьюринга понятие нормального алгорифма Маркова (называемого далее нормальным алгорифмом или даже просто алгорифмом) есть одно из математических уточнений интуитивного представления об алгоритме.

Нормальный алгорифм в алфавите задается как упорядоченная тройка

,

где - конечный алфавит, - упорядоченный набор (кортеж) правил вывода (формул подстановок), - выделенные в наборе заключительные правила вывода (формулы подстановки).

Правило вывода, не являющееся заключительным (и называемое простым), задается как слово в алфавите , где символ («стрелка») не есть символ алфавита , вида , в котором - слова в алфавите . Заключительное правило вывода задается как слово в алфавите , где символы («стрелка») и · («точка») не являются символами алфавита , вида , в котором - слова в алфавите . В правиле вывода , где есть либо пустое слово, либо «точка», слово называется левой частью, а слово - правой частью правила вывода. Термин «правило вывода» часто заменяется его синонимом – термином «формула подстановки», иногда даже просто термином «подстановка» или «формула».

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

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

Определим отношение непосредственной выводимости по схеме алгорифма на множестве слов в алфавите .

Говорят, что слово непосредственно выводится из слова по схеме алгорифма и записывают это как ├ (или ├ _A ), если слово может быть получено из слова в результате выполнения следующих действий:

1) в схеме отыскивают первую в упорядоченном наборе формулу подстановки, левая часть которой входит в слово (такую формулу называют подходящей для слова );

2) первое вхождение левой части этой формулы заменяют ее правой частью.

Если при этом указанная формула является заключительной, то будем писать ├ × (или ├ _A × ).

Таким образом, в силу определения отношения ├ и ├ × функциональны по второй компоненте (т.е. для каждого существует не более одного слова , для которого ├ _A или ├ _A × ) и его область определения есть множество всех таких слов в алфавите , в которые входит левая часть хотя бы одной формулы подстановки заданной схемы. В таком случае говорят, что слово поддается схеме нормального алгорифма .

Итак, имеет место ├ _A тогда и только тогда, когда слово есть результат замены первого вхождения левой части первой подходящей для слова формулы в схеме алгорифма ее правой частью, причем эта формула не является заключительной. Отношение же ├ _A × выполняется при тех же условиях, но для заключительной формулы. При этом, если - указанная формула, то говорят, что слово получено из слова применением формулы .

Дадим теперь определение процесса работы нормального алгорифма с заданным словом в алфавите .

Так называют последовательность (конечную или бесконечную) слов в алфавите

такую, что для каждого имеет место ├ _A , если слово определено, причем последовательность является конечной, и слово ее последнее слово тогда и только тогда (по определению), когда получено из применением некоторой заключительной формулы схемы алгорифма , или слово не поддается схеме алгорифма.

Если процесс работы алгорифма со словом конечен и имеет вид , то слово называется результатом работы алгорифма со словом и обозначается . Говорят также, что алгорифм перерабатывает слово в слово , используя при этом запись

╞ (или ╞ _A ). В частности, если слово получено применением некоторой заключительной формулы схемы алгорифма к предыдущему слову, то говорят, что алгорифм заключительно перерабатывает слово в слово , записывая ╞ · (или

╞ _A · ).

Мы будем писать ╞ и в том случае, когда существует последовательность слов такая, что для каждого ├ _A . В этом случае слово не будет вообще говоря результатом работы с .

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

Алгорифм , который каждое слово из множества такое, что , перерабатывает в слово из множества , называют алгорифмом типа ; если , то алгорифм называют алгорифмом типа .

Таким образом, алгорифм типа (типа ) определяет функцию (частичную функцию) из в .

Если , то говорят об алгорифме типа (или ).

Алгорифм называют алгорифмом над алфавитом , если он является алгорифмом в некотором расширении алфавита .

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

Замечание. Мы используем термин «существует» для обозначения классического квантора существования. В противоположность этому термин «можно построить» (или «осуществим») мы применяем в определении или формулировки теоремы в том случае, когда это определение или доказательство теоремы дает метод построения объекта, существование которого утверждается.

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

Примеры. 1) Тождественный алгорифм. Алгорифм , задаваемый схемой

любое слово в заданном алфавите перерабатывает в это же слово за один шаг, т.е.

├· .

2) Алгорифм левого присоединения фиксированного слова.

Алгорифм , заданный схемой

,

где - фиксированное слово в алфавите , вычисляет функцию левого присоединения к любому слову в алфавите данного слова , т.е.

├· .

3) Алгорифм правого присоединения фиксированного слова.

Алгорифм , заданный схемой

в алфавите , где , вычисляет функцию правого присоединения данного фиксированного слова в алфавите к любому слову в алфавите , т.е.

╞· .

Действительно, к произвольному слову применима только самая нижняя формула в схеме алгорифма . После ее применения оказывается применимой одна из формул верхней строки, если слово не пусто. Эти формулы применяются до тех пор, пока «решетка» (#) не окажется последней буквой очередного слова, выводимого из исходного слова . Тогда она посредством применения средней формулы схемы заключительно заменяется на слово . Для пустого входного слова имеем:

├ #├ · u.

Для непустого слова получим:

├ # x (1) x (2)… x (m) ├ x (1)# x (2)… x (m)├…├ x #├· xu.

4) Алгорифм удвоения

Рассмотрим алгорифм Double, задаваемый схемой в алфавите V ₁ = V È{a, b}, причем a, b Ï V:

Можно показать, что ╞· , т.е. этот алгорифм удваивает любое входное слово в алфавите V.

Например, пусть x = abca. Тогда

Double: abca ├ a abca ├ a b a a bca ├ a b ab b b a ca ├ a b ab b bc b c a a ├ a b ab b bc b ca b a a ├ ab b a b bc b ca b a a├ ab b ac b b b ca b a a├ ab b ac b ba b c b a a├ abc b a b ba b c b a a ├ abc b aa b b b c b a a├ abca b a b b b c b a a ├⁴ abcaabca a ├ · abcaabca = xx.

Можно заметить следующее: ко входному слову применима только формула нижней строки рассматриваемой схемы. После ее применения посредством применения формул верхней строки каждая буква входного слова копируется и «копия» слева отмечается буквой b (буква a играет роль указателя и продолжает «бежать» вправо). После того, как указатель a пробежит все слово, начинают работать формулы второй строки, в результате применения которых каждая «копия» «добегает» до конца исходного слова (т.е. так, чтобы после нее не было «оригинальных» букв). Затем все буквы b и указатель a стираются.

Можно заметить также, что если вместо формулы поставить формулу , то копия будет инвертирована, т.е. получится слово .

5) Инвертирующий алгорифм

Зададим алгорифм над алфавитом такой схемой:

В этой схеме буквы a и b не принадлежат алфавиту V.

Пусть x = x (1) x (2)… x (m), m > 0, есть непустое слово в алфавите V.

В схеме алгорифма Rv к слову x применима только самая нижняя формула. После ее применения, при условии, что m > 1, будет применима одна из формул верхней строки. Эти формулы применяются до тех пор, пока слово ax не окажется в конце слова:

x (1) x (2)… x (m) ├ a x (1) x (2)… x (m) ├ x (2)a x (1) … x (m) ├ … ├ x (2) x (3) … x (m)a x (1).

Затем буква a «превратится» в букву b (вторая сверху строка схемы) и получится слово x (2) x (3) … x (m)b x (1). К нему опять-таки применима только самая нижняя формула; после ее применения будем иметь:

x (2) x (3) … x (m)b x (1) ├ a x (2) x (3) … x (m)b x (1) ├

├ x (3) a x (2) … x (m)b x (1) ├ … ├ x (3)… x (m) a x (2) b x (1) ├

├ x (3)… x (m) b x (2) b x (1) ├ x (3)… x (m) b x (2) x (1).

Потом буква x (3) (если она есть) будет точно так же перенесена в конец слова и т. д. до тех пор, пока не получится слово x (m) b x (m -1)… x (2) x (1).

Далее:

x (m) b x (m -1)… x (2) x (1) ├ a x (m) b x (m -1)… x (2) x (1) ├

├ b x (m) b x (m -1)… x (2) x (1) ├ b x (m) x (m -1)… x (2) x (1)

├ ab x (m) x (m -1)… x (2) x (1) ├ · x (m) x (m -1)… x (2) x (1).

Итак, алгорифм Rv перерабатывает слово x, длина которого больше 1, в его инверсию x ^R.

Для пустого и однобуквенного слова соответственно имеем:

l ├ a├ × l

и

a ├ a a ├ b a ├ ab a ├ × a.

Итак, мы можем утверждать, что .

---

Дата добавления: 2015-07-15