Primitive/Partial Recursive
Primitive Recursive functions
A function is said to be primitive recursive if it is one of the following:
The successor function
A projection for some fixed
A constant function
Partial Recursive functions
A partial function is said to be partial recursive if it can be generated from the same building blocks as primitive recursive functions, but we also include this building block:
(Minimization) If is partial recursive, then the function , defined as follows, is partial recursive. evaluates to the least such that , if one exists and converges for each . If this condition fails, then diverges.
We are essentially adding the “for loop combinator”
function minimize(f, ...xs) {
for (let y = 0; true; y++)
if (f(...xs, y) === 0)
return y;
}
Historical Context
The primitive recursive functions and partial recursive functions were one attempt to pin down the collection of functions which could be carried out by an “effective procedure”, ie, by a set of rules requiring no creativity (ie, an algorithm). This search was motivated by Hilbert’s Program and the search to ‘solve math’ by giving an effective procedure that could solve all mathematical questions.
Properties and Remarks
The partial recursive functions are strictly more powerful than the primitive recursive functions, since the primitive recursive functions are a subset of the partial recursive functions. A natural question to ask is whether there are degrees of power ‘between’ these two notions: is there a collection of functions which is more powerful than primitive recursive but less powerful than partial recursive?
The answer is yes: the Ackermann function is a computable function which is both total and non-primitive, so we could consider the functions generated by the primitive recursive functions alongside the Ackermann function. This would be more powerful than the primitive recursive functions (since the Ackermann function is not primitive recursive) but less powerful than the partial recursive functions (since this collection would contain only total functions).