General Recursive Function

General recursive functions (GRFs), also called µ-recursive functions or partial recursive functions, are the collection of partial functions ${\mathbb{\mathbb{N}}}^k\rightharpoonup \mathbb{\mathbb{N}}$ that are computable. This definition is equivalent using any Turing complete system of computation. See Wikipedia:general recursive function for background.

Historically it was defined as the smallest class of partial functions ${\mathbb{\mathbb{N}}}^k\rightharpoonup \mathbb{\mathbb{N}}$ that is closed under composition, recursion, and minimization, and includes zero, successor, and all projections (see formal definitions below). In the rest of this article, this is the formulation that we focus on exclusively. In this way, it can be considered to be a Turing complete model of computation. In fact, it is one of the oldest Turing complete models, first formalized by Kurt Gödel and Jacques Herbrand in 1933, 3 years before λ-calculus and Turing machines.

BBµ(n) is a Busy Beaver function for GRFs:$$BB\mu (n)=\max \{f()|f\in {\text{GRF}}_0,|f|=n\}$$

where $f\in GR{F}_k$ means that $f:{\mathbb{\mathbb{N}}}^k\rightharpoonup \mathbb{\mathbb{N}}$ is a k-ary GRF and $|f|$ is the "structural size" of f (defined below). In other words, it is the largest number computable via a 0-ary function (a constant) with a limited "program" size. It is more akin to the traditional Sigma score for a Turing machine rather than the Step function in the sense that it maximizes over the produced value, not the number of steps needed to reach that value.

Definition

Structure

Define $GR{F}_k$ inductively based on the following construction rules, start with Atoms and combine them using Combinators.

Atoms

• Zero: $\mathrm{\forall }k\in \mathbb{\mathbb{N}},Z^k\in GR{F}_k$ is the constant 0 function $Z^k(x_1,\dots ,x_k)=0$
• Successor: $S\in GR{F}_1$ is the successor function $S(x)=x+1$
• Projection: $\mathrm{\forall }1\le i\le k\in \mathbb{\mathbb{N}},P_i^k\in GR{F}_k$ is a projection function $P_i^k(x_1,\dots x_k)=x_i$

Combinators

• Composition: $\mathrm{\forall }k,m\in \mathbb{\mathbb{N}},\mathrm{\forall }h\in GR{F}_m,\mathrm{\forall }{g}_1,\dots g_m\in GR{F}_k,C(h,g_1,\dots g_m)\in GR{F}_k$ is the composition or substitution of the gs into h: $C(h,g_1,\dots g_m)(x_1,\dots x_k)=h(g_1(x_1,\dots x_k),\dots g_m(x_1,\dots x_k))$
• Primitive Recursion: $\mathrm{\forall }k\in \mathbb{\mathbb{N}},\mathrm{\forall }g\in GR{F}_k,\mathrm{\forall }h\in GR{F}_{k+2},R(g,h)\in GR{F}_{k+1}$ is primitive recursion using g as the base case and h as the inductive step.
• Minimization / Unlimited Search: $\mathrm{\forall }k\in \mathbb{\mathbb{N}},\mathrm{\forall }f\in GR{F}_{k+1},M(f)\in GR{F}_k$ is the µ-operator which allows unlimited search.

Primitive Recursion

$R$ models a typical iterative function definition over ℕ.

Base case: $R^k(g,h)(0,x_2,x_3,...,x_k)=g(x_2,x_3,...,x_k)$

Iterative case (for $x_1>0$): $R^k(g,h)(x_1,x_2,...,x_k)=h(x_1-1,v,x_2,x_3,...,x_k)$ where $v=R(g,h)(x_1-1,x_2,x_3,...,x_k)$.

$R$ can be recursively evaluated following its definition directly. Or it can be iterated over its first argument, starting with 0 (and thus a call to $g$), then 1, 2, 3, etc. until $x_1$ is reached, each time calling $h$ with the prior iteration count for its first argument and the result of the prior call for its second.

Minimization

$M^k(f)(x_1,...,x_k)\triangleq \min \{i\in \mathbb{\mathbb{N}}:f(i,x_1,...,x_k)=0\}$

In computational language, when M(f) is evaluated it can be considered to calculate $f(i,x_1,...,x_k)$ with $i=0$, then $i=1$, then $i=2$ etc. until one of the calls to $f$ returns 0, at which point it returns the value of $i$ which first gave a result of 0. If no first argument causes $f$ to return 0, $M(f)$ doesn't return. (This is the only way for a GRF to not halt.)

Macros

In order to improve readability we define the following macros. For all $f\in GR{F}_1$

	Macro	arity	Definition	Size	Function
Constant	$K^k[n]$	k	$\begin{array}{lcl}{K}^k[0]& :=& Z^k\\ K^k[n]& :=& C(Plus[n],Z^k)\end{array}$	$2n+1$	$\lambda x_1\dots x_k.n$
Plus constant	$Plus[n]$	1	$\begin{array}{lcl}Plus[1]& :=& S\\ Plus[n+1]& :=& C(S,Plus[n])\end{array}$	$2n-1$	$\lambda x.x+n$
Triangular numbers	$Tri$	1	$Tri:=R(Z^0,R(S,C(Plus[2],P_2^3)))$	$7$	$\lambda x.\frac{x(x+1)}{2}$
Iteration	$RepSucc[f]$	2	$RepSucc[f]:=R(S,C(f,P_2^3))$	$|f|+4$	$\lambda xy.f^x(y+1)$
Diagonalization & Iteration	$DiagRep[f]$	2	$DiagRep[f]:=R(S,C(f,P_2^3,P_2^3))$	$|f|+5$	$\lambda xy.(\lambda z.f(z,z){)}^x(y+1)$
Diagonalization	$DiagS[f]$	1	$DiagS[f]:=C(f,S,S)$	$|f|+3$	$\lambda x.f(x+1,x+1)$
Ackermann iteration	$AckDiag2[n,f]$	2	$\begin{array}{lcl}AckDiag2[0,f]& :=& RepSucc[f]\\ AckDiag2[n+1,f]& :=& DiagRep[AckDiag2[n,f]]\end{array}$	$5n+4+|f|$
	$AckDiag[n,f]$	1	$AckDiag[n,f]:=DiagS[AckDiag2[n,f]]$	$5n+7+|f|$

Champions

n	BBµ(n)	Champion	Champion Found	Holdouts Proven
1	= 0	$Z^0$		Shawn Ligocki 8 Dec 2025 By hand
2	= 0	$M^0(Z^1),M^0(P_1^1),C^0(Z^0)$		Shawn Ligocki 8 Dec 2025 By hand
3	= 1	$K^0[1]$		Shawn Ligocki 8 Dec 2025 By hand
4	= 1	$C^0(K^0[1])$		Jacob Mandelson 3 Apr 2026
5	= 2	$K^0[2]$		Jacob Mandelson 3 Apr 2026
6	= 2	$C^0(K^0[2])$		Jacob Mandelson 3 Apr 2026
7	= 3	$K^0[3]$		Jacob Mandelson 3 Apr 2026
8	≥ 3	$C^0(K^0[3])$
9	≥ 4	$K^0[4]$
10	≥ 4	$C^0(K^0[4])$
11	≥ 5	$K^0[5]$
12	≥ 5	$C^0(K^0[5])$
13	≥ 6	$K^0[6]$
14	≥ 32	$M^0(C^1(R^2(P_1^1,R^3(P_1^2,C^4(R^2(P_1^1,P_1^3),P_2^4,P_1^4))),P_1^1,S))$	Shawn Ligocki 29 Apr 2026
15
16
17	≥ 15	$C(AckDiag[1,S],K^0[1])$	Shawn Ligocki 12 Apr 2026
18	≥ 21	$C(AckDiag[0,Tri],K^0[1])$	Jacob Mandelson 9 Apr 2026
19	≥ 39	$C(AckDiag[1,S],K^0[2])$	Shawn Ligocki 12 Apr 2026
20	≥ 1540	$C(AckDiag[0,Tri],K^0[2])$	Jacob Mandelson 9 Apr 2026
21
22	$>10^{13.35}$	$C(AckDiag[2,S],K^0[1])$	Shawn Ligocki 13 Apr 2026
23	$>10^{10^{463}}$	$C(AckDiag[1,Tri],K^0[1])$	Shawn Ligocki 13 Apr 2026
24
25	$>10\uparrow \uparrow 5$	$C(AckDiag[1,Tri],K^0[2])$	Shawn Ligocki 13 Apr 2026
26
27	$>10\uparrow \uparrow 10\uparrow \uparrow 3$	$C(AckDiag[3,S],K^0[1])$	Shawn Ligocki 13 Apr 2026
28	$>10\uparrow \uparrow 10\uparrow \uparrow 5$	$C(AckDiag[2,Tri],K^0[1])$	Shawn Ligocki 13 Apr 2026
29	$>10\uparrow \uparrow 10\uparrow \uparrow 10\uparrow \uparrow 4$	$C(AckDiag[3,S],K^0[2])$	Shawn Ligocki 13 Apr 2026
30	$>10\uparrow \uparrow 10\uparrow \uparrow 10\uparrow \uparrow 8$	$C(AckDiag[2,Tri],K^0[2])$	Shawn Ligocki 13 Apr 2026
31	$>10\uparrow \uparrow 10\uparrow \uparrow 10\uparrow \uparrow 10\uparrow \uparrow 5$	$C(AckDiag[3,S],K^0[3])$	Shawn Ligocki 13 Apr 2026
...
5k+17	> $10{\uparrow }^{k}10{\uparrow }^{k}3$	$C(AckDiag[k+1,S],K^0[1])$	Shawn Ligocki 13 Apr 2026
5k+18	> $10{\uparrow }^{k}10{\uparrow }^{k}3$	$C(AckDiag[k,Tri],K^0[1])$	Shawn Ligocki 13 Apr 2026
5k+19	> $10{\uparrow }^{k}10{\uparrow }^{k}10{\uparrow }^{k}4$	$C(AckDiag[k+1,S],K^0[2])$	Shawn Ligocki 13 Apr 2026
5k+20	> $10{\uparrow }^{k}10{\uparrow }^{k}10{\uparrow }^{k}5$	$C(AckDiag[k,Tri],K^0[2])$	Shawn Ligocki 13 Apr 2026
5k+21	> $10{\uparrow }^{k}10{\uparrow }^{k}10{\uparrow }^{k}10{\uparrow }^{k}5$	$C(AckDiag[k+1,S],K^0[3])$	Shawn Ligocki 13 Apr 2026
...
94	> $10{\uparrow }^{15}10{\uparrow }^{15}10{\uparrow }^{15}4$	$C(AckDiag[16,S],K^0[2])$	Shawn Ligocki 13 Apr 2026
95	$>f_{\omega }(10^{13})$	Omega() from example_ack.rs	Shawn Ligocki 16 Apr 2026
96
97	$>f_{\omega }^3(3)$	Omega3() from example_ack.rs	Shawn Ligocki 22 Apr 2026
98
99	$>f_{\omega }^4(3)$	Omega4() from example_ack.rs	Shawn Ligocki 22 Apr 2026
100	$>f_{\omega +1}(f_{\omega }^2(10^{13}))\gg \text{Graham's number}$	Graham() from example_ack.rs	Shawn Ligocki 16 Apr 2026

Cryptids

Jacob Mandelson constructed a size 141 Cryptid on 8 Apr 2026 [1], shrunk to 139 by 17 Apr 2026.[2]

Macro Bounds

Let $C=\frac{1}{{\log }_{10}(2)}\approx 3.32$

AckDiag[k, S]

Let $A{S}_k(n):=DiagRe{p}^k[RepSucc[S]](n,n)=AckDiag[k,S](n-1)$

• $A{S}_0(n)=S^n(n+1)=2n+1$
• $A{S}_1(n)=A{S}_0^n(n+1)=(n+2)2^n-1$
• $A{S}_1(n)>C\cdot 10^{n/C}$ (for $n\ge 2$)
• $A{S}_2(n)=A{S}_1^n(n+1)>C\cdot (10\uparrow {)}^n\left(\frac{n+1}{C}\right)>10\uparrow \uparrow n[\uparrow \frac{n+1}{C}]$ (for $n\ge 2$)
• $A{S}_k(n)=A{S}_{k-1}^n(n+1)>(10{\uparrow }^{k-1}{)}^n(n+1)$ (for $k\ge 3$ and $n\ge 1$)

AckDiag[k, Tri]

Let $A{T}_k(n):=DiagRe{p}^k[RepSucc[Tri]](n,n)=AckDiag[k,Tri](n-1)$

• $Tri(n)=\frac{n(n+1)}{2}>\frac{1}{2}{n}^2$
• $A{T}_0(n)=Tr{i}^n(n+1)>2{\left(\frac{n+1}{2}\right)}^{2^n}$
• $A{T}_0(2)=21$, $A{T}_0(3)=1540$, $A{T}_0(4)>10^{7.42}$
• $A{T}_0(n)>C10^{10^{\left(\frac{n-1}{C}\right)}}+1$ (for $n\ge 5$)
• $A{T}_1(n)=A{T}_0^n(n+1)>C(10\uparrow {)}^{2n-2}\left(\frac{A{T}_0(n+1)}{C}\right)$
• $A{T}_1(2)>10^{10^{A{T}_0(3)/C}}>10^{10^{463}}$, $A{T}_1(3)>10^{10^{10^{10^{A{T}_0(4)/C}}}}>10\uparrow \uparrow 5$
• $A{T}_1(n)>10\uparrow \uparrow 2n$ (for $n\ge 4$)
• $A{T}_2(n)=A{T}_1^n(n+1)>(10\uparrow \uparrow {)}^{n-1}(A{T}_1(n+1))$
• $A{T}_2(2)=A{T}_1^2(3)>A{T}_1(10\uparrow \uparrow 5)>10\uparrow \uparrow 10\uparrow \uparrow 5$, $A{T}_2(3)=A{T}_1^3(4)>10\uparrow \uparrow 10\uparrow \uparrow 10\uparrow \uparrow 8$
• $A{T}_2(n)>10\uparrow \uparrow \uparrow (n+1)$ (for $n\ge 4$)
• $A{T}_3(n)=A{T}_2^n(n+1)>(10\uparrow \uparrow \uparrow {)}^{n-1}(A{T}_2(n+1))$
• $A{T}_3(2)=A{T}_2^2(3)>A{T}_2(10\uparrow \uparrow \uparrow 3)>10\uparrow \uparrow \uparrow 10\uparrow \uparrow \uparrow 3$

Utilizing Minimization

All the current champions are primitive recursive functions. In other words none use the minimization combinator M. This fundamentally limits their growth rate. In fact, no primitive recursive function can grow faster than the Ackermann function and we can see that above where the assymtotic growth of the known BBµ bound is Ackermann growth: $BB\mu (6k+17)\ge 2{\uparrow }^{k}4$.

But, like the traditional BB function, BBµ grows uncomputably fast, so eventually it must surpass primitive recursive functions. In order to do that, it needs to use the M combinator. However, in order to do arbitrary computation, you need a way to store arbitrarily large amounts of data into a single integer and extract it back out. In other words, you need to implement a pairing function. Thus there is value in finding small pairing/unpairing functions. A set of pairing functions is a triple Pair,Left,Right such that for all a,b: Left(Pair(a,b)) = a and Right(Pair(a,b)) = b. When functions consume both the left and right values, common subexpression elimination can be used to reduce the number of operations below that from calling Left and Right individually. The smallest known pairing functions are:

Smallest Pairing Functions

Macro	arity	Definition	Size	Function
$Pair$	2	$Pair:=C(AddS,C(Tri,Add),P_1^2)$	20	$\lambda xy.\frac{(x+y)(x+y+1)}{2}+x+1$
$Left$	1	$Left:=C(RMonus,C(TriP,InvTriCeil),Pred)$	38	$Left(Pair(x,y))=x$
$Right$	1	$Right:=C(RMonus,P_1^1,C(Tri,InvTriCeil))$	36	$Right(Pair(x,y))=y$
$LRCall[f^2]$	1	$LRCall[f]:=C(LRpart3[f],InvTriCeil,P_1^1)$	$59+|f|$	$LRCall[f](Pair(x,y))=f(x,y)$

Where these are based on the following definitions:

Macros

	Macro	arity	Definition	Size	Function
Addition	Add	2	$Add:=R(P_1^1,C(S,P_2^3))$	5	$\lambda xy.x+y$
	AddXA	3	$AddXA:=R(P_1^2,C(S,P_2^4))$	5	$\lambda xyz.x+y$
	AddS	2	$AddS:=R(S,C(S,P_2^3))$	5	$\lambda xy.x+y+1$
Predecesor	Pred	1	$Pred:=R(Z^0,P_1^2)$	3	$\lambda x.x\dot{-}1$
Monus	RMonus	2	$RMonus:=R(P_1^1,C(Pred,P_2^3))$	7	$\lambda xy.y\dot{-}x$
Triangular numbers	Tri	1	$Tri:=R(Z^0,AddS)$	7	$\lambda x.\frac{x(x+1)}{2}$
	TriP	1	$TriP:=R(Z^0,Add)$	7	$TriP(x+1)=Tri(x)$
	TriPXA	2	$TriPXA:=R(Z^1,AddXA)$	7	$TriPXA(x,y)=TriP(x)$
Inverting Tri	RMonusTri	2	$RMonusTri:=C(RMonus,C(Tri,P_1^2),P_2^2)$	18	$\lambda xy.y\dot{-}Tri(x)$
	InvTriCeil	1	$InvTriCeil:=M(RMonusTri)$	19	$\lambda y.\min \{x|Tri(x)\ge y\}$
Combined LRCall	RightPiece	3	$RightPiece:=R(P_2^2,C(Pred,P_2^4))$	7	$\lambda xyz.z\dot{-}x$
	LeftPiece	3	$LeftPiece:=C(RMonus,C(S,P_2^3),P_1^3)$	12	$\lambda xyz.x\dot{-}(y+1)$
	LRpart1[f]	3	$LRpart1[f]:=C(f,LeftPiece,RightPiece)$	$20+|f|$	$\lambda xyz.f(x\dot{-}(y+1),z\dot{-}x)$
	LRpart2[f]	3	$LRpart2[f]:=C(LRpart1[f],P_3^3,P_1^3,AddXA)$	$28+|f|$	$\lambda xyz.f(z\dot{-}(x+1),x+y\dot{-}z)$
	LRpart3[f]	2	$LRpart3[f]:=C(LRpart2[f],TriPXA,P_1^2,P_2^2)$	$38+|f|$	$\lambda xy.f(y\dot{-}(TriP(x)+1),TriP(x)+x\dot{-}y)$