Shortest total non-primitive recursive function Natural numbers ≡ \$\mathbb{N}≡\{0,1,2,...\}\$

The submission can be either a program or a function, both cases will henceforth be referred to as "function".

The task is to golf the shortest function \$\mathbb{N}^n→\mathbb{N}\$, i.e. a function that maps \$n\$ natural numbers (with \$n&gt;0\$ being a number of your choosing) to a natural number, such that the function is not primitive recursive, that is, a function that is not composable from only the following functions (each variable being a natural number):

(from https://en.wikipedia.org/wiki/Primitive_recursive_function)

Zero
$$Z()=0$$

Successor
$$S(x)=x+1$$

Projection
$$P_i^n(x_0,x_1,\dots,x_{n-1})=x_i$$

Composition
$$h(x_0,x_1,\dots,x_m)=f(g_1(x_0,x_1,\dots,x_m),\dots,g_k(x_0,x_1,\dots,x_m))$$

Primitive recursion

$$\begin{align}h(0,x_0,\dots,x_k)&amp;=f(x_0,\dots,x_k)\\h(S(y),x_0,\dots,x_k)&amp;=g(y,h(y,x_0,\dots,x_k),x_0,\dots,x_k)\end{align}$$



From the above five functions/operations, we can get many functions like the constant function, addition, multiplication, exponentiation, factorial, primality test, etc.

A (total) function that is not primitive recursive could be one that grows faster than any primitive recursive function, like the Ackermann function. Its proof of not being primitive recursive is on Wikipedia.

Or a function could be non primitive recursive due to contradictions that would arise otherwise; examples are provided in the answers to this Math Stack Exchange question as pointed out by Bubbler.



The submissions are free to use any radix as long as the same radix is used for each of the input and output numbers.

Your submission can take input as a list of numbers, a list of strings representing numbers, a string containing (constant) delimiter-separated numbers, or the like. In the case of using a string or equivalent, your submissions are free to use any character to represent each digit of the radix chosen, as long the choice is consistent throughout all inputs and output.

The function will always be called with the same number of inputs.

The submission should always terminate and return a result, that is, it cannot loop indefinitely.

The function should always give deterministic output.

The submission should theoretically work for any input, including those outside of the used numeric data types.

A proof accompanying your answer is appreciated, but not required.



This challenge was drafted thanks to the helpful commenters at its Sandbox.
Haskell, 29 bytes



(+1)?(2?)
z?f=(iterate f z!!)


Try it online!

An Ackermann-like function. Starting the base numerical value at 2 makes for a simple base case. An annoying number of bytes are spent converting the arguments order for "apply f n times starting from z" from iterate f z!!n to (?) z f n which can be curried nicely.

Same thing written more explicitly for 2 bytes longer:

31 bytes



0%n=n+1
m%n=iterate((m-1)%)2!!n


Try it online!

Another alternative to the original is to flip the two arguments to ?, allowing it to be defined in a point-free way for the same byte count.

29 bytes



(?2)?(+1)
(?)=((!!).).iterate


Try it online!

29 bytes



(?2)?(+1)
(?)f=(!!).iterate f


Try it online!

31 bytes



n?0=n+1
0?m=2
n?m=(n-1)?m?(m-1)


Try it online!