# 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>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):

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.

This challenge was drafted thanks to the helpful commenters at its Sandbox.

• I'm afraid most winning entries will just output infinite lists, or apply the same operator to the input ad infinitum... – AviFS Mar 21 '20 at 12:24
• @AviF.S. 1) The submission cannot loop indefinitely, as per "it cannot loop indefinitely." 2) Isn't f(n)=1 still unproven? 3) The input is mapped to one output natural number (finite in size), so an infinite array/stream would not count as valid output. – user41805 Mar 21 '20 at 14:43
• I think people are misinterpreting this challenge. It's supposed to be a total function, meaning mathematically that its domain is the entire set of natural numbers -- that is, it halts for every natural number as input. Also, you need to show that there is no primitive recursive algorithm for it, not just that the particular algorithm you have doesn't appear to match how primitive recursive functions work. – Mitchell Spector Mar 21 '20 at 15:23
• @JonathanAllan It is a little unconventional as really the program is just there for scoring. You write a program which maps some vector $x \in \{ 0, 1, 2, \dots \}^{n}$ to a single number. If that total mapping cannot be replicated by a primitive recursion function, then your submission is valid. Hope that helps. – FryAmTheEggman Mar 21 '20 at 16:55
• @JonathanAllan It is not too difficult to come up with certain classes of functions which aren't primitive recursive. For example, the quickly growing functions like the Ackermann function are not too hard to modify or replicate and then "reprove." That said, it is not trivial - but I am no expert in this area, so there could be another approach that is easier. – FryAmTheEggman Mar 21 '20 at 17:09

(+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!

• Very neat how the explicit version only differs from my version by 1 byte (plus some variable renames). Could you use a modified version of the proof I linked to prove this answer correct? – Wheat Wizard Mar 21 '20 at 17:53
• @AdHocGarfHunter I might be able to, but I think I can piggyback off existing results more easily. Something like, the Ackermann functions grows faster than any primitive recursive function, and this function grows as fast as the Ackermann function. Specifically, for both of them, f 3 grows as fast as exponentiation. So I think my function at layer m should grow at least as fast as Ackermann at later m-1, which would suffice. – xnor Mar 21 '20 at 18:24

# C (gcc) -lm, 268197 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).

• You write "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." This is surprising since the required function accepts lists of naturals as inputs, not single naturals. What is the justification that you can restrict to single input functions? – Eric Towers Mar 22 '20 at 19:01
• @EricTowers One way to look at it is that for each program $P$ (in a language like LOOP or my miniLOOP) and for each $k>0,$ there's a corresponding primitive recursive function $F^P_k:\mathbb{N}^k \to \mathbb{N},$ where $F(x_1,\dots,x_k)$ is the value left in $x_0$ if you initialize $x_1, \dots, x_k$ to the right values (and set the other variables to $0$) and run $P.$ All the primitive recursive functions of any number of variables are covered by this. The only ones actually needed for the solution are the functions of one variable $F^P_1,$ but you get the others for free. – Mitchell Spector Mar 22 '20 at 19:48
• @EricTowers In my previous comment (which it's too late to edit), I meant to write: "...where $F_k^P(x_1,\dots,x_k)$ is the value..." – Mitchell Spector Mar 22 '20 at 20:52
• You can simplify miniLOOP further into four constructs x_n = 0, x_n++, P;Q, and LOOP x_n DO P END. Conversions from miniLOOP: x_n = c -> x_n = 0 followed by c copies of x_n++; x_n = x_m -> x_n = 0; LOOP x_m DO x_n++ END; x_n-- -> x_u = 0; x_v = 0; LOOP x_n DO x_u = x_v; x_v++ END; x_n = x_u. – Bubbler Mar 23 '20 at 5:30
• @Bubbler Great point. In fact, we can eliminate $x_n=0$ also because we can simply designate some otherwise unused variable whose value is always $0$ to be used instead of $0$ (if we're implementing a function of $k$ variables, all the variables but $x_1, \dots, x_k$ are initialized to $0$). That leaves just 3 constructs, which would simplify and shorten the program in my answer, but also may be of some independent interest. – Mitchell Spector Mar 23 '20 at 6:02

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.

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


Try it online!

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


Try it online!

• @FryAmTheEggman It is still correct (%) is $f$ with the first argument fixed at $0$. I do think it is a bit confusing. So I will probably include the definition used in the linked document. – Wheat Wizard Mar 21 '20 at 17:44
• This is the fast-growing hierarchy. – user76284 Mar 22 '20 at 0:41
• @user76284 Do you want me to place this function in a hierarchy? I'm not sure the intention of the comment. – Wheat Wizard Mar 22 '20 at 0:49
• I'm just linking to the page explaining the concept, in case readers want to learn more. – user76284 Mar 22 '20 at 0:50

# 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.

• It seems you can add another d after [ly to remove the first occurrence of ly after that part – user41805 Mar 21 '20 at 15:37
• @user41805 Yes, it's probably golfable more -- I'll check it out. I quickly put this together, but the code to save and restore things from the stack can probably be shortened too. – Mitchell Spector Mar 21 '20 at 15:40

# 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)

• Upvoted for not just a neat esolang I didn't know, but one that you personally created! Plus it's Peano... Do you mind submitting to TIO.run or making an online compiler/interpreter? It'd be nice to be able to try it out without installing! – AviFS Mar 21 '20 at 14:02
• @AviF.S. I have already asked to add it to TIO, however TIO's maintainer currently has other priorities. – Jonathan Frech Mar 21 '20 at 14:06
• Awesome! I looked it up and it looks like the source is on Github. Perhaps with a pull request they'll be more timely? Looks like someone else has done the same here (requested adding a language with a pull)! – AviFS Mar 21 '20 at 14:13
• I do not want to overwhelm TIO's maintainer. If you want to use Zpr'(h yourself, building is not that cumbersome. – Jonathan Frech Mar 21 '20 at 14:17
• Haha, I already did! I only meant since this community seems to like links to verify answers online without any effort or commitment :p – AviFS Mar 21 '20 at 14:20

# 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.

• I believe you can use <1 instead of ==0 – user41805 Mar 21 '20 at 16:20
• I don't know Python well. How would you set this up to show some examples which work without getting stack overflow from the recursion? – Mitchell Spector Mar 21 '20 at 16:31
• You can usually assume the recursion limit is set high enough without including it in your byte count. Also, I suggest looking into the Ackermann function, I'm pretty sure it is shorter. – FryAmTheEggman Mar 21 '20 at 16:43
• You should be able to compute F(1,1,1) and other small values like that. Again, I don't really do Python programming, but I think your formulas aren't set up right. Your formula for f(n,x,y) should involve n-1 and y-1, not n+1 and y+1. I think that's why your recursion is never ending. Also, for $y<1,$ be sure to return x; I'm not sure you're doing that. – Mitchell Spector Mar 21 '20 at 16:48
• @MitchellSpector Started to see major bugs in my code so switched over to the Ackermann function. – Noodle9 Mar 21 '20 at 16:53

# C (gcc) Ackermann, 37 36 bytes

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


Try it online!

• Nicely done. I'm wondering if you did this by yourself or if you saw my solution to the Ackermann function challenge. – S.S. Anne Mar 22 '20 at 15:40
• @S.S.Anne Golfed your solution - thanks! :D If you haven't already, you'll want to update your Ackermann function solution to this. – Noodle9 Mar 22 '20 at 16:37
• This is my solution. It has been since two days ago, when I posted it. – S.S. Anne Mar 22 '20 at 16:38
• @S.S.Anne Ah, checking I see it was feersum's solution I golfed. If you look at the edit history you'll see first I simply use m= instead of return then got rid of the !. – Noodle9 Mar 22 '20 at 16:40

# JavaScript (Node.js),  81  76 bytes

An inefficient but non-recursive1 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[].

• Hmm... Is it really right to call this non-recursive? This is only a question of nomenclature, but I would say that you're just implementing a recursive approach yourself using a stack (that's what I did in my dc implementation of Sudan's function). Now, to be fair, something like that is presumably unavoidable, since this can't be done with bounded loops. But I would still call it recursion. (On the other hand, it's true that you're not literally calling a function inside itself, of course.) – Mitchell Spector Mar 21 '20 at 18:07
• Yes, the call stack is bounded (since it isn’t added to internally), but the stack in your program is unbounded since you’re storing there the things that would usually be stored in the call stack frame. Just to be clear, this isn’t a criticism — doing something like that is unavoidable. – Mitchell Spector Mar 21 '20 at 18:24
• Yes, I think that’s clearer. – Mitchell Spector Mar 21 '20 at 19:56

# 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*)12,$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.

# 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+⍵