21.Класс примитивно рекурсивных функций

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

s (x) = x+1, o(x) = 0, I с индексом m – внизу n – вверху (x1,…, xn) = xm

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

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

x+y, x*y, x в степени y, остаток от деления х на y, p(х) - простое число с номером х и т. д.