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

В данной лекции дается представление об одном подходе к уточнению понятия алгоритма, предложенном А.А. Марковым и называемом нормальные алгоритмы (в авторской транскрипции — алгорифмы). Данный подход связывает неформальное понятие эффективности с переработкой слов в некотором конечном алфавите в соответствии с определенными правилами. В качестве элементарного преобразования используется подстановка одного слова вместо другого. Множество таких подстановок определяет схему алгоритма. Правила, определяющие порядок применения подстановок, а также правила останова являются общими для всех нормальных алгоритмов. Дадим формальные определения. Пусть А = {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. ba à ab, для любых a Î A

3. ba à b

4. b à ×^

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

6. ^ à a.

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

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

.

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

.

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

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

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

Л е к ц и я 15