Введение в дискретную математику - Яблонский С.В.
Скачать (прямая ссылка):
Если р = 1, т. е. ф' Ф а„, то;
7) Оператор 0(2) очищает 2-ю решетку.
8) Оператор Л+(р, 1) увеличивает код у на 1-й решетке на единицу.
9) Оператор 11(1,2) переносит код с 1-й решетки на
2-ю и возвращается к оператору 3).
Если р = 0, т. е. ф' = ап, то:
10) Оператор 0(2, 3) очищает решетки 2 и 3.
11) Оператор 0(1) стирает на 1-й решетке все, кроме первого, массивы из единиц.
12) Оператор К3 преобразует квазпосновной код в основной код и останавливается.
Операторная схема имеет вид
*Н3 ФТіДґД~/\%)^ 0ж(«п)ФК)Кп№)Рв\ ВітЩй
При реализации отдельных операторов необходимо учитывать их согласование и простановку единиц на 3-й решетке в пределах рабочей зоны. Теорема доказана.
Замечание. В доказательстве используется по существу тот факт, что если хоть одно из значений ф(аі, ...
ап-и 0), ф(а1? ..., ап_1} (.і*— 1) не определено,"то
/(аь ..ап) также не определено.
Теорема 4. Класс Рвыч замкнут относительно систе-мы операций Л = {С, Пр, р).
Следствие. Рчр^Рвыч.
Данная теорема дает возможность устанавливать вычислимость функций, не прибегая к построению машин Тьюринга, путем доказательства их частичной рекур-сивности.
Примеры: а) На стр. 149 построен ряд примитивно-рекурсивных функций. В силу доказанного они являются также и вычислимыми,
11 С. В. Яблонский
|62 Ч. I. ФУНКЦИОНАЛЬНЫЕ СИСТЕМЫ С ОПЕРАЦИЯМИ
б) Пусть 1(х) = х*. Очевидно, что /^Р«р, так как /(0) = 0, {(х+1) = }(х)+2х + 1.
Следовательно, / ^ Р
ВЫЧ*
§ 7. Формула Клинп. Частичная рекурсивность . вычислимых функций. Примеры полных систем
Этот параграф мы начнем с установления примитивной рекурсивности некоторых функций.
1. Пусть р(г) обозначает число разрядов, содержащихся в двоичной записи числа х. Очевидно, что
Р(0)“ 1, _
р{х Ч- 1) = р(ж) Ч- Sg(2p(*) [х + 1))'.
Следовательно, р (#) ^ Рпр.
2. Пусть хп) обозначает натуральное число,
двоичная запись которого имеет вид
1 ... 1 0 1 ... 1 ...01...1
х1 + 1 *а + 1 хп+1
Примитивная рекурсивность доказывается индукцией по п:
0.(0) = 1,
*1(аг1 + 1)-2&, (*.)+!,
хл-и 0) = 4^п-|(л?!, яп_.)'Ч-1,
0« (*^1, . • Хп— I, Хп Ч- 1)== 2'0’й (лч, ..Хп—1, Д'п) Ч-1.
3. Рассмотрим функцию я(,ач, х2) (см. табл. 20). Эта функция называется пеаноеской функцией и служит для нумерации всех пар (сч, а2) чисел из расширенного натурального ряда. Очевидно,
я(1и^_^?зЖ±^±Ч
1. е. является примитивно-рекурсивной.
4. С пеановской функцией л(лч, х2) связаны Я{:г) и
р (ж). Пусть Я (х) = л (0, х)
,т. е. функция Я (я)
ГЛ. 4. ВЫЧИСЛИМЫЕ ФУПКЦИИ 163
задается первой строкой табл. 20 для я. Значит, Я(я:)^Рпр.
Определим функцию р(я) через табл. 21. Из таблицы видна связь функций л, А и р,: значения функции я пробегают расширенный натуральный ряд и они делятся
Таблица 20
х\ 0 1 2 3 . . .
0 0 1 3 6
1 2 4 7 ? - -
2 5 8
3 9
диагоналями + х2 = с) на конечные куски; если а (а е Е к 0)~ произвольное значение из таблицы для л, то р(а) указывает номер с диагонали, на которой находится а, а Цр{а)) —наименьшее число из Ец0, лежащее на этой диагонали.
Таблица 21
X 0 1 2 3 4 5 6 7 8 9
р(;г) 0 1 1 2 2 2 3 3 3 3
Из этих соображений имеем
р(0) = 0, ^
р(я + 1) = р(а;)+8§ {рг (а) — (а: Я (рі (аг)))}*
Поэтому ц(х)єРвр.
5. Пусть {аи а2) — произвольная пара. Тогда ч = •=л(а1( аг) — ее номер. Обозначим через Цх) и г(:г) функции, которые по номеру ч пары (а(, а2) дают ее 11*
164 Ч. I. ФУНКЦИОНАЛЬНЫЕ СИСТЕМЫ С ОПЕРАЦИЯМИ
компоненты и а2. Таким образом, — и г(у) = а2. Данные функции удовлетворяют тождествам
л(Дя), г{я)) = Я, Я2))* Хи Г(л(я„ Я2))^Я2.
Так как
/(я^я^ЛЫя)), г(я)=р(я)-М(я),
то Цх), г{х)^Рир.
С. Функции л, / и г могут быть обобщены па случай многих переменных. Пеановская функция лДя(, .я») определяет номер 5-ки (а,, ..аД чисел из расширенного натурального ряда, а функции ?Дя), ..., (Дя) указывают по номеру $-ки значения ее компонент, т. е. числа
СС(, . .ССа.
Для 5 = 3 данные функции определяются так: кЛхи х2, яЕ) = л(яь я(я2, яа)),
Ъ(х) = 1(х), к(х) = 1{г(х)), (з(я) = г(г(я)).
Очевидно, что Л8 {и (л) , и (г), и (я)) = Я, и (Л3 (яи Я2, хг) ) аа Хи 1г(п3(хи Х2, Яз))^Я2, «з(л*(лг1, Я2, Я3) ) = Ял.
Из определения следует, что Лз(яи я2, яД, (Дя), (Дя), (3 (я) принадлежат Рпр.
Для дальнейших рассмотрений нам понадобится один способ построения функций.
Пусть я = (яь я*) и функции /Дя, у), /Да:, у)
заданы при ноыощи схемы одновременной примитивной рекурсии:
/Дя, 0)= фДя),
| ? I I
/Дя, 0)= фДя),
А (я, У + 1)“-ф*(а:, у, /Дя, у) /Дя, у)),
/Д*. г/ + 1} = фДя, у, /Дя, у), /Дя, I/)),
представляющей естественное обобщение схемы примитивной рекурсии. Эту схему используем для случая, когда ф„ ..., ф„ ф* примитивно-рекурсивны. Покажем,
что эти функции могут быть получены из функций фц . * ч Ф», фи ..ф., а также примитивно-рекурсивных
функций зт„ tu ..., f, при помощи суперпозиций и примитивной рекурсии.
Рассмотрим функцию
Цх, р) = я.(Л(;Г, у), /.(л, у));
мы имеем
Их> 0) = М/,(я, 0)‘, /.(Л, 0)) = яв(гр,(4, <Р-(?»))'.
/(яг, У + 1) = п.(А(л:, у+1), tf+1))-
р, Д(г, у), /.(л, I/)), ...
