Файл: Кушнер, Б. А. Лекции по конструктивному математическому анализу.pdf

применим к тем словам в Л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 и

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

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