Primitive recursive function
New to topics? Read the documentation here!
In intuitive terms it consists of all integer functions, possibly with multiple input arguments, that can be written only with a sequence of:
and such that
- variable assignments
- addition and subtraction
- integer comparisons and if/else
- for loops
for (i = 0; i < n; i++)n does not change inside the loop body, i.e. no while loops with arbitrary conditions.n does not have to be a constant, it may come from previous calculations. But it must not change inside the loop body.Primitive recursive functions basically include every integer function that comes up in practice. Primitive recursive functions can have huge complexity, and it strictly contains EXPTIME. As such, they mostly only come up in foundation of mathematics contexts.
The cool thing about primitive recursive functions is that the number of iterations is always bound, so we are certain that they terminate and are therefore computable.
This also means that there are necessarily functions which are not primitive recursive, as we know that there must exist uncomputable functions, e.g. the busy beaver function.
Adding unbounded while loops of course enables us to simulate arbitrary Turing machines, and therefore increases the complexity class.
More finely, there are non-primitive total recursive functions, e.g. most famously the Ackermann function.