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

Скачать файл
Заказать решение

ВУЗ: Не указан

Категория: Не указан

Дисциплина: Не указана

Добавлен: 15.10.2024

Просмотров: 143

Скачиваний: 0

ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.

62

АЛГОРИФМЫ

I I ПЕРЕЧИСЛИМЫЕ МНОЖЕСТВА

[ГЛ. 1

со схемой

 

 

 

(16)

 

 

 

(17)

 

а —>

 

(18)

ь\->\ь

 

(19)

| ,

0 - > , 0а

 

(20)

00 — 0

 

(21)

,

о - о ,

 

(22)

,

1-*,

 

(23)

.

6 - 1 ,

 

(24)

 

 

 

и

покажем, что

Ям (m, п)~ т

 

 

 

 

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

букву

«6»

и слово

«|6».

Например,

если

& = 0 | | | ,

то

* = Н I I . кь=^ЬЬЬ,

 

 

к'ь^\Ь\Ь\Ь.

 

 

 

 

 

 

Рассмотрим сначала случаи обращения в нуль ка­

кого-нибудь из сомножителей.

 

 

 

 

 

 

а) т = 0. Формулы

(16) — (19)

применяться не

мо­

гут. Используется

формула

(21), затем

(20):

 

 

 

 

Я „ :

0,

п

b

00,

п

НО,

п.

 

 

Далее,

очевидно

((22),

(24)),

 

 

 

 

 

Итак,

 

 

Ю,,: 0,

 

rtf=0,

 

Н О .

 

 

 

 

 

 

%i

(0, п)==0.

 

 

 

 

 

 

 

 

 

 

 

 

 

б)

п =

0.

Поскольку

случай

т

=

0 уже разобран,

можно

считать,

что

т >

0.

Тогда

т

заканчивается

буквой

« | »

и ((19),

(17))

 

 

 

 

 

 

 

 

 

Я и : т, O h m - 1 , 0а H m — 1, О Н О . 0.

 

Наконец

((21)-(20), (24)),

 

 

 

 

 

 

 

 

 

Я „ :

0,

0 Н 0 0 ,

НО,

Н - 0 .

 

 

 

НОРМАЛЬНЫЕ АЛГОРИФМЫ

63

Итак,

и в этом случае

 

 

 

 

«R,,(m, 0) =

m-0 =

0.

 

в) т >

0, п > 0. Очевидно

((19)),

 

 

ЭДП: т,

п\-т—\,

Оап.

Далее

((16) — (17))

«а» «проходит» через п, оставляя

у каждой буквы «|» букву «6»:

 

 

9tn : т — \,0ап\=

т — \,0nrba

\-т

— \,0п'ь.

Затем

буквы «Ь» «проходят» вправо

((18)):

 

91п : т — 1,0п'ь \= т — 1 ,ппь.

После т таких циклов получим

 

 

 

ЭТП: т,

n\=r0,nnbnb . . .

пь.

 

 

 

т раз

 

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

9?п: Q I - OO.nrtj . . . гц (- 0,п/ц . . .

«jj =

 

 

m раз

т раз

 

 

 

f= 0,% . . . ПЬ |= 0Я . . . Я,

г- • ОД . . . П-

 

 

т раз

/п раз

т раз

Последнее натуральное число, очевидно, и есть m-n.

Итак,

всегда

(т, п)~т

• п,

 

 

9?п

 

что и требовалось.

 

 

 

5.

Регламентация

использования вспомогательных

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

64

АЛГОРИФМЫ И ПЕРЕЧИСЛИМЫЕ МНОЖЕСТВА

[ГЛ. 1

в алфавите Л, содержащем не менее двух букв, обра­ щающий все слова в А (ср. Н а г о р н ы й [2]). В связи со сказанным возникает вопрос: как сильно нужно расши­ рять исходный алфавит, чтобы получать всевозможные преобразования слов в этом алфавите, вообще доступ­ ные нормальным алгорифмам. Этот вопрос решается теоремой А. А. Маркова о переводе ( М а р к о в [2]), по­ казывающей, что всегда можно обойтись (если нас инте­ ресуют преобразования слов в данном алфавите) всего двумя вспомогательными буквами, т. е. двухбуквенным расширением исходного алфавита*).

Пусть

А — некоторый алфавит (возможно,

пустой),

буквы

а,

р,

уь

• • •

I Уп не входят в А, а отлична от Р

и все

\{,

у,

(i ф

])

различны.

(Однако буквы

а,

р мо­

гут, вообще

говоря,

совпадать

с некоторыми

из у\.)

Рас­

смотрим

алфавиты

 

 

 

 

 

 

 

(25)

 

 

 

Л, =

Л [Дар},

 

 

 

 

(26)

 

 

 

Л2

=

Ли{у,У2

••• УпЬ

 

 

 

Сопоставим

каждой

 

букве

у<

( 1 ^ ' ^ я )

слово

вида

(27)

 

 

 

 

 

ар

. . _ Р а

 

 

 

tраз

иназовем это слово переводом буквы yt. Переводом про­ извольной буквы алфавита А назовем саму эту букву.

Перевод буквы г\ (алфавита А2) будем обозначать по­ средством [т]т. Пусть теперь

Р=f= 4l • • • Л*

— произвольное (непустое) слово в алфавите Л2 . Под переводом Р мы будем понимать слово

К• • • Не­

очевидно, являющееся словом в алфавите А\. Перевод Р будет обозначаться через [Рх. Переводом пустого слова считается пустое слово (т. е. [ Л т =т= Л ) .

*) Как показал Н а г о р н ы й [1]—[2], всегда достаточно даже одной вспомогательной буквы, т. е. однобуквенного расширения ис­ ходного алфавита.

§1]

НОРМАЛЬНЫЕ

АЛГОРИФМЫ

65

 

Отметим, что для любого слова Р в алфавите А

 

(28)

[ЯТ =

Р,

 

и обратно, если для Q е А2

выполняется [ Q T e / l ,

то

Q e

А.

 

 

Описанный только что способ кодирования слов в ал­ фавите Аг словами в алфавите А\ обладает, как можно

показать (М а р к о в [2; гл. 1, § 6]), свойством

однознач­

ности:

[PX=^[QX

для

произвольных

слов Р

и Q

в А2

тогда

и только тогда,

когда Р — Q.

В приводимой

ниже

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

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

Пусть 21— нормальный алгорифм в алфавите (26). Заменим в схеме 21 левую и правую часть каждой фор­ мулы подстановки на ее перевод. В результате полу­ чится некоторый нормальный алгорифм в алфавите А\ ((25)), который мы назовем переводом 21. Оказывается, перевод 21 работает над переводами слов в алфавите А2 точно так же, как 21 работает над самими этими сло­

вами, точнее говоря, имеет место

 

 

 

 

Т е о р е м а

1 (теорема

о переводе: М а р к о в

[2; гл. 3,

§ 7]). Пусть

21 — нормальный

алгорифм

в алфавите

An

((26))

и

21 — перевод

этого

алгорифма.

Тогда

для

лю­

бого слова

Р в алфавите Ач

 

 

 

 

 

 

 

 

 

Й ( | р т ) ~ [ 2 1 ( Р ) т .

 

 

 

В

частности,

когда

Р — слозо

в А и

21 перерабаты­

вает Р в слово в А, то

((28))

 

 

 

 

 

 

 

 

 

21 (Я) =

21 (Р).

 

 

 

Таким образом, имеет

место

 

 

 

 

Т е о р е м а

2

(теорема

приведения: М а р к о в [2; гл. 3,

§ 7]). Пусть а и

р — две

различные

буквы,

не

принадле­

жащие алфавиту

А. Тогда

всякий

нормальный

алгорифм

3 Б. А. Кушнер

66

АЛГОРИФМЫ

И

ПЕРЕЧИСЛИМЫЕ

МНОЖЕСТВА

[ГЛ. 1

над А

эквивалентен

относительно

А

(см.

п.

1)

некото­

рому

нормальному

 

алгорифму

в

алфавите

A

U {ар}.

Отметим следующий важный частный случай тео­

ремы

приведения.

 

 

 

 

 

 

 

 

 

 

Т е о р е м а 3.

При

условиях

теоремы

2

всякий нор­

мальный алгорифм

над А типа

(Л-г* А)

вполне

эквива­

лентен

относительно

А

(см.

п.

1)

некоторому

 

нормаль­

ному алгорифму

в алфавите

A U {оф}.

 

 

 

 

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

теоремы о переводе, очевидно, также

вытекает

 

 

 

С л е д с т в и е

1. При

условиях

теоремы 2

для

вся­

кого нормального

алгорифма над

алфавитом

А

может

быть построен нормальный

алгорифм

в

A

U {ар},

приме­

нимый

к тем и

только тем словам

в

А,

к

которым

при­

меним

исходный

алгорифм.

 

 

 

 

 

 

 

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

двухбуквенном

расширении Л. Таким образом, если

нас интересуют

нормальные алгорифмы, определен­

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

обозначение

Аа.

 

 

 

6.

Распространение нормального алгорифма на более

широкий

алфавит. Пусть

91— нормальный

алгорифм

в

алфавите

А{

и алфавит Л2 является расширением

А\.

Тогда

можно

рассмотреть

нормальный

алгорифм

91'

в алфавите Л 2

с той же самой схемой, что и 91. Очевидно,

для

любого слова Я в Л]

(29)

 

21 (Р) ~ %' (Р),

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

Смотрите также файлы