General Recursive Function: Difference between revisions

Latest revision as of 16:54, 8 May 2026

General recursive functions (GRFs), also called µ-recursive functions or partial recursive functions, are the collection of partial functions $ℕ^{k} ⇀ ℕ$ 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 $ℕ^{k} ⇀ ℕ$ 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: $B B μ (n) = \max {f () | f \in {GRF}_{0}, | f | = n}$

where $f \in G R F_{k}$ means that $f : ℕ^{k} ⇀ ℕ$ is a k-ary GRF and $| f |$ is the "structural size" of f (the number of atoms and combinators in the definition, see details 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 $G R F_{k}$ inductively based on the following construction rules, start with Atoms and combine them using Combinators.

Atoms

Zero: $\forall k \in ℕ, Z^{k} \in G R F_{k}$ is the constant 0 function $Z^{k} (x_{1}, \dots, x_{k}) = 0$
Successor: $S \in G R F_{1}$ is the successor function $S (x) = x + 1$
Projection: $\forall 1 \leq i \leq k \in ℕ, P_{i}^{k} \in G R F_{k}$ is a projection function $P_{i}^{k} (x_{1}, \dots x_{k}) = x_{i}$

Combinators

Composition: $\forall k, m \in ℕ, \forall h \in G R F_{m}, \forall g_{1}, \dots g_{m} \in G R F_{k}, C^{k} (h, g_{1}, \dots g_{m}) \in G R F_{k}$ is the composition or substitution of the gs into h: $C^{k} (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: $\forall k \in ℕ, \forall g \in G R F_{k}, \forall h \in G R F_{k + 2}, R^{k + 1} (g, h) \in G R F_{k + 1}$ is primitive recursion using g as the base case and h as the inductive step.
Minimization / Unlimited Search: $\forall k \in ℕ, \forall f \in G R F_{k + 1}, M^{k} (f) \in G R F_{k}$ is the µ-operator which allows unlimited search.

The arity superscripts for C, R and M are redundant (except for $C^{k} (h)$ ) and so are sometimes omitted below.

Size

The size of a GRF is the number of atoms and combinators in the definition:

$| Z^{k} | = | P_{i}^{k} | = | S | = 1$
$| C (h, g_{1}, \dots, g_{m}) | = 1 + | h | + | g_{1} | + \dots + | g_{m} |$
$| R (g, h) | = 1 + | g | + | h |$
$| M (f) | = 1 + | f |$

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 simulated as a bounded for loop like this python code:

# f = R(g,h)
def f(n, *xs):
  acc = g(*xs)
  for k in range(n):
    acc = h(k, acc, *xs)
  return acc

The iterative function h is passed two synthetic args in the front: (k) iteration number (0-indexed) and (acc) "accumulator" from previous iterations.

Both the base and iterative cases can be parameterized by values $x_{2}, x_{3}, . . ., x_{k}$ .

If you restrict functions to only those constructible with Z, S, P, C, R (no M) then this defines the Primitive Recursive Functions, a subset of the General Recursive Functions that always halt.

Minimization

$M^{k} (f) (x_{1}, . . ., x_{k}) ≜ \min {i \in ℕ : 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 G R F_{1}$


	Macro	arity	Definition	Size	Function
Constant	$K^{k} [n]$	k	$\begin{array}{lcl} K^{k} [0] & : = & Z^{k} \\ K^{k} [n] & : = & C (P l u s [n], Z^{k}) \end{array}$	$2 n + 1$	$λ x_{1} \dots x_{k} . n$
Plus constant	$P l u s [n]$	1	$\begin{array}{lcl} P l u s [1] & : = & S \\ P l u s [n + 1] & : = & C (S, P l u s [n]) \end{array}$	$2 n - 1$	$λ x . x + n$
Triangular numbers	$T r i$	1	$T r i : = R (Z^{0}, R (S, C (P l u s [2], P_{2}^{3})))$	$7$	$λ x . \frac{x (x + 1)}{2}$
Iteration	$R e p S u c c [f]$	2	$R e p S u c c [f] : = R (S, C (f, P_{2}^{3}))$	$\| f \| + 4$	$λ x y . f^{x} (y + 1)$
Diagonalization & Iteration	$D i a g R e p [f]$	2	$D i a g R e p [f] : = R (S, C (f, P_{2}^{3}, P_{2}^{3}))$	$\| f \| + 5$	$λ x y . (λ z . f (z, z))^{x} (y + 1)$
Diagonalization	$D i a g S [f]$	1	$D i a g S [f] : = C (f, S, S)$	$\| f \| + 3$	$λ x . f (x + 1, x + 1)$
Ackermann iteration	$A c k D i a g 2 [n, f]$	2	$\begin{array}{lcl} A c k D i a g 2 [0, f] & : = & R e p S u c c [f] \\ A c k D i a g 2 [n + 1, f] & : = & D i a g R e p [A c k D i a g 2 [n, f]] \end{array}$	$5 n + 4 + \| f \|$
Ackermann iteration	$A c k D i a g [n, f]$	1	$A c k D i a g [n, f] : = D i a g S [A c k D i a g 2 [n, f]]$	$5 n + 7 + \| f \|$

Champions

n	BBµ(n)	Champion	Champion Found	Holdouts Proven
1	= 0	$Z^{0}$		Shawn Ligocki 8 Dec 2025 By hand
2	= 0	$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	≥ 47	$M (C (R (S, R (P_{1}^{2}, R (P_{2}^{3}, C (R (S, P_{1}^{3}), P_{3}^{5}, P_{2}^{5})))), P_{1}^{1}, S))$	Shawn Ligocki 5 May 2026
17	≥ 2090	$M^{0} (C^{1} (R^{2} (P_{1}^{1}, R^{3} (P_{1}^{2}, R^{4} (R^{3} (R^{2} (S, C^{3} (S, P_{2}^{3})), P_{1}^{4}), P_{2}^{5}))), P_{1}^{1}, S))$	Shawn Ligocki 8 May 2026
18
19
20
21
22	$> 1 0^{13.35}$	$C (A c k D i a g [2, S], K^{0} [1])$	Shawn Ligocki 13 Apr 2026
23	$> 1 0^{1 0^{463}}$	$C (A c k D i a g [1, T r i], K^{0} [1])$	Shawn Ligocki 13 Apr 2026
24
25	$> 10 ↑ ↑ 5$	$C (A c k D i a g [1, T r i], K^{0} [2])$	Shawn Ligocki 13 Apr 2026
26
27	$> 10 ↑ ↑ 10 ↑ ↑ 3$	$C (A c k D i a g [3, S], K^{0} [1])$	Shawn Ligocki 13 Apr 2026
28	$> 10 ↑ ↑ 10 ↑ ↑ 5$	$C (A c k D i a g [2, T r i], K^{0} [1])$	Shawn Ligocki 13 Apr 2026
29	$> 10 ↑ ↑ 10 ↑ ↑ 10 ↑ ↑ 4$	$C (A c k D i a g [3, S], K^{0} [2])$	Shawn Ligocki 13 Apr 2026
30	$> 10 ↑ ↑ 10 ↑ ↑ 10 ↑ ↑ 8$	$C (A c k D i a g [2, T r i], K^{0} [2])$	Shawn Ligocki 13 Apr 2026
31	$> 10 ↑ ↑ 10 ↑ ↑ 10 ↑ ↑ 10 ↑ ↑ 5$	$C (A c k D i a g [3, S], K^{0} [3])$	Shawn Ligocki 13 Apr 2026
...
5k+17	> $10 ↑^{k} 10 ↑^{k} 3$	$C (A c k D i a g [k + 1, S], K^{0} [1])$	Shawn Ligocki 13 Apr 2026
5k+18	> $10 ↑^{k} 10 ↑^{k} 3$	$C (A c k D i a g [k, T r i], K^{0} [1])$	Shawn Ligocki 13 Apr 2026
5k+19	> $10 ↑^{k} 10 ↑^{k} 10 ↑^{k} 4$	$C (A c k D i a g [k + 1, S], K^{0} [2])$	Shawn Ligocki 13 Apr 2026
5k+20	> $10 ↑^{k} 10 ↑^{k} 10 ↑^{k} 5$	$C (A c k D i a g [k, T r i], K^{0} [2])$	Shawn Ligocki 13 Apr 2026
5k+21	> $10 ↑^{k} 10 ↑^{k} 10 ↑^{k} 10 ↑^{k} 5$	$C (A c k D i a g [k + 1, S], K^{0} [3])$	Shawn Ligocki 13 Apr 2026
...
94	> $10 ↑^{15} 10 ↑^{15} 10 ↑^{15} 4$	$C (A c k D i a g [16, S], K^{0} [2])$	Shawn Ligocki 13 Apr 2026
95	$> f_{ω} (1 0^{13})$	Omega() from example_ack.rs	Shawn Ligocki 16 Apr 2026
96
97	$> f_{ω}^{3} (3)$	Omega3() from example_ack.rs	Shawn Ligocki 22 Apr 2026
98
99	$> f_{ω}^{4} (3)$	Omega4() from example_ack.rs	Shawn Ligocki 22 Apr 2026
100	$> f_{ω + 1} (f_{ω}^{2} (1 0^{13})) ≫ Graham's number$	Graham() from example_ack.rs	Shawn Ligocki 16 Apr 2026

Cryptids

So far all Cryptids have been constructed by hand. None found "in the wild" yet.

Hand Constructed Cryptids
Size	Problem	Authors	Ref
49	Brocard's problem	aparker, star and Shawn 3 May 2026	brocard.mgrf Discord
56	5x+1 trajectory of 7	Shawn Ligocki 2 May 2026	collatz.mgrf
81	Erdos Ternary Conjecture	Shawn Ligocki 28 Apr 2026	erdos.mgrf
139	Antihydra-like problem	Jacob Mandelson 8 Apr 2026	Orig (size 141) Size 139

Notable Divergent GRF

Tetrahedral Divisibility

The GRF $M^{0} (C^{1} (R^{2} (S, R^{3} (P_{1}^{2}, R^{4} (P_{1}^{3}, R^{5} (R^{4} (P_{3}^{3}, P_{1}^{5}), P_{2}^{6})))), S, S))$ (Size 15) halts iff there exists some n ≥ 1 such that n+3 divides $T e t r (n) = \frac{n (n + 1) (n + 2)}{6}$ .^[1] aparker^[2] and star^[3] proved that there is no such n, therefore this GRF diverges.

Macro Bounds

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

AckDiag[k, S]

Let $A S_{k} (n) : = D i a g R e p^{k} [R e p S u c c [S]] (n, n) = A c k D i a g [k, S] (n - 1)$

$A S_{0} (n) = S^{n} (n + 1) = 2 n + 1$
$A S_{1} (n) = A S_{0}^{n} (n + 1) = (n + 2) 2^{n} - 1$
$A S_{1} (n) > C \cdot 1 0^{n / C}$ (for $n \geq 2$ )
$A S_{2} (n) = A S_{1}^{n} (n + 1) > C \cdot (10 ↑)^{n} (\frac{n + 1}{C}) > 10 ↑ ↑ n [↑ \frac{n + 1}{C}]$ (for $n \geq 2$ )
$A S_{k} (n) = A S_{k - 1}^{n} (n + 1) > (10 ↑^{k - 1})^{n} (n + 1)$ (for $k \geq 3$ and $n \geq 1$ )

AckDiag[k, Tri]

Let $A T_{k} (n) : = D i a g R e p^{k} [R e p S u c c [T r i]] (n, n) = A c k D i a g [k, T r i] (n - 1)$

$T r i (n) = \frac{n (n + 1)}{2} > \frac{1}{2} n^{2}$
$A T_{0} (n) = T r i^{n} (n + 1) > 2 {(\frac{n + 1}{2})}^{2^{n}}$
$A T_{0} (2) = 21$ , $A T_{0} (3) = 1540$ , $A T_{0} (4) > 1 0^{7.42}$
$A T_{0} (n) > C 1 0^{1 0^{(\frac{n - 1}{C})}} + 1$ (for $n \geq 5$ )
$A T_{1} (n) = A T_{0}^{n} (n + 1) > C (10 ↑)^{2 n - 2} (\frac{A T_{0} (n + 1)}{C})$
$A T_{1} (2) > 1 0^{1 0^{A T_{0} (3) / C}} > 1 0^{1 0^{463}}$ , $A T_{1} (3) > 1 0^{1 0^{1 0^{1 0^{A T_{0} (4) / C}}}} > 10 ↑ ↑ 5$
$A T_{1} (n) > 10 ↑ ↑ 2 n$ (for $n \geq 4$ )
$A T_{2} (n) = A T_{1}^{n} (n + 1) > (10 ↑ ↑)^{n - 1} (A T_{1} (n + 1))$
$A T_{2} (2) = A T_{1}^{2} (3) > A T_{1} (10 ↑ ↑ 5) > 10 ↑ ↑ 10 ↑ ↑ 5$ , $A T_{2} (3) = A T_{1}^{3} (4) > 10 ↑ ↑ 10 ↑ ↑ 10 ↑ ↑ 8$
$A T_{2} (n) > 10 ↑ ↑ ↑ (n + 1)$ (for $n \geq 4$ )
$A T_{3} (n) = A T_{2}^{n} (n + 1) > (10 ↑ ↑ ↑)^{n - 1} (A T_{2} (n + 1))$
$A T_{3} (2) = A T_{2}^{2} (3) > A T_{2} (10 ↑ ↑ ↑ 3) > 10 ↑ ↑ ↑ 10 ↑ ↑ ↑ 3$

Utilizing Minimization

Most champions are primitive recursive functions. In other words they do not 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: $B B μ (6 k + 17) \geq 2 ↑^{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
$P a i r$	2	$P a i r : = C (A d d S, C (T r i, A d d), P_{1}^{2})$	20	$λ x y . \frac{(x + y) (x + y + 1)}{2} + x + 1$
$L e f t$	1	$L e f t : = C (R M o n u s, C (T r i P, I n v T r i C e i l), P r e d)$	38	$L e f t (P a i r (x, y)) = x$
$R i g h t$	1	$R i g h t : = C (R M o n u s, P_{1}^{1}, C (T r i, I n v T r i C e i l))$	36	$R i g h t (P a i r (x, y)) = y$
$L R C a l l [f^{2}]$	1	$L R C a l l [f] : = C (L R p a r t 3 [f], I n v T r i C e i l, P_{1}^{1})$	$59 + \| f \|$	$L R C a l l [f] (P a i r (x, y)) = f (x, y)$

Where these are based on the following definitions:

Macros
	Macro	arity	Definition	Size	Function
Addition	Add	2	$A d d : = R (P_{1}^{1}, C (S, P_{2}^{3}))$	5	$λ x y . x + y$
	AddXA	3	$A d d X A : = R (P_{1}^{2}, C (S, P_{2}^{4}))$	5	$λ x y z . x + y$
	AddS	2	$A d d S : = R (S, C (S, P_{2}^{3}))$	5	$λ x y . x + y + 1$
Predecesor	Pred	1	$P r e d : = R (Z^{0}, P_{1}^{2})$	3	$λ x . x \dot{-} 1$
Monus	RMonus	2	$R M o n u s : = R (P_{1}^{1}, C (P r e d, P_{2}^{3}))$	7	$λ x y . y \dot{-} x$
Triangular numbers	Tri	1	$T r i : = R (Z^{0}, A d d S)$	7	$λ x . \frac{x (x + 1)}{2}$
	TriP	1	$T r i P : = R (Z^{0}, A d d)$	7	$T r i P (x + 1) = T r i (x)$
	TriPXA	2	$T r i P X A : = R (Z^{1}, A d d X A)$	7	$T r i P X A (x, y) = T r i P (x)$
Inverting Tri	RMonusTri	2	$R M o n u s T r i : = C (R M o n u s, C (T r i, P_{1}^{2}), P_{2}^{2})$	18	$λ x y . y \dot{-} T r i (x)$
Inverting Tri	InvTriCeil	1	$I n v T r i C e i l : = M (R M o n u s T r i)$	19	$λ y . \min {x \| T r i (x) \geq y}$
Combined LRCall	RightPiece	3	$R i g h t P i e c e : = R (P_{2}^{2}, C (P r e d, P_{2}^{4}))$	7	$λ x y z . z \dot{-} x$
	LeftPiece	3	$L e f t P i e c e : = C (R M o n u s, C (S, P_{2}^{3}), P_{1}^{3})$	12	$λ x y z . x \dot{-} (y + 1)$
	LRpart1[f]	3	$L R p a r t 1 [f] : = C (f, L e f t P i e c e, R i g h t P i e c e)$	$20 + \| f \|$	$λ x y z . f (x \dot{-} (y + 1), z \dot{-} x)$
	LRpart2[f]	3	$L R p a r t 2 [f] : = C (L R p a r t 1 [f], P_{3}^{3}, P_{1}^{3}, A d d X A)$	$28 + \| f \|$	$λ x y z . f (z \dot{-} (x + 1), x + y \dot{-} z)$
	LRpart3[f]	2	$L R p a r t 3 [f] : = C (L R p a r t 2 [f], T r i P X A, P_{1}^{2}, P_{2}^{2})$	$38 + \| f \|$	$λ x y . f (y \dot{-} (T r i P (x) + 1), T r i P (x) + x \dot{-} y)$

@@ Line 232: / Line 232: @@
 |-
 |16
-|
+|≥ 47
-|
+|<math>M(C(R(S, R(P^2_1, R(P^3_2, C(R(S, P^3_1), P^5_3, P^5_2)))), P^1_1, S))</math>
-|
+|Shawn Ligocki [https://discord.com/channels/960643023006490684/1447627603698647303/1501347538287067267 5 May 2026]
 |
 |-
 |17
-|
+|≥ 2090
-|
+|<math>M^0(C^1(R^2(P^1_1, R^3(P^2_1, R^4(R^3(R^2(S, C^3(S, P^3_2)), P^4_1), P^5_2))), P^1_1, S))</math>
-|
+|Shawn Ligocki [https://discord.com/channels/960643023006490684/1447627603698647303/1502314241766588468 8 May 2026]
 |
 |-
@@ Line 250: / Line 250: @@
 |-
 |19
-|≥ 39
+|
-|<math>C(AckDiag[1, S], K^0[2])</math>
+|
-|Shawn Ligocki [https://discord.com/channels/960643023006490684/1447627603698647303/1492997385247264941 12 Apr 2026]
+|
 |
 |-
 |20
-|≥ 1540
+|
-|<math>C(AckDiag[0,Tri], K^0[2])</math>
+|
-|Jacob Mandelson 9 Apr 2026
+|
 |
 |-

General Recursive Function: Difference between revisions

Latest revision as of 16:54, 8 May 2026

Contents

Definition

Structure

Atoms

Combinators

Size

Primitive Recursion

Minimization

Macros

Champions

Cryptids

Notable Divergent GRF

Tetrahedral Divisibility

Macro Bounds

AckDiag[k, S]

AckDiag[k, Tri]

Utilizing Minimization

Navigation menu

General Recursive Function: Difference between revisions

Latest revision as of 16:54, 8 May 2026

Definition

Structure

Atoms

Combinators

Size

Primitive Recursion

Minimization

Macros

Champions

Cryptids

Notable Divergent GRF

Tetrahedral Divisibility

Macro Bounds

AckDiag[k, S]

AckDiag[k, Tri]

Utilizing Minimization

Navigation menu

Search