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


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

20 А, Гжегорчик
Операция ограниченной рекурсии. Класс S6 замкнут относительно операции ограниченной рекурсии, если он удовлетворяет следующим условиям:
если g, /г, I — функции класса <% и функция f удовлетворяет условиям
(a) f(u, 0) = g(u), (I) (b) f(u, х+1) = Л(и, x, f(u, (c) f(u, x) то функция f также принадлежит классу
Условия (а) и (Ь) — обычные условия рекурсивных определений функций, применяемых в арифметике.
Условие (а) определяет начальное значение f, а условие (Ь) выражает значение / для следующего числа в зависимости от ее значения для предыдущего числа с помощью функции Я. При этом значение f определяется для каждого значения переменного х. Таким образом, функция f(utx) однозначно определяется условиями (а) и (Ь). Условие (с) ограничивает зту возможность определения теми функциями, которые не превосходят некоторую другую функцию, содержащуюся в классе
Примеры. Если класс $6 замкнут относительно операции ограниченной рекурсии 1) и содержит функции S(x) = х + 1 и ху, то он также включает функции х + у и х- у, поскольку эти функции могут быть определены посредством ограниченной рекурсии. Полагая
8i (У) = ^2 (У. У)> AI (у> х, г) = С/2 (У* U z (x, S (г)
можно легко доказать, что функция f(ytx) = y + x удовлетво ряет схеме
(a) f(y,Q) = gi(y),
(A) (b) f(yt д;+1) = Ы#> х, f(y, x)), (с) f(yt xXji(y, х).
Имея функцию у + х, аналогичным образом положим g2(y) = U2(y> 0), hz(y, к, z) = U2(xt y + z) и видим, что умножение удовлетворяет условиям
(а) у-0 = 82(у)> (В) (Ь) У'(Х+ 1) = А2(у, х, у • _ (с) y>x^h(y> х).
1) И подстановки. — Прим. ред.

 

1 10 20 21 22 23 24 25 26 27 28 29 30 40 50 60 70 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


Математика