Shortest total non-primitive recursive function

Question

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>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)&=f(x_0,\dots,x_k)\\h(S(y),x_0,\dots,x_k)&=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.

Answer 1

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!

Answer 2

C (gcc) -lm, 268 197 194 bytes

x[9];e(n,c){int w=sqrt(n/6*8+1)/2-.5,b=n/6+w*~w/2,*z=x+b;for(n%=6;c--;)n-2?n-3?n-4?n-5?x[w-b]=n?*z:b:e(w-b,*z):e(w-b,1,e(b,1)):*z&&--*z:++*z;}main(n){e(x[1]=n,scanf("%d",&n));printf("%d",1+*x);}

Try it online!

Now 3 more bytes off thanks to @ceilingcat again (saving a pointer z to x[b], and then using *z instead of x[b] throughout).

Thanks to C golfing expert @ceilingcat for reducing this by an amazing 71 bytes!

---

I decided to write an answer that works completely differently from the other solutions posted so far. This uses diagonalization of the primitive recursive functions (it's not a function that grows faster than any primitive recursive function, the way the Ackermann and Sudan functions do).

I don't think there's any way to golf this to be as short as the Ackermann or Sudan programs, but it has two advantages: (1) It's easy to understand the proof that it's not primitive recursive, and (2) you can actually run it on reasonably sized inputs without running out of time or getting stack overflows!

---

The basic idea behind this function \$F\$ is first to enumerate all programs to compute primitive recursive functions of one variable. Let \$P_0, P_1, ...\$ be this enumeration. Then, for any input \$n,\$ here's how to compute \$F(n)\$: First supply \$n\$ as input to the program \$P_n\$ and run that. When \$P_n\$ halts with an integer as output (as it's guaranteed to do, because it's computing a primitive recursive function), add \$1\$ to that output. That's \$F(n).\$

\$F\$ is clearly total.

Now,

• \$F\$ is not the function computed by \$P_0\$ because \$F(0)\$ is one higher than the output of \$P_0\$ on input \$0,\$

• \$F\$ is not the function computed by \$P_1\$ because \$F(1)\$ is one higher than the output of \$P_1\$ on input \$1,\$

• \$F\$ is not the function computed by \$P_2\$ because \$F(2)\$ is one higher than the output of \$P_2\$ on input \$2,\$

etc. In general, \$F\$ isn't the function computed by \$P_n,\$ because \$F(n)\$ is one higher than the output of \$P_n\$ on input \$n.\$

So \$F\$ isn't the same as the function computed by any of the programs \$P_n.\$ But those are all the primitive recursive functions. So \$F\$ isn't primitive recursive.

---

The way I enumerate all the primitive recursive functions is by implementing a variant of Uwe Schöning's programming language LOOP. It is known that the functions computable by a LOOP program are precisely the primitive recursive functions. (These programs actually cover all primitive recursive functions, not just the primitive recursive functions of one variable, even though that's ultimately all we would need.)

My variant miniLOOP is even simpler than the original language. Just as in LOOP, there are variables \$x_0, x_1, x_2, \dots\$; each of these variables can hold a natural number (a non-negative integer). To use a miniLOOP program to compute a function of \$k\$ variables, you store the values of the \$k\$ arguments in \$x_1, \dots, x_k,\$ and then run the program. The output is the value of \$x_0\$ at the end.

Here are the basic programming statements available in miniLOOP (all variables are restricted to the natural numbers):

• \$x_n=m,\$

• \$x_n=x_m,\$

• \$x_n\$++ (increment),

• \$x_n\$-- (decrement except that if \$x_n\$ is equal to 0, its value is left unchanged, because we don't allow negative numbers).

Statements can also be constructed from other statements using the following two constructs:

• \$P;Q\$ where \$P\$ and \$Q\$ are statements; this means to execute \$P\$ first and then \$Q.\$

• \$\text{LOOP } x_n \text{ DO } P \text{ END},\$ which means to execute \$P\$ repeatedly, \$x_n\$ times in a row. (Repeating it 0 times means not doing it at all, of course.) Note that the number of repetitions is the value that \$x_n\$ has when the loop starts. Even if the body of the loop changes the value of \$x_n,\$ the number of repetitions won't change. This is the key thing that makes this an implementation of primitive recursion.

---

For example, the following program doubles its input:

LOOP x1 DO x1++ END
x0 = x1

(Recall that a function of one variable takes its input in \$x_1\$ and leaves its output in \$x_0.\$)

---

You can check that even though miniLOOP is a bit simpler than the LOOP language defined in the Wikipedia article, you can simulate all the LOOP constructs with miniLOOP programs. So miniLOOP also computes precisely the primitive recursive functions.

---

Every miniLOOP program is assigned a number; that is how we enumerate them. This enumeration uses the Cantor pairing function

$$\pi(x,y)=\frac{(x+y)(x+y+1)}{2}+y.$$

Here is the numerical assignment:

• \$x_n=c\$ is assigned the number \$6 \pi(n,c).\$

• \$x_n=x_m\$ is assigned the number \$6 \pi(n,m)+1.\$

• \$x_m\$++ is assigned all the numbers \$6 \pi(n,m)+2\$ for any \$n\$ (it doesn't matter that one program can be included multiple times in the enumeration).

• \$x_m\$-- is assigned all the numbers \$6 \pi(n,m)+3\$ for any \$n.\$

• \$P;Q\$ is assigned all the numbers \$6 \pi(q,p)+4\$, where \$p\$ is assigned to \$P\$ and \$q\$ is assigned to \$Q.\$ (\$q\$ and \$p\$ are "backwards" in this formula only because this is code golf and I ended up saving a few bytes by doing it that way.)

• \$\text{LOOP } x_n \text{ DO } P \text{ END}\$ is assigned the numbers \$6 \pi(p,n)+5,\$ where \$p\$ is a number assigned to \$P.\$

Note that every number is assigned to a unique program. (A program can have more than one number assigned to it, but a number is associated with exactly one program.) And it's easy to take a number and figure out what program it's assigned to.

For example, you can check that the program above that doubles its input is assigned 1667230. This is computed as \$6 \pi(13,731)+4,\$ where \$13 =6\pi(0,1)+1\$ and \$731=6\pi(14,1)+5.\$ In that last formula, \$14=6\pi(0,1)+2.\$

---

In the C program, \$x\$ is a global array holding all the variables needed for what you're running. I've only declared it to hold 9 variables, since that's plenty for demonstrating it, but in practice you would really want to allow that to grow using malloc as needed.

The function e takes an input n and runs the miniLOOP program assigned to n. It assumes that x[1], ..., x[k] have already been set up as desired for the input, and it leaves the output in x[0].

The main program simply takes its input n, stores it in x[1], and calls e(n) to run the miniLOOP program assigned to n. It then adds 1 to the output and prints that as the output of the main program.

As described in the outline at the beginning, this program halts on every input. But it's not primitive recursive, since it disagrees with miniLOOP program number n (at input n), and those miniLOOP programs compute all the primitive recursive functions.

The TIO link shows what this program does with input 1667230. Recall that 1667230 is assigned to a miniLOOP program that doubles its input, and you can see that the output of the main program here is 3334461 (which is not equal to double 1667230, being one higher, as intended).

Answer 3

Haskell, (Ackermann-like) 31 bytes

Inspiration from this answer.

0%x=x+1
n%x=iterate((n-1)%)x!!x

Try it online!

Or if \$g^n\$ is \$n\$ compositions of \$g\$ then

\$ f_0(x)=x+1 \\ f_n(x)=f_{n-1}^x(x) \$

This function appears here with a proof that it is not primitive recursive.

Haskell, (Ackermann) 39 bytes

0%n=n+1
m%0=(m-1)%1
m%n=(m-1)%(m%(n-1))

Try it online!

Haskell, (Sudan) 45 bytes

(n#x)y|n<1=x+y|y<1=x|q<-n#x$y-1=(n-1)#q$q+y+1

Try it online!

Answer 4

dc, 76 bytes

?sysxsn[lx+q]sp[lydln*0=ply1-sylFxdSxly1+dsy+Syln1-snlFxln1+snLxsDLysD]dsFxp

Try it online!

This implements Sudan's function, which I believe was the first computable but non-primitive-recursive function discovered. It grows faster than any primitive recursive function.

Three space-separated arguments \$n, x,\$ and \$y\$ are read from stdin, and the output \$F(n, x, y)\$ is written to stdout.

The function grows so quickly that you need something like dc that supports arbitrarily large integers to have a chance at computing any interesting examples at all.

I'll post an explanation later (dc is a pain to document), but the TIO link shows how large its outputs get: \$F(2,11,2)\$ is 16,031 digits long! This appears to be the largest example I can compute on TIO without overflowing the stack (due to the heavy use of recursive calls).

The Wikipedia link above has a table of sample outputs. You can run my program at TIO and see that it matches the ones that Wikipedia shows.

There's a proof that it's not primitive recursive in Theories of Computational Complexity, by Cristian Calude.

Answer 5

Zpr'(h, 81 bytes

(a () .n)|>(S n)
(a (S .k) ())|>(a k (S ()))
(a (S .k) (S .n))|>(a k (a (S k) n))

<| constants.zpr
main |> (a 3 4)

Execution

stdlib % ../Zprh --de-peano above.zpr
125

Explanation

; implementation of the Ackermann-Peter function in Zpr'(h


; base case for k = 0
(ackermann-peter () .n)         |> (S n)

; base case for n = 0
(ackermann-peter (S .k) ())     |> (ackermann-peter k (S ()))

; general case for k, n > 0
(ackermann-peter (S .k) (S .n)) |> (ackermann-peter k (ackermann-peter (S k) n))


; include integer constants
<| constants.zpr

; test the implementation
main |> (ackermann-peter 3 4)

Answer 6

Python Ackermann, ^{78 \$\cdots\$ 59} 45 bytes

Save 2 bytes (in pre production) thanks to user41805!!!

A=lambda m,n:m and A(m-1,n<1or A(m,n-1))or-~n

Try it online!

Going with FryAmTheEggman's most excellent advice and implementing the Ackermann function.

Answer 7

C (gcc) Ackermann, ³⁷ 36 bytes

A(m,n){m=m?A(m-1,n?A(m,n-1):1):n+1;}

Try it online!

Answer 8

JavaScript (Node.js),  81  76 bytes

An inefficient but non-recursive¹ implementation of the Ackermann function, accepting either Numbers or BigInts.

Given enough time and memory, this should work in theory for any pair \$(m,n)\$.

Takes input as ([m])(n).

s=>n=>eval("for(;s+s;){(m=s.pop())?s.push(~-m)&&n?s.push(n--&&m):n++:n++}n")

Try it online!

---

_{1: By 'non-recursive', I mean that there's no recursive function call. Therefore, the code does not depend on the size of the call stack, which is always bounded regardless of the total amount of available memory. Instead, it's using its own stack s[].}

Answer 9

Retina 0.8.2, 51 bytes

\d+
$*
{`((1*)1,1*)1$
$2,$1
1,$
,1
}`\B,(1*)$
1$1
1

Try it online! An implementation of the Ackermann function in unary arithmetic, so don't try to compute anything larger than A(4, 1) on TIO. Explanation:

\d+
$*

Convert to unary.

{`
}`

Repeat the steps until there is only one value left on the stack.

((1*)1,1*)1$
$2,$1

If the top of the stack is m+1, n+1 then decrement the latter to n and push a copy of m below m+1 so the stack is now m, m+1, n.

1,$
,1

If the top of the stack is m+1, 0 then decrement the former to m and increment the latter to 1.

\B,(1*)$
1$1

If the top of the stack is 0, n then remove the 0 and increment n.

1

Convert to decimal.

Answer 10

APL (Dyalog Unicode), 16 bytes

{×⍺:∇⍣⍵⍨⍺-1⋄2+⍵}

Try it online!

This function \$ f(\alpha,\omega) \$ is a variation of the commonly-known Ackermann function, which turns out as follows:

$$ \begin{align} f(0,\omega)&= 2+\omega \\ f(1,\omega)&= 2\times\omega \\ f(2,\omega)&= 2^\omega \\ \end{align} $$

But the pattern doesn't extend for \$ \alpha \ge 3 \$.

How it works

{×⍺:∇⍣⍵⍨⍺-1⋄2+⍵}
{×⍺:           }   ⍝ If ⍺ is nonzero,
    ∇⍣⍵⍨⍺-1        ⍝ Compute this expression, which expands to...
    (⍺-1)(∇⍣⍵)⍺-1  ⍝   Recursively call self with left arg ⍺-1, ⍵ times
                   ⍝   on the starting value of ⍺-1
           ⋄2+⍵    ⍝ Otherwise, return 2+⍵

Answer 11

MMIX, Ackermann, 60 bytes (15 instrs)

(jxd)

00000000: 5a000003 23000101 f8010000 5a010004  Z¡¡¤#¡¢¢ẏ¢¡¡Z¢¡¥
00000010: e3010001 27000001 f1fffffa c1040000  ẉ¢¡¢'¡¡¢ȯ””«Ḋ¥¡¡
00000020: 27050101 fe020004 f303fff6 f6040002  '¦¢¢“£¡¥ṙ¤”ẇẇ¥¡£
00000030: c1010300 27000001 f1fffff2           Ḋ¢¤¡'¡¡¢ȯ””ṗ

Disassembly and explanation:

ack PBNZ  $0,0F     // if(!m)
    ADDU  $0,$1,1
    POP   1,0       // return n + 1
0H  PBNZ  $1,0F     // if(!n)
    SETL  $1,1
    SUBU  $0,$0,1
    JMP   ack       // return ack(m - 1, 1)
0H  SET   $4,$0
    SUBU  $5,$1,1
    GET   $2,rJ
    PUSHJ $3,ack
    PUT   rJ,$2
    SET   $1,$3     // n = ack(m, n - 1)
    SUBU  $0,$0,1   // m--
    JMP   ack       // return ack(m,n)