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


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

120 П. Акст
очевидны. В случае 4 ф (а\> ..., ak) = ty (xi (аь ..., afe), ... • ••> Xm(ai* • ••» afe))- По допущению индукции по глубине ф и вследствие монотонности YO существуют числа &0, blt ..., bm>
такие, что для a^max[ab ..., ak]y i= 1, ..., m,
0(^ a).
Заметим, что fr = max[&0> &i» • ••» W может быть использовано для замещения в этих неравенствах Ь0 и bit Таким образом, ^(ср ..., cm)> a), i= 1, . . ., m. Отсюда
если а = тах[а!, ..., afe] 1). Таким образом, для любой (p и для a = max[ai, •••> ak]>b имеем ф(^1, ..., «ft) сивная относительно х. Следовательно, базис индукции по п доказан.
Для п^О определим функции Y^ и уп следующим образом:
Пусть Нп+\ — класс функций, полученных примитивной рекур-
сией с вспомогательными функциями из /С«- Предположим по индукции, что Y^ и уп возрастающие и примитивно рекурсив-
ные и что для каждой фе/(? существует число Ъ, такое, что если а = max [ар . . ., aft], то ф(ар . . ., flft) и если к тому же а является достаточно большим, то ф(#1, . . ., ak) < Yn(a)>
!) В оригинале Yo(^>Yo(^> a)) = YO (2? + 1, а), что, как легко видеть, неверно:
b+ 1 раз b+ 1 раз В то же время
YQ (2& + 1, а) = х (х ( . . . и (а') ...)).
26 + 2 раза ~-Прим. перев

 

1 10 20 30 40 50 60 70 80 90 100 110 120 121 122 123 124 125 126 127 128 129 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


Математика