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. 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
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$
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$
Iteration	$Rep[f,n]$	1	$Rep[f,n]:=R(K^0[n],C(f,P_2^2))$	$|f|+2n+4$	$\lambda x.f^x(n)$
Iteration of successor	$RepSucc[f]$	2	$RepSucc[f]:=R(S,C(f,P_2^3))$	$|f|+4$	$\lambda xy.f^x(y+1)$
Diagonalization	$RepDiag[f]$	1	$RepDiag[f]:=C(RepSucc[f],S,S)$	$|f|+7$	$\lambda x.f^{x+1}(x+2)$
Ackermann iteration	$Ack[n,f]$	1	$\begin{array}{lcl}Ack[0,f]& :=& f\\ Ack[n+1,f]& :=& Rep[Ack[n,f],1]\end{array}$	$6n+|f|$
Knuth base 2 up-arrows	$Knuth2[n]$	1	$\begin{array}{lcl}Knuth2[0]& :=& Rep[Plus[2],0]\\ Knuth2[n+1]& :=& Rep[Knuth2[n],1]\end{array}$	$6n+7$	$\lambda x.2{\uparrow }^{n}x$
Ackermann Diagonalization on Triangular nums	$ADT[n]$	1	$\begin{array}{lcl}ADT[0]& :=& Tri\\ ADT[n+1]& :=& RepDiag[ADT[n]]\end{array}$	$7n+7$	$\lambda x.>10{\uparrow }^n(x+1)$
Polygonal	$Poly[n]$	1	$Poly[n]:=R(Z^0,R(S,C(Plus[n],P_2^3)))$	$2n+5$	$\lambda x.\frac{n}{2}x(x-1)+x$
	$Tri$	1	$Tri:=Poly[1]=R(Z^0,R(S,C(S,P_2^3)))$	$7$	$\lambda x.\frac{x(x+1)}{2}$
	$Square$	1	$Square:=Poly[2]$	$9$	$\lambda x.x^2$

Champions

n	BBµ(n)	Champion	Champion Found	Holdouts Proven
1	= 0	$Z^0$		Shawn Ligocki 8 Dec 2025 By hand
2	= 0	$M(Z^1),M(P_1^1),C(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
9	≥ 4	$K^0[4]$
11	≥ 5	$K^0[5]$
13	≥ 6	$K^0[6]$
14	≥ 7	$C(RepDiag[S],K^0[2])$	Shawn Ligocki 10 Apr 2026
16	≥ 9	$C(RepDiag[S],K^0[3])$	Shawn Ligocki 10 Apr 2026
17	≥ 10	$C(Tri,K^0[4])$	Shawn Ligocki 9 Dec 2025
18	≥ 21	$C(RepDiag[Tri],K^0[1])$	Jacob Mandelson 9 Apr 2026
20	≥ 1540	$C(RepDiag[Tri],K^0[2])$	Jacob Mandelson 9 Apr 2026
22	≥ 26'357'430	$C(RepDiag[Tri],K^0[3])$	Jacob Mandelson 9 Apr 2026
24	≥ 64'449'908'476'890'321 > 1016.8	$C(RepDiag[Tri],K^0[4])$	Jacob Mandelson 9 Apr 2026
25	$>10^{10^{10^{6.899}}}>10\uparrow \uparrow 3.8388$	$C(ADT[2],K^0[1])$	Jacob Mandelson 9 Apr 2026
27	> $10\uparrow \uparrow 6.0834$	$C(ADT[2],K^0[2])$	Jacob Mandelson 9 Apr 2026
29	> $10\uparrow \uparrow 8.1944$	$C(ADT[2],K^0[3])$	Jacob Mandelson 9 Apr 2026
31	> $10\uparrow \uparrow 10.2800$	$C(ADT[2],K^0[4])$	Jacob Mandelson 9 Apr 2026
32	> $10\uparrow \uparrow 10\uparrow \uparrow 8.1944$	$C(ADT[3],K^0[1])$	Jacob Mandelson 9 Apr 2026
34	> $10\uparrow \uparrow \uparrow 4$	$C(ADT[3],K^0[2])$	Jacob Mandelson 9 Apr 2026
36	> $10\uparrow \uparrow \uparrow 5$	$C(ADT[3],K^0[3])$	Jacob Mandelson 9 Apr 2026
38	> $10\uparrow \uparrow \uparrow 6$	$C(ADT[3],K^0[4])$	Jacob Mandelson 9 Apr 2026
7k+11	> $10{\uparrow }^{k}2$	$C(ADT[k],K^0[1])$	Jacob Mandelson 9 Apr 2026
7k+13	> $10{\uparrow }^{k}3$	$C(ADT[k],K^0[2])$	Jacob Mandelson 9 Apr 2026
7k+15	> $10{\uparrow }^{k}4$	$C(ADT[k],K^0[3])$	Jacob Mandelson 9 Apr 2026
7k+17	> $10{\uparrow }^{k}5$	$C(ADT[k],K^0[4])$	Jacob Mandelson 9 Apr 2026
6k+17	$\ge 2{\uparrow }^{k}4$	$C(Knuth2[k],K^0[4])$	Shawn Ligocki 8 Dec 2025
6k+19	$\ge 2{\uparrow }^{k}5$	$C(Knuth2[k],K^0[5])$	Shawn Ligocki 8 Dec 2025
6k+21	$\ge 2{\uparrow }^{k}6$	$C(Knuth2[k],K^0[6])$	Shawn Ligocki 8 Dec 2025

Macro Bounds

ADT[k]

• $ADT[0](n)=Tri(n)=\frac{n(n+1)}{2}>\frac{1}{2}{n}^2$
• $ADT[0{]}^k(n)>2{\left(\frac{n}{2}\right)}^{2^k}$
• $ADT[1](n)=Tr{i}^{n+1}(n+2)>2{\left(\frac{n+2}{2}\right)}^{2^{n+1}}=2{\left(\frac{(n+2{)}^2}{4}\right)}^{2^n}>A10^{10^{n/A}}$ where $A=\frac{1}{{\log }_{10}(2)}$ (if $n\ge 5$, for smaller values, this can be calculated directly)
• $ADT[1{]}^k(n)>A(10\uparrow {)}^{2k}\frac{n}{A}>10\uparrow \uparrow 2k$ (if $n\ge 4$)
• $ADT[2](n)=ADT[1{]}^{n+1}(n+2)>10\uparrow \uparrow (2n+2)$ (if $n\ge 2$)
• $ADT[k](n)>10{\uparrow }^k(n+1)$ (proof by induction on k with ADT[2] bound above as base case)

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)$	$61+|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$
	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)$
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,R(P_1^2,C(S,P_2^4)))$	$28+|f|$	$\lambda xyz.f(z\dot{-}(x+1),x+y\dot{-}z)$
	LRpart3[f]	2	$LRpart3[f]:=C(LRpart2[f],C(TriP,P_1^2),P_1^2,P_2^2)$	$40+|f|$	$\lambda xy.f(y\dot{-}(TriP(x)+1),TriP(x)+x\dot{-}y)$