markov_teorija_algorifmov (522344), страница 52
Текст из файла (страница 52)
Значит, й', а потому и й, применйм к Р, что и требовалось доказать. 8.29. Если Р, Я вЂ” слова в А и 9(Р) Х Ч, той(Р) Х Я ° В самом деле, пусть Р, Я вЂ” слова в А, и пусть 9(Р) д~ 'с. Тогда й применйм к Р. Пусть й(Р) лг)с. Тогда й': Р' Р. Но тогда 9: аа,'а [Р')=иа",а [Л'ааьа [8,24]. Предположим теперь, что [Ее ~Г Л. Тогда в силу 8.18 В (аа'а [Я'аа;"и) определено и не является словом в Л. Но Ю тг 9(Р) т 9 (аа,'а [Р') в. В (аа',а [)т'аа,'а), и, значит, 1г не является словом в А, что противоречит условию леммы. Таким образом, [Ре.кЛ, т. е. Я есть слово в А.
Но тогда в силу 8.26 В (Р) ль)т. Значит, й (Р) А В(Р), что и оставалось доказать. 8.30. й сильно эквивалентен В относительно А [8.26, 8.29, 8,27, 8.28]. Таким образом, теорема 8.1 доказана. Дальнейшее усиление теоремы приведения в направле- ' нии дальнейшего уменьшения числа дополнительных букв, как уже отмечалось в начале параграфа, невозможно. 9. Теорема 6.22 доказана нами для некоторой конкрет- ной операции А перевода слов. Г.
И. С ы р к и н [1] нашел необходимые и достаточные условия, которые нужно нало- жить на произвольную операцию 3 побуквенного кодиро- вания слов в алфавите АБ для того, чтобы она сохраняла формулировку этой теоремы. ГЛАВА УНИВЕРСАЛЬНЫЙ АЛГОРИФМ В этой главе мы построим нормальный алгорифм иад данным произвольным алфавитом А, способный в известном смысле выполнить работу любого алгорифма в А,— «универсальный алгорифм» для алфавита А. Универсальный алгорифм, как и любой другой нормальный алгорифм, будет допускать в качестве исходных данных произвольные слова в своем алфавите.
Однако мы будем интересоваться лишь тем, как он работает над словами специального типа, являющимися комбинациями слов в А с линейно записанными (з 25.4) схемами нормальных алгорифмов в А. Здесь применяется тот же самый метод, что и в современных вычислительных машинах дискретного действия: не только исходные данные, но и предписания, устанавливающие последовательность применяемых действий, записываются в виде слов в надлежащем алфавите и вводятся в машину, способную „разбираться" в записанных предписаниях и выполнять их. Возможность такой записи предписаний Обеспечивается их стандартизацией, чему соответствуют у нас схемы нормальных алгорифмов.
Существование универсального алгорифма является центральным фактом общей теории алгорифмов — читатель вскоре сумеет оценить его важность. Разумеется, факт этот не является специфической особенностью теории нормальных алгорифмов: теоремы, аналогичные нашей теореме з 42.1.1, были известны для машин Тьюринга и для рекурсивных функций практически с момента выработки соответствукицих понятий. й 42. Формулировка теоремы об универсальном алгорифме 1. Перейдем теперь к точной формулировке теоремы об универсальном алгорифме. Мы будем считать фиксированным некоторый непустой ь) алфавит А такой, что попарно различные буквы а, (), у и ") Случай, когда алфавит А пуст, малоинтересен, н мы его не рассматриваем. В пустом алфавите имеется лишь два неэквивалентных лруг другу нормальных алгорифма, и оба они тривиальны.
28! »21 ФОРМУЛИРОВКА ТЕОРЕМЫ 6 не входят в А. Говоря о схемах нормальных алгориф- мов в А, мы будем иметь в виду у-схемы в алфавите Аар [$ 25.41 с обычным изображением формул подстановок. Схему нормального алгорифма Я в алфавите А мы будем называть изображением алгорифма 21. Изображение алго- рифма мы будем обозначать символом Я". Слово в алфавите Аа1)уб вида (1) Я'6Р, где Я вЂ” нормальный алгорифм в А, Р— слово в А, изобра- жает пару «алгорнфм Й и слово Р» в том смысле, что оно этой парой однозначно определяется и само ее однозначно определяет.
Первое очевидно, а второе ясно из того, что Р есть правое крыло единственного вхождения 6 в Я'6Р, Й" †лев крыло этого вхождения, а алгорифм Я опреде- ляется однозначно по Я'. К парам вида (1) естественно применять предписание: ' «построив по паре Я'6Р слово Р и алгорифм Я, применить затем Я к Р». Это предписание само составляет некоторый алгорифм, перерабатывающий Я'6Р в Я(Р), если алгорифм Й прнменйм к Р, и неприменимый к этому слову, если алгорифм Я непрнменйм к Р, Возникает вопрос о возмож- ности оформления такого алгорифма как нормального. Положительный ответ на этот вопрос дает следующая теорема.
1.1. Теорема об у н ивер с а л ьном ал г о рифме, Может бить построен такой нормальный алгорифм 11 над Ааруб, нто условное равенство (2) 11 (Я "6Р) Я (Р) имеет место для любых слов Р в А и норма ьных алгориф- мов Я в А. Доказательство этой теоремы составляет главное содержа- ние настоящей главы.
В настоящее время может быть предложено несколько раз- личных доказательств этой теоремы, опирающихся на пред- шествующие доказательства ее аналогов, в которых понятие изображения нормального алгорифма определялось чуть-чуть иначе. Первое по времени доказательство принадлежит А.
А. Маркову (1951 г.). Подробное изложение его составляет 1Ч главу его монографии [2]. В нем указывается основанный на теоремах сочетания прозрачный способ построения схемы универсального алгорнфма, но сама схема в явном виде не вы- писывается и сложность ее (см. з' 31.3 данной книги) не оцени- 282 УНИВЕРСАЛЬНЫЙ АЛГОРИФМ игл. и вается. В1орое по времени (1958 г.) доказательство принадлежит Э.С. О р л о в с к о м у П!. В нем приводится явная конструкция схемы универсального алгорифма, причем сложность схемы оказывается квадратично зависящей от и, где и — число букв алфавита А.
Впоследствии (1973 г.) Д. А. О с т р о у х о в 12) построил универсальный алгорифм со сложностью 10п+ +сопз1, а В. Г. Ж а р о в 12) — со сложностью бл+сопз1 (1974 г.). В последних двух доказательствах, рассчитанных на первоначальное определение изображения, аддитивные константы подсчитаны: они равны 426 и 296 соответственно. При переходе к определению изображения, принятому в данной книге, значения констант несколько изменились бы, однако это не затронуло бы значений коэффициентов при и.
. Конструкция и доказательство, приводимые ниже,— с точностью до деталей, ответственность за которые берет на себя второй из авторов книги,— восходят к В. Г. Жарову. Сначала в э 43 строится вспомогательный алгорифм В, являющийся легкой модификацией универсального алгорифма для двухбуквенного алфавита аЬ, а затем в $ 44 с его помощью путем надлежащего кодирования строится универсальный алгорифм для произвольного алфавита, й 43. Случай двухбуквенного алфавита 1. Мы введем буквы а„Ь,х, Л,рс,и,л,о,ф,ф,в, попарно различные и отличные от букв алфавита Ааруб Мы введем также «двойники» В) а, Ь,й,Л,(А, л,ф, тоже попарно различные и отличные от всех упоминавшихся предшествующих букв. Кроме того, нам будет удобно положить а а.
АлфавитчаЬ мы обозначим" буквой А„а алфавит А,ЯЛ(зф— буквой Б. Посредством х1 мы обозначим нормальный алгорифм в алфавите ББауиол1раис со следующей сокращенно записан- ~) Ср. 437.2. ЛВ1 й схемой: случАЙ дВухБукВеннОГО АлФАВитА где $ пробегает алфавит А„т1 — алфавит А,с4, Ь вЂ” алфавит А,аиду, 0 †алфав А,арув, с †алфав АсаДуфв, а )( †алфавит ар.
Строки схемы алгорифма В мы для удобства ссылок нумеруем, и в дальнейшем индекс 1 в записи х1: Х (- 1' будет указывать на номер строки, представляющей формулу подстановки, активную на слове Х, зс — с з йфй-йф $х- $х Ои — и'0 фу —. Уср )рси ф Ли 1и Луу уЛ(с )су — г и >Л(А фЬ вЂ” "кафф ф — ~. о'— ЛЧ ЧЛ ЛрХ вЂ” "А (с Лру "РЛ(с рй — й~4 Л вЂ” Л К-ф срф —. х фв — л 1с 'рс х — ~и — ио в — г ивялр <1, <2> <3> <4> <5> <6> <7> <8> <9> <1О> <11) <12> <13> <14) <15> <16> ,17> <18> <19> <20> <21> <22> <23> <24> <25> <26>, УНИВВРСАЛЬНЫИ АЛГОРИФМ случьи дВухвукВвнного АлФАВитА; 285 О АЗ! [гл. у 2.
Мы стремимся показать, что имеет место следующая теорема. 2.1. Длл любого нормального алгорифма Й в алфавите А, и для любого слова [е в этом алфавите имеет место условное равенство Е (ит['нь7~) н, 7[Й ([и!) (Здесь Я' означает замыкание алгорифма Й [з 35 21.) Следующие ниже леммы 2.2 — 2.5 в общих чертах проясняют работу алгорифма В.
2.2. Если Я вЂ” нормальный алгорифм в А„а йг — слово в Аи то ия. Я'иь7~ ) )Ч ~[ и ~,[и 2.3. Если [и' — слово в АнаРУ[Р7(хо, то З: 1руи! — у)рП. !7 2.4. Если Ь и 
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
