Математическая энциклопедия - примитивно рекурсивная функция

функция от натуральных аргументов с натуральными значениями, к-рую можно получить из простейших функций

конечным числом операций суперпозиции и примитивной рекурсии.

Поскольку исходные функции являются вычислимыми, а операторы суперпозиции и примитивной рекурсии вычислимость сохраняют, множество всех П. р. ф. есть подкласс класса всех вычислимых функций. Каждая П. р. ф. задается описанием ее построения из исходных функций (примитивно рекурсивное описание) и, следовательно, класс всех П. р. ф. счетен. Практически все арифметич. функции, употребляемые в математике по конкретным поводам, являются П. р. ф., напр.: остаток от деления х на y, p(х) - простое число с номером хи т. д.

Отношение P(x1 ... , х п). на натуральных числах наз. примитивно рекурсивным отношением (п. р. о.), если функция g(x1, ... , х п), равная 1, когда P(x1 , ... , х n).истинно, и 0, когда P(x1 ,... , х п).ложно, является П. р. ф. Говорят, что отношение Р(x1 ,... , х п, z) получено из отношения Q(x1 , ... , х п, у, z).с помощью ограниченного квантора, если

или

Класс п. р. о. замкнут относительно применения всех логич. связок (включая отрицание) и ограниченных кванторов.

Пусть f1, ... , fs+1 суть n-местные П. р. ф., a P1, ..., Ps - такие п. р. о., что на любом наборе значений аргументов истинно не более одного из них. Тогда функция

является П. р. ф.

Говорят, что функция f(x1, ... , х п, z).получена из всюду определенной функции g(x1 ,... , х п, у, z) применением ограниченного оператора минимизации, если f(x1, ... , х п, z).равно минимальному утакому, что и g(x1 , ... , х n, у, z)=0, и равно z+1, если такого унет. Класс П. р. ф. замкнут относительно применения ограниченных операторов минимизации.

Функция Ф ( у, x1 ,... , х п).наа. универсальной для класса всех re-местных П. р. ф., если для каждой П. р. ф. f(x1, ... , х п).найдется натуральное число kтакое, что

Для каждого такая универсальная функция существует, но она не может быть П. р. ф.

Всякое рекурсивно перечислимое множество есть область значений П. р. ф.; всякое рекурсивно перечислимое отношение R( х 1, ... , х n).представимо в виде $ уА( у, x1 ,... , х п), где Ап. р. о. Всякая П. р. ф. представима в арифметике формальной, т. е. для каждой П. р. ф. f(x1, ... , х n).найдется арифметич. формула Р( у, х 1, ... , х n).такая, что для натуральных k1 , ... , kn, т при f(k1, ... , kn)=m в формальной арифметике выводима формула , а при выводима (здесь -арифметич. термы, изображающие в формальной арифметике натуральные числа k1, ... , kn, т). Этот факт занимает центральное место в доказательстве неполноты формальной арифметики (см. [4]).

Лит.:[1] Успенский В. А., Лекции о вычислимых функциях, М., 1960; [2] Мальцев А. И., Алгоритмы и рекурсивные функции, М., 1965; [3] Роджерс X., Теория рекурсивных функций и эффективная вычислимость, пер. с англ., М., 1972; [4] Мендельсон Э., Введение в математическую логику, пер. с англ., М., 1976. С. Н. Артемов.

Математическая энциклопедия. — М.: Советская энциклопедия

И. М. Виноградов

1977—1985