Примитивно рекурсивные функции

Операции над числовыми функции назовем операторами. В этом параграфе мы определим ряд операторов, обладающих тем свойством, что, применяя их к функциям, вычислимым в интуитивном смысле, мы получим функции, также вычислимые в интуитивном смысле.

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

Основная гипотеза Черча состоит в том, что класс частично рекурсивных функций совпадает с классом функций, допускающих машинное или алгоритмическое вычисление.