книги из ГПНТБ / Кушнер, Б. А. Лекции по конструктивному математическому анализу

Условимся для краткости при произвольном нату­ ральном k обозначать через к слово, получающееся из k выбрасыванием буквы «0», а через къ, к'ъ слова, полу­ чающиеся из к заменой всех букв «|» соответственно на

Обозначим последнее слово через Q. Чтобы получить искомый результат, достаточно выбросить из Q слово «, п» и заменить всюду букву «Ь» на «|». Именно это и происходит. По формулам (20) — (24)

букв. Теорема о переводе. Теорема приведения. Чита­ тель, наверно, обратил внимание на то, что в последних примерах предыдущего пункта для построения нормаль­ ных алгорифмов, определенным образом работающих на словах в данном алфавите, приходилось использовать вспомогательные буквы, т. е. строить эти алгорифмы в более широком алфавите, чем исходный. Можно показать, что это обстоятельство не является случай­ ным— например, невозможен нормальный алгорифм

Для доказательства теорем 2—3 достаточно опреде­ лить перевод из алфавита рассматриваемого нормаль­ ного алгорифма (являющегося расширением алфавита Л) в Л U {ар}, использующий кодирующие буквы а и р и сохраняющий алфавит Л. В качестве искомого алго­ рифма в алфавите Л U {ар} можно, ввиду теоремы 1, взять перевод исходного нормального алгорифма. Из

Теоремы 2—3 показывают, что любое алгорифмическое преобразование слов в алфавите Л, которое может быть выполнено нормальным алгорифмом над Л, может быть выполнено также и нормальным алгорифмом в

ным образом перерабатывающие слова в алфавите Л снова в слова в Л, то достаточно рассматривать нор­ мальные алгорифмы в каком-нибудь фиксированном (стандартном) двухбуквенном расширении алфавита А. Для этого расширения мы будем обычно использовать

т. е. 91 и 91' вполне эквивалентны относительно А\. Нор-

применим к тем словам в Л2 , которые не являются сло­

лучившийся нормальный алгорифм, называемый фор­

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

7. Теоремы сочетания нормальных алгорифмов. При практическом построении алгорифмов часто применяются приемы, состоящие во включении в искомый алгорифм в тех или иных сочетаниях уже известных ранее алго­ рифмов.

В этом пункте приводится ряд теорем, позволяющих строить некоторые новые нормальные алгорифмы, исполь­ зуя уже построенные алгорифмы. Эти теоремы показы­ вают, что практически важные способы комбинирования алгорифмов воспроизводимы в теории нормальных алго­ рифмов, т. е., будучи примененными к нормальным алго­ рифмам, они дают снова нормальные алгорифмы. Исполь­ зование теорем сочетания нормальных алгорифмов по­ зволяет, кроме того, в большинстве случаев существенно

3'

сводятся к построению схемы искомого нормального ал­

рифма.

1) Композиция нормальных алгорифмов. Одним из наиболее часто встречающихся способов комбинирова­

хода к общему случаю достаточно воспользоваться фор­ мальными распространениями (см. п. 6) 21 и 23 на объ­ единение их алфавитов).

Итак, пусть 91 и 23 — нормальные алгорифмы в алфа­ вите А. Сопоставим каждой букве п этого алфавита не­ которую новую букву fj, не принадлежащую Л, таким образом, чтобы разным буквам Л отвечали разные бук-

*) Если Ш — нормальный алгорифм в алфавите А{ н Н не является словом в этом алфавите, то выражение Ш(Р) считается лишенным смысла.

вы. Букву fj назовем двойником г). Двойники букв алфа­ вита Л, очевидно, образуют новый алфавит, который мы обозначим через А. Обозначим далее через а и $ две различные буквы, отличные как от всех букв Л, так и от всех букв А. Перейдем от алгорифма 21 к его замыка­ нию 2Г (см. п. 3 — напомним, что схема 2Г получается из схемы 21 присоединением снизу формулы -*-•) и за­ меним в схеме 21' каждую точку буквой а. Получив­ шуюся систему формул обозначим через 2Ха. Построим также систему формул 23а, получаемую из схемы 33" по­ средством замены всех букв алфавита А их двойниками, замены всех точек буквами р и после этого замены всех

(заметим, что именно с этой целью — отличать формулы алгорифма 23 (им соответствуют формулы группы (37)) от формул 21 — и вводились двойники). Далее, поскольку группа формул (38) содержит формулу с пустой левой частью (такова последняя формула этой группы), то применяется одна из формул группы (38). Алгорифм (5 воспроизводит работу алгорифма 21" (а следовательно, и 21). При этом, если

21:P K Q ,

ТО

6: Р \=nQ,

и, таким образом, из неприменимости 9 к Р вытекает неприменимость 6 к Р. Пусть теперь 91 применим к Р и

Q —Q,Q2 ,

выполняется

6:P\r=QlaQ2.

б) Применяются формулы группы (30), в резуль­ тате чего а «бежит» влево (при пустом Qi этот этап от­ падает) :

(Е: Qi<xQ2 h= ceQ,Q2.

варительно, однако, поскольку группа формул (37), представляющая алгорифм 93, записана в двойниках,

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

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

в частности, то обстоятельство, что при построении 93а

в формулы с пустой левой частью вставлялось а ) , что если

то

S:aQ\=naS.

Отсюда, ввиду (40) — (41), получаем, что если 53 не­ применим к Q, то (Е не применим к Р.

Пусть теперь S3 применим к Q и

что и требуется.

Заметим, что вполне строгое доказательство равен­