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

Наметим доказательство этой теоремы. Обозначим через £)i такой нормальный алгорифм над А\, что при любых натуральных тип

!£>i {man)

и

композиции и объединения к алгорифму £>i и «высекаю­ щим» алгорифмам В2, Вц (см. стр. 72), легко построить нормальный алгорифм Ф 2 (над Ах) так, что при любых словах Р и Q в А и любых натуральных т, п

I5D2 (PamaQan)

и

(59)3)2 (PamaQan) = Л == m = п.

Аналогично, нетрудно построить алгорифм Ф 3 так,

что

(60)2>3 (PamaQan) ~ РатаЪ (PanaQ) an |.

Построим теперь нормальный алгорифм 3?4 как ви­ доизмененное повторение 5)3 с управляющим алгориф­ мом ф 2 (теорема 10) и рассмотрим композицию Фв этого алгорифма с алгорифмом 2D5 таким, что

S)s (Pam) ~ Pamal (Р) a0

(несложное построение © 5 с помощью теоремы объеди­ нения предоставляется читателю).

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

При т > 0 применимость £>6 к слову Рат равно­ сильна существованию цепочки слов Р 0 , Р\, ..., Рт та­ кой, что

Алгорифм Фб уже очень близок к искомому. В самом деле, по теореме композиции построим алгорифм g так, что

Ясно тогда, что применимость алгорифма (5 к слову Рат равносильна существованию указанной выше це­ почки Р0, ..., Рт, причем в случае существования та­ кой цепочки

Из (62) — (65) получаем

К (PaO) ~ 1 (Р),

6 (Pam + 1) ~ 23 (PamaS (Pam)),

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

Предлагаем читателю в качестве упражнения по­

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

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

точки и не принадлежащие А. Обозначим через Б ал­ фавит A U {офу}-

слово в алфавите Б, получаемое следующим образом: выписываются в порядке очередности формулы подста­

является слово аРу, а изображением алгорифма со схе­ мой

Р^Р2 Рз^-Р4

(где Pi, Р2, Рз, Pi — какие-то слова) является слово

Р1аР2уР3а^Р4у.

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

Имеет место следующая теорема, утверждающая су­ ществование универсального алгорифма при кодирова­

84 АЛГОРИФМЫ И ПЕРЕЧИСЛИМЫЕ МНОХ<ЕСТВА [ГЛ. I

букв. В таких случаях прибегают к более сложным спо­

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

нормальных алгорифмов в алфавит {0|}, использующая кодирующие буквы 0 и | (сохраняемый алфавит в дан­ ном случае пуст), и записью данного нормального ал­

Приведем два примера записей алгорифмов. В каче­ стве алфавита А возьмем в этих примерах двухбуквенный алфавит {ab}, а в качестве букв а, р\ у соответ­