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


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

ПО Дж. П. Клив
что для всех X справедливо g(X) < /*(m, max X). Фактически в силу леммы 4.2 необходимо только показать, что для любых Nun существует т, такое, что FN(n,x) Теперь f(n,x)>n+\. Следовательно, F0(n, x)^Fn(Q, x). Индукцией по N и т получаем FN(n, x)^.FN+n(Q, x), Fm(Q, л;)< Теорема 2.2 следует теперь из леммы 5 и следствия 6.
7. ОГРАНИЧЕННАЯ РЕКУРСИЯ
Пусть S — класс функций. Функция f определена ограниченной рекурсией из S, если существуют такие функции g, h, k e 5,
что
f(xi, ..., хп> 0) = g(xi, ..., хп),
f (v v 11 I 1 \ — ti Iv v // ri v v 11 \ I
/ \AI, . . ., xn, у ~r i) — п\л\, . . ., лл, i/, / \л\, . . ., лп, */; ^,
ill'* v* //1 ^^L^ f? i "V* v* //i
Из леммы З следует, что если g, Ле?(2)ш, то можно построить для f SL 2-программу я. Если 2 нормальное и ?е?(Е)щ, лемма 4 и следствие 4 позволяют отыскать границу для С-пре-дела я в одном из классов ?(2)г; таким образом, для f имеем:
Лемма 6. Пусть 2 — нормальное множество функций.
Tit i о 11 Гм _i 1 11
От-ч f ^^__ f-i /VI \litH-Z. 1 / _ j~i / VI \ I'*' ~Г -1 » * J ?/ \/^ /Л\ / \^ \
Если he=E (2)}) ^ , gе ? (S)J- м если f (л, 0) = g(X),
i 1 \ L. / V -Р / V^ \ \ -Р ^-'-'•* С1 / V^\ l^ "i"^»^J / 1\
2) ?сли Ле?(2)д+2* ^, s>0, ^e?(S)r 1] и существует такая
функция /ее ?(S)[n+1> 1]» чго <5ля всех Х^Ып справедливо f(X, y)^k(Xy у), где f(Xt Q) = g(X), f(Xt y+\) = h(XJ y> f(Xt y))t
Пусть f(X, y) = 2 F(X, /), g(X, у)— Ц F(X, /). Из леммы
3.1 следует, что если Fe ?(2)f+1> 1], то f, gre?(2)Jl+1'11. Таким образом, каждый класс ?(2)г замкнут относительно операций ограниченного умножения и суммирования. Более того, если 2 —нормальное множество, то класс ?(2)ш замкнут относительно ограниченной рекурсии.
Пункты 1, 2, 3 теоремы 2.3 сразу следуют из лемм 5 и 6.
8. ИЕРАРХИЯ ГЖЕГОРЧИКА КЛАССОВ ПРИМИТИВНО РЕКУРСИВНЫХ ФУНКЦИЙ
Для установления результатов этого раздела целесообразно свести совместную итерацию к простой итерации, используя функции, нумерующие пары. Пусть 2 = С/(2*U{/,/(, L}).

 

1 10 20 30 40 50 60 70 80 90 100 110 111 112 113 114 115 116 117 118 119 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


Математика