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


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

I. КЛАССИФИКАЦИЯ РЕКУРСИВНЫХ ФУНКЦИЙ
НЕКОТОРЫЕ КЛАССЫ РЕКУРСИВНЫХ ФУНКЦИЙ1)
Л. Гжегорчик
ВВЕДЕНИЕ
В этой статье исследуется возрастающая последовательность ?Г1,... классов рекурсивных функций. Каждый класс &п замкнут относительно операций подстановки и операции ограниченной рекурсии. Исходными являются примитивно рекурсивные функции. Поэтому <$п с $2, где $2 —класс примитивно рекурсивных функций. Говоря точнее, <й? = S %*"• Следовательно, в опре-
п
делении класса $2 операцию рекурсии нельзя исключить или заменить операцией ограниченной рекурсии.
Отдельно рассматриваются классы &0 и 1. ПРЕДВАРИТЕЛЬНЫЕ ЗАМЕЧАНИЯ
1. Функции, нумерующие пары. Мы назовем функциями, нумерующими пары, каждую тройку функций Я, Q, /?, определенных над неотрицательными целыми числами и удовлетворяющих следующим условиям:
(1) P(Qz, Rz) = z,
(2) Q(P(xt y)) = x,
(3) R(P(x, у))-у.
Функции, которые удовлетворяют этим трем формулам, устанавливают взаимно однозначное соответствие между множеством пар неотрицательных целых чисел и всем множеством неотрицательных целых чисел. Функции Q и R являются обратными для функции Р. Первый элемент пары, представимой z, является значением функции Qz, а второй элемент есть значение Функции Rz.
^Grzegorczyk A., Some classes of recursive functions, Rozprawy Matematiczne, IV, Warszawa, 1953.

 

1 2 3 4 5 6 7 8 9 10 20 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


Математика