Нормальные алгоритмы

Л е к ц и я 14

В данной лекции дается представление об одном подходе к уточнению понятия алгоритма, предложенном А.А. Марковым и называемом нормальные алгоритмы (в авторской транскрипции — алгорифмы). Данный подход связывает неформальное понятие эффективности с переработкой слов в некотором конечном алфавите в соответствии с определенными правилами. В качестве элементарного преобразования используется подстановка одного слова вместо другого. Множество таких подстановок определяет схему алгоритма. Правила, определяющие порядок применения подстановок, а также правила останова являются общими для всех нормальных алгоритмов. Дадим формальные определения. Пусть А = { a ₁, …, a_n } — алфавит. Если P, Q — слова в алфавите А (возможно, пустые), то выражения P à Q P à × Q называются формулами подстановки в алфавите А (предполагается, что знаки à, × не входят в алфавит А). При этом формула P à Q называется простой, а формула P à × Q — заключительной. Обозначим P à (×) Q — любую из этих формул. Произвольная конечная последовательность таких формул называется схемой S_N нормального алгоритма N. Значит схема нормального алгоритма имеет вид:

Схема S_N определяет следующий алгоритм N, перерабатывающий слова в алфавите А (т.е. вычисляющий словарную функцию на словах в алфавите А). Говорим, что слово Р входит в слово W, если существуют слова V ₁ и V ₂ (возможно, пустые) такие, что W = = V ₁ P V _2. Если слово V ₁ имеет наименьшую длину из всех слов такого вида, то говорят о первом вхождении Р в слово W.

Пусть дано произвольное слово К в алфавите А. Возможны следующие случаи:

1) ни одно из слов P ₁, …, P_m не входит в слово К. В этом случае говорим, что схема S_N не применима к К и пишем S_N: --|;

2) среди слов P ₁, …, P_m существует P_i, входящее в К.

Пусть t — минимальное число такое, что P_t входит в К, и пусть К = V ₁ P_t V ₂, где V ₁ имеет минимальную длину (т.е. берется первое вхождение P_t в К). Тогда определим слово W = V ₁ Q_t V ₂. В этом случае говорим, что схема S_N применима к К и пишем S_N: К W или S_N: К W в зависимости от того, применялась простая формула или заключительная соответственно.

Теперь пишем S_N: К | W, если существует конечная последовательность слов W ₀, W ₁, … W_k в алфавите А такая, что К = W ₀, W = W_k и выполнено

S_N: W _{0 1}, S_N: W ₁ W ₂, …, S_N: W_{k – 1} × W_k,

либо S_N: W_{k – 1} W_k.

В первом случае пишем также S_N: К | × W. Говорим, что нормальный алгоритм N со схемой S_N вычисляет словарную функцию F_s: A * à A *, где А * — множество слов в алфавите А, если для любых слов P, Q Î A * имеем:

F_s (P) = Q

Работа нормального алгоритма может быть описана так. Если дано слово Р, то находим в схеме алгоритма S_N первую формулу P_t à (×) Q_t такую, что P_t входит в Р, и производим замену первого вхождения P_t словом Q_t. Пусть W ₁ — результат этой подстановки. Если применяемая формула P_t à (×) Q_t — заключительная, то работа алгоритма заканчивается, и слово W ₁ есть результат работы алгоритма. Если применяемая формула P_t à Q_t — простая, то к слову W ₁ применяем описанную процедуру. Если на некотором шаге получено слово W_i, к которому не применима схема алгоритма S_N (т.е. ни одно из не входит в P_j, ), то работа алгоритма заканчивается, и W_i есть результат работы алгоритма. Если описанный процесс не заканчивается, то, по определению, алгоритм не применим к слову Р.

Словарная функция f в алфавите А (т.е. типа f: A * à A *) называется вычислимой по Маркову, если существует схема нормального алгоритма S_N в алфавите В Ê А, вычисляющая f, т.е. F_s = f. Класс функций, вычислимых по Маркову, обозначим М.

Рассмотрим несколько примеров.

1) А = { a ₁, a ₂}. Схема S_N: . Данный алгоритм оставляет пустое слово ^ без изменения и всякое слово Р в алфавите А переводит в слово Q, полученное из Р путем вычеркивания первого вхождения буквы а ₁. Алгоритм N не применим к словам, не содержащим вхождений буквы а ₁.

2) А = { a ₁, …, a_n }.

Схема

S_N: .

Данный алгоритм переводит всякое слово Р в алфавите А в пустое слово.

3) А = {1}. Схема S_N: . Данный алгоритм переводит всякое слово Р = в слово Q = . Если представить натуральное число n словом 1 ^{n + 1}, то данный алгоритм вычисляет функцию f (n) = n + 1.

4) A = { a ₁, …, a_n }. Схема S_N: . Данный алгоритм вычисляет функцию F_s (P) = P, для любого слова Р. Если же взять схему S_N: , то данный алгоритм вычисляет нигде не определенную функцию.

5) A = { a ₁, …, a_n }. Если , то обращением слова Р назовем слово .

Рассмотрим алфавит В = А È {a, b} и соответственно схему S_N (a, b — новые буквы):

1. aa à b

2. b a à a b, для любых a Î A

3. ba à b

4. b à ×^

5. a ab à b a a, для любых a, b Î A

6. ^ à a.

Покажем, что данный алгоритм N осуществляет обращение слов в алфавите А.

Пусть — слово в алфавите А. Тогда

.

Теперь, повторяя этот процесс, получим:

.

Для нормальных алгоритмов разработана техника программирования, позволяющая осуществлять операции композиции алгоритмов, реализовывать операторы «если Ф, то выполнить F ₁, иначе F ₂», «пока Ф, выполнять F ₁, иначе F ₂». Следовательно, класс функций М достаточно широк. Много конкретных нормальных алгоритмов и соответствующая техника программирования представлены в книге «Теория алгорифмов»[7]. В связи с этим Марковым А.А. был выдвинут принцип нормализации, который заключается в том, что все алгоритмы исчерпываются нормальными алгоритмами или, что то же самое — всякий алгоритм нормализуем. Принятие данного принципа позволяет истолковывать утверждения о несуществовании нормальных алгоритмов для решения конкретных задач как утверждения о несуществовании алгоритмов вообще. Данный принцип эквивалентен тезисам Черча и Тьюринга, поскольку справедлива следующая теорема.

Теорема 14.1. Класс функций М, вычислимых по Маркову, совпадает с классом функций Т, вычислимых по Тьюрингу, и, следовательно, с классом частично рекурсивных функций Ч и с классом МПД, вычислимых функций Е.

Доказательство совпадения классов М и Ч проводится по той же схеме, что и приведенное выше доказательство совпадения классов Т и Ч [8].

Дата добавления: 2014-12-29