Primitive recursive function
Limitations

Primitive recursive functions tend to correspond very closely with our intuition of what a computable function must be. Certainly the initial functions are intuitively computable (in their very simplicity), and the two operations by which one can create new primitive recursive functions are also very straightforward. However, the set of primitive recursive functions does not include every possible total computable function—this can be seen with a variant of Cantor's diagonal argument. This argument provides a total computable function that is not primitive recursive. A sketch of the proof is as follows:

Now define the "evaluator function" e v {\displaystyle ev} with two arguments, by e v (i, j) = f i (j) {\displaystyle ev(i,j)=f_{i}(j)}. Clearly e v {\displaystyle ev} is total and computable, since one can effectively determine the definition of f i {\displaystyle f_{i}}, and being a primitive recursive function f i {\displaystyle f_{i}} is itself total and computable, so f i (j) {\displaystyle f_{i}(j)} is always defined and effectively computable. However a diagonal argument will show that the function e v {\displaystyle ev} of two arguments is not primitive recursive.

This argument can be applied to any class of computable (total) functions that can be enumerated in this way, as explained in the article Machine that always halts. Note however that the partial computable functions (those that need not be defined for all arguments) can be explicitly enumerated, for instance by enumerating Turing machine encodings.

Other examples of total recursive but not primitive recursive functions are known:
length_constraints:number_words[324], oulipo:avoid_letter[e]