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

10 ) . В данном разделе дается представление об одном подходе к уточнению понятия алгоритма, предложенном А. А.Марковым и называемом нормальные алгоритмы (в авторской транскрипции - алгорифмы). Данный подход связывает неформальное понятие эффективности с переработкой слов в некотором конечном алфавите в соответствии с определенными правилами. В качестве элементарного преобразования используется подстановка одного слова вместо другого. Множество таких подстановок определяет схему алгоритма. Правила, определяющие порядок применения подстановок, а также правила останова являются общими для всех нормальных алгоритмов. Дадим формальные определения. Пусть A = {a1,...,an} - алфавит. Если Р,Q - слова в алфавите А

(возможно пустые), то выражения P → Q , P → ( )Q называются Формулами подстановки в алфавите А (предполагается, что знаки → , , не входят в алфавит А ). При этом формула P → Q называется простой, а формула P → Q заключительной .Обозначим P → ( )Q любую из этих формул. Произвольная конечная последовательность таких формул называется схемой Sa нормального

алгоритма a. Значит схема нормального алгоритма имеет вид:

P1 → ( )Q1

P2 → ( )Q2

Sa : . . .

(1)

Pm → ( )Qm

Схема Sa определяет следующий алгоритм a, перерабатывающий слова

в алфавите А (т,е, вычисляющий словарную функцию на словах в алфавите А ). Говорим, что слово Р входит в слово W , если существуют слова V1 и V2 (возможно, пустые)) такие, что

W=V1PV2	(2)
Если слово V1 имеет наименьшую длину из всех слов вида (2), то говорят о
первом вхождении P в слово W.
Пусть дано произвольное слово K в алфавите A. Возможны следующие
случаи:
1) Ни одно из слов P1,...,Рm не входит в слово K.

В этом случае говорим, что схема Sa неприменима к K1 и пишем Sa :K .

2) Среди слов P1,...,Рm существует Рi , входящее в K.

Пусть t-минимальное число, такое, что Рt входит в K , и пусть K=V1PtV2 ,где V1 имеет минимальную длину (т.е. берется первое вхождение Рt в K.)

Тогда определим слово W=V1QtV2

В этом случае говорим, что схема Sa применима к K и пишем

Sa : K W

Sa : K W (3)

в зависимости от того, применялась простая формула или заключительная соответственно.

50

Pj , j 1,m

P → Qt

Теперь пишем Sa : K W ,если существует конечная последовательность

слов W0 ,W1,...,Wk в алфавите A такая, что K = W0		, W = Wk и выполнено
W0 W1,W2 W3,...,Wk −1 Wk		(4)
либо Wk −1 Wk
В первом случае пишем также Sa : K W .
Говорим, что нормальный алгоритм a со схемой Sa вычисляет словарную
функцию F : A → A , где A -множество слов в алфавите А, если для любых
s	S : P Q и S :Q
ливо
слов P,Q A имеем Fs(P) = Q	a	a
	ливо Sa: P Q

Работа нормального алгоритма может быть описана так. Если дано слово Р , то находим в схеме алгоритма Sa первую формулу P → ( )Qt , такую, что Рt входит в P, и производим замену первого вхождения Pt словом Qt .Пусть W1 результат этой подстановки. Если применяемая формула P → Qt - заключительная, то работа алгоритма заканчивается и слово W1 есть результат работы алгоритма. Если применяемая формула простая, то, к слову W1 применяем описанную процедуру. Если на некотором шаге получено слово Wi ,

к которому неприменима схема алгоритма Sa (т.е. ни одно из не

входит в Wi ,то работа алгоритма заканчивается, и Wi есть результат работы алгоритма. Если описанный процесс не заканчивается то, по определению, алгоритм неприменим к слову Р.

Словарная функция f в алфавите A (т.е. типа f : A → A ) называется вычислимой по Маркову, если существует схема нормального алгоритма Sa в алфавите B A , вычисляющая f , т.е. f = Fs . Класс функций, вычислимых по Маркову, обозначим M. Рассмотрим несколько примеров.

1) A = {a1,a2}

Схема Sa : a1 → λ a2 → a2

Данный алгоритм оставляет пустое слово λ без изменения и всякое слово Р в алфавите А переводит в слово Q , полученное из Р путем вычеркивания первого вхождения буквы a1. Алгоритм a неприменим к словам, не

содержащим вхождений буквы a1. 2) A = {a1,a2 ,...,an}

			a1 → λ
	Схема Sa	:	a2 → λ
			...
			an → λ

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

51

3) A = { }

Схема Sa :λ →

x

678

Данный алгоритм переводит всякое слово P = ... в слово Q = ... .

123 x+1

Если представить натуральное число

n словом n+1 , то данный алгоритм вычисляет функцию f(n)=n+1.

4) A = {a1,a2 ,...,an}

Схема Sa :λ → λ .

Данный алгоритм вычисляет функцию Fs ( P) = P , P .Если же взять

схему Sa :λ → λ

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

5) A = {a1,a2 ,...,an}.Если P = ai1 ...aik ,то обращением слова P назовем слово

P−1 = aik ...ai1 .

Рассмотрим алфавит B = A U{α, β} и соответственно схему Sa (α, β - новые буквы).

1. αα → β

2. βα → αβ, a A

3. βα → β

4. β → λ

5. α ab → bα a, a,b A

6.

λ → α

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

алфавите A.

Док-во.

Пусть P = a j0 ...a jk

слово в алфавите А. Тогда

P →αP →aj

α aj ... aj

k

→aj

aj

α aj

aj

... aj

k

→

(п о 6)

(п о5)

1

0

(п о5)

1

2

0

3

(п о5)

→ aj

aj

... aj

α aj

0

→α aj

aj

... aj α aj

→...→ aj

aj

... aj

α aj

α aj

0

1

2

k

(п о6)

1

2

k

0

2

3

k

1

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

α aj

α aj

...α aj α aj

→αα aj

α aj

k−1

...α aj

α aj

→

k

k−1

1

0

(п о 6)

k

1

0

(п о 4)

β aj

α aj

...α aj α aj

→aj

βα aj

k−1

...α aj

α aj

→

k

k−1

1

0

(п о 2)

k

1

0

(п о 3)

aj β aj

k−1

...α aj

α aj

...(п о 2,3,4)... aj

aj

... aj

0

k

1

0

k

k−1

20 ) Для нормальных алгоритмов разработана техника програмирования,

позволяющая осуществлять операции композиции алгоритмов, реализовывать операторы "если Ф , то выполнить F1 , иначе F2 ", "пока Ф выполнить F1 , иначе F2 ”.Следовательно, класс функций М достаточно широк. Много конкретных

52

нормальных алгоритмов и соответствующая техника программирования представлены в книге [8].В связи с этим Марковым А.А.был выдвинут принцип нормализации, который заключается в том, что все алгоритмы исчерпываются нормальными алгоритмами или, что то же самое - всякий алгоритм нормализуем. Принятие данного принципа позволяет истолковывать утверждения о несуществовании нормальных алгоритмов для решения конкретных задач как утверждения о несуществовании алгоритмов вообще. Данный принцип эквивалентен тезисам Черча и Тьюринга поскольку справедлива Теорема

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

Доказательство совпадения классов M и Ч проводится по той же схеме, что и приведенное выше доказательство совпадения классов Т и Ч. Полностью оно приведено в книге [19], гл. 5.

53