Ш.И._Галиев_МЛ_и_ТА_2004

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

Пусть -задан алфашгг А, не содержащий в качестве букв символов и и пусть Р и Q - слова в алфавите А. Тогда выражения P-*Q, P-**Q называются формулами подстановки в алфа-

Формула подстановки P-*Q наитвает;! простой подстановкой и означает, «по вместо ? нужно гшдетавить слово Q и перейти к следующей подстановке.

Формула подстановки P-*»Q называется заключительной подстановкой и означает, что вместо Р нужно подставшь Q и закон­ чить процесс преобразования.

Пусть	означает любую из формул подстановки P-*Q
или Г-*шд.

Нормальный алгоритм в алфавите А считается заданным, если задана конечная таблица (схема) формул подстановок слов

п > 1, Р, и Q/, (!<(<«) - слова в А, причем согласно этой таблице (схеме) формул подстановок можно осуществлять преобразование слов алфавита^ следующим образом.

Пусть Л} слово в алфавите А. Если ни одно аз Р],Р2....Р« не входит в fij, то процесс применения В к Ло заканчивается и его результатом считается слово Ry Если хотя бы олно из ,Р„ входит в До, та отыскиваем самую первую (в порядке следований в таблице) формулу подстановки, такую, что Ре входит в й), Совершаем подстановку снова Qt вместо самого'левого вхождения слова РЛв слово Йо. Пусть R\ - результат такой подстановки. Если использованная подстановка Pi~>(*)Qj - заключительная, то работа алгоритма заканчивается и его результатом считается Я|. Если

221

пустого слова (Л) в Ял слово (i по 5), имеем р%. Если первой в йц стоит буква о, то применяем подстановку I), если же первая буква-6, то применяем подстановку 2), а «ли первая с, то применяем 3) и переметаем р за первую букву в слове Rn Повтори этот процесс столько раз, сколько йукв в олсве Я5, получим R$. По подстановке 4) окончательно имеем ftj.j, т.е, этот алгоритм приписывает к произ­ вольному слону Kg е алфавитеА справа oi Rt букву а.

В рассмотренном алгоритме Й подстановки 1), 2) и 3) служат для перестановки местями 0 и а или р и Ь или р и с , т.в. для перестановки 0 с любой буквой алфавита А. Тогда можно ввести для нашего алгоритмаВ более краткую формузаписи:

[рх	-У жр	(жеЛ) и
Б '- j p	-» {.)в	2*)
[л	-» Р	3*)

Здесь запись (1*): 0х -> j(3 применена для обозначения подстановок 1)-3) в Я.

Пусть A = {a i,c > b .Р, Q и R - слова в алфавите А. Догово­

римся, чта запись		вида PxQ -* (*)S (ге<4) обозначает таблицу
подстановок;
?а,е	-* («)й
Р ай	-> т
?«„(?	-> OR
3.	Пусть заданы алфавиты.4 и В буква а не входит в A he В и
<3\.Oi,...at - фиксированные				буквы из алфавита A, a Qi.Qi, - ,Qt -
фиксированные слова в алфавите В. Рассмотрим нормальный
алгоритм в алфавите /<и5и{а}, задаваемый таблицей
см,	-*	Q,o.		{1 =1,2,...к)
	^	“	“	л ' я . ч ....ч !

223

Этот алгоритм в любом слове Р (алфавита А) все встреча­ ющиеся там буиы £11,¾....о* заменяет ни слова Й .Й .-.Й соответственно. Если же a Р букв 0(,0),...,¾ нет, то оставляет его без изменения.

Пусть .W- {!,*), Любое неотрицательное целое (натуральное) число можно записать (обозначить) в алфавите М словом, состоящим из и+1 букв 1:

число 0 обозначим словом 0-1, число 1 обозначим словом Т-11,

число в обозначим словом я = 111,,.1 -

Слова л будем пюылйть цифрами. Поставим теперь в соот­ ветствие истеому -вектору (¾¾.....¾). где - натуральные числа, слово Sj*itj *—*4s в алфавите М, которое обозначим через

(К ],К {,Н алри м ер, (1,2,3) обозначает слово 11*111*1111.

4. Нормальный алгоритм:

как легко убедиться, применим только к чем словам в алфавит! М, которые суть цифры, и переводит любое слово п а 0 ,т.е. Нд(п)=5 для любого натурального п.. Зачетам, что алгоритм А-, не применим

кпустому слову.

5.Нормальныйалгаршм:

очевидно, тоже применимтолько ктем словам в алфавите М, которые суть щфры, и преобразует любое слово п s слово л +1, те.

A\(n)~n l l до* любого нагурального л. Алгоритм А\, как и Ап, не применим к пустому слипу.

§4. Функции часгечно вычислимый

иямчнсиииые по Маркову

Напомним, что функцияJ(x) называется частично определенной на множестве М, если значения атой функции определены не дли всех

хтМ .

Функция/называете!! арифметической, если ее значения и зна­ чения ев аргументов являются целыми неотрицательными числами,

мномгепю нгггуральяыхчисел.

Положим, как и раньше, алфавит {],*).

аргументов. Положим, что существует некоторый алгорюм (us обязачельно нормальный) Ащ в алфавите itf, позволяющий вычислять значения чтой функции вмкнй раз, когда мтячение функции

существует, т.е. Л , ..,£„))= ф ( А . , А„ ) тогда и только

тогда, когда хотя 6м одка ия 'гастей wort> равенстиа определена. Призом.:чиием, что алгоретм А, но прнчы(им t слони*, (ПЛИЧНЫМ

отслоилида (kx,hi....кп ). Назовем функцию 9 частично вычислимой по Марии«у ijiyitxifuei3, если существует пормальный алгоритм В im M , ип(шпе зквавалеитвыйИф шкооигельнD алфавитам

Иными словами ^-аргументная частично определенипи функция ф пычислима по Миркпву тогда

225

сушестяуе1 нормальный алгоритм, позволяющий вычислгпъ '«имение fikuki-.X ) ДЛЯ любых совокупностей значенийx,=kt, xj-ij,. , х„= fc„, при коюрых ф(А|,*3,.. существует.

Если функция определена всюду, те. определена для любой совокупности значений своих аргументов и является частично вычислимой ло Маркову, назовем ее вычаелаиой по Маркову. Таким оброзом, л-вргументнвя функция q> вычислима па Маркову тогда и только тогда, когда существует нормальный алгоритм, позволяющий вычислить значение ф(Л)Л...,ля) для любых совокупностей значений

х,^ъ..„хт

В § 3 показано, что лля всюду определенных арифметических функций

Д*)=х+1, VjrOtiO)

существуют нормальные алгоритмы, вычисляющие их значения (примеры 4, 5). Слеповгпелько, эти функции являются вычисничыми по Маркову.

ХМы-Шито»

§5, Замыканве, распространение нормального алгоритма ПустьА - произвольный нормальный алгоритм в алфавитеА.

226

Зпыыг.аинем алгоритм А называется алгоритм А ', полученный изА добавлением формулы подстановки Л-*»Л в качеств последней подстановки, т.е.;

№ -* (•&

U^M a

л-А... .

к -»(•)& IЛ-**Л

Нам wssecTHO, что тобой нормальный алгоритм закалчивает

подстановки, либо если все апоъъ?\,Р%Ръ.-, Р,:не содержатся а глове, полученном при предыдущем таге. Подстановка /]-*»/! применима клюбому слову. Следовательно, алгоритмЛ ‘заканчивает переработку слов всегда по заключительной подстановке, кспирая ctib либо некоторая из плдстанопок Рг-»(*)Р; !is is и) либо Л—>»Л

Отметим, что подстановка Л-у Л, добавленная к А для нолучгния Л \ стоит последней. Поэтому эта подстановка будет приме­ няться только тогда, когда не [фимекимы все подстановки алгоритма А, причем применение Л >»Л к либому слову не изменяет этого слапа. Следовательно, ргзупьтэты применения алгоритмов А и А' к любому слягу в А буду г совпадать; т.е. алгэретиы А а А' вполне эквивалентны.

Пусть А - нормальный алгоритм в алфавите А,, а алфавит А-, является расширением Ai, t.a AiizAi. Тогда можно рассмотреть

Очевисно, в алфавитеЛ,: ЛЕ'1') ^Л ‘(Р), ' (6.1)

т.е. А я А* вполне эквиваленты относительно А\. Нормальный алго­ ритм А"будем наэыцать естественным распространением А на алфа-

227

13 некоторых случаях удобнее, чтобы алгоритм А , удометворяющий (6.1), был по применим к тем словам в А% которые i* являются словами в А\. Гйош легко достигнуть, приписав к сльмвА сверху формулу вида *-«. гад * - люба» буква н* A,\A}.

8 6. Операции над нормальными алгоритмами

Кпмтмшгии алгогомов, ПустьА и В - два алгоритма и алфа­ вите А. Композицией алгоритмов Л и Я в алфавите А называют алгоритм Стекой,что^РпЛ: City zB[A(P)).

Таким образом, конгпвиция алюрнгмои А и Я представггпег собой алгоритм, шлучахшлийсп п результате последовательного при­ менения влтпигмов к данному слову Р. что-можно продсмоютрироааи, блок<хемой, представленнойна рис. 6.!,

Композиция алгоритмов А и В обо5иач&етс! как: ОДП. Пли

A,,At,--Ai ~ алгоритмы в шравите л, тогда под а^А*.? ... СЛ, будем пониматьследующее:

228

Теорема 6.1 Композиция нормальных алгоритмов Л[,Л1,...Ил]

аалфавитеA tan caosa нормальный алгоритм (налалфавитом/1).

1

Ясно, что достаточно оров*сти доказательство для композиции двух алгоритмов.

ДикизатЁЛЬство. I [yen. А и В нормальные алгоритмы в алфа­ вите А. Сопоставим каждой букве а из А новую букву а , которую назовем двойником буты а. При атом считаем, что идя любой буквы а ил А ее двойник не принадлежит А. Пусть А - алфавит, состоящий из всех двойников букв алфавита А Выберем какие-нибудь две Буквы, например, cl и 5, не принадлежащие А и Л . Обозначив через Аа схему, полученную ю схемы нормального алгоритма/*' зпменой в ней

Обозначим через 3 схему, полученную ья В* заиечой

формул подстановок вида A-*Q формулами подстановок о.-tag.

Рассмотрим схему:
о<х-.оа	М
п а - ю г	( - Н )
ab-*ab	(аМ А )
гв-»&«	(«4
р5-»Ца	(а *А)
	{аМ А)

В*

Эта схема представляет собой сокращенную запись некоторого нормального алгоритма С(в алфавите А и А и {а, р }), прмси в 1Н) буквы а и b означают произвольные буквы из А, а строки 8] и 9)

означают, что нужно ташкаи все подстановки сначала алгорита В!, затем алгоритма-*'

Покажем, чтонормальныйалгорнш Стакоа, что VP в А: С{В)=ЩЛ(Р),,

т е С есть композиция А и В. Пусть задано произвольное сково Р,

например,	Р =ak)ai!...aim (at eA ).	Сначала подстановки i)-8)
не применимы к Г, ибо буквы а, р и		буквы-двойники (алгоритм ?
залисан о	двойниках) не содержатся в слове Р, а также в 8) нет

подстановок пила Л-»Й, ибо они заменены на подстановки a-MxQ. Если алгоритм А не применим к слову Р (перерабатывал cm бескоиечни), то по 9) и Сбудете применим кР. Если Л Применим к Р, го врезультате мм получилибынекоторое словоЛ=Л.(Р).

Пусть, например, ^ = (i„ е А) . Известна, что алго­

ритмы .4 и.1' вполне эквивалентны, т.е. результаты их применения к любому слову из А совпадают. В § 5 отмечалось, чю алгоритм А' всегда заканчивает переработку слова заключительной подстановкой

^ -> •0 , либо Так как в А" вег заменены на "а",

ли в результате применения 9) получим, что и слове Я где-то вклн-

\ t ,1 i i /< t ) .

Применяя q раз подстановку I) к последнему слову, получим (а4(Р)).

После этого, применяя подстановку 2) и Ы раз подстановку 3), придем кслову

230