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


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

'130 Добавление редактора
Представляют интерес некоторые проблемы, связанные с двойной рекурсией (проблемы 6 и 9 статьи Гжегорчика, стр. 46). Операция ограниченной («bounded») двойной рекурсии R2-b над функциями G, Я, h и Е определяется так:
F (О, х) = h (x),
F(n+lt 0) = Я(я+ 1, F(n, F(n, 0)), F(n, 0)), F(n+ 1, jc+l) = G(n + l, x, F(/i + 1, jc), F(n, f(/i, * + 1))),
(Без последнего неравенства имеем обычную упрощенную схему двойной рекурсии R2.)
Нетрудно показать, что операция R2-b, будучи применена к функциям G, Я, h и Е из класса (^г, дает функцию из класса ?ГГ+1. Марченков установил, что замыкание класса тельно операции R2-b (класс <§ГГ+1) есть в точности подкласс класса ?ГГ+1, состоящий из функций, ограниченных функциями
из <^г (так, например, Таким образом, класс HI примитивно рекурсивных функций замкнут относительно ограниченной двойной рекурсии. Инте-
ресно отметить, что классы %>г (r^-З) не имеют конечного базиса относительно суперпозиций. (Этот факт установлен студентом МГУ В. Альперовичем в 1968 — 1969 гг.) Аналогичные результаты должны иметь место для ограниченных ^-кратных рекурсий.
Классификацию Гжегорчика можно продолжить, взяв последовательность функций (hn(U)(x)} (и = О, 1, 2, . . .) из [10], где л(0)— 1, п(и+ \) = 2п(и\ а через Су обозначается класс функций, примитивно рекурсивных относительно hy(x) (n(u) является обозначением для ординала, соответствующего натуральному числу и в системах О и О' Клини [10]). Однако можно построить последовательность значительно более простых, чем hn(U)(x), функций еи(х), порождающих классы Cn(U) посредством лишь суперпозиций и примитивных рекурсий, основываясь на скорости роста еи(х), причем eu+i(x) будет получаться из еи(х) с помощью одной двойной рекурсии. Идея построения еи(х) такова: е\(х) = В(х, я), где В (/г, х) — функция Аккермана, а п — число примитивных рекурсий, необходимых для получения функции hxB(n,x]. Далее берем итерации функций ei(*): /(0, я) =е\(х), fi(n+ 1 , х) == ei[f ( п, х) ]. Пусть /1 (х) = f (х, х) (диагональная про-

 

1 10 20 30 40 50 60 70 80 90 100 110 120 130 131 132 133 134 135 136 137 138 139 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


Математика