Первоначальной целью теории вычислимости (рекурсии) было придать строгость интуитивной идее вычислимой функции, т.е. функции, значения которой могут быть вычислены или автоматически или каким-либо другим эффективным способом
Рекурсивные функции уже в силу характера своего определения оказываются вычислимыми, т.к. каждая рекурсивная функция задается конечной системой равенств точно охарактеризованного типа в том смысле, что ее значения вычисляются с помощью этой системы равенств по точно формулируемым правилам, причем таким образом, что в итоге для вычисления значений заданной рекурсивной функции получается алгоритм определенного типа.
Очевидно, что к вычислимым функциям следует отнести все константы, т.е. все натуральные числа 0,1,2.... Нет необходимости включать в базис бесконечное множество констант. Достаточно 0 и функции следования f(x)= x+1, (x').
Кроме того в базис включается семейство функций тождества (или введения фиктивных переменных)
(x1,...xn)=xm (m<=n)
Мощным средством получения новых функций из уже имеющихся является суперпозиция. Оператором суперпозиции называется подстановка
(h,g1,...gm)=h(g1(x1,...xn)...gm(x1,...xn)).
Если заданы функции 
и операторы 
, то можно считать заданными всевозможные операторы подстановки функций в функции, а также переименования, перестановки и отождествления переменных.
Оператором примитивной рекурсии 
называются подстановки, удовлетворяющие системе уравнений 
f(x1,...,xn)= g(x1,...,xn)
f(x1,...,xn,y+1)= h(x1,...,xn,y,f(x1,...,xn,y)),
которая называется схемой примитивной рекурсии.
Функция называется примитивно-рекурсивной, если она может быть получена из константы 0, функции следования и функций с помощью конечного числа применений операторов суперпозиции и примитивной рекурсии 
.
В формально-индуктивном виде это определение выглядит следующим образом:
1. Функции 0, Х', 
для всех натуральных m и n являются примитивно-рекурсивными.
2. Если h,g1,...gm – примитивно-рекурсивные функции, то 
– примитивно-рекурсивная функция.
3. Если g(x1,...xn),h(x1,...xm,y,z) – примитивно-рекурсивные функции, то – примитивно-рекурсивная функция.
4. Других примитивно-рекурсивных функций нет.
Примерами примитивно-рекурсивных функций являются
1. 
.
2. 
.
3. 
.
Отношение R(x1,...xn) называется примитивно-рекурсивным, если примитивно-рекурсивна его характеристическая функция
.
ПР-операторы
Оператор называется примитивно-рекурсивным (ПР), если он сохраняет примитивную рекурсивность функций, т.е. если результат его применения дает снова примитивно-рекурсивную функцию.
Операторы 
и 
являются ПР-операторами по определению.
Еще один ПР-оператор – оператор условного перехода 
, который по функциям 
и 
и предикату 
строит функцию 
Существует теорема: если 
, 
и 
вычислимы по Тьюрингу, то разветвление 
и по 
также вычислимо.
В силу этой теоремы ПР-оператор 
вычислим по Тьюрингу.
Обобщение опреатора перехода на случай многозначного перехода по 
, из которых истиннен всегда только один 
, также примитивно-рекурсивно.
Ограниченный оператор минимизации – применяется к предикатам.
Из предиката 
с помощью оператора 
получается функция 
.
Ограничение z в операторе дает гарантию окончания вычислений, поскольку оно оценивает сверху число вычислений предиката 
.
Если 
(ПР-оператор), то для вычисления f понадобится k+1 вычисление g и k вычислений h. В силу конечности общего числа операторов и 
, использованных для построения f из базисных функций, для любого k можно оценить количество элементарных действий для вычисления f.
Еще один ПР-оператор – оператор одновременной рекурсии – точнее целое семейство 
.
C его помощью строится рекурсивное описание сразу нескольких функций 
от (n-1)-ой переменной, причем значение каждой функции в точке y+1 зависит от значения всех функций в точке y.
По существу, совместная рекурсия дает рекурсивное описание функции-вектора.
Подведем некоторые итоги. Из простейших функций - константы 0, функции следования и функций тождества с помощью операторов суперпозиции и примитивной рекурсии может быть получено огромное разнообразие функций, включающих основные функции арифметики, алгебры и анализа (с поправкой на целочисленность). Следует сделать два замечания
1. Все примитивно-рекурсивные функции всюду опре-делены. Это следует из того, что простейшие функции всюду определены, а 
и это свойство сохраняют.
2. Строго говоря, мы имеем дело не с функциями, а с их примитивно-рекурсивным описанием. Различие здесь имеет тот же смысл, что и различие между функциями и их представлением в виде формул.
Возникает вопрос: все ли функции являются примитивно-рекурсивными? Простые теоретико-множественные соображения пока-зывают, что нет.
Функция называется частично-рекурсивной, если она может быть построена из простейших функций: 0, х`, с помощью конечного числа применений 
, и -оператора.
По определению -оператор применяется к предикатам. Поскольку в теории рекурсивных функций истинность предиката всегда связана со справедливостью некоторого равенства, то -оператору можно придать стандартную форму:
Будучи применен к вычислимой функции - оператор снова дает вычислимую функцию.
Однако эта процедура может не привести к результату: когда на данном наборе уравнение 
не имеет решения. В таком случае функция считается неопределенной.
Т.о. среди рекурсивных функций появляются неполностью опреде-ленные, т.е. частичные функции. Операторы над частичными функциями по-рождают новые частичные функции. При этом характер неопределенности может оказаться довольно сложным, а именно: для данного набора не най-дется способа установить определена ли на этом наборе и придется про-должать процесс вычисления неопределенное время, не зная, остановится он или нет.
Частично-рекурсивная функция называется общерекурсивной, если она всюду определена.