Избранное
ЭБ Нефть
и Газ
Главная
Оглавление
Поиск +
Еще книги ...
Энциклопедия
Помощь
Для просмотра
необходимо:


Книга: Главная » Сборник N.N. Проблемы математической логики Сложность алгоритмов и классы вычислимых функций
 
djvu / html
 

70 Р. В. Ричи
Свойств классов Fiy описанных в теореме 6, достаточно, чтобы охарактеризовать эти классы. Мы сделаем это, определив сначала классы Fi, которые, как мы потом докажем, в точности совпадают с классами F*.
Определение 7. Для каждого положительного целого i класс Fi есть наименьший класс X функций,_ включающий <^2 и содержащий функции f\ of для любой f ^ FI-I, если i > 1, или f e F, если 1=1, который замкнут относительно явных преобразований, подстановок в ^-местные функции из Xk и ограниченной рекурсии по отношению к функциям от (&+ 1) аргумента, лежащим в Xh+l, для всех /е> 1. (Fi определены корректно, "поскольку существуют классы X, удовлетворяющие этим условиям, и, так как Хп П Уп = (X П Y)n, пересечение таких классов снова удовлетворяет условиям.)
Определение 7 предназначено для того, чтобы отразить свойства классов Fi, перечисленные в теореме 6, так что мы немедленно получаем, что Fi =; /*V Объединим непосредственные следствия из наших предыдущих результатов и этого определения.
Теорема 7. Для всех /^ 1 Ft<=. Fit Ft cz Fi + l, Ft =з <^2 и F{
Доказательство. Ft^ Ft по теореме 6, /^ci/^+! no
определению, ^2 cz Ft снова по определению. То, что /^ci^, очевидно, так как умножение и 2х лежат в_<^.
Перейдем к доказательству того, что Fi == Fi. Итак, каждая элементарная функция лежит в некотором Fi. Заметим кстати, что этот результат дает новое описание класса %> в терминах специального вида подстановок и рекурсий, появляющихся выше в определении 7.
Чтобы ^завершить описание классов Fh мы хотим доказать, что Fi ^ /V Для этого мы берем за образец доказательство
того, что Ff ^ ?*~, т. е. мы определяем Tln, z ^ (F^ и С/я, 2, Ьгп, и показываем, что если f^Fit то
f (х) = U п. z (x, min у^Ъ1п,г (х) \Тп, z (х, у)] ). Мы покажем в действительности, что
mmy^bntZ(x)[Tn>z(xt у)}
определяет функцию из Ft и что Un.z^F. Таким образом, будет показано, что /(х) есть результат подстановки функции
из FI в (п+ 1)-местную функцию из F?+ _и, следовательно (по определению 7), /(х) должна лежать в F(. Докажем сначала

 

1 10 20 30 40 50 60 70 71 72 73 74 75 76 77 78 79 80 90 100 110 120 130 140 150 160 170 180 190 200 210 220 230 240 250 260 270 280 290 300 310 320 330 340 350 360 370 380 390 400 410 420 430


Математика