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

Советский ученый А. А. Марков избрал другой путь уточ­нения понятия алгоритма. Им разработана строгая теория класса алгоритмов, которые он назвал нормальными алго­ритмами[14].

Нормальные алгоритмы в качестве исходных данных и искомых результатов имеют, подобно машинам Тьюрин­га, строки букв — слова.

Предположим, что заранее выделен некоторый алфавит (это' было и в случае машин Тьюринга). Обозначим его А. Букву, одинаковую с одной из букв, входящих в алфавит Л, называют буквой, в А. Слово, состоящее из букв в А, назы­вают словом в А. При этом для удобства рассуждений до­пускают и пустые слова (не имеющие в своем составе ни одной буквы).

Если А и В — два алфавита, причем каждая буква ал­фавита А является буквой в В, а хотя бы одна из букв ал­фавита В не является буквой в А, то В называется расши­рением алфавита А.

Например, если

A = {а, б, в, г}, B={1, а, б, в, г, д},

то В является расширением А, так как содержит две бук­вы («1» и «д»), не являющиеся буквами в А, тогда как все буквы алфавита А являются буквами в В.

Рассмотрим какое-либо конкретное слово для опреде­ленности в алфавите русских букв, например слово «са­молет». Мы видим, что из него можно вырезать подслова, например «сам», «амол» или «олет», или «лет», или, нако­нец, однобуквенное слово «т». Про такие подслова гово­рят, что они входят в рассматриваемое слово или являются вхождениями в него. Заметим, что в наше слово входит и пустое слово, причем — несколько раз (оно входит перед первой буквой, между каждыми двумя буквами и, наконец, после последней буквы, т. е., в данном случае, 8 раз).

Условимся обозначать слова заглавными латинскими буквами (если эти буквы не являются буквами в применяе­мом алфавите). Если задано некоторое слово и нами выбра­на буква, являющаяся его обозначением (именем), то будем ставить между ними знак = (равенства). Возвращаясь к нашему примеру, мы можем написать: для слова R= самолет слово P=амол является вхождением.

Заметим, что не только пустое слово может многократно входить в другое слово. Например, в слово R=тарарам слово Р=ара входит два раза. Особый интерес для нас будет представлять так называемое первое вхождение.

Марковской подстановкой называется операция над словами, задаваемая с помощью пары слов (Р, Q), заклю­чающаяся в следующем.

Если задано исходное слово R, то в нем находят первое вхождение слова Р (если таковое имеется) и, не изменяя остальных частей слова R, заменяют в нем это вхождение словом Q. Полученное слово является результатом приме­нения марковской подстановки (Р, Q) к слову R. Если же нет первого вхождения Р в слово R (при этом нет вообще ни одного вхождения Р в R), то считается, что марковской подстановке слово R не поддается.

Частными случаями марковских подстановок являются (,Q), (Р,) и (,). В первом из приведенных примеров Р, во втором Q, а в третьем и Р, и Q являются пустыми. При­ведем некоторые примеры преобразования слов с помощью марковских подстановок (табл. 3).

Таблица 3 Преобразование слов с помощью марковских подстановок

	Преобразуемое слово	Марковская подстановка	Результат
		(923, 0000)
	функция	( ,λ-)	Λ-функция
	паровоз	(овоз,)	пар
	терек	(е, )	трек
	слово	( , )	слово
	слово	(ра, да)	(результата нет)

Будем рассматривать слова в некотором алфавите А. Предположим, что символы «→» и «→•» не являются бук­вами в А. Записи

P→Q и P→•Q

будем называть записями марковской подстановки (Р, Q), причем первую из них будем называть подстановкой, а вторую

заключительной подстановкой. Смысл этих назва­ний станет ясным немного ниже.

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

Записью нормального алгоритма в алфавите А называ­ют столбец формул, левые и правые части которых явля­ются словами в А. Выполнение нормального алгоритма применительно к исходному данному R, являющемуся сло­вом в А, заключается в следующем.

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

Затем смотрят, является ли выполненная подстановка заключительной. Если она является заключительной, то процесс окончен. В противном случае весь процесс повто­ряют с самого начала.

Пусть В является расширением алфавита А. Нормаль­ный алгоритм в В, который слова в А, если он к ним при­меним, перерабатывает в результаты, являющиеся словами в А, называется нормальным алгоритмом над А. В некото­рых случаях построение нормального алгоритма над А гораздо легче, чем построение нормального алгоритма в А.

Приведем примеры некоторых нормальных алгорит­мов. Мы уже показывали, как можно для λ(х)=х+1по­строить машину Тьюринга, изображая х в виде слова, состоящего из палочек, количество которых равно значе­нию х (в частности, для х=0 количество палочек равно нулю, т. е. изображающее его слово является пустым). Полагая алфавит А состоящим из единственной буквы |, мы искомый нормальный алгоритм запишем в виде един­ственной формулы →•|•.

Интереснее нормальный алгоритм для вычисления λ(х)в случае, когда х записано в обычной десятичной системе счисления. В этом случае в качестве алфавита А возьмем перечень арабских цифр 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. Нормаль­ный алгоритм мы будем строить не в А, а над А, добавив к перечисленным буквам (цифры,. для нас — буквы) еще две буквы х и у. Ради экономии места столбец формул нашего алгоритма запишем в виде четырех подстолбцов.

Искомый нормальный алгоритм будет иметь вид

0y→•1	8y→•9	x5→5x	3x→3y
1y→•2	9y→y0	x6→6x	4x→4y
2y→•3	y→•1	x7→7x	5x→5y
3y→•4	x0→0x	x8→8x	6x→6y
4y→•5	x1→1x	x9→9x	7x→7y
5y→•6	x2→2x	0x→0y	8x→8y
6y→•7	x3→3x	1x→1y	9x→9y
7y→•8	x4→4x	2x→2y	→y

Если бы этот алгоритм мы применили к исходному данному R= (пустому), то получили бы бесконечный процесс, промежуточными результатами которого были бы слова х, хх, ххх, . . . Это означает, что к пустому слову наш ал­горитм неприменим. Его применение к слову R=299 дало бы промежуточные результаты х299 (в силу последней строки) 2x99, 29x9, 299х (в силу строк, расположенных в конце второго и начале третьего подстолбцов), 299у (в силу предпоследней формулы), 29у0, 2у00 (в результате двукратного применения второй формулы второго подстолбца), и привело бы к искомому результату 300 (в силу третьей формулы алгоритма). Мы получили бы λ(299)=300, что и требуется.

Внимательно рассматривая нормальные алгоритмы, мы видим, что они вполне соответствуют нашему пониманию алгоритма, но имеют очень частный характер. Большинство алгоритмов, встречающихся на практике, не являются нормальными алгоритмами. Но, безусловно, нормальные алгоритмы описаны с полной математической строгостью и точностью. Они вполне пригодны для тех целей, для которых были разработаны, а именно — для целей обос­нования математики и исследования неразрешимости проблем.

Иной вопрос, как это делать. Для них, как и для рас­смотренных нами других семейств избранных алгоритмов, выдвигается гипотеза (которую нельзя доказать, но можно принять, опираясь на весь предыдущий опыт человече­ства), известная под названием принципа нормализации.

Принцип нормализации. Каков бы ни был алгоритм, для которого допустимыми исходными данными и соответствующими им результатами являются слова в А, существует эквивалентный ему нормальный алгоритм над А.