Примитивно рекурсивно для примитивно рекурсивных операндов:
Примитивно рекурсивно для примитивно рекурсивных операндов:
Множество является примитивно рекурсивной, если его характеристическая функция:
Всякая функция, вычислимая программой с конечным числом переменных:
Вычислимая функция, не имеющая всюду определенного вычислимого продолжения:
Универсальную вычислимую функцию, для которой каждая вычислимая функция имеет ровно один номер:
Вычислимая функция двух аргументов, являющаяся универсальной функцией для класса вычислимых функций одного аргумента:
Вычислимая всюду определенная функция двух аргументов, универсальная для класса всех вычислимых функций одного аргумента:
Вычислимая функция трех аргументов, универсальная для класса вычислимых функций двух аргументов:
Вычислимая функция со значением {0,1} и не имеющая всюду определенного вычислимого продолжения:
