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

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

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

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

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

2) среди слов P1, …, PM существует PI, входящее в К.

Пусть T — минимальное число такое, что PT входит в К, и пусть К = V1 PT V2, где V1 имеет минимальную длину (т. е. берется первое вхождение PT в К). Тогда определим слово W = V1 QT V2. В этом случае говорим, что схема SN применима к К и пишем SN : К  W Или SN : К W В зависимости от того, применялась простая формула или заключительная соответственно.

Теперь пишем SN : К |W, если существует конечная последовательность слов W0, W1, … WK в алфавите А такая, что К = W0, W = WK и выполнено

SN : W0  1, SN : W1  W2, …, SN : WK – 1 ×WK,

Либо SN : WK – 1  WK.

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

FS(P) = Q

Работа нормального алгоритма может быть описана так. Если дано слово Р, то находим в схеме алгоритма SN первую формулу PT à (×)QT такую, что PT входит в Р, и производим замену первого вхождения PT словом QT. Пусть W1 — результат этой подстановки. Если применяемая формула PT à (×)QT — заключительная, то работа алгоритма заканчивается, и слово W1 есть результат работы алгоритма. Если применяемая формула PT à QT — простая, то к слову W1 применяем описанную процедуру. Если на некотором шаге получено слово WI, к которому не применима схема алгоритма SN (т. е. ни одно из не входит в PJ, ), то работа алгоритма заканчивается, и WI есть результат работы алгоритма. Если описанный процесс не заканчивается, то, по определению, алгоритм не применим к слову Р.

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

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

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

2) А = {A1, …, AN}.

Схема

SN : .

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

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

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

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

Рассмотрим алфавит В = А È {a, b} и соответственно схему SN (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 осуществляет обращение слов в алфавите А.

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

.

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

.

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

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

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

< Предыдущая		Следующая >