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


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

100
Дж. /7. Клав
1.2. Если а<&, то F(E&a) ^ E®(a+D и Cl(F (Е&а)) = Е® (а+\). 2. Если 2 — нормальное множество функций, то Ег с: Es, г < s < со2.
3.1. Ясли 2 — нормальное множество функций, а<со,
у _ ЫЛ+2.1] c-f*. 1]
то
3.2. s>0,
., хп, f (Xit
> ..., хп, G) — g\Xij ..., хп),
., *я, г/ + 1) = h (xit . . . , хп, у, f (xit . . . , хп, у) ),
l\ m = coo + max(r, 1).
нормальное множество функций, а < со, /г
'г w существует функция k^E[^+il], такая, что . . . , х„, г/),
= g(^i, ..., хп),
= h(xl, ..., хп, у, f(x:, ..., ^„, у)),
тогда f^Em ', где ш = соа + тах(г, s + t).
3.3. Если 2 — нормальное множество, тогда для всех г, г =< со2, Ег замкнуто относительно операций ограниченного суммирования и умножения, т. е. если [+l> 1]
1-", где
то
п,
=2mi r \х\> ...» xnt i),
\9 ..., хп, у)—
..., х
п,
Рекурсивные равенства, определяющие работу /-ограниченных машин, приводят естественным образом к получению классов Ег с помощью совместной итерации, с другой стороны, ограниченная рекурсия играет решающую роль в порождении классов (эг Гжегорчика. Так, (оп определяется как наименьший
класс функций, содержащий х + 1, U\(x, у] = x, Ul(x,y) = y, fn(x,y) и замкнутый относительно подстановки и ограниченной рекурсии, причем
для
f I (x ti\ = х 4-/1\Л> У) л ~
12 (Х> У) = (Х ~^
fn+i (О, У) = fn(y+l, У+1),
I fn + l (X + 1, У) = fn + l (X, fn+l (*> У))- .
|
(4)

 

1 10 20 30 40 50 60 70 80 90 100 101 102 103 104 105 106 107 108 109 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


Математика