BusyBeaverWiki - User contributions [en]

General Recursive Function

2026-04-18T05:07:05Z

JLM: /* Macros */ Fix typos in AckDiag2 macro def'n.

'''General recursive functions''' ('''GRFs'''), also called '''µ-recursive functions''' or '''partial recursive functions''', are the collection of [[Wikipedia:partial functions|partial functions]] <math>\N^k \rightharpoonup \N</math> 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 <math>\N^k \rightharpoonup \N</math> 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:<math display="block">BB \mu (n) = \max \{ f() | f \in \text{GRF}_0 , |f| = n \}</math>

where <math>f \in GRF_k</math> means that <math>f: \N^k \rightharpoonup \N</math> is a k-ary GRF and <math>|f|</math> 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 <math>GRF_k</math> inductively based on the following construction rules, start with Atoms and combine them using Combinators.

====== Atoms ======

* Zero: <math>\forall k \in \N, Z^k \in GRF_k</math> is the constant 0 function <math>Z^k(x_1, \dots, x_k) = 0</math>
* Successor: <math>S \in GRF_1</math> is the successor function <math>S(x) = x+1</math>
* Projection: <math>\forall 1 \le i \le k \in \N, P^k_i \in GRF_k</math> is a projection function <math>P^k_i(x_1, \dots x_k) = x_i</math>

===== Combinators =====

* Composition: <math>\forall k,m \in \N, \forall h \in GRF_m, \forall g_1, \dots g_m \in GRF_k, C(h, g_1, \dots g_m) \in GRF_k</math> is the composition or substitution of the ''g''s into ''h'': <math>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))</math>
* Primitive Recursion: <math>\forall k \in \N, \forall g \in GRF_k, \forall h \in GRF_{k+2}, R(g, h) \in GRF_{k+1}</math> is primitive recursion using ''g'' as the base case and ''h'' as the inductive step.
* Minimization / Unlimited Search: <math>\forall k \in \N, \forall f \in GRF_{k+1}, M(f) \in GRF_k</math> is the µ-operator which allows unlimited search.

=== Primitive Recursion ===
<math>R</math> models a typical iterative function definition over ℕ.

Base case: <math>R^k(g, h)(0, x_2, x_3, ..., x_k) = g(x_2, x_3, ..., x_k)</math>

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

<math>R</math> 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 <math>g</math>), then 1, 2, 3, etc. until <math>x_1</math> is reached, each time calling <math>h</math> with the prior iteration count for its first argument and the result of the prior call for its second.

=== Minimization ===
<math>M^k(f)(x_1, ..., x_k) \triangleq \min \{i \in \N: f(i, x_1, ..., x_k) = 0\}</math>

In computational language, when ''M(f)'' is evaluated it can be considered to calculate <math>f(i, x_1, ..., x_k)</math> with <math>i=0</math>, then <math>i=1</math>, then <math>i=2</math> etc. until one of the calls to <math>f</math> returns 0, at which point it returns the value of <math>i</math> which first gave a result of 0. If no first argument causes <math>f</math> to return 0, <math>M(f)</math> 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 <math>f \in GRF_1</math>
{| class="wikitable"
|+
!
!Macro
!arity
!Definition
!Size
!Function
|-
|Constant
|<math>K^k[n]</math>
|k
|<math>\begin{array}{lcl}
K^k[0] & := & Z^k \\
K^k[n] & := & C(Plus[n], Z^k)
\end{array}</math>
|<math>2n+1</math>
|<math>\lambda x_1 \dots x_k. n</math>
|-
|Plus constant
|<math>Plus[n]</math>
|1
|<math>\begin{array}{lcl}
Plus[1] & := & S \\
Plus[n+1] & := & C(S, Plus[n])
\end{array}</math>
|<math>2n-1</math>
|<math>\lambda x. x+n</math>
|-
|Triangular numbers
|<math>Tri</math>
|1
|<math>Tri := R(Z^0, R(S, C(Plus[2], P^3_2)))</math>
|<math>7</math>
|<math>\lambda x. \frac{x(x+1)}{2}</math>
|-
|Iteration
|<math>RepSucc[f]</math>
|2
|<math>RepSucc[f] := R(S, C(f, P^3_2))</math>
|<math>|f| + 4</math>
|<math>\lambda x\ y. f^x(y+1)</math>
|-
|Diagonalization & Iteration
|<math>DiagRep[f]</math>
|2
|<math>DiagRep[f] := R(S, C(f, P^3_2, P^3_2))</math>
|<math>|f| + 5</math>
|<math>\lambda x\ y. (\lambda z. f(z,z))^x (y+1)</math>
|-
|Diagonalization
|<math>DiagS[f]</math>
|1
|<math>DiagS[f] := C(f, S, S)</math>
|<math>|f| + 3</math>
|<math>\lambda x. f(x+1, x+1)</math>
|-
| rowspan="2" |Ackermann iteration
|<math>AckDiag2[n,f]</math>
|2
|<math>\begin{array}{lcl}
AckDiag2[0,f] & := & RepSucc[f] \\
AckDiag2[n+1,f] & := & DiagRep[AckDiag2[n,f]]
\end{array}</math>
|<math>5n + 4 + |f|</math>
|
|-
|<math>AckDiag[n,f]</math>
|1
|<math>AckDiag[n,f] := DiagS[AckDiag2[n,f]]</math>
|<math>5n + 7 + |f|</math>
|
|}

== Champions ==
{| class="wikitable"
!n
!BBµ(n)
!Champion
!Champion Found
!Holdouts Proven
|-
|1
|= 0
|<math>Z^0</math>
|
|Shawn Ligocki [https://discord.com/channels/960643023006490684/1447627603698647303/1447693296322215976 8 Dec 2025] By hand
|-
|2
|= 0
|<math>M(Z^1), M(P^1_1), C(Z^0)</math>
|
|Shawn Ligocki [https://discord.com/channels/960643023006490684/1447627603698647303/1447693296322215976 8 Dec 2025] By hand
|-
|3
|= 1
|<math>K^0[1]</math>
|
|Shawn Ligocki [https://discord.com/channels/960643023006490684/1447627603698647303/1447693296322215976 8 Dec 2025] By hand
|-
|4
|= 1
|<math>C^0(K^0[1])</math>
|
|Jacob Mandelson [https://mandelson.org/grf/ 3 Apr 2026]
|-
|5
|= 2
|<math>K^0[2]</math>
|
|Jacob Mandelson [https://mandelson.org/grf/ 3 Apr 2026]
|-
|6
|= 2
|<math>C^0(K^0[2])</math>
|
|Jacob Mandelson [https://mandelson.org/grf/ 3 Apr 2026]
|-
|7
|= 3
|<math>K^0[3]</math>
|
|Jacob Mandelson [https://mandelson.org/grf/ 3 Apr 2026]
|-
|8
|≥ 3
|<math>C^0(K^0[3])</math>
|
|
|-
|9
|≥ 4
|<math>K^0[4]</math>
|
|
|-
|10
|≥ 4
|<math>C^0(K^0[4])</math>
|
|
|-
|11
|≥ 5
|<math>K^0[5]</math>
|
|
|-
|12
|≥ 5
|<math>C^0(K^0[5])</math>
|
|
|-
|13
|≥ 6
|<math>K^0[6]</math>
|
|
|-
|14
|≥ 7
|<math>C(AckDiag[0, S], K^0[2])</math>
|Shawn Ligocki [https://discord.com/channels/960643023006490684/1447627603698647303/1492246885329670184 10 Apr 2026]
|
|-
|15
|≥ 7
|<math>K^0[7]</math>
|
|
|-
|16
|≥ 10
|<math>C(AckDiag[0, Plus[2]], K^0[2])</math>
|Shawn Ligocki [https://discord.com/channels/960643023006490684/1447627603698647303/1492394919728517160 11 Apr 2026]
|
|-
|17
|≥ 15
|<math>C(AckDiag[1, S], K^0[1])</math>
|Shawn Ligocki [https://discord.com/channels/960643023006490684/1447627603698647303/1492990073820545125 12 Apr 2026]
|
|-
|18
|≥ 21
|<math>C(AckDiag[0,Tri], K^0[1])</math>
|Jacob Mandelson [https://discord.com/channels/960643023006490684/1447627603698647303/1492021428546179182 9 Apr 2026]
|
|-
|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
|
|-
|21
|
|
|
|
|-
|22
|<math>> 10^{13.35}</math>
|<math>C(AckDiag[2, S], K^0[1])</math>
|Shawn Ligocki 13 Apr 2026
|
|-
|23
|<math>> 10^{10^{463}}</math>
|<math>C(AckDiag[1,Tri], K^0[1])</math>
|Shawn Ligocki 13 Apr 2026
|
|-
|24
|
|
|
|
|-
|25
|<math>> 10 \uparrow\uparrow 5</math>
|<math>C(AckDiag[1,Tri], K^0[2])</math>
|Shawn Ligocki 13 Apr 2026
|
|-
|26
|
|
|
|
|-
|27
|<math>> 10 \uparrow\uparrow 10 \uparrow\uparrow 3</math>
|<math>C(AckDiag[3, S], K^0[1])</math>
|Shawn Ligocki 13 Apr 2026
|
|-
|28
|<math>> 10 \uparrow\uparrow 10 \uparrow\uparrow 5</math>
|<math>C(AckDiag[2,Tri], K^0[1])</math>
|Shawn Ligocki 13 Apr 2026
|
|-
|29
|<math>> 10 \uparrow\uparrow 10 \uparrow\uparrow 10 \uparrow\uparrow 4</math>
|<math>C(AckDiag[3, S], K^0[2])</math>
|Shawn Ligocki 13 Apr 2026
|
|-
|30
|<math>> 10 \uparrow\uparrow 10 \uparrow\uparrow 10 \uparrow\uparrow 8</math>
|<math>C(AckDiag[2,Tri], K^0[2])</math>
|Shawn Ligocki 13 Apr 2026
|
|-
|31
|<math>> 10 \uparrow\uparrow 10 \uparrow\uparrow 10 \uparrow\uparrow 10 \uparrow\uparrow 5</math>
|<math>C(AckDiag[3, S], K^0[3])</math>
|Shawn Ligocki 13 Apr 2026
|
|-
|
|
|
|
|
|-
|5k+17
|> <math>10 \uparrow^k 10 \uparrow^k 3</math>
|<math>C(AckDiag[k+1, S], K^0[1])</math>
|Shawn Ligocki 13 Apr 2026
|
|-
|5k+18
|> <math>10 \uparrow^k 10 \uparrow^k 3</math>
|<math>C(AckDiag[k,Tri], K^0[1])</math>
|Shawn Ligocki 13 Apr 2026
|
|-
|5k+19
|> <math>10 \uparrow^k 10 \uparrow^k 10 \uparrow^k 4</math>
|<math>C(AckDiag[k+1, S], K^0[2])</math>
|Shawn Ligocki 13 Apr 2026
|
|-
|5k+20
|> <math>10 \uparrow^k 10 \uparrow^k 10 \uparrow^k 5</math>
|<math>C(AckDiag[k,Tri], K^0[2])</math>
|Shawn Ligocki 13 Apr 2026
|
|-
|5k+21
|> <math>10 \uparrow^k 10 \uparrow^k 10 \uparrow^k 10 \uparrow^k 5</math>
|<math>C(AckDiag[k+1, S], K^0[3])</math>
|Shawn Ligocki 13 Apr 2026
|
|-
|
|
|
|
|
|-
|100
|> Graham's number
|See [https://github.com/sligocki/etc/blob/main/gen_rec/src/example_ack.rs example_ack.rs]
|Shawn Ligocki [https://discord.com/channels/960643023006490684/1447627603698647303/1494396445208608788 16 Apr 2026]
|
|}

== Cryptids ==
Jacob Mandelson constructed a size 141 [[Cryptid]] on 8 Apr 2026 [https://discord.com/channels/960643023006490684/1447627603698647303/1491642156295913482], shrunk to 139 by 17 Apr 2026.[https://discord.com/channels/960643023006490684/1447627603698647303/1494889866704588983]

== Macro Bounds ==
Let <math>C = \frac{1}{\log_{10}(2)} \approx 3.32</math>

=== AckDiag[k, S] ===
Let <math>AS_k(n) := DiagRep^k[RepSucc[S]](n,n) = AckDiag[k,S](n-1)</math>

* <math>AS_0(n) = S^n(n+1) = 2n+1</math>
* <math>AS_1(n) = AS_0^n(n+1) = (n+2) 2^n - 1</math>
* <math>AS_1(n) > C \cdot 10^{n/C}</math> (for <math>n \ge 2</math>)
* <math>AS_2(n) = AS_1^n(n+1) > C \cdot (10 \uparrow)^n \left( \frac{n+1}{C} \right) > 10 \uparrow\uparrow n \left[ \uparrow \frac{n+1}{C} \right]</math> (for <math>n \ge 2</math>)
* <math>AS_k(n) = AS_{k-1}^n(n+1) > (10 \uparrow^{k-1})^n (n+1)</math> (for <math>k \ge 3</math> and <math>n \ge 1</math>)

=== AckDiag[k, Tri] ===
Let <math>AT_k(n) := DiagRep^k[RepSucc[Tri]](n,n) = AckDiag[k,Tri](n-1)</math>
* <math>Tri(n) = \frac{n(n+1)}{2} > \frac{1}{2} n^2</math>
* <math>AT_0(n) = Tri^n(n+1) > 2 \left( \frac{n+1}{2} \right)^{2^n}</math>
* <math>AT_0(2) = 21</math>, <math>AT_0(3) = 1540</math>, <math>AT_0(4) > 10^{7.42}</math>
* <math>AT_0(n) > C 10^{10^{\left(\frac{n-1}{C}\right)}} + 1</math> (for <math>n \ge 5</math>)
* <math>AT_1(n) = AT_0^n(n+1) > C (10 \uparrow)^{2n-2} \left( \frac{AT_0(n+1)}{C} \right)</math>
* <math>AT_1(2) > 10^{10^{AT_0(3) / C}} > 10^{10^{463}}</math>, <math>AT_1(3) > 10^{10^{10^{10^{AT_0(4) / C}}}} > 10 \uparrow\uparrow 5</math>
* <math>AT_1(n) > 10 \uparrow\uparrow 2n</math> (for <math>n \ge 4</math>)
* <math>AT_2(n) = AT_1^n(n+1) > (10 \uparrow\uparrow)^{n-1} (AT_1(n+1))</math>
* <math>AT_2(2) = AT_1^2(3) > AT_1(10 \uparrow\uparrow 5) > 10 \uparrow\uparrow 10 \uparrow\uparrow 5</math>, <math>AT_2(3) = AT_1^3(4) > 10 \uparrow\uparrow 10 \uparrow\uparrow 10 \uparrow\uparrow 8</math>
* <math>AT_2(n) > 10 \uparrow\uparrow\uparrow (n+1)</math> (for <math>n \ge 4</math>)
* <math>AT_3(n) = AT_2^n(n+1) > (10 \uparrow\uparrow\uparrow)^{n-1} (AT_2(n+1))</math>
* <math>AT_3(2) = AT_2^2(3) > AT_2(10 \uparrow\uparrow\uparrow 3) > 10 \uparrow\uparrow\uparrow 10 \uparrow\uparrow\uparrow 3</math>

== 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: <math>BB\mu(6k+17) \ge 2 \uparrow^k 4</math>.

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 [[wikipedia:Pairing_function|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, [[wikipedia:Common_subexpression_elimination|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:
{| class="wikitable"
|+Smallest Pairing Functions
!Macro
!arity
!Definition
!Size
!Function
|-
|<math>Pair</math>
|2
|<math>Pair := C(AddS, C(Tri, Add), P^2_1)</math>
|20
|<math>\lambda xy. \frac{(x+y)(x+y+1)}{2} + x + 1</math>
|-
|<math>Left</math>
|1
|<math>Left := C(RMonus, C(TriP, InvTriCeil), Pred)</math>
|38
|<math>Left(Pair(x,y)) = x</math>
|-
|<math>Right</math>
|1
|<math>Right := C(RMonus, P^1_1, C(Tri, InvTriCeil))</math>
|36
|<math>Right(Pair(x,y)) = y</math>
|-
|<math>LRCall[f^2]</math>
|1
|<math>LRCall[f] := C(LRpart3[f], InvTriCeil, P^1_1)</math>
|<math>59 + |f|</math>
|<math>LRCall[f](Pair(x,y)) = f(x,y)</math>
|}
Where these are based on the following definitions:
{| class="wikitable"
|+Macros
!
!Macro
!arity
!Definition
!Size
!Function
|-
| rowspan="3" |Addition
|Add
|2
|<math>Add := R(P^1_1, C(S, P^3_2))</math>
|5
|<math>\lambda xy. x+y</math>
|-
|AddXA
|3
|<math>AddXA := R(P^2_1, C(S, P^4_2))</math>
|5
|<math>\lambda xyz. x+y</math>
|-
|AddS
|2
|<math>AddS := R(S, C(S, P^3_2))</math>
|5
|<math>\lambda xy. x+y+1</math>
|-
|[[wikipedia:Primitive_recursive_function#Predecessor|Predecesor]]
|Pred
|1
|<math>Pred := R(Z^0, P^2_1)</math>
|3
|<math>\lambda x. x \dot - 1</math>
|-
|[[wikipedia:Monus#Natural_numbers|Monus]]
|RMonus
|2
|<math>RMonus := R(P^1_1, C(Pred, P^3_2))</math>
|7
|<math>\lambda xy. y \dot - x</math>
|-
| rowspan="3" |Triangular numbers
|Tri
|1
|<math>Tri := R(Z^0, AddS)</math>
|7
|<math>\lambda x. \frac{x(x+1)}{2}</math>
|-
|TriP
|1
|<math>TriP := R(Z^0, Add)</math>
|7
|<math>TriP(x+1) = Tri(x)</math>
|-
|TriPXA
|2
|<math>TriPXA := R(Z^1, AddXA)</math>
|7
|<math>TriPXA(x,y) = TriP(x)</math>
|-
| rowspan="2" |Inverting Tri
|RMonusTri
|2
|<math>RMonusTri := C(RMonus, C(Tri, P^2_1), P^2_2)</math>
|18
|<math>\lambda xy. y \dot - Tri(x)</math>
|-
|InvTriCeil
|1
|<math>InvTriCeil := M(RMonusTri)</math>
|19
|<math>\lambda y. \min \{x | Tri(x) \ge y \}</math>
|-
| rowspan="5" | Combined LRCall
|RightPiece
|3
|<math>RightPiece := R(P^2_2, C(Pred, P^4_2))</math>
|7
|<math>\lambda xyz. z \dot - x</math>
|-
|LeftPiece
|3
|<math>LeftPiece := C(RMonus, C(S, P^3_2), P^3_1)</math>
|12
|<math>\lambda xyz. x \dot - (y+1)</math>
|-
|LRpart1[f]
|3
|<math>LRpart1[f] := C(f, LeftPiece, RightPiece)</math>
|<math>20 + |f|</math>
|<math>\lambda xyz. f(x \dot - (y+1), z \dot - x)</math>
|-
|LRpart2[f]
|3
|<math>LRpart2[f] := C(LRpart1[f], P^3_3, P^3_1, AddXA)</math>
|<math>28 + |f|</math>
|<math>\lambda xyz. f(z \dot - (x+1), x+y\dot - z)</math>
|-
|LRpart3[f]
|2
|<math>LRpart3[f] := C(LRpart2[f], TriPXA, P^2_1, P^2_2)</math>
|<math>38 + |f|</math>
|<math>\lambda xy. f(y\dot - (TriP(x)+1), TriP(x)+x\dot - y)</math>
|}

[[Category:functions]]

General Recursive Function

2026-04-18T02:46:08Z

JLM: /* Cryptids */ Shrinkage

'''General recursive functions''' ('''GRFs'''), also called '''µ-recursive functions''' or '''partial recursive functions''', are the collection of [[Wikipedia:partial functions|partial functions]] <math>\N^k \rightharpoonup \N</math> 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 <math>\N^k \rightharpoonup \N</math> 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:<math display="block">BB \mu (n) = \max \{ f() | f \in \text{GRF}_0 , |f| = n \}</math>

where <math>f \in GRF_k</math> means that <math>f: \N^k \rightharpoonup \N</math> is a k-ary GRF and <math>|f|</math> 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 <math>GRF_k</math> inductively based on the following construction rules, start with Atoms and combine them using Combinators.

====== Atoms ======

* Zero: <math>\forall k \in \N, Z^k \in GRF_k</math> is the constant 0 function <math>Z^k(x_1, \dots, x_k) = 0</math>
* Successor: <math>S \in GRF_1</math> is the successor function <math>S(x) = x+1</math>
* Projection: <math>\forall 1 \le i \le k \in \N, P^k_i \in GRF_k</math> is a projection function <math>P^k_i(x_1, \dots x_k) = x_i</math>

===== Combinators =====

* Composition: <math>\forall k,m \in \N, \forall h \in GRF_m, \forall g_1, \dots g_m \in GRF_k, C(h, g_1, \dots g_m) \in GRF_k</math> is the composition or substitution of the ''g''s into ''h'': <math>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))</math>
* Primitive Recursion: <math>\forall k \in \N, \forall g \in GRF_k, \forall h \in GRF_{k+2}, R(g, h) \in GRF_{k+1}</math> is primitive recursion using ''g'' as the base case and ''h'' as the inductive step.
* Minimization / Unlimited Search: <math>\forall k \in \N, \forall f \in GRF_{k+1}, M(f) \in GRF_k</math> is the µ-operator which allows unlimited search.

=== Primitive Recursion ===
<math>R</math> models a typical iterative function definition over ℕ.

Base case: <math>R^k(g, h)(0, x_2, x_3, ..., x_k) = g(x_2, x_3, ..., x_k)</math>

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

<math>R</math> 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 <math>g</math>), then 1, 2, 3, etc. until <math>x_1</math> is reached, each time calling <math>h</math> with the prior iteration count for its first argument and the result of the prior call for its second.

=== Minimization ===
<math>M^k(f)(x_1, ..., x_k) \triangleq \min \{i \in \N: f(i, x_1, ..., x_k) = 0\}</math>

In computational language, when ''M(f)'' is evaluated it can be considered to calculate <math>f(i, x_1, ..., x_k)</math> with <math>i=0</math>, then <math>i=1</math>, then <math>i=2</math> etc. until one of the calls to <math>f</math> returns 0, at which point it returns the value of <math>i</math> which first gave a result of 0. If no first argument causes <math>f</math> to return 0, <math>M(f)</math> 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 <math>f \in GRF_1</math>
{| class="wikitable"
|+
!
!Macro
!arity
!Definition
!Size
!Function
|-
|Constant
|<math>K^k[n]</math>
|k
|<math>\begin{array}{lcl}
K^k[0] & := & Z^k \\
K^k[n] & := & C(Plus[n], Z^k)
\end{array}</math>
|<math>2n+1</math>
|<math>\lambda x_1 \dots x_k. n</math>
|-
|Plus constant
|<math>Plus[n]</math>
|1
|<math>\begin{array}{lcl}
Plus[1] & := & S \\
Plus[n+1] & := & C(S, Plus[n])
\end{array}</math>
|<math>2n-1</math>
|<math>\lambda x. x+n</math>
|-
|Triangular numbers
|<math>Tri</math>
|1
|<math>Tri := R(Z^0, R(S, C(Plus[2], P^3_2)))</math>
|<math>7</math>
|<math>\lambda x. \frac{x(x+1)}{2}</math>
|-
|Iteration
|<math>RepSucc[f]</math>
|2
|<math>RepSucc[f] := R(S, C(f, P^3_2))</math>
|<math>|f| + 4</math>
|<math>\lambda x\ y. f^x(y+1)</math>
|-
|Diagonalization & Iteration
|<math>DiagRep[f]</math>
|2
|<math>DiagRep[f] := R(S, C(f, P^3_2, P^3_2))</math>
|<math>|f| + 5</math>
|<math>\lambda x\ y. (\lambda z. f(z,z))^x (y+1)</math>
|-
|Diagonalization
|<math>DiagS[f]</math>
|1
|<math>DiagS[f] := C(f, S, S)</math>
|<math>|f| + 3</math>
|<math>\lambda x. f(x+1, x+1)</math>
|-
| rowspan="2" |Ackermann iteration
|<math>AckDiag2[f]</math>
|2
|<math>\begin{array}{lcl}
AckDiag2[0,f] & := & RepSucc[f] \\
AckDiag2[n+1,f] & := & DiagRep[Ack[n,f]]
\end{array}</math>
|<math>5n + 4 + |f|</math>
|
|-
|<math>AckDiag[n,f]</math>
|1
|<math>AckDiag[n,f] := DiagS[AckDiag2[n,f]]</math>
|<math>5n + 7 + |f|</math>
|
|}

== Champions ==
{| class="wikitable"
!n
!BBµ(n)
!Champion
!Champion Found
!Holdouts Proven
|-
|1
|= 0
|<math>Z^0</math>
|
|Shawn Ligocki [https://discord.com/channels/960643023006490684/1447627603698647303/1447693296322215976 8 Dec 2025] By hand
|-
|2
|= 0
|<math>M(Z^1), M(P^1_1), C(Z^0)</math>
|
|Shawn Ligocki [https://discord.com/channels/960643023006490684/1447627603698647303/1447693296322215976 8 Dec 2025] By hand
|-
|3
|= 1
|<math>K^0[1]</math>
|
|Shawn Ligocki [https://discord.com/channels/960643023006490684/1447627603698647303/1447693296322215976 8 Dec 2025] By hand
|-
|4
|= 1
|<math>C^0(K^0[1])</math>
|
|Jacob Mandelson [https://mandelson.org/grf/ 3 Apr 2026]
|-
|5
|= 2
|<math>K^0[2]</math>
|
|Jacob Mandelson [https://mandelson.org/grf/ 3 Apr 2026]
|-
|6
|= 2
|<math>C^0(K^0[2])</math>
|
|Jacob Mandelson [https://mandelson.org/grf/ 3 Apr 2026]
|-
|7
|= 3
|<math>K^0[3]</math>
|
|Jacob Mandelson [https://mandelson.org/grf/ 3 Apr 2026]
|-
|8
|≥ 3
|<math>C^0(K^0[3])</math>
|
|
|-
|9
|≥ 4
|<math>K^0[4]</math>
|
|
|-
|10
|≥ 4
|<math>C^0(K^0[4])</math>
|
|
|-
|11
|≥ 5
|<math>K^0[5]</math>
|
|
|-
|12
|≥ 5
|<math>C^0(K^0[5])</math>
|
|
|-
|13
|≥ 6
|<math>K^0[6]</math>
|
|
|-
|14
|≥ 7
|<math>C(AckDiag[0, S], K^0[2])</math>
|Shawn Ligocki [https://discord.com/channels/960643023006490684/1447627603698647303/1492246885329670184 10 Apr 2026]
|
|-
|15
|≥ 7
|<math>K^0[7]</math>
|
|
|-
|16
|≥ 10
|<math>C(AckDiag[0, Plus[2]], K^0[2])</math>
|Shawn Ligocki [https://discord.com/channels/960643023006490684/1447627603698647303/1492394919728517160 11 Apr 2026]
|
|-
|17
|≥ 15
|<math>C(AckDiag[1, S], K^0[1])</math>
|Shawn Ligocki [https://discord.com/channels/960643023006490684/1447627603698647303/1492990073820545125 12 Apr 2026]
|
|-
|18
|≥ 21
|<math>C(AckDiag[0,Tri], K^0[1])</math>
|Jacob Mandelson [https://discord.com/channels/960643023006490684/1447627603698647303/1492021428546179182 9 Apr 2026]
|
|-
|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
|
|-
|21
|
|
|
|
|-
|22
|<math>> 10^{13.35}</math>
|<math>C(AckDiag[2, S], K^0[1])</math>
|Shawn Ligocki 13 Apr 2026
|
|-
|23
|<math>> 10^{10^{463}}</math>
|<math>C(AckDiag[1,Tri], K^0[1])</math>
|Shawn Ligocki 13 Apr 2026
|
|-
|24
|
|
|
|
|-
|25
|<math>> 10 \uparrow\uparrow 5</math>
|<math>C(AckDiag[1,Tri], K^0[2])</math>
|Shawn Ligocki 13 Apr 2026
|
|-
|26
|
|
|
|
|-
|27
|<math>> 10 \uparrow\uparrow 10 \uparrow\uparrow 3</math>
|<math>C(AckDiag[3, S], K^0[1])</math>
|Shawn Ligocki 13 Apr 2026
|
|-
|28
|<math>> 10 \uparrow\uparrow 10 \uparrow\uparrow 5</math>
|<math>C(AckDiag[2,Tri], K^0[1])</math>
|Shawn Ligocki 13 Apr 2026
|
|-
|29
|<math>> 10 \uparrow\uparrow 10 \uparrow\uparrow 10 \uparrow\uparrow 4</math>
|<math>C(AckDiag[3, S], K^0[2])</math>
|Shawn Ligocki 13 Apr 2026
|
|-
|30
|<math>> 10 \uparrow\uparrow 10 \uparrow\uparrow 10 \uparrow\uparrow 8</math>
|<math>C(AckDiag[2,Tri], K^0[2])</math>
|Shawn Ligocki 13 Apr 2026
|
|-
|31
|<math>> 10 \uparrow\uparrow 10 \uparrow\uparrow 10 \uparrow\uparrow 10 \uparrow\uparrow 5</math>
|<math>C(AckDiag[3, S], K^0[3])</math>
|Shawn Ligocki 13 Apr 2026
|
|-
|
|
|
|
|
|-
|5k+17
|> <math>10 \uparrow^k 10 \uparrow^k 3</math>
|<math>C(AckDiag[k+1, S], K^0[1])</math>
|Shawn Ligocki 13 Apr 2026
|
|-
|5k+18
|> <math>10 \uparrow^k 10 \uparrow^k 3</math>
|<math>C(AckDiag[k,Tri], K^0[1])</math>
|Shawn Ligocki 13 Apr 2026
|
|-
|5k+19
|> <math>10 \uparrow^k 10 \uparrow^k 10 \uparrow^k 4</math>
|<math>C(AckDiag[k+1, S], K^0[2])</math>
|Shawn Ligocki 13 Apr 2026
|
|-
|5k+20
|> <math>10 \uparrow^k 10 \uparrow^k 10 \uparrow^k 5</math>
|<math>C(AckDiag[k,Tri], K^0[2])</math>
|Shawn Ligocki 13 Apr 2026
|
|-
|5k+21
|> <math>10 \uparrow^k 10 \uparrow^k 10 \uparrow^k 10 \uparrow^k 5</math>
|<math>C(AckDiag[k+1, S], K^0[3])</math>
|Shawn Ligocki 13 Apr 2026
|
|-
|
|
|
|
|
|-
|100
|> Graham's number
|See [https://github.com/sligocki/etc/blob/main/gen_rec/src/example_ack.rs example_ack.rs]
|Shawn Ligocki [https://discord.com/channels/960643023006490684/1447627603698647303/1494396445208608788 16 Apr 2026]
|
|}

== Cryptids ==
Jacob Mandelson constructed a size 141 [[Cryptid]] on 8 Apr 2026 [https://discord.com/channels/960643023006490684/1447627603698647303/1491642156295913482], shrunk to 139 by 17 Apr 2026.[https://discord.com/channels/960643023006490684/1447627603698647303/1494889866704588983]

== Macro Bounds ==
Let <math>C = \frac{1}{\log_{10}(2)} \approx 3.32</math>

=== AckDiag[k, S] ===
Let <math>AS_k(n) := DiagRep^k[RepSucc[S]](n,n) = AckDiag[k,S](n-1)</math>

* <math>AS_0(n) = S^n(n+1) = 2n+1</math>
* <math>AS_1(n) = AS_0^n(n+1) = (n+2) 2^n - 1</math>
* <math>AS_1(n) > C \cdot 10^{n/C}</math> (for <math>n \ge 2</math>)
* <math>AS_2(n) = AS_1^n(n+1) > C \cdot (10 \uparrow)^n \left( \frac{n+1}{C} \right) > 10 \uparrow\uparrow n \left[ \uparrow \frac{n+1}{C} \right]</math> (for <math>n \ge 2</math>)
* <math>AS_k(n) = AS_{k-1}^n(n+1) > (10 \uparrow^{k-1})^n (n+1)</math> (for <math>k \ge 3</math> and <math>n \ge 1</math>)

=== AckDiag[k, Tri] ===
Let <math>AT_k(n) := DiagRep^k[RepSucc[Tri]](n,n) = AckDiag[k,Tri](n-1)</math>
* <math>Tri(n) = \frac{n(n+1)}{2} > \frac{1}{2} n^2</math>
* <math>AT_0(n) = Tri^n(n+1) > 2 \left( \frac{n+1}{2} \right)^{2^n}</math>
* <math>AT_0(2) = 21</math>, <math>AT_0(3) = 1540</math>, <math>AT_0(4) > 10^{7.42}</math>
* <math>AT_0(n) > C 10^{10^{\left(\frac{n-1}{C}\right)}} + 1</math> (for <math>n \ge 5</math>)
* <math>AT_1(n) = AT_0^n(n+1) > C (10 \uparrow)^{2n-2} \left( \frac{AT_0(n+1)}{C} \right)</math>
* <math>AT_1(2) > 10^{10^{AT_0(3) / C}} > 10^{10^{463}}</math>, <math>AT_1(3) > 10^{10^{10^{10^{AT_0(4) / C}}}} > 10 \uparrow\uparrow 5</math>
* <math>AT_1(n) > 10 \uparrow\uparrow 2n</math> (for <math>n \ge 4</math>)
* <math>AT_2(n) = AT_1^n(n+1) > (10 \uparrow\uparrow)^{n-1} (AT_1(n+1))</math>
* <math>AT_2(2) = AT_1^2(3) > AT_1(10 \uparrow\uparrow 5) > 10 \uparrow\uparrow 10 \uparrow\uparrow 5</math>, <math>AT_2(3) = AT_1^3(4) > 10 \uparrow\uparrow 10 \uparrow\uparrow 10 \uparrow\uparrow 8</math>
* <math>AT_2(n) > 10 \uparrow\uparrow\uparrow (n+1)</math> (for <math>n \ge 4</math>)
* <math>AT_3(n) = AT_2^n(n+1) > (10 \uparrow\uparrow\uparrow)^{n-1} (AT_2(n+1))</math>
* <math>AT_3(2) = AT_2^2(3) > AT_2(10 \uparrow\uparrow\uparrow 3) > 10 \uparrow\uparrow\uparrow 10 \uparrow\uparrow\uparrow 3</math>

== 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: <math>BB\mu(6k+17) \ge 2 \uparrow^k 4</math>.

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 [[wikipedia:Pairing_function|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, [[wikipedia:Common_subexpression_elimination|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:
{| class="wikitable"
|+Smallest Pairing Functions
!Macro
!arity
!Definition
!Size
!Function
|-
|<math>Pair</math>
|2
|<math>Pair := C(AddS, C(Tri, Add), P^2_1)</math>
|20
|<math>\lambda xy. \frac{(x+y)(x+y+1)}{2} + x + 1</math>
|-
|<math>Left</math>
|1
|<math>Left := C(RMonus, C(TriP, InvTriCeil), Pred)</math>
|38
|<math>Left(Pair(x,y)) = x</math>
|-
|<math>Right</math>
|1
|<math>Right := C(RMonus, P^1_1, C(Tri, InvTriCeil))</math>
|36
|<math>Right(Pair(x,y)) = y</math>
|-
|<math>LRCall[f^2]</math>
|1
|<math>LRCall[f] := C(LRpart3[f], InvTriCeil, P^1_1)</math>
|<math>59 + |f|</math>
|<math>LRCall[f](Pair(x,y)) = f(x,y)</math>
|}
Where these are based on the following definitions:
{| class="wikitable"
|+Macros
!
!Macro
!arity
!Definition
!Size
!Function
|-
| rowspan="3" |Addition
|Add
|2
|<math>Add := R(P^1_1, C(S, P^3_2))</math>
|5
|<math>\lambda xy. x+y</math>
|-
|AddXA
|3
|<math>AddXA := R(P^2_1, C(S, P^4_2))</math>
|5
|<math>\lambda xyz. x+y</math>
|-
|AddS
|2
|<math>AddS := R(S, C(S, P^3_2))</math>
|5
|<math>\lambda xy. x+y+1</math>
|-
|[[wikipedia:Primitive_recursive_function#Predecessor|Predecesor]]
|Pred
|1
|<math>Pred := R(Z^0, P^2_1)</math>
|3
|<math>\lambda x. x \dot - 1</math>
|-
|[[wikipedia:Monus#Natural_numbers|Monus]]
|RMonus
|2
|<math>RMonus := R(P^1_1, C(Pred, P^3_2))</math>
|7
|<math>\lambda xy. y \dot - x</math>
|-
| rowspan="3" |Triangular numbers
|Tri
|1
|<math>Tri := R(Z^0, AddS)</math>
|7
|<math>\lambda x. \frac{x(x+1)}{2}</math>
|-
|TriP
|1
|<math>TriP := R(Z^0, Add)</math>
|7
|<math>TriP(x+1) = Tri(x)</math>
|-
|TriPXA
|2
|<math>TriPXA := R(Z^1, AddXA)</math>
|7
|<math>TriPXA(x,y) = TriP(x)</math>
|-
| rowspan="2" |Inverting Tri
|RMonusTri
|2
|<math>RMonusTri := C(RMonus, C(Tri, P^2_1), P^2_2)</math>
|18
|<math>\lambda xy. y \dot - Tri(x)</math>
|-
|InvTriCeil
|1
|<math>InvTriCeil := M(RMonusTri)</math>
|19
|<math>\lambda y. \min \{x | Tri(x) \ge y \}</math>
|-
| rowspan="5" | Combined LRCall
|RightPiece
|3
|<math>RightPiece := R(P^2_2, C(Pred, P^4_2))</math>
|7
|<math>\lambda xyz. z \dot - x</math>
|-
|LeftPiece
|3
|<math>LeftPiece := C(RMonus, C(S, P^3_2), P^3_1)</math>
|12
|<math>\lambda xyz. x \dot - (y+1)</math>
|-
|LRpart1[f]
|3
|<math>LRpart1[f] := C(f, LeftPiece, RightPiece)</math>
|<math>20 + |f|</math>
|<math>\lambda xyz. f(x \dot - (y+1), z \dot - x)</math>
|-
|LRpart2[f]
|3
|<math>LRpart2[f] := C(LRpart1[f], P^3_3, P^3_1, AddXA)</math>
|<math>28 + |f|</math>
|<math>\lambda xyz. f(z \dot - (x+1), x+y\dot - z)</math>
|-
|LRpart3[f]
|2
|<math>LRpart3[f] := C(LRpart2[f], TriPXA, P^2_1, P^2_2)</math>
|<math>38 + |f|</math>
|<math>\lambda xy. f(y\dot - (TriP(x)+1), TriP(x)+x\dot - y)</math>
|}

[[Category:functions]]

General Recursive Function

2026-04-13T02:20:12Z

JLM: Rename RepDiag to RepDiagS.

'''General recursive functions''' ('''GRFs'''), also called '''µ-recursive functions''' or '''partial recursive functions''', are the collection of [[Wikipedia:partial functions|partial functions]] <math>\N^k \rightharpoonup \N</math> 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 <math>\N^k \rightharpoonup \N</math> 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:<math display="block">BB \mu (n) = \max \{ f() | f \in \text{GRF}_0 , |f| = n \}</math>

where <math>f \in GRF_k</math> means that <math>f: \N^k \rightharpoonup \N</math> is a k-ary GRF and <math>|f|</math> 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 <math>GRF_k</math> inductively based on the following construction rules, start with Atoms and combine them using Combinators.

====== Atoms ======

* Zero: <math>\forall k \in \N, Z^k \in GRF_k</math> is the constant 0 function <math>Z^k(x_1, \dots, x_k) = 0</math>
* Successor: <math>S \in GRF_1</math> is the successor function <math>S(x) = x+1</math>
* Projection: <math>\forall 1 \le i \le k \in \N, P^k_i \in GRF_k</math> is a projection function <math>P^k_i(x_1, \dots x_k) = x_i</math>

===== Combinators =====

* Composition: <math>\forall k,m \in \N, \forall h \in GRF_m, \forall g_1, \dots g_m \in GRF_k, C(h, g_1, \dots g_m) \in GRF_k</math> is the composition or substitution of the ''g''s into ''h'': <math>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))</math>
* Primitive Recursion: <math>\forall k \in \N, \forall g \in GRF_k, \forall h \in GRF_{k+2}, R(g, h) \in GRF_{k+1}</math> is primitive recursion using ''g'' as the base case and ''h'' as the inductive step.
* Minimization / Unlimited Search: <math>\forall k \in \N, \forall f \in GRF_{k+1}, M(f) \in GRF_k</math> is the µ-operator which allows unlimited search.

=== Primitive Recursion ===
<math>R</math> models a typical iterative function definition over ℕ.

Base case: <math>R^k(g, h)(0, x_2, x_3, ..., x_k) = g(x_2, x_3, ..., x_k)</math>

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

<math>R</math> 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 <math>g</math>), then 1, 2, 3, etc. until <math>x_1</math> is reached, each time calling <math>h</math> with the prior iteration count for its first argument and the result of the prior call for its second.

=== Minimization ===
<math>M^k(f)(x_1, ..., x_k) \triangleq \min \{i \in \N: f(i, x_1, ..., x_k) = 0\}</math>

In computational language, when ''M(f)'' is evaluated it can be considered to calculate <math>f(i, x_1, ..., x_k)</math> with <math>i=0</math>, then <math>i=1</math>, then <math>i=2</math> etc. until one of the calls to <math>f</math> returns 0, at which point it returns the value of <math>i</math> which first gave a result of 0. If no first argument causes <math>f</math> to return 0, <math>M(f)</math> 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 <math>f \in GRF_1</math>
{| class="wikitable"
|+
!
!Macro
!arity
!Definition
!Size
!Function
|-
|Plus constant
|<math>Plus[n]</math>
|1
|<math>\begin{array}{lcl}
Plus[1] & := & S \\
Plus[n+1] & := & C(S, Plus[n])
\end{array}</math>
|<math>2n-1</math>
|<math>\lambda x. x+n</math>
|-
|Constant
|<math>K^k[n]</math>
|k
|<math>\begin{array}{lcl}
K^k[0] & := & Z^k \\
K^k[n] & := & C(Plus[n], Z^k)
\end{array}</math>
|<math>2n+1</math>
|<math>\lambda x_1 \dots x_k. n</math>
|-
|Iteration
|<math>Rep[f,n]</math>
|1
|<math>Rep[f,n] := R(K^0[n], C(f, P^2_2))</math>
|<math>|f| + 2n + 4</math>
|<math>\lambda x. f^x(n)</math>
|-
|Iteration of successor
|<math>RepSucc[f]</math>
|2
|<math>RepSucc[f] := R(S, C(f, P^3_2))</math>
|<math>|f| + 4</math>
|<math>\lambda x\ y. f^x(y+1)</math>
|-
|Diagonalization
|<math>RepDiagS[f]</math>
|1
|<math>RepDiagS[f] := C(RepSucc[f], S, S)</math>
|<math>|f| + 7</math>
|<math>\lambda x. f^{x+1}(x+2)</math>
|-
|Ackermann iteration
|<math>Ack[n,f]</math>
|1
|<math>\begin{array}{lcl}
Ack[0,f] & := & f \\
Ack[n+1,f] & := & Rep[Ack[n,f],1]
\end{array}</math>
|<math>6n + |f|</math>
|
|-
|Knuth base 2 up-arrows
|<math>Knuth2[n]</math>
|1
|<math>\begin{array}{lcl}
Knuth2[0] & := & Rep[Plus[2],0] \\
Knuth2[n+1] & := & Rep[Knuth2[n],1]
\end{array}</math>
|<math>6n+7</math>
|<math>\lambda x. 2 \uparrow^n x</math>
|-
|Ackermann Diagonalization
on Triangular nums
|<math>ADT[n]</math>
|1
|<math>\begin{array}{lcl}
ADT[0] & := & Tri \\
ADT[n+1] & := & RepDiagS[ADT[n]]
\end{array}</math>
|<math>7n + 7</math>
|<math>\lambda x. > 10 \uparrow^n (x+1)</math>
|-
|Polygonal
|<math>Poly[n]</math>
|1
|<math>Poly[n] := R(Z^0, R(S, C(Plus[n], P^3_2)))</math>
|<math>2n+5</math>
|<math>\lambda x. \frac{n}{2} x(x-1) + x</math>
|-
|
|<math>Tri</math>
|1
|<math>Tri := Poly[1] = R(Z^0, R(S, C(S, P^3_2)))</math>
|<math>7</math>
|<math>\lambda x. \frac{x(x+1)}{2}</math>
|-
|
|<math>Square</math>
|1
|<math>Square := Poly[2]</math>
|<math>9</math>
|<math>\lambda x. x^2</math>
|}

== Champions ==
{| class="wikitable"
!n
!BBµ(n)
!Champion
!Champion Found
!Holdouts Proven
|-
|1
|= 0
|<math>Z^0</math>
|
|Shawn Ligocki [https://discord.com/channels/960643023006490684/1447627603698647303/1447693296322215976 8 Dec 2025] By hand
|-
|2
|= 0
|<math>M(Z^1), M(P^1_1), C(Z^0)</math>
|
|Shawn Ligocki [https://discord.com/channels/960643023006490684/1447627603698647303/1447693296322215976 8 Dec 2025] By hand
|-
|3
|= 1
|<math>K^0[1]</math>
|
|Shawn Ligocki [https://discord.com/channels/960643023006490684/1447627603698647303/1447693296322215976 8 Dec 2025] By hand
|-
|4
|= 1
|<math>C^0(K^0[1])</math>
|
|Jacob Mandelson [https://mandelson.org/grf/ 3 Apr 2026]
|-
|5
|= 2
|<math>K^0[2]</math>
|
|Jacob Mandelson [https://mandelson.org/grf/ 3 Apr 2026]
|-
|6
|= 2
|<math>C^0(K^0[2])</math>
|
|Jacob Mandelson [https://mandelson.org/grf/ 3 Apr 2026]
|-
|7
|= 3
|<math>K^0[3]</math>
|
|Jacob Mandelson [https://mandelson.org/grf/ 3 Apr 2026]
|-
|9
|≥ 4
|<math>K^0[4]</math>
|
|
|-
|11
|≥ 5
|<math>K^0[5]</math>
|
|
|-
|13
|≥ 6
|<math>K^0[6]</math>
|
|
|-
|14
|≥ 7
|<math>C(RepDiagS[S], K^0[2])</math>
|Shawn Ligocki [https://discord.com/channels/960643023006490684/1447627603698647303/1492246885329670184 10 Apr 2026]
|
|-
|16
|≥ 10
|<math>C(RepDiagS[Plus[2]], K^0[2])</math>
|Shawn Ligocki [https://discord.com/channels/960643023006490684/1447627603698647303/1492394919728517160 11 Apr 2026]
|
|-
|17
|≥ 10
|<math>C(Tri, K^0[4])</math>
|Shawn Ligocki 9 Dec 2025
|
|-
|18
|≥ 21
|<math>C(RepDiagS[Tri], K^0[1])</math>
|Jacob Mandelson [https://discord.com/channels/960643023006490684/1447627603698647303/1492021428546179182 9 Apr 2026]
|
|-
|20
|≥ 1540
|<math>C(RepDiagS[Tri], K^0[2])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|22
|≥ 26'357'430
|<math>C(RepDiagS[Tri], K^0[3])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|24
|≥ 64'449'908'476'890'321 > 1016.8
|<math>C(RepDiagS[Tri], K^0[4])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|25
|<math> > 10^{10^{10^{6.899}}} > 10 \uparrow\uparrow 3.8388</math>
|<math>C(ADT[2], K^0[1])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|27
|> <math>10 \uparrow\uparrow 6.0834</math>
|<math>C(ADT[2], K^0[2])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|29
|> <math>10 \uparrow\uparrow 8.1944</math>
|<math>C(ADT[2], K^0[3])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|31
|> <math>10 \uparrow\uparrow 10.2800</math>
|<math>C(ADT[2], K^0[4])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|32
|> <math>10 \uparrow\uparrow 10 \uparrow\uparrow 8.1944</math>
|<math>C(ADT[3], K^0[1])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|34
|> <math>10 \uparrow\uparrow\uparrow 4</math>
|<math>C(ADT[3], K^0[2])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|36
|> <math>10 \uparrow\uparrow\uparrow 5</math>
|<math>C(ADT[3], K^0[3])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|38
|> <math>10 \uparrow\uparrow\uparrow 6</math>
|<math>C(ADT[3], K^0[4])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|
|
|
|
|
|-
|7k+11
|> <math>10 \uparrow^k 2</math>
|<math>C(ADT[k], K^0[1])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|7k+13
|> <math>10 \uparrow^k 3</math>
|<math>C(ADT[k], K^0[2])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|7k+15
|> <math>10 \uparrow^k 4</math>
|<math>C(ADT[k], K^0[3])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|7k+17
|> <math>10 \uparrow^k 5</math>
|<math>C(ADT[k], K^0[4])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|
|
|
|
|
|-
|6k+17
|<math>\ge 2 \uparrow^k 4</math>
|<math>C(Knuth2[k], K^0[4])</math>
|Shawn Ligocki [https://discord.com/channels/960643023006490684/1447627603698647303/1447633458510692385 8 Dec 2025]
|
|-
|6k+19
|<math>\ge 2 \uparrow^k 5</math>
|<math>C(Knuth2[k], K^0[5])</math>
|Shawn Ligocki [https://discord.com/channels/960643023006490684/1447627603698647303/1447633458510692385 8 Dec 2025]
|
|-
|6k+21
|<math>\ge 2 \uparrow^k 6</math>
|<math>C(Knuth2[k], K^0[6])</math>
|Shawn Ligocki [https://discord.com/channels/960643023006490684/1447627603698647303/1447633458510692385 8 Dec 2025]
|
|}

== Macro Bounds ==

=== ADT[k] ===

* <math>ADT[0](n) = Tri(n) = \frac{n(n+1)}{2} > \frac{1}{2} n^2</math>
* <math>ADT[0]^k(n) > 2 \left( \frac{n}{2} \right)^{2^k}</math>
* <math>ADT[1](n) = Tri^{n+1}(n+2) > 2 \left(\frac{n+2}{2} \right)^{2^{n+1}} = 2 \left(\frac{(n+2)^2}{4} \right)^{2^n} > A 10^{10^{n/A}}</math> where <math>A = \frac{1}{\log_{10}(2)}</math> (if <math>n \ge 5</math>, for smaller values, this can be calculated directly)
* <math>ADT[1]^k(n) > A (10 \uparrow)^{2k} \frac{n}{A} > 10 \uparrow\uparrow 2k</math> (if <math>n \ge 4</math>)
* <math>ADT[2](n) = ADT[1]^{n+1}(n+2) > 10 \uparrow\uparrow (2n+2) </math> (if <math>n \ge 2</math>)
* <math>ADT[k](n) > 10 \uparrow^k (n+1) </math> (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: <math>BB\mu(6k+17) \ge 2 \uparrow^k 4</math>.

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 [[wikipedia:Pairing_function|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, [[wikipedia:Common_subexpression_elimination|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:
{| class="wikitable"
|+Smallest Pairing Functions
!Macro
!arity
!Definition
!Size
!Function
|-
|<math>Pair</math>
|2
|<math>Pair := C(AddS, C(Tri, Add), P^2_1)</math>
|20
|<math>\lambda xy. \frac{(x+y)(x+y+1)}{2} + x + 1</math>
|-
|<math>Left</math>
|1
|<math>Left := C(RMonus, C(TriP, InvTriCeil), Pred)</math>
|38
|<math>Left(Pair(x,y)) = x</math>
|-
|<math>Right</math>
|1
|<math>Right := C(RMonus, P^1_1, C(Tri, InvTriCeil))</math>
|36
|<math>Right(Pair(x,y)) = y</math>
|-
|<math>LRCall[f^2]</math>
|1
|<math>LRCall[f] := C(LRpart3[f], InvTriCeil, P^1_1)</math>
|<math>59 + |f|</math>
|<math>LRCall[f](Pair(x,y)) = f(x,y)</math>
|}
Where these are based on the following definitions:
{| class="wikitable"
|+Macros
!
!Macro
!arity
!Definition
!Size
!Function
|-
| rowspan="3" |Addition
|Add
|2
|<math>Add := R(P^1_1, C(S, P^3_2))</math>
|5
|<math>\lambda xy. x+y</math>
|-
|AddXA
|3
|<math>AddXA := R(P^2_1, C(S, P^4_2))</math>
|5
|<math>\lambda xyz. x+y</math>
|-
|AddS
|2
|<math>AddS := R(S, C(S, P^3_2))</math>
|5
|<math>\lambda xy. x+y+1</math>
|-
|[[wikipedia:Primitive_recursive_function#Predecessor|Predecesor]]
|Pred
|1
|<math>Pred := R(Z^0, P^2_1)</math>
|3
|<math>\lambda x. x \dot - 1</math>
|-
|[[wikipedia:Monus#Natural_numbers|Monus]]
|RMonus
|2
|<math>RMonus := R(P^1_1, C(Pred, P^3_2))</math>
|7
|<math>\lambda xy. y \dot - x</math>
|-
| rowspan="3" |Triangular numbers
|Tri
|1
|<math>Tri := R(Z^0, AddS)</math>
|7
|<math>\lambda x. \frac{x(x+1)}{2}</math>
|-
|TriP
|1
|<math>TriP := R(Z^0, Add)</math>
|7
|<math>TriP(x+1) = Tri(x)</math>
|-
|TriPXA
|2
|<math>TriPXA := R(Z^1, AddXA)</math>
|7
|<math>TriPXA(x,y) = TriP(x)</math>
|-
| rowspan="2" |Inverting Tri
|RMonusTri
|2
|<math>RMonusTri := C(RMonus, C(Tri, P^2_1), P^2_2)</math>
|18
|<math>\lambda xy. y \dot - Tri(x)</math>
|-
|InvTriCeil
|1
|<math>InvTriCeil := M(RMonusTri)</math>
|19
|<math>\lambda y. \min \{x | Tri(x) \ge y \}</math>
|-
| rowspan="5" | Combined LRCall
|RightPiece
|3
|<math>RightPiece := R(P^2_2, C(Pred, P^4_2))</math>
|7
|<math>\lambda xyz. z \dot - x</math>
|-
|LeftPiece
|3
|<math>LeftPiece := C(RMonus, C(S, P^3_2), P^3_1)</math>
|12
|<math>\lambda xyz. x \dot - (y+1)</math>
|-
|LRpart1[f]
|3
|<math>LRpart1[f] := C(f, LeftPiece, RightPiece)</math>
|<math>20 + |f|</math>
|<math>\lambda xyz. f(x \dot - (y+1), z \dot - x)</math>
|-
|LRpart2[f]
|3
|<math>LRpart2[f] := C(LRpart1[f], P^3_3, P^3_1, AddXA)</math>
|<math>28 + |f|</math>
|<math>\lambda xyz. f(z \dot - (x+1), x+y\dot - z)</math>
|-
|LRpart3[f]
|2
|<math>LRpart3[f] := C(LRpart2[f], TriPXA, P^2_1, P^2_2)</math>
|<math>38 + |f|</math>
|<math>\lambda xy. f(y\dot - (TriP(x)+1), TriP(x)+x\dot - y)</math>
|}

[[Category:functions]]

General Recursive Function

2026-04-11T07:36:48Z

JLM: /* Minimization */ Improve wording of M's return mechanism.

'''General recursive functions''' ('''GRFs'''), also called '''µ-recursive functions''' or '''partial recursive functions''', are the collection of [[Wikipedia:partial functions|partial functions]] <math>\N^k \rightharpoonup \N</math> 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 <math>\N^k \rightharpoonup \N</math> 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:<math display="block">BB \mu (n) = \max \{ f() | f \in \text{GRF}_0 , |f| = n \}</math>

where <math>f \in GRF_k</math> means that <math>f: \N^k \rightharpoonup \N</math> is a k-ary GRF and <math>|f|</math> 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 <math>GRF_k</math> inductively based on the following construction rules, start with Atoms and combine them using Combinators.

====== Atoms ======

* Zero: <math>\forall k \in \N, Z^k \in GRF_k</math> is the constant 0 function <math>Z^k(x_1, \dots, x_k) = 0</math>
* Successor: <math>S \in GRF_1</math> is the successor function <math>S(x) = x+1</math>
* Projection: <math>\forall 1 \le i \le k \in \N, P^k_i \in GRF_k</math> is a projection function <math>P^k_i(x_1, \dots x_k) = x_i</math>

===== Combinators =====

* Composition: <math>\forall k,m \in \N, \forall h \in GRF_m, \forall g_1, \dots g_m \in GRF_k, C(h, g_1, \dots g_m) \in GRF_k</math> is the composition or substitution of the ''g''s into ''h'': <math>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))</math>
* Primitive Recursion: <math>\forall k \in \N, \forall g \in GRF_k, \forall h \in GRF_{k+2}, R(g, h) \in GRF_{k+1}</math> is primitive recursion using ''g'' as the base case and ''h'' as the inductive step.
* Minimization / Unlimited Search: <math>\forall k \in \N, \forall f \in GRF_{k+1}, M(f) \in GRF_k</math> is the µ-operator which allows unlimited search.

=== Primitive Recursion ===
<math>R</math> models a typical iterative function definition over ℕ.

Base case: <math>R^k(g, h)(0, x_2, x_3, ..., x_k) = g(x_2, x_3, ..., x_k)</math>

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

<math>R</math> 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 <math>g</math>), then 1, 2, 3, etc. until <math>x_1</math> is reached, each time calling <math>h</math> with the prior iteration count for its first argument and the result of the prior call for its second.

=== Minimization ===
<math>M^k(f)(x_1, ..., x_k) \triangleq \min \{i \in \N: f(i, x_1, ..., x_k) = 0\}</math>

In computational language, when ''M(f)'' is evaluated it can be considered to calculate <math>f(i, x_1, ..., x_k)</math> with <math>i=0</math>, then <math>i=1</math>, then <math>i=2</math> etc. until one of the calls to <math>f</math> returns 0, at which point it returns the value of <math>i</math> which first gave a result of 0. If no first argument causes <math>f</math> to return 0, <math>M(f)</math> 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 <math>f \in GRF_1</math>
{| class="wikitable"
|+
!
!Macro
!arity
!Definition
!Size
!Function
|-
|Plus constant
|<math>Plus[n]</math>
|1
|<math>\begin{array}{lcl}
Plus[1] & := & S \\
Plus[n+1] & := & C(S, Plus[n])
\end{array}</math>
|<math>2n-1</math>
|<math>\lambda x. x+n</math>
|-
|Constant
|<math>K^k[n]</math>
|k
|<math>\begin{array}{lcl}
K^k[0] & := & Z^k \\
K^k[n] & := & C(Plus[n], Z^k)
\end{array}</math>
|<math>2n+1</math>
|<math>\lambda x_1 \dots x_k. n</math>
|-
|Iteration
|<math>Rep[f,n]</math>
|1
|<math>Rep[f,n] := R(K^0[n], C(f, P^2_2))</math>
|<math>|f| + 2n + 4</math>
|<math>\lambda x. f^x(n)</math>
|-
|Iteration of successor
|<math>RepSucc[f]</math>
|2
|<math>RepSucc[f] := R(S, C(f, P^3_2))</math>
|<math>|f| + 4</math>
|<math>\lambda x\ y. f^x(y+1)</math>
|-
|Diagonalization
|<math>RepDiag[f]</math>
|1
|<math>RepDiag[f] := C(RepSucc[f], S, S)</math>
|<math>|f| + 7</math>
|<math>\lambda x. f^{x+1}(x+2)</math>
|-
|Ackermann iteration
|<math>Ack[n,f]</math>
|1
|<math>\begin{array}{lcl}
Ack[0,f] & := & f \\
Ack[n+1,f] & := & Rep[Ack[n,f],1]
\end{array}</math>
|<math>6n + |f|</math>
|
|-
|Knuth base 2 up-arrows
|<math>Knuth2[n]</math>
|1
|<math>\begin{array}{lcl}
Knuth2[0] & := & Rep[Plus[2],0] \\
Knuth2[n+1] & := & Rep[Knuth2[n],1]
\end{array}</math>
|<math>6n+7</math>
|<math>\lambda x. 2 \uparrow^n x</math>
|-
|Ackermann Diagonalization
on Triangular nums
|<math>ADT[n]</math>
|1
|<math>\begin{array}{lcl}
ADT[0] & := & Tri \\
ADT[n+1] & := & RepDiag[ADT[n]]
\end{array}</math>
|<math>7n + 7</math>
|<math>\lambda x. > 10 \uparrow^n (x+1)</math>
|-
|Polygonal
|<math>Poly[n]</math>
|1
|<math>Poly[n] := R(Z^0, R(S, C(Plus[n], P^3_2)))</math>
|<math>2n+5</math>
|<math>\lambda x. \frac{n}{2} x(x-1) + x</math>
|-
|
|<math>Tri</math>
|1
|<math>Tri := Poly[1] = R(Z^0, R(S, C(S, P^3_2)))</math>
|<math>7</math>
|<math>\lambda x. \frac{x(x+1)}{2}</math>
|-
|
|<math>Square</math>
|1
|<math>Square := Poly[2]</math>
|<math>9</math>
|<math>\lambda x. x^2</math>
|}

== Champions ==
{| class="wikitable"
!n
!BBµ(n)
!Champion
!Champion Found
!Holdouts Proven
|-
|1
|= 0
|<math>Z^0</math>
|
|Shawn Ligocki [https://discord.com/channels/960643023006490684/1447627603698647303/1447693296322215976 8 Dec 2025] By hand
|-
|2
|= 0
|<math>M(Z^1), M(P^1_1), C(Z^0)</math>
|
|Shawn Ligocki [https://discord.com/channels/960643023006490684/1447627603698647303/1447693296322215976 8 Dec 2025] By hand
|-
|3
|= 1
|<math>K^0[1]</math>
|
|Shawn Ligocki [https://discord.com/channels/960643023006490684/1447627603698647303/1447693296322215976 8 Dec 2025] By hand
|-
|4
|= 1
|<math>C^0(K^0[1])</math>
|
|Jacob Mandelson [https://mandelson.org/grf/ 3 Apr 2026]
|-
|5
|= 2
|<math>K^0[2]</math>
|
|Jacob Mandelson [https://mandelson.org/grf/ 3 Apr 2026]
|-
|6
|= 2
|<math>C^0(K^0[2])</math>
|
|Jacob Mandelson [https://mandelson.org/grf/ 3 Apr 2026]
|-
|7
|= 3
|<math>K^0[3]</math>
|
|Jacob Mandelson [https://mandelson.org/grf/ 3 Apr 2026]
|-
|9
|≥ 4
|<math>K^0[4]</math>
|
|
|-
|11
|≥ 5
|<math>K^0[5]</math>
|
|
|-
|13
|≥ 6
|<math>K^0[6]</math>
|
|
|-
|14
|≥ 7
|<math>C(RepDiag[S], K^0[2])</math>
|Shawn Ligocki [https://discord.com/channels/960643023006490684/1447627603698647303/1492246885329670184 10 Apr 2026]
|
|-
|16
|≥ 10
|<math>C(RepDiag[Plus[2]], K^0[2])</math>
|Shawn Ligocki [https://discord.com/channels/960643023006490684/1447627603698647303/1492394919728517160 11 Apr 2026]
|
|-
|17
|≥ 10
|<math>C(Tri, K^0[4])</math>
|Shawn Ligocki 9 Dec 2025
|
|-
|18
|≥ 21
|<math>C(RepDiag[Tri], K^0[1])</math>
|Jacob Mandelson [https://discord.com/channels/960643023006490684/1447627603698647303/1492021428546179182 9 Apr 2026]
|
|-
|20
|≥ 1540
|<math>C(RepDiag[Tri], K^0[2])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|22
|≥ 26'357'430
|<math>C(RepDiag[Tri], K^0[3])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|24
|≥ 64'449'908'476'890'321 > 1016.8
|<math>C(RepDiag[Tri], K^0[4])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|25
|<math> > 10^{10^{10^{6.899}}} > 10 \uparrow\uparrow 3.8388</math>
|<math>C(ADT[2], K^0[1])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|27
|> <math>10 \uparrow\uparrow 6.0834</math>
|<math>C(ADT[2], K^0[2])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|29
|> <math>10 \uparrow\uparrow 8.1944</math>
|<math>C(ADT[2], K^0[3])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|31
|> <math>10 \uparrow\uparrow 10.2800</math>
|<math>C(ADT[2], K^0[4])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|32
|> <math>10 \uparrow\uparrow 10 \uparrow\uparrow 8.1944</math>
|<math>C(ADT[3], K^0[1])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|34
|> <math>10 \uparrow\uparrow\uparrow 4</math>
|<math>C(ADT[3], K^0[2])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|36
|> <math>10 \uparrow\uparrow\uparrow 5</math>
|<math>C(ADT[3], K^0[3])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|38
|> <math>10 \uparrow\uparrow\uparrow 6</math>
|<math>C(ADT[3], K^0[4])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|
|
|
|
|
|-
|7k+11
|> <math>10 \uparrow^k 2</math>
|<math>C(ADT[k], K^0[1])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|7k+13
|> <math>10 \uparrow^k 3</math>
|<math>C(ADT[k], K^0[2])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|7k+15
|> <math>10 \uparrow^k 4</math>
|<math>C(ADT[k], K^0[3])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|7k+17
|> <math>10 \uparrow^k 5</math>
|<math>C(ADT[k], K^0[4])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|
|
|
|
|
|-
|6k+17
|<math>\ge 2 \uparrow^k 4</math>
|<math>C(Knuth2[k], K^0[4])</math>
|Shawn Ligocki [https://discord.com/channels/960643023006490684/1447627603698647303/1447633458510692385 8 Dec 2025]
|
|-
|6k+19
|<math>\ge 2 \uparrow^k 5</math>
|<math>C(Knuth2[k], K^0[5])</math>
|Shawn Ligocki [https://discord.com/channels/960643023006490684/1447627603698647303/1447633458510692385 8 Dec 2025]
|
|-
|6k+21
|<math>\ge 2 \uparrow^k 6</math>
|<math>C(Knuth2[k], K^0[6])</math>
|Shawn Ligocki [https://discord.com/channels/960643023006490684/1447627603698647303/1447633458510692385 8 Dec 2025]
|
|}

== Macro Bounds ==

=== ADT[k] ===

* <math>ADT[0](n) = Tri(n) = \frac{n(n+1)}{2} > \frac{1}{2} n^2</math>
* <math>ADT[0]^k(n) > 2 \left( \frac{n}{2} \right)^{2^k}</math>
* <math>ADT[1](n) = Tri^{n+1}(n+2) > 2 \left(\frac{n+2}{2} \right)^{2^{n+1}} = 2 \left(\frac{(n+2)^2}{4} \right)^{2^n} > A 10^{10^{n/A}}</math> where <math>A = \frac{1}{\log_{10}(2)}</math> (if <math>n \ge 5</math>, for smaller values, this can be calculated directly)
* <math>ADT[1]^k(n) > A (10 \uparrow)^{2k} \frac{n}{A} > 10 \uparrow\uparrow 2k</math> (if <math>n \ge 4</math>)
* <math>ADT[2](n) = ADT[1]^{n+1}(n+2) > 10 \uparrow\uparrow (2n+2) </math> (if <math>n \ge 2</math>)
* <math>ADT[k](n) > 10 \uparrow^k (n+1) </math> (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: <math>BB\mu(6k+17) \ge 2 \uparrow^k 4</math>.

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 [[wikipedia:Pairing_function|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, [[wikipedia:Common_subexpression_elimination|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:
{| class="wikitable"
|+Smallest Pairing Functions
!Macro
!arity
!Definition
!Size
!Function
|-
|<math>Pair</math>
|2
|<math>Pair := C(AddS, C(Tri, Add), P^2_1)</math>
|20
|<math>\lambda xy. \frac{(x+y)(x+y+1)}{2} + x + 1</math>
|-
|<math>Left</math>
|1
|<math>Left := C(RMonus, C(TriP, InvTriCeil), Pred)</math>
|38
|<math>Left(Pair(x,y)) = x</math>
|-
|<math>Right</math>
|1
|<math>Right := C(RMonus, P^1_1, C(Tri, InvTriCeil))</math>
|36
|<math>Right(Pair(x,y)) = y</math>
|-
|<math>LRCall[f^2]</math>
|1
|<math>LRCall[f] := C(LRpart3[f], InvTriCeil, P^1_1)</math>
|<math>59 + |f|</math>
|<math>LRCall[f](Pair(x,y)) = f(x,y)</math>
|}
Where these are based on the following definitions:
{| class="wikitable"
|+Macros
!
!Macro
!arity
!Definition
!Size
!Function
|-
| rowspan="3" |Addition
|Add
|2
|<math>Add := R(P^1_1, C(S, P^3_2))</math>
|5
|<math>\lambda xy. x+y</math>
|-
|AddXA
|3
|<math>AddXA := R(P^2_1, C(S, P^4_2))</math>
|5
|<math>\lambda xyz. x+y</math>
|-
|AddS
|2
|<math>AddS := R(S, C(S, P^3_2))</math>
|5
|<math>\lambda xy. x+y+1</math>
|-
|[[wikipedia:Primitive_recursive_function#Predecessor|Predecesor]]
|Pred
|1
|<math>Pred := R(Z^0, P^2_1)</math>
|3
|<math>\lambda x. x \dot - 1</math>
|-
|[[wikipedia:Monus#Natural_numbers|Monus]]
|RMonus
|2
|<math>RMonus := R(P^1_1, C(Pred, P^3_2))</math>
|7
|<math>\lambda xy. y \dot - x</math>
|-
| rowspan="3" |Triangular numbers
|Tri
|1
|<math>Tri := R(Z^0, AddS)</math>
|7
|<math>\lambda x. \frac{x(x+1)}{2}</math>
|-
|TriP
|1
|<math>TriP := R(Z^0, Add)</math>
|7
|<math>TriP(x+1) = Tri(x)</math>
|-
|TriPXA
|2
|<math>TriPXA := R(Z^1, AddXA)</math>
|7
|<math>TriPXA(x,y) = TriP(x)</math>
|-
| rowspan="2" |Inverting Tri
|RMonusTri
|2
|<math>RMonusTri := C(RMonus, C(Tri, P^2_1), P^2_2)</math>
|18
|<math>\lambda xy. y \dot - Tri(x)</math>
|-
|InvTriCeil
|1
|<math>InvTriCeil := M(RMonusTri)</math>
|19
|<math>\lambda y. \min \{x | Tri(x) \ge y \}</math>
|-
| rowspan="5" | Combined LRCall
|RightPiece
|3
|<math>RightPiece := R(P^2_2, C(Pred, P^4_2))</math>
|7
|<math>\lambda xyz. z \dot - x</math>
|-
|LeftPiece
|3
|<math>LeftPiece := C(RMonus, C(S, P^3_2), P^3_1)</math>
|12
|<math>\lambda xyz. x \dot - (y+1)</math>
|-
|LRpart1[f]
|3
|<math>LRpart1[f] := C(f, LeftPiece, RightPiece)</math>
|<math>20 + |f|</math>
|<math>\lambda xyz. f(x \dot - (y+1), z \dot - x)</math>
|-
|LRpart2[f]
|3
|<math>LRpart2[f] := C(LRpart1[f], P^3_3, P^3_1, AddXA)</math>
|<math>28 + |f|</math>
|<math>\lambda xyz. f(z \dot - (x+1), x+y\dot - z)</math>
|-
|LRpart3[f]
|2
|<math>LRpart3[f] := C(LRpart2[f], TriPXA, P^2_1, P^2_2)</math>
|<math>38 + |f|</math>
|<math>\lambda xy. f(y\dot - (TriP(x)+1), TriP(x)+x\dot - y)</math>
|}

[[Category:functions]]

General Recursive Function

2026-04-11T07:07:00Z

JLM: /* Utilizing Minimization */ Simplify LRpart2 using the AddXA macro.

'''General recursive functions''' ('''GRFs'''), also called '''µ-recursive functions''' or '''partial recursive functions''', are the collection of [[Wikipedia:partial functions|partial functions]] <math>\N^k \rightharpoonup \N</math> 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 <math>\N^k \rightharpoonup \N</math> 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:<math display="block">BB \mu (n) = \max \{ f() | f \in \text{GRF}_0 , |f| = n \}</math>

where <math>f \in GRF_k</math> means that <math>f: \N^k \rightharpoonup \N</math> is a k-ary GRF and <math>|f|</math> 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 <math>GRF_k</math> inductively based on the following construction rules, start with Atoms and combine them using Combinators.

====== Atoms ======

* Zero: <math>\forall k \in \N, Z^k \in GRF_k</math> is the constant 0 function <math>Z^k(x_1, \dots, x_k) = 0</math>
* Successor: <math>S \in GRF_1</math> is the successor function <math>S(x) = x+1</math>
* Projection: <math>\forall 1 \le i \le k \in \N, P^k_i \in GRF_k</math> is a projection function <math>P^k_i(x_1, \dots x_k) = x_i</math>

===== Combinators =====

* Composition: <math>\forall k,m \in \N, \forall h \in GRF_m, \forall g_1, \dots g_m \in GRF_k, C(h, g_1, \dots g_m) \in GRF_k</math> is the composition or substitution of the ''g''s into ''h'': <math>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))</math>
* Primitive Recursion: <math>\forall k \in \N, \forall g \in GRF_k, \forall h \in GRF_{k+2}, R(g, h) \in GRF_{k+1}</math> is primitive recursion using ''g'' as the base case and ''h'' as the inductive step.
* Minimization / Unlimited Search: <math>\forall k \in \N, \forall f \in GRF_{k+1}, M(f) \in GRF_k</math> is the µ-operator which allows unlimited search.

=== Primitive Recursion ===
<math>R</math> models a typical iterative function definition over ℕ.

Base case: <math>R^k(g, h)(0, x_2, x_3, ..., x_k) = g(x_2, x_3, ..., x_k)</math>

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

<math>R</math> 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 <math>g</math>), then 1, 2, 3, etc. until <math>x_1</math> is reached, each time calling <math>h</math> with the prior iteration count for its first argument and the result of the prior call for its second.

=== Minimization ===
<math>M^k(f)(x_1, ..., x_k) \triangleq \min \{i \in \N: f(i, x_1, ..., x_k) = 0\}</math>

In computational language, when ''M(f)'' is evaluated it can be considered to calculate <math>f(i, x_1, ..., x_k)</math> with <math>i=0</math>, then <math>i=1</math>, then <math>i=2</math> etc. until one of the calls to <math>f</math> returns 0. It returns the value of <math>i</math> which first gave a result of 0. If no first argument causes <math>f</math> to return 0, <math>M(f)</math> 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 <math>f \in GRF_1</math>
{| class="wikitable"
|+
!
!Macro
!arity
!Definition
!Size
!Function
|-
|Plus constant
|<math>Plus[n]</math>
|1
|<math>\begin{array}{lcl}
Plus[1] & := & S \\
Plus[n+1] & := & C(S, Plus[n])
\end{array}</math>
|<math>2n-1</math>
|<math>\lambda x. x+n</math>
|-
|Constant
|<math>K^k[n]</math>
|k
|<math>\begin{array}{lcl}
K^k[0] & := & Z^k \\
K^k[n] & := & C(Plus[n], Z^k)
\end{array}</math>
|<math>2n+1</math>
|<math>\lambda x_1 \dots x_k. n</math>
|-
|Iteration
|<math>Rep[f,n]</math>
|1
|<math>Rep[f,n] := R(K^0[n], C(f, P^2_2))</math>
|<math>|f| + 2n + 4</math>
|<math>\lambda x. f^x(n)</math>
|-
|Iteration of successor
|<math>RepSucc[f]</math>
|2
|<math>RepSucc[f] := R(S, C(f, P^3_2))</math>
|<math>|f| + 4</math>
|<math>\lambda x\ y. f^x(y+1)</math>
|-
|Diagonalization
|<math>RepDiag[f]</math>
|1
|<math>RepDiag[f] := C(RepSucc[f], S, S)</math>
|<math>|f| + 7</math>
|<math>\lambda x. f^{x+1}(x+2)</math>
|-
|Ackermann iteration
|<math>Ack[n,f]</math>
|1
|<math>\begin{array}{lcl}
Ack[0,f] & := & f \\
Ack[n+1,f] & := & Rep[Ack[n,f],1]
\end{array}</math>
|<math>6n + |f|</math>
|
|-
|Knuth base 2 up-arrows
|<math>Knuth2[n]</math>
|1
|<math>\begin{array}{lcl}
Knuth2[0] & := & Rep[Plus[2],0] \\
Knuth2[n+1] & := & Rep[Knuth2[n],1]
\end{array}</math>
|<math>6n+7</math>
|<math>\lambda x. 2 \uparrow^n x</math>
|-
|Ackermann Diagonalization
on Triangular nums
|<math>ADT[n]</math>
|1
|<math>\begin{array}{lcl}
ADT[0] & := & Tri \\
ADT[n+1] & := & RepDiag[ADT[n]]
\end{array}</math>
|<math>7n + 7</math>
|<math>\lambda x. > 10 \uparrow^n (x+1)</math>
|-
|Polygonal
|<math>Poly[n]</math>
|1
|<math>Poly[n] := R(Z^0, R(S, C(Plus[n], P^3_2)))</math>
|<math>2n+5</math>
|<math>\lambda x. \frac{n}{2} x(x-1) + x</math>
|-
|
|<math>Tri</math>
|1
|<math>Tri := Poly[1] = R(Z^0, R(S, C(S, P^3_2)))</math>
|<math>7</math>
|<math>\lambda x. \frac{x(x+1)}{2}</math>
|-
|
|<math>Square</math>
|1
|<math>Square := Poly[2]</math>
|<math>9</math>
|<math>\lambda x. x^2</math>
|}

== Champions ==
{| class="wikitable"
!n
!BBµ(n)
!Champion
!Champion Found
!Holdouts Proven
|-
|1
|= 0
|<math>Z^0</math>
|
|Shawn Ligocki [https://discord.com/channels/960643023006490684/1447627603698647303/1447693296322215976 8 Dec 2025] By hand
|-
|2
|= 0
|<math>M(Z^1), M(P^1_1), C(Z^0)</math>
|
|Shawn Ligocki [https://discord.com/channels/960643023006490684/1447627603698647303/1447693296322215976 8 Dec 2025] By hand
|-
|3
|= 1
|<math>K^0[1]</math>
|
|Shawn Ligocki [https://discord.com/channels/960643023006490684/1447627603698647303/1447693296322215976 8 Dec 2025] By hand
|-
|4
|= 1
|<math>C^0(K^0[1])</math>
|
|Jacob Mandelson [https://mandelson.org/grf/ 3 Apr 2026]
|-
|5
|= 2
|<math>K^0[2]</math>
|
|Jacob Mandelson [https://mandelson.org/grf/ 3 Apr 2026]
|-
|6
|= 2
|<math>C^0(K^0[2])</math>
|
|Jacob Mandelson [https://mandelson.org/grf/ 3 Apr 2026]
|-
|7
|= 3
|<math>K^0[3]</math>
|
|Jacob Mandelson [https://mandelson.org/grf/ 3 Apr 2026]
|-
|9
|≥ 4
|<math>K^0[4]</math>
|
|
|-
|11
|≥ 5
|<math>K^0[5]</math>
|
|
|-
|13
|≥ 6
|<math>K^0[6]</math>
|
|
|-
|14
|≥ 7
|<math>C(RepDiag[S], K^0[2])</math>
|Shawn Ligocki [https://discord.com/channels/960643023006490684/1447627603698647303/1492246885329670184 10 Apr 2026]
|
|-
|16
|≥ 10
|<math>C(RepDiag[Plus[2]], K^0[2])</math>
|Shawn Ligocki [https://discord.com/channels/960643023006490684/1447627603698647303/1492394919728517160 11 Apr 2026]
|
|-
|17
|≥ 10
|<math>C(Tri, K^0[4])</math>
|Shawn Ligocki 9 Dec 2025
|
|-
|18
|≥ 21
|<math>C(RepDiag[Tri], K^0[1])</math>
|Jacob Mandelson [https://discord.com/channels/960643023006490684/1447627603698647303/1492021428546179182 9 Apr 2026]
|
|-
|20
|≥ 1540
|<math>C(RepDiag[Tri], K^0[2])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|22
|≥ 26'357'430
|<math>C(RepDiag[Tri], K^0[3])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|24
|≥ 64'449'908'476'890'321 > 1016.8
|<math>C(RepDiag[Tri], K^0[4])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|25
|<math> > 10^{10^{10^{6.899}}} > 10 \uparrow\uparrow 3.8388</math>
|<math>C(ADT[2], K^0[1])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|27
|> <math>10 \uparrow\uparrow 6.0834</math>
|<math>C(ADT[2], K^0[2])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|29
|> <math>10 \uparrow\uparrow 8.1944</math>
|<math>C(ADT[2], K^0[3])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|31
|> <math>10 \uparrow\uparrow 10.2800</math>
|<math>C(ADT[2], K^0[4])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|32
|> <math>10 \uparrow\uparrow 10 \uparrow\uparrow 8.1944</math>
|<math>C(ADT[3], K^0[1])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|34
|> <math>10 \uparrow\uparrow\uparrow 4</math>
|<math>C(ADT[3], K^0[2])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|36
|> <math>10 \uparrow\uparrow\uparrow 5</math>
|<math>C(ADT[3], K^0[3])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|38
|> <math>10 \uparrow\uparrow\uparrow 6</math>
|<math>C(ADT[3], K^0[4])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|
|
|
|
|
|-
|7k+11
|> <math>10 \uparrow^k 2</math>
|<math>C(ADT[k], K^0[1])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|7k+13
|> <math>10 \uparrow^k 3</math>
|<math>C(ADT[k], K^0[2])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|7k+15
|> <math>10 \uparrow^k 4</math>
|<math>C(ADT[k], K^0[3])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|7k+17
|> <math>10 \uparrow^k 5</math>
|<math>C(ADT[k], K^0[4])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|
|
|
|
|
|-
|6k+17
|<math>\ge 2 \uparrow^k 4</math>
|<math>C(Knuth2[k], K^0[4])</math>
|Shawn Ligocki [https://discord.com/channels/960643023006490684/1447627603698647303/1447633458510692385 8 Dec 2025]
|
|-
|6k+19
|<math>\ge 2 \uparrow^k 5</math>
|<math>C(Knuth2[k], K^0[5])</math>
|Shawn Ligocki [https://discord.com/channels/960643023006490684/1447627603698647303/1447633458510692385 8 Dec 2025]
|
|-
|6k+21
|<math>\ge 2 \uparrow^k 6</math>
|<math>C(Knuth2[k], K^0[6])</math>
|Shawn Ligocki [https://discord.com/channels/960643023006490684/1447627603698647303/1447633458510692385 8 Dec 2025]
|
|}

== Macro Bounds ==

=== ADT[k] ===

* <math>ADT[0](n) = Tri(n) = \frac{n(n+1)}{2} > \frac{1}{2} n^2</math>
* <math>ADT[0]^k(n) > 2 \left( \frac{n}{2} \right)^{2^k}</math>
* <math>ADT[1](n) = Tri^{n+1}(n+2) > 2 \left(\frac{n+2}{2} \right)^{2^{n+1}} = 2 \left(\frac{(n+2)^2}{4} \right)^{2^n} > A 10^{10^{n/A}}</math> where <math>A = \frac{1}{\log_{10}(2)}</math> (if <math>n \ge 5</math>, for smaller values, this can be calculated directly)
* <math>ADT[1]^k(n) > A (10 \uparrow)^{2k} \frac{n}{A} > 10 \uparrow\uparrow 2k</math> (if <math>n \ge 4</math>)
* <math>ADT[2](n) = ADT[1]^{n+1}(n+2) > 10 \uparrow\uparrow (2n+2) </math> (if <math>n \ge 2</math>)
* <math>ADT[k](n) > 10 \uparrow^k (n+1) </math> (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: <math>BB\mu(6k+17) \ge 2 \uparrow^k 4</math>.

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 [[wikipedia:Pairing_function|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, [[wikipedia:Common_subexpression_elimination|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:
{| class="wikitable"
|+Smallest Pairing Functions
!Macro
!arity
!Definition
!Size
!Function
|-
|<math>Pair</math>
|2
|<math>Pair := C(AddS, C(Tri, Add), P^2_1)</math>
|20
|<math>\lambda xy. \frac{(x+y)(x+y+1)}{2} + x + 1</math>
|-
|<math>Left</math>
|1
|<math>Left := C(RMonus, C(TriP, InvTriCeil), Pred)</math>
|38
|<math>Left(Pair(x,y)) = x</math>
|-
|<math>Right</math>
|1
|<math>Right := C(RMonus, P^1_1, C(Tri, InvTriCeil))</math>
|36
|<math>Right(Pair(x,y)) = y</math>
|-
|<math>LRCall[f^2]</math>
|1
|<math>LRCall[f] := C(LRpart3[f], InvTriCeil, P^1_1)</math>
|<math>59 + |f|</math>
|<math>LRCall[f](Pair(x,y)) = f(x,y)</math>
|}
Where these are based on the following definitions:
{| class="wikitable"
|+Macros
!
!Macro
!arity
!Definition
!Size
!Function
|-
| rowspan="3" |Addition
|Add
|2
|<math>Add := R(P^1_1, C(S, P^3_2))</math>
|5
|<math>\lambda xy. x+y</math>
|-
|AddXA
|3
|<math>AddXA := R(P^2_1, C(S, P^4_2))</math>
|5
|<math>\lambda xyz. x+y</math>
|-
|AddS
|2
|<math>AddS := R(S, C(S, P^3_2))</math>
|5
|<math>\lambda xy. x+y+1</math>
|-
|[[wikipedia:Primitive_recursive_function#Predecessor|Predecesor]]
|Pred
|1
|<math>Pred := R(Z^0, P^2_1)</math>
|3
|<math>\lambda x. x \dot - 1</math>
|-
|[[wikipedia:Monus#Natural_numbers|Monus]]
|RMonus
|2
|<math>RMonus := R(P^1_1, C(Pred, P^3_2))</math>
|7
|<math>\lambda xy. y \dot - x</math>
|-
| rowspan="3" |Triangular numbers
|Tri
|1
|<math>Tri := R(Z^0, AddS)</math>
|7
|<math>\lambda x. \frac{x(x+1)}{2}</math>
|-
|TriP
|1
|<math>TriP := R(Z^0, Add)</math>
|7
|<math>TriP(x+1) = Tri(x)</math>
|-
|TriPXA
|2
|<math>TriPXA := R(Z^1, AddXA)</math>
|7
|<math>TriPXA(x,y) = TriP(x)</math>
|-
| rowspan="2" |Inverting Tri
|RMonusTri
|2
|<math>RMonusTri := C(RMonus, C(Tri, P^2_1), P^2_2)</math>
|18
|<math>\lambda xy. y \dot - Tri(x)</math>
|-
|InvTriCeil
|1
|<math>InvTriCeil := M(RMonusTri)</math>
|19
|<math>\lambda y. \min \{x | Tri(x) \ge y \}</math>
|-
| rowspan="5" | Combined LRCall
|RightPiece
|3
|<math>RightPiece := R(P^2_2, C(Pred, P^4_2))</math>
|7
|<math>\lambda xyz. z \dot - x</math>
|-
|LeftPiece
|3
|<math>LeftPiece := C(RMonus, C(S, P^3_2), P^3_1)</math>
|12
|<math>\lambda xyz. x \dot - (y+1)</math>
|-
|LRpart1[f]
|3
|<math>LRpart1[f] := C(f, LeftPiece, RightPiece)</math>
|<math>20 + |f|</math>
|<math>\lambda xyz. f(x \dot - (y+1), z \dot - x)</math>
|-
|LRpart2[f]
|3
|<math>LRpart2[f] := C(LRpart1[f], P^3_3, P^3_1, AddXA)</math>
|<math>28 + |f|</math>
|<math>\lambda xyz. f(z \dot - (x+1), x+y\dot - z)</math>
|-
|LRpart3[f]
|2
|<math>LRpart3[f] := C(LRpart2[f], TriPXA, P^2_1, P^2_2)</math>
|<math>38 + |f|</math>
|<math>\lambda xy. f(y\dot - (TriP(x)+1), TriP(x)+x\dot - y)</math>
|}

[[Category:functions]]

General Recursive Function

2026-04-11T06:47:17Z

JLM: /* Utilizing Minimization */ Reduce size of LRCall by 2 by using ignored extra arguments

'''General recursive functions''' ('''GRFs'''), also called '''µ-recursive functions''' or '''partial recursive functions''', are the collection of [[Wikipedia:partial functions|partial functions]] <math>\N^k \rightharpoonup \N</math> 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 <math>\N^k \rightharpoonup \N</math> 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:<math display="block">BB \mu (n) = \max \{ f() | f \in \text{GRF}_0 , |f| = n \}</math>

where <math>f \in GRF_k</math> means that <math>f: \N^k \rightharpoonup \N</math> is a k-ary GRF and <math>|f|</math> 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 <math>GRF_k</math> inductively based on the following construction rules, start with Atoms and combine them using Combinators.

====== Atoms ======

* Zero: <math>\forall k \in \N, Z^k \in GRF_k</math> is the constant 0 function <math>Z^k(x_1, \dots, x_k) = 0</math>
* Successor: <math>S \in GRF_1</math> is the successor function <math>S(x) = x+1</math>
* Projection: <math>\forall 1 \le i \le k \in \N, P^k_i \in GRF_k</math> is a projection function <math>P^k_i(x_1, \dots x_k) = x_i</math>

===== Combinators =====

* Composition: <math>\forall k,m \in \N, \forall h \in GRF_m, \forall g_1, \dots g_m \in GRF_k, C(h, g_1, \dots g_m) \in GRF_k</math> is the composition or substitution of the ''g''s into ''h'': <math>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))</math>
* Primitive Recursion: <math>\forall k \in \N, \forall g \in GRF_k, \forall h \in GRF_{k+2}, R(g, h) \in GRF_{k+1}</math> is primitive recursion using ''g'' as the base case and ''h'' as the inductive step.
* Minimization / Unlimited Search: <math>\forall k \in \N, \forall f \in GRF_{k+1}, M(f) \in GRF_k</math> is the µ-operator which allows unlimited search.

=== Primitive Recursion ===
<math>R</math> models a typical iterative function definition over ℕ.

Base case: <math>R^k(g, h)(0, x_2, x_3, ..., x_k) = g(x_2, x_3, ..., x_k)</math>

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

<math>R</math> 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 <math>g</math>), then 1, 2, 3, etc. until <math>x_1</math> is reached, each time calling <math>h</math> with the prior iteration count for its first argument and the result of the prior call for its second.

=== Minimization ===
<math>M^k(f)(x_1, ..., x_k) \triangleq \min \{i \in \N: f(i, x_1, ..., x_k) = 0\}</math>

In computational language, when ''M(f)'' is evaluated it can be considered to calculate <math>f(i, x_1, ..., x_k)</math> with <math>i=0</math>, then <math>i=1</math>, then <math>i=2</math> etc. until one of the calls to <math>f</math> returns 0. It returns the value of <math>i</math> which first gave a result of 0. If no first argument causes <math>f</math> to return 0, <math>M(f)</math> 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 <math>f \in GRF_1</math>
{| class="wikitable"
|+
!
!Macro
!arity
!Definition
!Size
!Function
|-
|Plus constant
|<math>Plus[n]</math>
|1
|<math>\begin{array}{lcl}
Plus[1] & := & S \\
Plus[n+1] & := & C(S, Plus[n])
\end{array}</math>
|<math>2n-1</math>
|<math>\lambda x. x+n</math>
|-
|Constant
|<math>K^k[n]</math>
|k
|<math>\begin{array}{lcl}
K^k[0] & := & Z^k \\
K^k[n] & := & C(Plus[n], Z^k)
\end{array}</math>
|<math>2n+1</math>
|<math>\lambda x_1 \dots x_k. n</math>
|-
|Iteration
|<math>Rep[f,n]</math>
|1
|<math>Rep[f,n] := R(K^0[n], C(f, P^2_2))</math>
|<math>|f| + 2n + 4</math>
|<math>\lambda x. f^x(n)</math>
|-
|Iteration of successor
|<math>RepSucc[f]</math>
|2
|<math>RepSucc[f] := R(S, C(f, P^3_2))</math>
|<math>|f| + 4</math>
|<math>\lambda x\ y. f^x(y+1)</math>
|-
|Diagonalization
|<math>RepDiag[f]</math>
|1
|<math>RepDiag[f] := C(RepSucc[f], S, S)</math>
|<math>|f| + 7</math>
|<math>\lambda x. f^{x+1}(x+2)</math>
|-
|Ackermann iteration
|<math>Ack[n,f]</math>
|1
|<math>\begin{array}{lcl}
Ack[0,f] & := & f \\
Ack[n+1,f] & := & Rep[Ack[n,f],1]
\end{array}</math>
|<math>6n + |f|</math>
|
|-
|Knuth base 2 up-arrows
|<math>Knuth2[n]</math>
|1
|<math>\begin{array}{lcl}
Knuth2[0] & := & Rep[Plus[2],0] \\
Knuth2[n+1] & := & Rep[Knuth2[n],1]
\end{array}</math>
|<math>6n+7</math>
|<math>\lambda x. 2 \uparrow^n x</math>
|-
|Ackermann Diagonalization
on Triangular nums
|<math>ADT[n]</math>
|1
|<math>\begin{array}{lcl}
ADT[0] & := & Tri \\
ADT[n+1] & := & RepDiag[ADT[n]]
\end{array}</math>
|<math>7n + 7</math>
|<math>\lambda x. > 10 \uparrow^n (x+1)</math>
|-
|Polygonal
|<math>Poly[n]</math>
|1
|<math>Poly[n] := R(Z^0, R(S, C(Plus[n], P^3_2)))</math>
|<math>2n+5</math>
|<math>\lambda x. \frac{n}{2} x(x-1) + x</math>
|-
|
|<math>Tri</math>
|1
|<math>Tri := Poly[1] = R(Z^0, R(S, C(S, P^3_2)))</math>
|<math>7</math>
|<math>\lambda x. \frac{x(x+1)}{2}</math>
|-
|
|<math>Square</math>
|1
|<math>Square := Poly[2]</math>
|<math>9</math>
|<math>\lambda x. x^2</math>
|}

== Champions ==
{| class="wikitable"
!n
!BBµ(n)
!Champion
!Champion Found
!Holdouts Proven
|-
|1
|= 0
|<math>Z^0</math>
|
|Shawn Ligocki [https://discord.com/channels/960643023006490684/1447627603698647303/1447693296322215976 8 Dec 2025] By hand
|-
|2
|= 0
|<math>M(Z^1), M(P^1_1), C(Z^0)</math>
|
|Shawn Ligocki [https://discord.com/channels/960643023006490684/1447627603698647303/1447693296322215976 8 Dec 2025] By hand
|-
|3
|= 1
|<math>K^0[1]</math>
|
|Shawn Ligocki [https://discord.com/channels/960643023006490684/1447627603698647303/1447693296322215976 8 Dec 2025] By hand
|-
|4
|= 1
|<math>C^0(K^0[1])</math>
|
|Jacob Mandelson [https://mandelson.org/grf/ 3 Apr 2026]
|-
|5
|= 2
|<math>K^0[2]</math>
|
|Jacob Mandelson [https://mandelson.org/grf/ 3 Apr 2026]
|-
|6
|= 2
|<math>C^0(K^0[2])</math>
|
|Jacob Mandelson [https://mandelson.org/grf/ 3 Apr 2026]
|-
|7
|= 3
|<math>K^0[3]</math>
|
|Jacob Mandelson [https://mandelson.org/grf/ 3 Apr 2026]
|-
|9
|≥ 4
|<math>K^0[4]</math>
|
|
|-
|11
|≥ 5
|<math>K^0[5]</math>
|
|
|-
|13
|≥ 6
|<math>K^0[6]</math>
|
|
|-
|14
|≥ 7
|<math>C(RepDiag[S], K^0[2])</math>
|Shawn Ligocki [https://discord.com/channels/960643023006490684/1447627603698647303/1492246885329670184 10 Apr 2026]
|
|-
|16
|≥ 10
|<math>C(RepDiag[Plus[2]], K^0[2])</math>
|Shawn Ligocki [https://discord.com/channels/960643023006490684/1447627603698647303/1492394919728517160 11 Apr 2026]
|
|-
|17
|≥ 10
|<math>C(Tri, K^0[4])</math>
|Shawn Ligocki 9 Dec 2025
|
|-
|18
|≥ 21
|<math>C(RepDiag[Tri], K^0[1])</math>
|Jacob Mandelson [https://discord.com/channels/960643023006490684/1447627603698647303/1492021428546179182 9 Apr 2026]
|
|-
|20
|≥ 1540
|<math>C(RepDiag[Tri], K^0[2])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|22
|≥ 26'357'430
|<math>C(RepDiag[Tri], K^0[3])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|24
|≥ 64'449'908'476'890'321 > 1016.8
|<math>C(RepDiag[Tri], K^0[4])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|25
|<math> > 10^{10^{10^{6.899}}} > 10 \uparrow\uparrow 3.8388</math>
|<math>C(ADT[2], K^0[1])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|27
|> <math>10 \uparrow\uparrow 6.0834</math>
|<math>C(ADT[2], K^0[2])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|29
|> <math>10 \uparrow\uparrow 8.1944</math>
|<math>C(ADT[2], K^0[3])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|31
|> <math>10 \uparrow\uparrow 10.2800</math>
|<math>C(ADT[2], K^0[4])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|32
|> <math>10 \uparrow\uparrow 10 \uparrow\uparrow 8.1944</math>
|<math>C(ADT[3], K^0[1])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|34
|> <math>10 \uparrow\uparrow\uparrow 4</math>
|<math>C(ADT[3], K^0[2])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|36
|> <math>10 \uparrow\uparrow\uparrow 5</math>
|<math>C(ADT[3], K^0[3])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|38
|> <math>10 \uparrow\uparrow\uparrow 6</math>
|<math>C(ADT[3], K^0[4])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|
|
|
|
|
|-
|7k+11
|> <math>10 \uparrow^k 2</math>
|<math>C(ADT[k], K^0[1])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|7k+13
|> <math>10 \uparrow^k 3</math>
|<math>C(ADT[k], K^0[2])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|7k+15
|> <math>10 \uparrow^k 4</math>
|<math>C(ADT[k], K^0[3])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|7k+17
|> <math>10 \uparrow^k 5</math>
|<math>C(ADT[k], K^0[4])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|
|
|
|
|
|-
|6k+17
|<math>\ge 2 \uparrow^k 4</math>
|<math>C(Knuth2[k], K^0[4])</math>
|Shawn Ligocki [https://discord.com/channels/960643023006490684/1447627603698647303/1447633458510692385 8 Dec 2025]
|
|-
|6k+19
|<math>\ge 2 \uparrow^k 5</math>
|<math>C(Knuth2[k], K^0[5])</math>
|Shawn Ligocki [https://discord.com/channels/960643023006490684/1447627603698647303/1447633458510692385 8 Dec 2025]
|
|-
|6k+21
|<math>\ge 2 \uparrow^k 6</math>
|<math>C(Knuth2[k], K^0[6])</math>
|Shawn Ligocki [https://discord.com/channels/960643023006490684/1447627603698647303/1447633458510692385 8 Dec 2025]
|
|}

== Macro Bounds ==

=== ADT[k] ===

* <math>ADT[0](n) = Tri(n) = \frac{n(n+1)}{2} > \frac{1}{2} n^2</math>
* <math>ADT[0]^k(n) > 2 \left( \frac{n}{2} \right)^{2^k}</math>
* <math>ADT[1](n) = Tri^{n+1}(n+2) > 2 \left(\frac{n+2}{2} \right)^{2^{n+1}} = 2 \left(\frac{(n+2)^2}{4} \right)^{2^n} > A 10^{10^{n/A}}</math> where <math>A = \frac{1}{\log_{10}(2)}</math> (if <math>n \ge 5</math>, for smaller values, this can be calculated directly)
* <math>ADT[1]^k(n) > A (10 \uparrow)^{2k} \frac{n}{A} > 10 \uparrow\uparrow 2k</math> (if <math>n \ge 4</math>)
* <math>ADT[2](n) = ADT[1]^{n+1}(n+2) > 10 \uparrow\uparrow (2n+2) </math> (if <math>n \ge 2</math>)
* <math>ADT[k](n) > 10 \uparrow^k (n+1) </math> (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: <math>BB\mu(6k+17) \ge 2 \uparrow^k 4</math>.

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 [[wikipedia:Pairing_function|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, [[wikipedia:Common_subexpression_elimination|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:
{| class="wikitable"
|+Smallest Pairing Functions
!Macro
!arity
!Definition
!Size
!Function
|-
|<math>Pair</math>
|2
|<math>Pair := C(AddS, C(Tri, Add), P^2_1)</math>
|20
|<math>\lambda xy. \frac{(x+y)(x+y+1)}{2} + x + 1</math>
|-
|<math>Left</math>
|1
|<math>Left := C(RMonus, C(TriP, InvTriCeil), Pred)</math>
|38
|<math>Left(Pair(x,y)) = x</math>
|-
|<math>Right</math>
|1
|<math>Right := C(RMonus, P^1_1, C(Tri, InvTriCeil))</math>
|36
|<math>Right(Pair(x,y)) = y</math>
|-
|<math>LRCall[f^2]</math>
|1
|<math>LRCall[f] := C(LRpart3[f], InvTriCeil, P^1_1)</math>
|<math>59 + |f|</math>
|<math>LRCall[f](Pair(x,y)) = f(x,y)</math>
|}
Where these are based on the following definitions:
{| class="wikitable"
|+Macros
!
!Macro
!arity
!Definition
!Size
!Function
|-
| rowspan="3" |Addition
|Add
|2
|<math>Add := R(P^1_1, C(S, P^3_2))</math>
|5
|<math>\lambda xy. x+y</math>
|-
|AddXA
|3
|<math>AddXA := R(P^2_1, C(S, P^4_2))</math>
|5
|<math>\lambda xyz. x+y</math>
|-
|AddS
|2
|<math>AddS := R(S, C(S, P^3_2))</math>
|5
|<math>\lambda xy. x+y+1</math>
|-
|[[wikipedia:Primitive_recursive_function#Predecessor|Predecesor]]
|Pred
|1
|<math>Pred := R(Z^0, P^2_1)</math>
|3
|<math>\lambda x. x \dot - 1</math>
|-
|[[wikipedia:Monus#Natural_numbers|Monus]]
|RMonus
|2
|<math>RMonus := R(P^1_1, C(Pred, P^3_2))</math>
|7
|<math>\lambda xy. y \dot - x</math>
|-
| rowspan="3" |Triangular numbers
|Tri
|1
|<math>Tri := R(Z^0, AddS)</math>
|7
|<math>\lambda x. \frac{x(x+1)}{2}</math>
|-
|TriP
|1
|<math>TriP := R(Z^0, Add)</math>
|7
|<math>TriP(x+1) = Tri(x)</math>
|-
|TriPXA
|2
|<math>TriPXA := R(Z^1, AddXA)</math>
|7
|<math>TriPXA(x,y) = TriP(x)</math>
|-
| rowspan="2" |Inverting Tri
|RMonusTri
|2
|<math>RMonusTri := C(RMonus, C(Tri, P^2_1), P^2_2)</math>
|18
|<math>\lambda xy. y \dot - Tri(x)</math>
|-
|InvTriCeil
|1
|<math>InvTriCeil := M(RMonusTri)</math>
|19
|<math>\lambda y. \min \{x | Tri(x) \ge y \}</math>
|-
| rowspan="5" | Combined LRCall
|RightPiece
|3
|<math>RightPiece := R(P^2_2, C(Pred, P^4_2))</math>
|7
|<math>\lambda xyz. z \dot - x</math>
|-
|LeftPiece
|3
|<math>LeftPiece := C(RMonus, C(S, P^3_2), P^3_1)</math>
|12
|<math>\lambda xyz. x \dot - (y+1)</math>
|-
|LRpart1[f]
|3
|<math>LRpart1[f] := C(f, LeftPiece, RightPiece)</math>
|<math>20 + |f|</math>
|<math>\lambda xyz. f(x \dot - (y+1), z \dot - x)</math>
|-
|LRpart2[f]
|3
|<math>LRpart2[f] := C(LRpart1[f], P^3_3, P^3_1, R(P^2_1, C(S, P^4_2)))</math>
|<math>28 + |f|</math>
|<math>\lambda xyz. f(z \dot - (x+1), x+y\dot - z)</math>
|-
|LRpart3[f]
|2
|<math>LRpart3[f] := C(LRpart2[f], TriPXA, P^2_1, P^2_2)</math>
|<math>38 + |f|</math>
|<math>\lambda xy. f(y\dot - (TriP(x)+1), TriP(x)+x\dot - y)</math>
|}

[[Category:functions]]

General Recursive Function

2026-04-11T05:03:54Z

JLM: /* Utilizing Minimization */ Simplify LRpart3 fcn explanation.

'''General recursive functions''' ('''GRFs'''), also called '''µ-recursive functions''' or '''partial recursive functions''', are the collection of [[Wikipedia:partial functions|partial functions]] <math>\N^k \rightharpoonup \N</math> 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 <math>\N^k \rightharpoonup \N</math> 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:<math display="block">BB \mu (n) = \max \{ f() | f \in \text{GRF}_0 , |f| = n \}</math>

where <math>f \in GRF_k</math> means that <math>f: \N^k \rightharpoonup \N</math> is a k-ary GRF and <math>|f|</math> 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 <math>GRF_k</math> inductively based on the following construction rules, start with Atoms and combine them using Combinators.

====== Atoms ======

* Zero: <math>\forall k \in \N, Z^k \in GRF_k</math> is the constant 0 function <math>Z^k(x_1, \dots, x_k) = 0</math>
* Successor: <math>S \in GRF_1</math> is the successor function <math>S(x) = x+1</math>
* Projection: <math>\forall 1 \le i \le k \in \N, P^k_i \in GRF_k</math> is a projection function <math>P^k_i(x_1, \dots x_k) = x_i</math>

===== Combinators =====

* Composition: <math>\forall k,m \in \N, \forall h \in GRF_m, \forall g_1, \dots g_m \in GRF_k, C(h, g_1, \dots g_m) \in GRF_k</math> is the composition or substitution of the ''g''s into ''h'': <math>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))</math>
* Primitive Recursion: <math>\forall k \in \N, \forall g \in GRF_k, \forall h \in GRF_{k+2}, R(g, h) \in GRF_{k+1}</math> is primitive recursion using ''g'' as the base case and ''h'' as the inductive step.
* Minimization / Unlimited Search: <math>\forall k \in \N, \forall f \in GRF_{k+1}, M(f) \in GRF_k</math> is the µ-operator which allows unlimited search.

=== Primitive Recursion ===
<math>R</math> models a typical iterative function definition over ℕ.

Base case: <math>R^k(g, h)(0, x_2, x_3, ..., x_k) = g(x_2, x_3, ..., x_k)</math>

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

<math>R</math> 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 <math>g</math>), then 1, 2, 3, etc. until <math>x_1</math> is reached, each time calling <math>h</math> with the prior iteration count for its first argument and the result of the prior call for its second.

=== Minimization ===
<math>M^k(f)(x_1, ..., x_k) \triangleq \min \{i \in \N: f(i, x_1, ..., x_k) = 0\}</math>

In computational language, when ''M(f)'' is evaluated it can be considered to calculate <math>f(i, x_1, ..., x_k)</math> with <math>i=0</math>, then <math>i=1</math>, then <math>i=2</math> etc. until one of the calls to <math>f</math> returns 0. It returns the value of <math>i</math> which first gave a result of 0. If no first argument causes <math>f</math> to return 0, <math>M(f)</math> 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 <math>f \in GRF_1</math>
{| class="wikitable"
|+
!
!Macro
!arity
!Definition
!Size
!Function
|-
|Plus constant
|<math>Plus[n]</math>
|1
|<math>\begin{array}{lcl}
Plus[1] & := & S \\
Plus[n+1] & := & C(S, Plus[n])
\end{array}</math>
|<math>2n-1</math>
|<math>\lambda x. x+n</math>
|-
|Constant
|<math>K^k[n]</math>
|k
|<math>\begin{array}{lcl}
K^k[0] & := & Z^k \\
K^k[n] & := & C(Plus[n], Z^k)
\end{array}</math>
|<math>2n+1</math>
|<math>\lambda x_1 \dots x_k. n</math>
|-
|Iteration
|<math>Rep[f,n]</math>
|1
|<math>Rep[f,n] := R(K^0[n], C(f, P^2_2))</math>
|<math>|f| + 2n + 4</math>
|<math>\lambda x. f^x(n)</math>
|-
|Iteration of successor
|<math>RepSucc[f]</math>
|2
|<math>RepSucc[f] := R(S, C(f, P^3_2))</math>
|<math>|f| + 4</math>
|<math>\lambda x\ y. f^x(y+1)</math>
|-
|Diagonalization
|<math>RepDiag[f]</math>
|1
|<math>RepDiag[f] := C(RepSucc[f], S, S)</math>
|<math>|f| + 7</math>
|<math>\lambda x. f^{x+1}(x+2)</math>
|-
|Ackermann iteration
|<math>Ack[n,f]</math>
|1
|<math>\begin{array}{lcl}
Ack[0,f] & := & f \\
Ack[n+1,f] & := & Rep[Ack[n,f],1]
\end{array}</math>
|<math>6n + |f|</math>
|
|-
|Knuth base 2 up-arrows
|<math>Knuth2[n]</math>
|1
|<math>\begin{array}{lcl}
Knuth2[0] & := & Rep[Plus[2],0] \\
Knuth2[n+1] & := & Rep[Knuth2[n],1]
\end{array}</math>
|<math>6n+7</math>
|<math>\lambda x. 2 \uparrow^n x</math>
|-
|Ackermann Diagonalization
on Triangular nums
|<math>ADT[n]</math>
|1
|<math>\begin{array}{lcl}
ADT[0] & := & Tri \\
ADT[n+1] & := & RepDiag[ADT[n]]
\end{array}</math>
|<math>7n + 7</math>
|<math>\lambda x. > 10 \uparrow^n (x+1)</math>
|-
|Polygonal
|<math>Poly[n]</math>
|1
|<math>Poly[n] := R(Z^0, R(S, C(Plus[n], P^3_2)))</math>
|<math>2n+5</math>
|<math>\lambda x. \frac{n}{2} x(x-1) + x</math>
|-
|
|<math>Tri</math>
|1
|<math>Tri := Poly[1] = R(Z^0, R(S, C(S, P^3_2)))</math>
|<math>7</math>
|<math>\lambda x. \frac{x(x+1)}{2}</math>
|-
|
|<math>Square</math>
|1
|<math>Square := Poly[2]</math>
|<math>9</math>
|<math>\lambda x. x^2</math>
|}

== Champions ==
{| class="wikitable"
!n
!BBµ(n)
!Champion
!Champion Found
!Holdouts Proven
|-
|1
|= 0
|<math>Z^0</math>
|
|Shawn Ligocki [https://discord.com/channels/960643023006490684/1447627603698647303/1447693296322215976 8 Dec 2025] By hand
|-
|2
|= 0
|<math>M(Z^1), M(P^1_1), C(Z^0)</math>
|
|Shawn Ligocki [https://discord.com/channels/960643023006490684/1447627603698647303/1447693296322215976 8 Dec 2025] By hand
|-
|3
|= 1
|<math>K^0[1]</math>
|
|Shawn Ligocki [https://discord.com/channels/960643023006490684/1447627603698647303/1447693296322215976 8 Dec 2025] By hand
|-
|4
|= 1
|<math>C^0(K^0[1])</math>
|
|Jacob Mandelson [https://mandelson.org/grf/ 3 Apr 2026]
|-
|5
|= 2
|<math>K^0[2]</math>
|
|Jacob Mandelson [https://mandelson.org/grf/ 3 Apr 2026]
|-
|6
|= 2
|<math>C^0(K^0[2])</math>
|
|Jacob Mandelson [https://mandelson.org/grf/ 3 Apr 2026]
|-
|7
|= 3
|<math>K^0[3]</math>
|
|Jacob Mandelson [https://mandelson.org/grf/ 3 Apr 2026]
|-
|9
|≥ 4
|<math>K^0[4]</math>
|
|
|-
|11
|≥ 5
|<math>K^0[5]</math>
|
|
|-
|13
|≥ 6
|<math>K^0[6]</math>
|
|
|-
|14
|≥ 7
|<math>C(RepDiag[S], K^0[2])</math>
|Shawn Ligocki [https://discord.com/channels/960643023006490684/1447627603698647303/1492246885329670184 10 Apr 2026]
|
|-
|16
|≥ 9
|<math>C(RepDiag[S], K^0[3])</math>
|Shawn Ligocki [https://discord.com/channels/960643023006490684/1447627603698647303/1492246885329670184 10 Apr 2026]
|
|-
|17
|≥ 10
|<math>C(Tri, K^0[4])</math>
|Shawn Ligocki 9 Dec 2025
|
|-
|18
|≥ 21
|<math>C(RepDiag[Tri], K^0[1])</math>
|Jacob Mandelson [https://discord.com/channels/960643023006490684/1447627603698647303/1492021428546179182 9 Apr 2026]
|
|-
|20
|≥ 1540
|<math>C(RepDiag[Tri], K^0[2])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|22
|≥ 26'357'430
|<math>C(RepDiag[Tri], K^0[3])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|24
|≥ 64'449'908'476'890'321 > 1016.8
|<math>C(RepDiag[Tri], K^0[4])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|25
|<math> > 10^{10^{10^{6.899}}} > 10 \uparrow\uparrow 3.8388</math>
|<math>C(ADT[2], K^0[1])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|27
|> <math>10 \uparrow\uparrow 6.0834</math>
|<math>C(ADT[2], K^0[2])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|29
|> <math>10 \uparrow\uparrow 8.1944</math>
|<math>C(ADT[2], K^0[3])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|31
|> <math>10 \uparrow\uparrow 10.2800</math>
|<math>C(ADT[2], K^0[4])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|32
|> <math>10 \uparrow\uparrow 10 \uparrow\uparrow 8.1944</math>
|<math>C(ADT[3], K^0[1])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|34
|> <math>10 \uparrow\uparrow\uparrow 4</math>
|<math>C(ADT[3], K^0[2])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|36
|> <math>10 \uparrow\uparrow\uparrow 5</math>
|<math>C(ADT[3], K^0[3])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|38
|> <math>10 \uparrow\uparrow\uparrow 6</math>
|<math>C(ADT[3], K^0[4])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|
|
|
|
|
|-
|7k+11
|> <math>10 \uparrow^k 2</math>
|<math>C(ADT[k], K^0[1])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|7k+13
|> <math>10 \uparrow^k 3</math>
|<math>C(ADT[k], K^0[2])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|7k+15
|> <math>10 \uparrow^k 4</math>
|<math>C(ADT[k], K^0[3])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|7k+17
|> <math>10 \uparrow^k 5</math>
|<math>C(ADT[k], K^0[4])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|
|
|
|
|
|-
|6k+17
|<math>\ge 2 \uparrow^k 4</math>
|<math>C(Knuth2[k], K^0[4])</math>
|Shawn Ligocki [https://discord.com/channels/960643023006490684/1447627603698647303/1447633458510692385 8 Dec 2025]
|
|-
|6k+19
|<math>\ge 2 \uparrow^k 5</math>
|<math>C(Knuth2[k], K^0[5])</math>
|Shawn Ligocki [https://discord.com/channels/960643023006490684/1447627603698647303/1447633458510692385 8 Dec 2025]
|
|-
|6k+21
|<math>\ge 2 \uparrow^k 6</math>
|<math>C(Knuth2[k], K^0[6])</math>
|Shawn Ligocki [https://discord.com/channels/960643023006490684/1447627603698647303/1447633458510692385 8 Dec 2025]
|
|}

== Macro Bounds ==

=== ADT[k] ===

* <math>ADT[0](n) = Tri(n) = \frac{n(n+1)}{2} > \frac{1}{2} n^2</math>
* <math>ADT[0]^k(n) > 2 \left( \frac{n}{2} \right)^{2^k}</math>
* <math>ADT[1](n) = Tri^{n+1}(n+2) > 2 \left(\frac{n+2}{2} \right)^{2^{n+1}} = 2 \left(\frac{(n+2)^2}{4} \right)^{2^n} > A 10^{10^{n/A}}</math> where <math>A = \frac{1}{\log_{10}(2)}</math> (if <math>n \ge 5</math>, for smaller values, this can be calculated directly)
* <math>ADT[1]^k(n) > A (10 \uparrow)^{2k} \frac{n}{A} > 10 \uparrow\uparrow 2k</math> (if <math>n \ge 4</math>)
* <math>ADT[2](n) = ADT[1]^{n+1}(n+2) > 10 \uparrow\uparrow (2n+2) </math> (if <math>n \ge 2</math>)
* <math>ADT[k](n) > 10 \uparrow^k (n+1) </math> (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: <math>BB\mu(6k+17) \ge 2 \uparrow^k 4</math>.

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 [[wikipedia:Pairing_function|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, [[wikipedia:Common_subexpression_elimination|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:
{| class="wikitable"
|+Smallest Pairing Functions
!Macro
!arity
!Definition
!Size
!Function
|-
|<math>Pair</math>
|2
|<math>Pair := C(AddS, C(Tri, Add), P^2_1)</math>
|20
|<math>\lambda xy. \frac{(x+y)(x+y+1)}{2} + x + 1</math>
|-
|<math>Left</math>
|1
|<math>Left := C(RMonus, C(TriP, InvTriCeil), Pred)</math>
|38
|<math>Left(Pair(x,y)) = x</math>
|-
|<math>Right</math>
|1
|<math>Right := C(RMonus, P^1_1, C(Tri, InvTriCeil))</math>
|36
|<math>Right(Pair(x,y)) = y</math>
|-
|<math>LRCall[f^2]</math>
|1
|<math>LRCall[f] := C(LRpart3[f], InvTriCeil, P^1_1)</math>
|<math>61 + |f|</math>
|<math>LRCall[f](Pair(x,y)) = f(x,y)</math>
|}
Where these are based on the following definitions:
{| class="wikitable"
|+Macros
!
!Macro
!arity
!Definition
!Size
!Function
|-
| rowspan="2" |Addition
|Add
|2
|<math>Add := R(P^1_1, C(S, P^3_2))</math>
|5
|<math>\lambda xy. x+y</math>
|-
|AddS
|2
|<math>AddS := R(S, C(S, P^3_2))</math>
|5
|<math>\lambda xy. x+y+1</math>
|-
|[[wikipedia:Primitive_recursive_function#Predecessor|Predecesor]]
|Pred
|1
|<math>Pred := R(Z^0, P^2_1)</math>
|3
|<math>\lambda x. x \dot - 1</math>
|-
|[[wikipedia:Monus#Natural_numbers|Monus]]
|RMonus
|2
|<math>RMonus := R(P^1_1, C(Pred, P^3_2))</math>
|7
|<math>\lambda xy. y \dot - x</math>
|-
| rowspan="2" |Triangular numbers
|Tri
|1
|<math>Tri := R(Z^0, AddS)</math>
|7
|<math>\lambda x. \frac{x(x+1)}{2}</math>
|-
|TriP
|1
|<math>TriP := R(Z^0, Add)</math>
|7
|<math>TriP(x+1) = Tri(x)</math>
|-
| rowspan="2" |Inverting Tri
|RMonusTri
|2
|<math>RMonusTri := C(RMonus, C(Tri, P^2_1), P^2_2)</math>
|18
|<math>\lambda xy. y \dot - Tri(x)</math>
|-
|InvTriCeil
|1
|<math>InvTriCeil := M(RMonusTri)</math>
|19
|<math>\lambda y. \min \{x | Tri(x) \ge y \}</math>
|-
| rowspan="5" | Combined LRCall
|RightPiece
|3
|<math>RightPiece := R(P^2_2, C(Pred, P^4_2))</math>
|7
|<math>\lambda xyz. z \dot - x</math>
|-
|LeftPiece
|3
|<math>LeftPiece := C(RMonus, C(S, P^3_2), P^3_1)</math>
|12
|<math>\lambda xyz. x \dot - (y+1)</math>
|-
|LRpart1[f]
|3
|<math>LRpart1[f] := C(f, LeftPiece, RightPiece)</math>
|<math>20 + |f|</math>
|<math>\lambda xyz. f(x \dot - (y+1), z \dot - x)</math>
|-
|LRpart2[f]
|3
|<math>LRpart2[f] := C(LRpart1[f], P^3_3, P^3_1, R(P^2_1, C(S, P^4_2)))</math>
|<math>28 + |f|</math>
|<math>\lambda xyz. f(z \dot - (x+1), x+y\dot - z)</math>
|-
|LRpart3[f]
|2
|<math>LRpart3[f] := C(LRpart2[f], C(TriP, P^2_1), P^2_1, P^2_2)</math>
|<math>40 + |f|</math>
|<math>\lambda xy. f(y\dot - (TriP(x)+1), TriP(x)+x\dot - y)</math>
|}

[[Category:functions]]

General Recursive Function

2026-04-11T04:58:57Z

JLM: /* Utilizing Minimization */ Simplify LRpart2 fcn explanation

'''General recursive functions''' ('''GRFs'''), also called '''µ-recursive functions''' or '''partial recursive functions''', are the collection of [[Wikipedia:partial functions|partial functions]] <math>\N^k \rightharpoonup \N</math> 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 <math>\N^k \rightharpoonup \N</math> 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:<math display="block">BB \mu (n) = \max \{ f() | f \in \text{GRF}_0 , |f| = n \}</math>

where <math>f \in GRF_k</math> means that <math>f: \N^k \rightharpoonup \N</math> is a k-ary GRF and <math>|f|</math> 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 <math>GRF_k</math> inductively based on the following construction rules, start with Atoms and combine them using Combinators.

====== Atoms ======

* Zero: <math>\forall k \in \N, Z^k \in GRF_k</math> is the constant 0 function <math>Z^k(x_1, \dots, x_k) = 0</math>
* Successor: <math>S \in GRF_1</math> is the successor function <math>S(x) = x+1</math>
* Projection: <math>\forall 1 \le i \le k \in \N, P^k_i \in GRF_k</math> is a projection function <math>P^k_i(x_1, \dots x_k) = x_i</math>

===== Combinators =====

* Composition: <math>\forall k,m \in \N, \forall h \in GRF_m, \forall g_1, \dots g_m \in GRF_k, C(h, g_1, \dots g_m) \in GRF_k</math> is the composition or substitution of the ''g''s into ''h'': <math>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))</math>
* Primitive Recursion: <math>\forall k \in \N, \forall g \in GRF_k, \forall h \in GRF_{k+2}, R(g, h) \in GRF_{k+1}</math> is primitive recursion using ''g'' as the base case and ''h'' as the inductive step.
* Minimization / Unlimited Search: <math>\forall k \in \N, \forall f \in GRF_{k+1}, M(f) \in GRF_k</math> is the µ-operator which allows unlimited search.

=== Primitive Recursion ===
<math>R</math> models a typical iterative function definition over ℕ.

Base case: <math>R^k(g, h)(0, x_2, x_3, ..., x_k) = g(x_2, x_3, ..., x_k)</math>

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

<math>R</math> 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 <math>g</math>), then 1, 2, 3, etc. until <math>x_1</math> is reached, each time calling <math>h</math> with the prior iteration count for its first argument and the result of the prior call for its second.

=== Minimization ===
<math>M^k(f)(x_1, ..., x_k) \triangleq \min \{i \in \N: f(i, x_1, ..., x_k) = 0\}</math>

In computational language, when ''M(f)'' is evaluated it can be considered to calculate <math>f(i, x_1, ..., x_k)</math> with <math>i=0</math>, then <math>i=1</math>, then <math>i=2</math> etc. until one of the calls to <math>f</math> returns 0. It returns the value of <math>i</math> which first gave a result of 0. If no first argument causes <math>f</math> to return 0, <math>M(f)</math> 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 <math>f \in GRF_1</math>
{| class="wikitable"
|+
!
!Macro
!arity
!Definition
!Size
!Function
|-
|Plus constant
|<math>Plus[n]</math>
|1
|<math>\begin{array}{lcl}
Plus[1] & := & S \\
Plus[n+1] & := & C(S, Plus[n])
\end{array}</math>
|<math>2n-1</math>
|<math>\lambda x. x+n</math>
|-
|Constant
|<math>K^k[n]</math>
|k
|<math>\begin{array}{lcl}
K^k[0] & := & Z^k \\
K^k[n] & := & C(Plus[n], Z^k)
\end{array}</math>
|<math>2n+1</math>
|<math>\lambda x_1 \dots x_k. n</math>
|-
|Iteration
|<math>Rep[f,n]</math>
|1
|<math>Rep[f,n] := R(K^0[n], C(f, P^2_2))</math>
|<math>|f| + 2n + 4</math>
|<math>\lambda x. f^x(n)</math>
|-
|Iteration of successor
|<math>RepSucc[f]</math>
|2
|<math>RepSucc[f] := R(S, C(f, P^3_2))</math>
|<math>|f| + 4</math>
|<math>\lambda x\ y. f^x(y+1)</math>
|-
|Diagonalization
|<math>RepDiag[f]</math>
|1
|<math>RepDiag[f] := C(RepSucc[f], S, S)</math>
|<math>|f| + 7</math>
|<math>\lambda x. f^{x+1}(x+2)</math>
|-
|Ackermann iteration
|<math>Ack[n,f]</math>
|1
|<math>\begin{array}{lcl}
Ack[0,f] & := & f \\
Ack[n+1,f] & := & Rep[Ack[n,f],1]
\end{array}</math>
|<math>6n + |f|</math>
|
|-
|Knuth base 2 up-arrows
|<math>Knuth2[n]</math>
|1
|<math>\begin{array}{lcl}
Knuth2[0] & := & Rep[Plus[2],0] \\
Knuth2[n+1] & := & Rep[Knuth2[n],1]
\end{array}</math>
|<math>6n+7</math>
|<math>\lambda x. 2 \uparrow^n x</math>
|-
|Ackermann Diagonalization
on Triangular nums
|<math>ADT[n]</math>
|1
|<math>\begin{array}{lcl}
ADT[0] & := & Tri \\
ADT[n+1] & := & RepDiag[ADT[n]]
\end{array}</math>
|<math>7n + 7</math>
|<math>\lambda x. > 10 \uparrow^n (x+1)</math>
|-
|Polygonal
|<math>Poly[n]</math>
|1
|<math>Poly[n] := R(Z^0, R(S, C(Plus[n], P^3_2)))</math>
|<math>2n+5</math>
|<math>\lambda x. \frac{n}{2} x(x-1) + x</math>
|-
|
|<math>Tri</math>
|1
|<math>Tri := Poly[1] = R(Z^0, R(S, C(S, P^3_2)))</math>
|<math>7</math>
|<math>\lambda x. \frac{x(x+1)}{2}</math>
|-
|
|<math>Square</math>
|1
|<math>Square := Poly[2]</math>
|<math>9</math>
|<math>\lambda x. x^2</math>
|}

== Champions ==
{| class="wikitable"
!n
!BBµ(n)
!Champion
!Champion Found
!Holdouts Proven
|-
|1
|= 0
|<math>Z^0</math>
|
|Shawn Ligocki [https://discord.com/channels/960643023006490684/1447627603698647303/1447693296322215976 8 Dec 2025] By hand
|-
|2
|= 0
|<math>M(Z^1), M(P^1_1), C(Z^0)</math>
|
|Shawn Ligocki [https://discord.com/channels/960643023006490684/1447627603698647303/1447693296322215976 8 Dec 2025] By hand
|-
|3
|= 1
|<math>K^0[1]</math>
|
|Shawn Ligocki [https://discord.com/channels/960643023006490684/1447627603698647303/1447693296322215976 8 Dec 2025] By hand
|-
|4
|= 1
|<math>C^0(K^0[1])</math>
|
|Jacob Mandelson [https://mandelson.org/grf/ 3 Apr 2026]
|-
|5
|= 2
|<math>K^0[2]</math>
|
|Jacob Mandelson [https://mandelson.org/grf/ 3 Apr 2026]
|-
|6
|= 2
|<math>C^0(K^0[2])</math>
|
|Jacob Mandelson [https://mandelson.org/grf/ 3 Apr 2026]
|-
|7
|= 3
|<math>K^0[3]</math>
|
|Jacob Mandelson [https://mandelson.org/grf/ 3 Apr 2026]
|-
|9
|≥ 4
|<math>K^0[4]</math>
|
|
|-
|11
|≥ 5
|<math>K^0[5]</math>
|
|
|-
|13
|≥ 6
|<math>K^0[6]</math>
|
|
|-
|14
|≥ 7
|<math>C(RepDiag[S], K^0[2])</math>
|Shawn Ligocki [https://discord.com/channels/960643023006490684/1447627603698647303/1492246885329670184 10 Apr 2026]
|
|-
|16
|≥ 9
|<math>C(RepDiag[S], K^0[3])</math>
|Shawn Ligocki [https://discord.com/channels/960643023006490684/1447627603698647303/1492246885329670184 10 Apr 2026]
|
|-
|17
|≥ 10
|<math>C(Tri, K^0[4])</math>
|Shawn Ligocki 9 Dec 2025
|
|-
|18
|≥ 21
|<math>C(RepDiag[Tri], K^0[1])</math>
|Jacob Mandelson [https://discord.com/channels/960643023006490684/1447627603698647303/1492021428546179182 9 Apr 2026]
|
|-
|20
|≥ 1540
|<math>C(RepDiag[Tri], K^0[2])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|22
|≥ 26'357'430
|<math>C(RepDiag[Tri], K^0[3])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|24
|≥ 64'449'908'476'890'321 > 1016.8
|<math>C(RepDiag[Tri], K^0[4])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|25
|<math> > 10^{10^{10^{6.899}}} > 10 \uparrow\uparrow 3.8388</math>
|<math>C(ADT[2], K^0[1])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|27
|> <math>10 \uparrow\uparrow 6.0834</math>
|<math>C(ADT[2], K^0[2])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|29
|> <math>10 \uparrow\uparrow 8.1944</math>
|<math>C(ADT[2], K^0[3])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|31
|> <math>10 \uparrow\uparrow 10.2800</math>
|<math>C(ADT[2], K^0[4])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|32
|> <math>10 \uparrow\uparrow 10 \uparrow\uparrow 8.1944</math>
|<math>C(ADT[3], K^0[1])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|34
|> <math>10 \uparrow\uparrow\uparrow 4</math>
|<math>C(ADT[3], K^0[2])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|36
|> <math>10 \uparrow\uparrow\uparrow 5</math>
|<math>C(ADT[3], K^0[3])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|38
|> <math>10 \uparrow\uparrow\uparrow 6</math>
|<math>C(ADT[3], K^0[4])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|
|
|
|
|
|-
|7k+11
|> <math>10 \uparrow^k 2</math>
|<math>C(ADT[k], K^0[1])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|7k+13
|> <math>10 \uparrow^k 3</math>
|<math>C(ADT[k], K^0[2])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|7k+15
|> <math>10 \uparrow^k 4</math>
|<math>C(ADT[k], K^0[3])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|7k+17
|> <math>10 \uparrow^k 5</math>
|<math>C(ADT[k], K^0[4])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|
|
|
|
|
|-
|6k+17
|<math>\ge 2 \uparrow^k 4</math>
|<math>C(Knuth2[k], K^0[4])</math>
|Shawn Ligocki [https://discord.com/channels/960643023006490684/1447627603698647303/1447633458510692385 8 Dec 2025]
|
|-
|6k+19
|<math>\ge 2 \uparrow^k 5</math>
|<math>C(Knuth2[k], K^0[5])</math>
|Shawn Ligocki [https://discord.com/channels/960643023006490684/1447627603698647303/1447633458510692385 8 Dec 2025]
|
|-
|6k+21
|<math>\ge 2 \uparrow^k 6</math>
|<math>C(Knuth2[k], K^0[6])</math>
|Shawn Ligocki [https://discord.com/channels/960643023006490684/1447627603698647303/1447633458510692385 8 Dec 2025]
|
|}

== Macro Bounds ==

=== ADT[k] ===

* <math>ADT[0](n) = Tri(n) = \frac{n(n+1)}{2} > \frac{1}{2} n^2</math>
* <math>ADT[0]^k(n) > 2 \left( \frac{n}{2} \right)^{2^k}</math>
* <math>ADT[1](n) = Tri^{n+1}(n+2) > 2 \left(\frac{n+2}{2} \right)^{2^{n+1}} = 2 \left(\frac{(n+2)^2}{4} \right)^{2^n} > A 10^{10^{n/A}}</math> where <math>A = \frac{1}{\log_{10}(2)}</math> (if <math>n \ge 5</math>, for smaller values, this can be calculated directly)
* <math>ADT[1]^k(n) > A (10 \uparrow)^{2k} \frac{n}{A} > 10 \uparrow\uparrow 2k</math> (if <math>n \ge 4</math>)
* <math>ADT[2](n) = ADT[1]^{n+1}(n+2) > 10 \uparrow\uparrow (2n+2) </math> (if <math>n \ge 2</math>)
* <math>ADT[k](n) > 10 \uparrow^k (n+1) </math> (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: <math>BB\mu(6k+17) \ge 2 \uparrow^k 4</math>.

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 [[wikipedia:Pairing_function|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, [[wikipedia:Common_subexpression_elimination|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:
{| class="wikitable"
|+Smallest Pairing Functions
!Macro
!arity
!Definition
!Size
!Function
|-
|<math>Pair</math>
|2
|<math>Pair := C(AddS, C(Tri, Add), P^2_1)</math>
|20
|<math>\lambda xy. \frac{(x+y)(x+y+1)}{2} + x + 1</math>
|-
|<math>Left</math>
|1
|<math>Left := C(RMonus, C(TriP, InvTriCeil), Pred)</math>
|38
|<math>Left(Pair(x,y)) = x</math>
|-
|<math>Right</math>
|1
|<math>Right := C(RMonus, P^1_1, C(Tri, InvTriCeil))</math>
|36
|<math>Right(Pair(x,y)) = y</math>
|-
|<math>LRCall[f^2]</math>
|1
|<math>LRCall[f] := C(LRpart3[f], InvTriCeil, P^1_1)</math>
|<math>61 + |f|</math>
|<math>LRCall[f](Pair(x,y)) = f(x,y)</math>
|}
Where these are based on the following definitions:
{| class="wikitable"
|+Macros
!
!Macro
!arity
!Definition
!Size
!Function
|-
| rowspan="2" |Addition
|Add
|2
|<math>Add := R(P^1_1, C(S, P^3_2))</math>
|5
|<math>\lambda xy. x+y</math>
|-
|AddS
|2
|<math>AddS := R(S, C(S, P^3_2))</math>
|5
|<math>\lambda xy. x+y+1</math>
|-
|[[wikipedia:Primitive_recursive_function#Predecessor|Predecesor]]
|Pred
|1
|<math>Pred := R(Z^0, P^2_1)</math>
|3
|<math>\lambda x. x \dot - 1</math>
|-
|[[wikipedia:Monus#Natural_numbers|Monus]]
|RMonus
|2
|<math>RMonus := R(P^1_1, C(Pred, P^3_2))</math>
|7
|<math>\lambda xy. y \dot - x</math>
|-
| rowspan="2" |Triangular numbers
|Tri
|1
|<math>Tri := R(Z^0, AddS)</math>
|7
|<math>\lambda x. \frac{x(x+1)}{2}</math>
|-
|TriP
|1
|<math>TriP := R(Z^0, Add)</math>
|7
|<math>TriP(x+1) = Tri(x)</math>
|-
| rowspan="2" |Inverting Tri
|RMonusTri
|2
|<math>RMonusTri := C(RMonus, C(Tri, P^2_1), P^2_2)</math>
|18
|<math>\lambda xy. y \dot - Tri(x)</math>
|-
|InvTriCeil
|1
|<math>InvTriCeil := M(RMonusTri)</math>
|19
|<math>\lambda y. \min \{x | Tri(x) \ge y \}</math>
|-
| rowspan="5" | Combined LRCall
|RightPiece
|3
|<math>RightPiece := R(P^2_2, C(Pred, P^4_2))</math>
|7
|<math>\lambda xyz. z \dot - x</math>
|-
|LeftPiece
|3
|<math>LeftPiece := C(RMonus, C(S, P^3_2), P^3_1)</math>
|12
|<math>\lambda xyz. x \dot - (y+1)</math>
|-
|LRpart1[f]
|3
|<math>LRpart1[f] := C(f, LeftPiece, RightPiece)</math>
|<math>20 + |f|</math>
|<math>\lambda xyz. f(x \dot - (y+1), z \dot - x)</math>
|-
|LRpart2[f]
|3
|<math>LRpart2[f] := C(LRpart1[f], P^3_3, P^3_1, R(P^2_1, C(S, P^4_2)))</math>
|<math>28 + |f|</math>
|<math>\lambda xyz. f(z \dot - (x+1), x+y\dot - z)</math>
|-
|LRpart3[f]
|2
|<math>LRpart3[f] := C(LRpart2[f], C(TriP, P^2_1), P^2_1, P^2_2)</math>
|<math>40 + |f|</math>
|<math>\lambda xy. LRpart2[f](TriP(x), x, y)</math>
|}

[[Category:functions]]

General Recursive Function

2026-04-11T04:53:39Z

JLM: /* Utilizing Minimization */ Simplify LRpart1 fcn explanation.

'''General recursive functions''' ('''GRFs'''), also called '''µ-recursive functions''' or '''partial recursive functions''', are the collection of [[Wikipedia:partial functions|partial functions]] <math>\N^k \rightharpoonup \N</math> 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 <math>\N^k \rightharpoonup \N</math> 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:<math display="block">BB \mu (n) = \max \{ f() | f \in \text{GRF}_0 , |f| = n \}</math>

where <math>f \in GRF_k</math> means that <math>f: \N^k \rightharpoonup \N</math> is a k-ary GRF and <math>|f|</math> 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 <math>GRF_k</math> inductively based on the following construction rules, start with Atoms and combine them using Combinators.

====== Atoms ======

* Zero: <math>\forall k \in \N, Z^k \in GRF_k</math> is the constant 0 function <math>Z^k(x_1, \dots, x_k) = 0</math>
* Successor: <math>S \in GRF_1</math> is the successor function <math>S(x) = x+1</math>
* Projection: <math>\forall 1 \le i \le k \in \N, P^k_i \in GRF_k</math> is a projection function <math>P^k_i(x_1, \dots x_k) = x_i</math>

===== Combinators =====

* Composition: <math>\forall k,m \in \N, \forall h \in GRF_m, \forall g_1, \dots g_m \in GRF_k, C(h, g_1, \dots g_m) \in GRF_k</math> is the composition or substitution of the ''g''s into ''h'': <math>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))</math>
* Primitive Recursion: <math>\forall k \in \N, \forall g \in GRF_k, \forall h \in GRF_{k+2}, R(g, h) \in GRF_{k+1}</math> is primitive recursion using ''g'' as the base case and ''h'' as the inductive step.
* Minimization / Unlimited Search: <math>\forall k \in \N, \forall f \in GRF_{k+1}, M(f) \in GRF_k</math> is the µ-operator which allows unlimited search.

=== Primitive Recursion ===
<math>R</math> models a typical iterative function definition over ℕ.

Base case: <math>R^k(g, h)(0, x_2, x_3, ..., x_k) = g(x_2, x_3, ..., x_k)</math>

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

<math>R</math> 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 <math>g</math>), then 1, 2, 3, etc. until <math>x_1</math> is reached, each time calling <math>h</math> with the prior iteration count for its first argument and the result of the prior call for its second.

=== Minimization ===
<math>M^k(f)(x_1, ..., x_k) \triangleq \min \{i \in \N: f(i, x_1, ..., x_k) = 0\}</math>

In computational language, when ''M(f)'' is evaluated it can be considered to calculate <math>f(i, x_1, ..., x_k)</math> with <math>i=0</math>, then <math>i=1</math>, then <math>i=2</math> etc. until one of the calls to <math>f</math> returns 0. It returns the value of <math>i</math> which first gave a result of 0. If no first argument causes <math>f</math> to return 0, <math>M(f)</math> 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 <math>f \in GRF_1</math>
{| class="wikitable"
|+
!
!Macro
!arity
!Definition
!Size
!Function
|-
|Plus constant
|<math>Plus[n]</math>
|1
|<math>\begin{array}{lcl}
Plus[1] & := & S \\
Plus[n+1] & := & C(S, Plus[n])
\end{array}</math>
|<math>2n-1</math>
|<math>\lambda x. x+n</math>
|-
|Constant
|<math>K^k[n]</math>
|k
|<math>\begin{array}{lcl}
K^k[0] & := & Z^k \\
K^k[n] & := & C(Plus[n], Z^k)
\end{array}</math>
|<math>2n+1</math>
|<math>\lambda x_1 \dots x_k. n</math>
|-
|Iteration
|<math>Rep[f,n]</math>
|1
|<math>Rep[f,n] := R(K^0[n], C(f, P^2_2))</math>
|<math>|f| + 2n + 4</math>
|<math>\lambda x. f^x(n)</math>
|-
|Iteration of successor
|<math>RepSucc[f]</math>
|2
|<math>RepSucc[f] := R(S, C(f, P^3_2))</math>
|<math>|f| + 4</math>
|<math>\lambda x\ y. f^x(y+1)</math>
|-
|Diagonalization
|<math>RepDiag[f]</math>
|1
|<math>RepDiag[f] := C(RepSucc[f], S, S)</math>
|<math>|f| + 7</math>
|<math>\lambda x. f^{x+1}(x+2)</math>
|-
|Ackermann iteration
|<math>Ack[n,f]</math>
|1
|<math>\begin{array}{lcl}
Ack[0,f] & := & f \\
Ack[n+1,f] & := & Rep[Ack[n,f],1]
\end{array}</math>
|<math>6n + |f|</math>
|
|-
|Knuth base 2 up-arrows
|<math>Knuth2[n]</math>
|1
|<math>\begin{array}{lcl}
Knuth2[0] & := & Rep[Plus[2],0] \\
Knuth2[n+1] & := & Rep[Knuth2[n],1]
\end{array}</math>
|<math>6n+7</math>
|<math>\lambda x. 2 \uparrow^n x</math>
|-
|Ackermann Diagonalization
on Triangular nums
|<math>ADT[n]</math>
|1
|<math>\begin{array}{lcl}
ADT[0] & := & Tri \\
ADT[n+1] & := & RepDiag[ADT[n]]
\end{array}</math>
|<math>7n + 7</math>
|<math>\lambda x. > 10 \uparrow^n (x+1)</math>
|-
|Polygonal
|<math>Poly[n]</math>
|1
|<math>Poly[n] := R(Z^0, R(S, C(Plus[n], P^3_2)))</math>
|<math>2n+5</math>
|<math>\lambda x. \frac{n}{2} x(x-1) + x</math>
|-
|
|<math>Tri</math>
|1
|<math>Tri := Poly[1] = R(Z^0, R(S, C(S, P^3_2)))</math>
|<math>7</math>
|<math>\lambda x. \frac{x(x+1)}{2}</math>
|-
|
|<math>Square</math>
|1
|<math>Square := Poly[2]</math>
|<math>9</math>
|<math>\lambda x. x^2</math>
|}

== Champions ==
{| class="wikitable"
!n
!BBµ(n)
!Champion
!Champion Found
!Holdouts Proven
|-
|1
|= 0
|<math>Z^0</math>
|
|Shawn Ligocki [https://discord.com/channels/960643023006490684/1447627603698647303/1447693296322215976 8 Dec 2025] By hand
|-
|2
|= 0
|<math>M(Z^1), M(P^1_1), C(Z^0)</math>
|
|Shawn Ligocki [https://discord.com/channels/960643023006490684/1447627603698647303/1447693296322215976 8 Dec 2025] By hand
|-
|3
|= 1
|<math>K^0[1]</math>
|
|Shawn Ligocki [https://discord.com/channels/960643023006490684/1447627603698647303/1447693296322215976 8 Dec 2025] By hand
|-
|4
|= 1
|<math>C^0(K^0[1])</math>
|
|Jacob Mandelson [https://mandelson.org/grf/ 3 Apr 2026]
|-
|5
|= 2
|<math>K^0[2]</math>
|
|Jacob Mandelson [https://mandelson.org/grf/ 3 Apr 2026]
|-
|6
|= 2
|<math>C^0(K^0[2])</math>
|
|Jacob Mandelson [https://mandelson.org/grf/ 3 Apr 2026]
|-
|7
|= 3
|<math>K^0[3]</math>
|
|Jacob Mandelson [https://mandelson.org/grf/ 3 Apr 2026]
|-
|9
|≥ 4
|<math>K^0[4]</math>
|
|
|-
|11
|≥ 5
|<math>K^0[5]</math>
|
|
|-
|13
|≥ 6
|<math>K^0[6]</math>
|
|
|-
|14
|≥ 7
|<math>C(RepDiag[S], K^0[2])</math>
|Shawn Ligocki [https://discord.com/channels/960643023006490684/1447627603698647303/1492246885329670184 10 Apr 2026]
|
|-
|16
|≥ 9
|<math>C(RepDiag[S], K^0[3])</math>
|Shawn Ligocki [https://discord.com/channels/960643023006490684/1447627603698647303/1492246885329670184 10 Apr 2026]
|
|-
|17
|≥ 10
|<math>C(Tri, K^0[4])</math>
|Shawn Ligocki 9 Dec 2025
|
|-
|18
|≥ 21
|<math>C(RepDiag[Tri], K^0[1])</math>
|Jacob Mandelson [https://discord.com/channels/960643023006490684/1447627603698647303/1492021428546179182 9 Apr 2026]
|
|-
|20
|≥ 1540
|<math>C(RepDiag[Tri], K^0[2])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|22
|≥ 26'357'430
|<math>C(RepDiag[Tri], K^0[3])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|24
|≥ 64'449'908'476'890'321 > 1016.8
|<math>C(RepDiag[Tri], K^0[4])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|25
|<math> > 10^{10^{10^{6.899}}} > 10 \uparrow\uparrow 3.8388</math>
|<math>C(ADT[2], K^0[1])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|27
|> <math>10 \uparrow\uparrow 6.0834</math>
|<math>C(ADT[2], K^0[2])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|29
|> <math>10 \uparrow\uparrow 8.1944</math>
|<math>C(ADT[2], K^0[3])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|31
|> <math>10 \uparrow\uparrow 10.2800</math>
|<math>C(ADT[2], K^0[4])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|32
|> <math>10 \uparrow\uparrow 10 \uparrow\uparrow 8.1944</math>
|<math>C(ADT[3], K^0[1])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|34
|> <math>10 \uparrow\uparrow\uparrow 4</math>
|<math>C(ADT[3], K^0[2])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|36
|> <math>10 \uparrow\uparrow\uparrow 5</math>
|<math>C(ADT[3], K^0[3])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|38
|> <math>10 \uparrow\uparrow\uparrow 6</math>
|<math>C(ADT[3], K^0[4])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|
|
|
|
|
|-
|7k+11
|> <math>10 \uparrow^k 2</math>
|<math>C(ADT[k], K^0[1])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|7k+13
|> <math>10 \uparrow^k 3</math>
|<math>C(ADT[k], K^0[2])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|7k+15
|> <math>10 \uparrow^k 4</math>
|<math>C(ADT[k], K^0[3])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|7k+17
|> <math>10 \uparrow^k 5</math>
|<math>C(ADT[k], K^0[4])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|
|
|
|
|
|-
|6k+17
|<math>\ge 2 \uparrow^k 4</math>
|<math>C(Knuth2[k], K^0[4])</math>
|Shawn Ligocki [https://discord.com/channels/960643023006490684/1447627603698647303/1447633458510692385 8 Dec 2025]
|
|-
|6k+19
|<math>\ge 2 \uparrow^k 5</math>
|<math>C(Knuth2[k], K^0[5])</math>
|Shawn Ligocki [https://discord.com/channels/960643023006490684/1447627603698647303/1447633458510692385 8 Dec 2025]
|
|-
|6k+21
|<math>\ge 2 \uparrow^k 6</math>
|<math>C(Knuth2[k], K^0[6])</math>
|Shawn Ligocki [https://discord.com/channels/960643023006490684/1447627603698647303/1447633458510692385 8 Dec 2025]
|
|}

== Macro Bounds ==

=== ADT[k] ===

* <math>ADT[0](n) = Tri(n) = \frac{n(n+1)}{2} > \frac{1}{2} n^2</math>
* <math>ADT[0]^k(n) > 2 \left( \frac{n}{2} \right)^{2^k}</math>
* <math>ADT[1](n) = Tri^{n+1}(n+2) > 2 \left(\frac{n+2}{2} \right)^{2^{n+1}} = 2 \left(\frac{(n+2)^2}{4} \right)^{2^n} > A 10^{10^{n/A}}</math> where <math>A = \frac{1}{\log_{10}(2)}</math> (if <math>n \ge 5</math>, for smaller values, this can be calculated directly)
* <math>ADT[1]^k(n) > A (10 \uparrow)^{2k} \frac{n}{A} > 10 \uparrow\uparrow 2k</math> (if <math>n \ge 4</math>)
* <math>ADT[2](n) = ADT[1]^{n+1}(n+2) > 10 \uparrow\uparrow (2n+2) </math> (if <math>n \ge 2</math>)
* <math>ADT[k](n) > 10 \uparrow^k (n+1) </math> (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: <math>BB\mu(6k+17) \ge 2 \uparrow^k 4</math>.

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 [[wikipedia:Pairing_function|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, [[wikipedia:Common_subexpression_elimination|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:
{| class="wikitable"
|+Smallest Pairing Functions
!Macro
!arity
!Definition
!Size
!Function
|-
|<math>Pair</math>
|2
|<math>Pair := C(AddS, C(Tri, Add), P^2_1)</math>
|20
|<math>\lambda xy. \frac{(x+y)(x+y+1)}{2} + x + 1</math>
|-
|<math>Left</math>
|1
|<math>Left := C(RMonus, C(TriP, InvTriCeil), Pred)</math>
|38
|<math>Left(Pair(x,y)) = x</math>
|-
|<math>Right</math>
|1
|<math>Right := C(RMonus, P^1_1, C(Tri, InvTriCeil))</math>
|36
|<math>Right(Pair(x,y)) = y</math>
|-
|<math>LRCall[f^2]</math>
|1
|<math>LRCall[f] := C(LRpart3[f], InvTriCeil, P^1_1)</math>
|<math>61 + |f|</math>
|<math>LRCall[f](Pair(x,y)) = f(x,y)</math>
|}
Where these are based on the following definitions:
{| class="wikitable"
|+Macros
!
!Macro
!arity
!Definition
!Size
!Function
|-
| rowspan="2" |Addition
|Add
|2
|<math>Add := R(P^1_1, C(S, P^3_2))</math>
|5
|<math>\lambda xy. x+y</math>
|-
|AddS
|2
|<math>AddS := R(S, C(S, P^3_2))</math>
|5
|<math>\lambda xy. x+y+1</math>
|-
|[[wikipedia:Primitive_recursive_function#Predecessor|Predecesor]]
|Pred
|1
|<math>Pred := R(Z^0, P^2_1)</math>
|3
|<math>\lambda x. x \dot - 1</math>
|-
|[[wikipedia:Monus#Natural_numbers|Monus]]
|RMonus
|2
|<math>RMonus := R(P^1_1, C(Pred, P^3_2))</math>
|7
|<math>\lambda xy. y \dot - x</math>
|-
| rowspan="2" |Triangular numbers
|Tri
|1
|<math>Tri := R(Z^0, AddS)</math>
|7
|<math>\lambda x. \frac{x(x+1)}{2}</math>
|-
|TriP
|1
|<math>TriP := R(Z^0, Add)</math>
|7
|<math>TriP(x+1) = Tri(x)</math>
|-
| rowspan="2" |Inverting Tri
|RMonusTri
|2
|<math>RMonusTri := C(RMonus, C(Tri, P^2_1), P^2_2)</math>
|18
|<math>\lambda xy. y \dot - Tri(x)</math>
|-
|InvTriCeil
|1
|<math>InvTriCeil := M(RMonusTri)</math>
|19
|<math>\lambda y. \min \{x | Tri(x) \ge y \}</math>
|-
| rowspan="5" | Combined LRCall
|RightPiece
|3
|<math>RightPiece := R(P^2_2, C(Pred, P^4_2))</math>
|7
|<math>\lambda xyz. z \dot - x</math>
|-
|LeftPiece
|3
|<math>LeftPiece := C(RMonus, C(S, P^3_2), P^3_1)</math>
|12
|<math>\lambda xyz. x \dot - (y+1)</math>
|-
|LRpart1[f]
|3
|<math>LRpart1[f] := C(f, LeftPiece, RightPiece)</math>
|<math>20 + |f|</math>
|<math>\lambda xyz. f(x \dot - (y+1), z \dot - x)</math>
|-
|LRPart2[f]
|3
|<math>LRpart2[f] := C(LRpart1[f], P^3_3, P^3_1, R(P^2_1, C(S, P^4_2)))</math>
|<math>28 + |f|</math>
|<math>\lambda xyz. LRpart1[f](z, x, x+y)</math>
|-
|LRpart3[f]
|2
|<math>LRpart3[f] := C(LRpart2[f], C(TriP, P^2_1), P^2_1, P^2_2)</math>
|<math>40 + |f|</math>
|<math>\lambda xy. LRpart2[f](TriP(x), x, y)</math>
|}

[[Category:functions]]

General Recursive Function

2026-04-11T04:46:06Z

JLM: /* Utilizing Minimization */ Mention technique for creating LRCall.

'''General recursive functions''' ('''GRFs'''), also called '''µ-recursive functions''' or '''partial recursive functions''', are the collection of [[Wikipedia:partial functions|partial functions]] <math>\N^k \rightharpoonup \N</math> 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 <math>\N^k \rightharpoonup \N</math> 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:<math display="block">BB \mu (n) = \max \{ f() | f \in \text{GRF}_0 , |f| = n \}</math>

where <math>f \in GRF_k</math> means that <math>f: \N^k \rightharpoonup \N</math> is a k-ary GRF and <math>|f|</math> 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 <math>GRF_k</math> inductively based on the following construction rules, start with Atoms and combine them using Combinators.

====== Atoms ======

* Zero: <math>\forall k \in \N, Z^k \in GRF_k</math> is the constant 0 function <math>Z^k(x_1, \dots, x_k) = 0</math>
* Successor: <math>S \in GRF_1</math> is the successor function <math>S(x) = x+1</math>
* Projection: <math>\forall 1 \le i \le k \in \N, P^k_i \in GRF_k</math> is a projection function <math>P^k_i(x_1, \dots x_k) = x_i</math>

===== Combinators =====

* Composition: <math>\forall k,m \in \N, \forall h \in GRF_m, \forall g_1, \dots g_m \in GRF_k, C(h, g_1, \dots g_m) \in GRF_k</math> is the composition or substitution of the ''g''s into ''h'': <math>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))</math>
* Primitive Recursion: <math>\forall k \in \N, \forall g \in GRF_k, \forall h \in GRF_{k+2}, R(g, h) \in GRF_{k+1}</math> is primitive recursion using ''g'' as the base case and ''h'' as the inductive step.
* Minimization / Unlimited Search: <math>\forall k \in \N, \forall f \in GRF_{k+1}, M(f) \in GRF_k</math> is the µ-operator which allows unlimited search.

=== Primitive Recursion ===
<math>R</math> models a typical iterative function definition over ℕ.

Base case: <math>R^k(g, h)(0, x_2, x_3, ..., x_k) = g(x_2, x_3, ..., x_k)</math>

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

<math>R</math> 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 <math>g</math>), then 1, 2, 3, etc. until <math>x_1</math> is reached, each time calling <math>h</math> with the prior iteration count for its first argument and the result of the prior call for its second.

=== Minimization ===
<math>M^k(f)(x_1, ..., x_k) \triangleq \min \{i \in \N: f(i, x_1, ..., x_k) = 0\}</math>

In computational language, when ''M(f)'' is evaluated it can be considered to calculate <math>f(i, x_1, ..., x_k)</math> with <math>i=0</math>, then <math>i=1</math>, then <math>i=2</math> etc. until one of the calls to <math>f</math> returns 0. It returns the value of <math>i</math> which first gave a result of 0. If no first argument causes <math>f</math> to return 0, <math>M(f)</math> 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 <math>f \in GRF_1</math>
{| class="wikitable"
|+
!
!Macro
!arity
!Definition
!Size
!Function
|-
|Plus constant
|<math>Plus[n]</math>
|1
|<math>\begin{array}{lcl}
Plus[1] & := & S \\
Plus[n+1] & := & C(S, Plus[n])
\end{array}</math>
|<math>2n-1</math>
|<math>\lambda x. x+n</math>
|-
|Constant
|<math>K^k[n]</math>
|k
|<math>\begin{array}{lcl}
K^k[0] & := & Z^k \\
K^k[n] & := & C(Plus[n], Z^k)
\end{array}</math>
|<math>2n+1</math>
|<math>\lambda x_1 \dots x_k. n</math>
|-
|Iteration
|<math>Rep[f,n]</math>
|1
|<math>Rep[f,n] := R(K^0[n], C(f, P^2_2))</math>
|<math>|f| + 2n + 4</math>
|<math>\lambda x. f^x(n)</math>
|-
|Iteration of successor
|<math>RepSucc[f]</math>
|2
|<math>RepSucc[f] := R(S, C(f, P^3_2))</math>
|<math>|f| + 4</math>
|<math>\lambda x\ y. f^x(y+1)</math>
|-
|Diagonalization
|<math>RepDiag[f]</math>
|1
|<math>RepDiag[f] := C(RepSucc[f], S, S)</math>
|<math>|f| + 7</math>
|<math>\lambda x. f^{x+1}(x+2)</math>
|-
|Ackermann iteration
|<math>Ack[n,f]</math>
|1
|<math>\begin{array}{lcl}
Ack[0,f] & := & f \\
Ack[n+1,f] & := & Rep[Ack[n,f],1]
\end{array}</math>
|<math>6n + |f|</math>
|
|-
|Knuth base 2 up-arrows
|<math>Knuth2[n]</math>
|1
|<math>\begin{array}{lcl}
Knuth2[0] & := & Rep[Plus[2],0] \\
Knuth2[n+1] & := & Rep[Knuth2[n],1]
\end{array}</math>
|<math>6n+7</math>
|<math>\lambda x. 2 \uparrow^n x</math>
|-
|Ackermann Diagonalization
on Triangular nums
|<math>ADT[n]</math>
|1
|<math>\begin{array}{lcl}
ADT[0] & := & Tri \\
ADT[n+1] & := & RepDiag[ADT[n]]
\end{array}</math>
|<math>7n + 7</math>
|<math>\lambda x. > 10 \uparrow^n (x+1)</math>
|-
|Polygonal
|<math>Poly[n]</math>
|1
|<math>Poly[n] := R(Z^0, R(S, C(Plus[n], P^3_2)))</math>
|<math>2n+5</math>
|<math>\lambda x. \frac{n}{2} x(x-1) + x</math>
|-
|
|<math>Tri</math>
|1
|<math>Tri := Poly[1] = R(Z^0, R(S, C(S, P^3_2)))</math>
|<math>7</math>
|<math>\lambda x. \frac{x(x+1)}{2}</math>
|-
|
|<math>Square</math>
|1
|<math>Square := Poly[2]</math>
|<math>9</math>
|<math>\lambda x. x^2</math>
|}

== Champions ==
{| class="wikitable"
!n
!BBµ(n)
!Champion
!Champion Found
!Holdouts Proven
|-
|1
|= 0
|<math>Z^0</math>
|
|Shawn Ligocki [https://discord.com/channels/960643023006490684/1447627603698647303/1447693296322215976 8 Dec 2025] By hand
|-
|2
|= 0
|<math>M(Z^1), M(P^1_1), C(Z^0)</math>
|
|Shawn Ligocki [https://discord.com/channels/960643023006490684/1447627603698647303/1447693296322215976 8 Dec 2025] By hand
|-
|3
|= 1
|<math>K^0[1]</math>
|
|Shawn Ligocki [https://discord.com/channels/960643023006490684/1447627603698647303/1447693296322215976 8 Dec 2025] By hand
|-
|4
|= 1
|<math>C^0(K^0[1])</math>
|
|Jacob Mandelson [https://mandelson.org/grf/ 3 Apr 2026]
|-
|5
|= 2
|<math>K^0[2]</math>
|
|Jacob Mandelson [https://mandelson.org/grf/ 3 Apr 2026]
|-
|6
|= 2
|<math>C^0(K^0[2])</math>
|
|Jacob Mandelson [https://mandelson.org/grf/ 3 Apr 2026]
|-
|7
|= 3
|<math>K^0[3]</math>
|
|Jacob Mandelson [https://mandelson.org/grf/ 3 Apr 2026]
|-
|9
|≥ 4
|<math>K^0[4]</math>
|
|
|-
|11
|≥ 5
|<math>K^0[5]</math>
|
|
|-
|13
|≥ 6
|<math>K^0[6]</math>
|
|
|-
|14
|≥ 7
|<math>C(RepDiag[S], K^0[2])</math>
|Shawn Ligocki [https://discord.com/channels/960643023006490684/1447627603698647303/1492246885329670184 10 Apr 2026]
|
|-
|16
|≥ 9
|<math>C(RepDiag[S], K^0[3])</math>
|Shawn Ligocki [https://discord.com/channels/960643023006490684/1447627603698647303/1492246885329670184 10 Apr 2026]
|
|-
|17
|≥ 10
|<math>C(Tri, K^0[4])</math>
|Shawn Ligocki 9 Dec 2025
|
|-
|18
|≥ 21
|<math>C(RepDiag[Tri], K^0[1])</math>
|Jacob Mandelson [https://discord.com/channels/960643023006490684/1447627603698647303/1492021428546179182 9 Apr 2026]
|
|-
|20
|≥ 1540
|<math>C(RepDiag[Tri], K^0[2])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|22
|≥ 26'357'430
|<math>C(RepDiag[Tri], K^0[3])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|24
|≥ 64'449'908'476'890'321 > 1016.8
|<math>C(RepDiag[Tri], K^0[4])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|25
|<math> > 10^{10^{10^{6.899}}} > 10 \uparrow\uparrow 3.8388</math>
|<math>C(ADT[2], K^0[1])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|27
|> <math>10 \uparrow\uparrow 6.0834</math>
|<math>C(ADT[2], K^0[2])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|29
|> <math>10 \uparrow\uparrow 8.1944</math>
|<math>C(ADT[2], K^0[3])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|31
|> <math>10 \uparrow\uparrow 10.2800</math>
|<math>C(ADT[2], K^0[4])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|32
|> <math>10 \uparrow\uparrow 10 \uparrow\uparrow 8.1944</math>
|<math>C(ADT[3], K^0[1])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|34
|> <math>10 \uparrow\uparrow\uparrow 4</math>
|<math>C(ADT[3], K^0[2])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|36
|> <math>10 \uparrow\uparrow\uparrow 5</math>
|<math>C(ADT[3], K^0[3])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|38
|> <math>10 \uparrow\uparrow\uparrow 6</math>
|<math>C(ADT[3], K^0[4])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|
|
|
|
|
|-
|7k+11
|> <math>10 \uparrow^k 2</math>
|<math>C(ADT[k], K^0[1])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|7k+13
|> <math>10 \uparrow^k 3</math>
|<math>C(ADT[k], K^0[2])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|7k+15
|> <math>10 \uparrow^k 4</math>
|<math>C(ADT[k], K^0[3])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|7k+17
|> <math>10 \uparrow^k 5</math>
|<math>C(ADT[k], K^0[4])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|
|
|
|
|
|-
|6k+17
|<math>\ge 2 \uparrow^k 4</math>
|<math>C(Knuth2[k], K^0[4])</math>
|Shawn Ligocki [https://discord.com/channels/960643023006490684/1447627603698647303/1447633458510692385 8 Dec 2025]
|
|-
|6k+19
|<math>\ge 2 \uparrow^k 5</math>
|<math>C(Knuth2[k], K^0[5])</math>
|Shawn Ligocki [https://discord.com/channels/960643023006490684/1447627603698647303/1447633458510692385 8 Dec 2025]
|
|-
|6k+21
|<math>\ge 2 \uparrow^k 6</math>
|<math>C(Knuth2[k], K^0[6])</math>
|Shawn Ligocki [https://discord.com/channels/960643023006490684/1447627603698647303/1447633458510692385 8 Dec 2025]
|
|}

== Macro Bounds ==

=== ADT[k] ===

* <math>ADT[0](n) = Tri(n) = \frac{n(n+1)}{2} > \frac{1}{2} n^2</math>
* <math>ADT[0]^k(n) > 2 \left( \frac{n}{2} \right)^{2^k}</math>
* <math>ADT[1](n) = Tri^{n+1}(n+2) > 2 \left(\frac{n+2}{2} \right)^{2^{n+1}} = 2 \left(\frac{(n+2)^2}{4} \right)^{2^n} > A 10^{10^{n/A}}</math> where <math>A = \frac{1}{\log_{10}(2)}</math> (if <math>n \ge 5</math>, for smaller values, this can be calculated directly)
* <math>ADT[1]^k(n) > A (10 \uparrow)^{2k} \frac{n}{A} > 10 \uparrow\uparrow 2k</math> (if <math>n \ge 4</math>)
* <math>ADT[2](n) = ADT[1]^{n+1}(n+2) > 10 \uparrow\uparrow (2n+2) </math> (if <math>n \ge 2</math>)
* <math>ADT[k](n) > 10 \uparrow^k (n+1) </math> (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: <math>BB\mu(6k+17) \ge 2 \uparrow^k 4</math>.

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 [[wikipedia:Pairing_function|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, [[wikipedia:Common_subexpression_elimination|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:
{| class="wikitable"
|+Smallest Pairing Functions
!Macro
!arity
!Definition
!Size
!Function
|-
|<math>Pair</math>
|2
|<math>Pair := C(AddS, C(Tri, Add), P^2_1)</math>
|20
|<math>\lambda xy. \frac{(x+y)(x+y+1)}{2} + x + 1</math>
|-
|<math>Left</math>
|1
|<math>Left := C(RMonus, C(TriP, InvTriCeil), Pred)</math>
|38
|<math>Left(Pair(x,y)) = x</math>
|-
|<math>Right</math>
|1
|<math>Right := C(RMonus, P^1_1, C(Tri, InvTriCeil))</math>
|36
|<math>Right(Pair(x,y)) = y</math>
|-
|<math>LRCall[f^2]</math>
|1
|<math>LRCall[f] := C(LRpart3[f], InvTriCeil, P^1_1)</math>
|<math>61 + |f|</math>
|<math>LRCall[f](Pair(x,y)) = f(x,y)</math>
|}
Where these are based on the following definitions:
{| class="wikitable"
|+Macros
!
!Macro
!arity
!Definition
!Size
!Function
|-
| rowspan="2" |Addition
|Add
|2
|<math>Add := R(P^1_1, C(S, P^3_2))</math>
|5
|<math>\lambda xy. x+y</math>
|-
|AddS
|2
|<math>AddS := R(S, C(S, P^3_2))</math>
|5
|<math>\lambda xy. x+y+1</math>
|-
|[[wikipedia:Primitive_recursive_function#Predecessor|Predecesor]]
|Pred
|1
|<math>Pred := R(Z^0, P^2_1)</math>
|3
|<math>\lambda x. x \dot - 1</math>
|-
|[[wikipedia:Monus#Natural_numbers|Monus]]
|RMonus
|2
|<math>RMonus := R(P^1_1, C(Pred, P^3_2))</math>
|7
|<math>\lambda xy. y \dot - x</math>
|-
| rowspan="2" |Triangular numbers
|Tri
|1
|<math>Tri := R(Z^0, AddS)</math>
|7
|<math>\lambda x. \frac{x(x+1)}{2}</math>
|-
|TriP
|1
|<math>TriP := R(Z^0, Add)</math>
|7
|<math>TriP(x+1) = Tri(x)</math>
|-
| rowspan="2" |Inverting Tri
|RMonusTri
|2
|<math>RMonusTri := C(RMonus, C(Tri, P^2_1), P^2_2)</math>
|18
|<math>\lambda xy. y \dot - Tri(x)</math>
|-
|InvTriCeil
|1
|<math>InvTriCeil := M(RMonusTri)</math>
|19
|<math>\lambda y. \min \{x | Tri(x) \ge y \}</math>
|-
| rowspan="5" | Combined LRCall
|RightPiece
|3
|<math>RightPiece := R(P^2_2, C(Pred, P^4_2))</math>
|7
|<math>\lambda xyz. z \dot - x</math>
|-
|LeftPiece
|3
|<math>LeftPiece := C(RMonus, C(S, P^3_2), P^3_1)</math>
|12
|<math>\lambda xyz. x \dot - (y+1)</math>
|-
|LRpart1[f]
|3
|<math>LRpart1[f] := C(f, LeftPiece, RightPiece)</math>
|<math>20 + |f|</math>
|<math>\lambda xyz. f(LeftPiece(x,y,z), RightPiece(x,y,z))</math>
|-
|LRPart2[f]
|3
|<math>LRpart2[f] := C(LRpart1[f], P^3_3, P^3_1, R(P^2_1, C(S, P^4_2)))</math>
|<math>28 + |f|</math>
|<math>\lambda xyz. LRpart1[f](z, x, x+y)</math>
|-
|LRpart3[f]
|2
|<math>LRpart3[f] := C(LRpart2[f], C(TriP, P^2_1), P^2_1, P^2_2)</math>
|<math>40 + |f|</math>
|<math>\lambda xy. LRpart2[f](TriP(x), x, y)</math>
|}

[[Category:functions]]

General Recursive Function

2026-04-11T04:37:46Z

JLM: /* Utilizing Minimization */ Define macros for combined Left+Right function calls

'''General recursive functions''' ('''GRFs'''), also called '''µ-recursive functions''' or '''partial recursive functions''', are the collection of [[Wikipedia:partial functions|partial functions]] <math>\N^k \rightharpoonup \N</math> 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 <math>\N^k \rightharpoonup \N</math> 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:<math display="block">BB \mu (n) = \max \{ f() | f \in \text{GRF}_0 , |f| = n \}</math>

where <math>f \in GRF_k</math> means that <math>f: \N^k \rightharpoonup \N</math> is a k-ary GRF and <math>|f|</math> 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 <math>GRF_k</math> inductively based on the following construction rules, start with Atoms and combine them using Combinators.

====== Atoms ======

* Zero: <math>\forall k \in \N, Z^k \in GRF_k</math> is the constant 0 function <math>Z^k(x_1, \dots, x_k) = 0</math>
* Successor: <math>S \in GRF_1</math> is the successor function <math>S(x) = x+1</math>
* Projection: <math>\forall 1 \le i \le k \in \N, P^k_i \in GRF_k</math> is a projection function <math>P^k_i(x_1, \dots x_k) = x_i</math>

===== Combinators =====

* Composition: <math>\forall k,m \in \N, \forall h \in GRF_m, \forall g_1, \dots g_m \in GRF_k, C(h, g_1, \dots g_m) \in GRF_k</math> is the composition or substitution of the ''g''s into ''h'': <math>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))</math>
* Primitive Recursion: <math>\forall k \in \N, \forall g \in GRF_k, \forall h \in GRF_{k+2}, R(g, h) \in GRF_{k+1}</math> is primitive recursion using ''g'' as the base case and ''h'' as the inductive step.
* Minimization / Unlimited Search: <math>\forall k \in \N, \forall f \in GRF_{k+1}, M(f) \in GRF_k</math> is the µ-operator which allows unlimited search.

=== Primitive Recursion ===
<math>R</math> models a typical iterative function definition over ℕ.

Base case: <math>R^k(g, h)(0, x_2, x_3, ..., x_k) = g(x_2, x_3, ..., x_k)</math>

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

<math>R</math> 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 <math>g</math>), then 1, 2, 3, etc. until <math>x_1</math> is reached, each time calling <math>h</math> with the prior iteration count for its first argument and the result of the prior call for its second.

=== Minimization ===
<math>M^k(f)(x_1, ..., x_k) \triangleq \min \{i \in \N: f(i, x_1, ..., x_k) = 0\}</math>

In computational language, when ''M(f)'' is evaluated it can be considered to calculate <math>f(i, x_1, ..., x_k)</math> with <math>i=0</math>, then <math>i=1</math>, then <math>i=2</math> etc. until one of the calls to <math>f</math> returns 0. It returns the value of <math>i</math> which first gave a result of 0. If no first argument causes <math>f</math> to return 0, <math>M(f)</math> 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 <math>f \in GRF_1</math>
{| class="wikitable"
|+
!
!Macro
!arity
!Definition
!Size
!Function
|-
|Plus constant
|<math>Plus[n]</math>
|1
|<math>\begin{array}{lcl}
Plus[1] & := & S \\
Plus[n+1] & := & C(S, Plus[n])
\end{array}</math>
|<math>2n-1</math>
|<math>\lambda x. x+n</math>
|-
|Constant
|<math>K^k[n]</math>
|k
|<math>\begin{array}{lcl}
K^k[0] & := & Z^k \\
K^k[n] & := & C(Plus[n], Z^k)
\end{array}</math>
|<math>2n+1</math>
|<math>\lambda x_1 \dots x_k. n</math>
|-
|Iteration
|<math>Rep[f,n]</math>
|1
|<math>Rep[f,n] := R(K^0[n], C(f, P^2_2))</math>
|<math>|f| + 2n + 4</math>
|<math>\lambda x. f^x(n)</math>
|-
|Iteration of successor
|<math>RepSucc[f]</math>
|2
|<math>RepSucc[f] := R(S, C(f, P^3_2))</math>
|<math>|f| + 4</math>
|<math>\lambda x\ y. f^x(y+1)</math>
|-
|Diagonalization
|<math>RepDiag[f]</math>
|1
|<math>RepDiag[f] := C(RepSucc[f], S, S)</math>
|<math>|f| + 7</math>
|<math>\lambda x. f^{x+1}(x+2)</math>
|-
|Ackermann iteration
|<math>Ack[n,f]</math>
|1
|<math>\begin{array}{lcl}
Ack[0,f] & := & f \\
Ack[n+1,f] & := & Rep[Ack[n,f],1]
\end{array}</math>
|<math>6n + |f|</math>
|
|-
|Knuth base 2 up-arrows
|<math>Knuth2[n]</math>
|1
|<math>\begin{array}{lcl}
Knuth2[0] & := & Rep[Plus[2],0] \\
Knuth2[n+1] & := & Rep[Knuth2[n],1]
\end{array}</math>
|<math>6n+7</math>
|<math>\lambda x. 2 \uparrow^n x</math>
|-
|Ackermann Diagonalization
on Triangular nums
|<math>ADT[n]</math>
|1
|<math>\begin{array}{lcl}
ADT[0] & := & Tri \\
ADT[n+1] & := & RepDiag[ADT[n]]
\end{array}</math>
|<math>7n + 7</math>
|<math>\lambda x. > 10 \uparrow^n (x+1)</math>
|-
|Polygonal
|<math>Poly[n]</math>
|1
|<math>Poly[n] := R(Z^0, R(S, C(Plus[n], P^3_2)))</math>
|<math>2n+5</math>
|<math>\lambda x. \frac{n}{2} x(x-1) + x</math>
|-
|
|<math>Tri</math>
|1
|<math>Tri := Poly[1] = R(Z^0, R(S, C(S, P^3_2)))</math>
|<math>7</math>
|<math>\lambda x. \frac{x(x+1)}{2}</math>
|-
|
|<math>Square</math>
|1
|<math>Square := Poly[2]</math>
|<math>9</math>
|<math>\lambda x. x^2</math>
|}

== Champions ==
{| class="wikitable"
!n
!BBµ(n)
!Champion
!Champion Found
!Holdouts Proven
|-
|1
|= 0
|<math>Z^0</math>
|
|Shawn Ligocki [https://discord.com/channels/960643023006490684/1447627603698647303/1447693296322215976 8 Dec 2025] By hand
|-
|2
|= 0
|<math>M(Z^1), M(P^1_1), C(Z^0)</math>
|
|Shawn Ligocki [https://discord.com/channels/960643023006490684/1447627603698647303/1447693296322215976 8 Dec 2025] By hand
|-
|3
|= 1
|<math>K^0[1]</math>
|
|Shawn Ligocki [https://discord.com/channels/960643023006490684/1447627603698647303/1447693296322215976 8 Dec 2025] By hand
|-
|4
|= 1
|<math>C^0(K^0[1])</math>
|
|Jacob Mandelson [https://mandelson.org/grf/ 3 Apr 2026]
|-
|5
|= 2
|<math>K^0[2]</math>
|
|Jacob Mandelson [https://mandelson.org/grf/ 3 Apr 2026]
|-
|6
|= 2
|<math>C^0(K^0[2])</math>
|
|Jacob Mandelson [https://mandelson.org/grf/ 3 Apr 2026]
|-
|7
|= 3
|<math>K^0[3]</math>
|
|Jacob Mandelson [https://mandelson.org/grf/ 3 Apr 2026]
|-
|9
|≥ 4
|<math>K^0[4]</math>
|
|
|-
|11
|≥ 5
|<math>K^0[5]</math>
|
|
|-
|13
|≥ 6
|<math>K^0[6]</math>
|
|
|-
|14
|≥ 7
|<math>C(RepDiag[S], K^0[2])</math>
|Shawn Ligocki [https://discord.com/channels/960643023006490684/1447627603698647303/1492246885329670184 10 Apr 2026]
|
|-
|16
|≥ 9
|<math>C(RepDiag[S], K^0[3])</math>
|Shawn Ligocki [https://discord.com/channels/960643023006490684/1447627603698647303/1492246885329670184 10 Apr 2026]
|
|-
|17
|≥ 10
|<math>C(Tri, K^0[4])</math>
|Shawn Ligocki 9 Dec 2025
|
|-
|18
|≥ 21
|<math>C(RepDiag[Tri], K^0[1])</math>
|Jacob Mandelson [https://discord.com/channels/960643023006490684/1447627603698647303/1492021428546179182 9 Apr 2026]
|
|-
|20
|≥ 1540
|<math>C(RepDiag[Tri], K^0[2])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|22
|≥ 26'357'430
|<math>C(RepDiag[Tri], K^0[3])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|24
|≥ 64'449'908'476'890'321 > 1016.8
|<math>C(RepDiag[Tri], K^0[4])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|25
|<math> > 10^{10^{10^{6.899}}} > 10 \uparrow\uparrow 3.8388</math>
|<math>C(ADT[2], K^0[1])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|27
|> <math>10 \uparrow\uparrow 6.0834</math>
|<math>C(ADT[2], K^0[2])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|29
|> <math>10 \uparrow\uparrow 8.1944</math>
|<math>C(ADT[2], K^0[3])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|31
|> <math>10 \uparrow\uparrow 10.2800</math>
|<math>C(ADT[2], K^0[4])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|32
|> <math>10 \uparrow\uparrow 10 \uparrow\uparrow 8.1944</math>
|<math>C(ADT[3], K^0[1])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|34
|> <math>10 \uparrow\uparrow\uparrow 4</math>
|<math>C(ADT[3], K^0[2])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|36
|> <math>10 \uparrow\uparrow\uparrow 5</math>
|<math>C(ADT[3], K^0[3])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|38
|> <math>10 \uparrow\uparrow\uparrow 6</math>
|<math>C(ADT[3], K^0[4])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|
|
|
|
|
|-
|7k+11
|> <math>10 \uparrow^k 2</math>
|<math>C(ADT[k], K^0[1])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|7k+13
|> <math>10 \uparrow^k 3</math>
|<math>C(ADT[k], K^0[2])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|7k+15
|> <math>10 \uparrow^k 4</math>
|<math>C(ADT[k], K^0[3])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|7k+17
|> <math>10 \uparrow^k 5</math>
|<math>C(ADT[k], K^0[4])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|
|
|
|
|
|-
|6k+17
|<math>\ge 2 \uparrow^k 4</math>
|<math>C(Knuth2[k], K^0[4])</math>
|Shawn Ligocki [https://discord.com/channels/960643023006490684/1447627603698647303/1447633458510692385 8 Dec 2025]
|
|-
|6k+19
|<math>\ge 2 \uparrow^k 5</math>
|<math>C(Knuth2[k], K^0[5])</math>
|Shawn Ligocki [https://discord.com/channels/960643023006490684/1447627603698647303/1447633458510692385 8 Dec 2025]
|
|-
|6k+21
|<math>\ge 2 \uparrow^k 6</math>
|<math>C(Knuth2[k], K^0[6])</math>
|Shawn Ligocki [https://discord.com/channels/960643023006490684/1447627603698647303/1447633458510692385 8 Dec 2025]
|
|}

== Macro Bounds ==

=== ADT[k] ===

* <math>ADT[0](n) = Tri(n) = \frac{n(n+1)}{2} > \frac{1}{2} n^2</math>
* <math>ADT[0]^k(n) > 2 \left( \frac{n}{2} \right)^{2^k}</math>
* <math>ADT[1](n) = Tri^{n+1}(n+2) > 2 \left(\frac{n+2}{2} \right)^{2^{n+1}} = 2 \left(\frac{(n+2)^2}{4} \right)^{2^n} > A 10^{10^{n/A}}</math> where <math>A = \frac{1}{\log_{10}(2)}</math> (if <math>n \ge 5</math>, for smaller values, this can be calculated directly)
* <math>ADT[1]^k(n) > A (10 \uparrow)^{2k} \frac{n}{A} > 10 \uparrow\uparrow 2k</math> (if <math>n \ge 4</math>)
* <math>ADT[2](n) = ADT[1]^{n+1}(n+2) > 10 \uparrow\uparrow (2n+2) </math> (if <math>n \ge 2</math>)
* <math>ADT[k](n) > 10 \uparrow^k (n+1) </math> (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: <math>BB\mu(6k+17) \ge 2 \uparrow^k 4</math>.

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 [[wikipedia:Pairing_function|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. The smallest known such pairing functions are:
{| class="wikitable"
|+Smallest Pairing Functions
!Macro
!arity
!Definition
!Size
!Function
|-
|<math>Pair</math>
|2
|<math>Pair := C(AddS, C(Tri, Add), P^2_1)</math>
|20
|<math>\lambda xy. \frac{(x+y)(x+y+1)}{2} + x + 1</math>
|-
|<math>Left</math>
|1
|<math>Left := C(RMonus, C(TriP, InvTriCeil), Pred)</math>
|38
|<math>Left(Pair(x,y)) = x</math>
|-
|<math>Right</math>
|1
|<math>Right := C(RMonus, P^1_1, C(Tri, InvTriCeil))</math>
|36
|<math>Right(Pair(x,y)) = y</math>
|-
|<math>LRCall[f^2]</math>
|1
|<math>LRCall[f] := C(LRpart3[f], InvTriCeil, P^1_1)</math>
|<math>61 + |f|</math>
|<math>LRCall[f](Pair(x,y)) = f(x,y)</math>
|}
Where these are based on the following definitions:
{| class="wikitable"
|+Macros
!
!Macro
!arity
!Definition
!Size
!Function
|-
| rowspan="2" |Addition
|Add
|2
|<math>Add := R(P^1_1, C(S, P^3_2))</math>
|5
|<math>\lambda xy. x+y</math>
|-
|AddS
|2
|<math>AddS := R(S, C(S, P^3_2))</math>
|5
|<math>\lambda xy. x+y+1</math>
|-
|[[wikipedia:Primitive_recursive_function#Predecessor|Predecesor]]
|Pred
|1
|<math>Pred := R(Z^0, P^2_1)</math>
|3
|<math>\lambda x. x \dot - 1</math>
|-
|[[wikipedia:Monus#Natural_numbers|Monus]]
|RMonus
|2
|<math>RMonus := R(P^1_1, C(Pred, P^3_2))</math>
|7
|<math>\lambda xy. y \dot - x</math>
|-
| rowspan="2" |Triangular numbers
|Tri
|1
|<math>Tri := R(Z^0, AddS)</math>
|7
|<math>\lambda x. \frac{x(x+1)}{2}</math>
|-
|TriP
|1
|<math>TriP := R(Z^0, Add)</math>
|7
|<math>TriP(x+1) = Tri(x)</math>
|-
| rowspan="2" |Inverting Tri
|RMonusTri
|2
|<math>RMonusTri := C(RMonus, C(Tri, P^2_1), P^2_2)</math>
|18
|<math>\lambda xy. y \dot - Tri(x)</math>
|-
|InvTriCeil
|1
|<math>InvTriCeil := M(RMonusTri)</math>
|19
|<math>\lambda y. \min \{x | Tri(x) \ge y \}</math>
|-
| rowspan="5" | Combined LRCall
|RightPiece
|3
|<math>RightPiece := R(P^2_2, C(Pred, P^4_2))</math>
|7
|<math>\lambda xyz. z \dot - x</math>
|-
|LeftPiece
|3
|<math>LeftPiece := C(RMonus, C(S, P^3_2), P^3_1)</math>
|12
|<math>\lambda xyz. x \dot - (y+1)</math>
|-
|LRpart1[f]
|3
|<math>LRpart1[f] := C(f, LeftPiece, RightPiece)</math>
|<math>20 + |f|</math>
|<math>\lambda xyz. f(LeftPiece(x,y,z), RightPiece(x,y,z))</math>
|-
|LRPart2[f]
|3
|<math>LRpart2[f] := C(LRpart1[f], P^3_3, P^3_1, R(P^2_1, C(S, P^4_2)))</math>
|<math>28 + |f|</math>
|<math>\lambda xyz. LRpart1[f](z, x, x+y)</math>
|-
|LRpart3[f]
|2
|<math>LRpart3[f] := C(LRpart2[f], C(TriP, P^2_1), P^2_1, P^2_2)</math>
|<math>40 + |f|</math>
|<math>\lambda xy. LRpart2[f](TriP(x), x, y)</math>
|}

[[Category:functions]]

General Recursive Function

2026-04-11T01:59:15Z

JLM: /* Champions */ Champs table looks nicer with the shorter "ADT[2]".

'''General recursive functions''' ('''GRFs'''), also called '''µ-recursive functions''' or '''partial recursive functions''', are the collection of [[Wikipedia:partial functions|partial functions]] <math>\N^k \rightharpoonup \N</math> 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 <math>\N^k \rightharpoonup \N</math> 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:<math display="block">BB \mu (n) = \max \{ f() | f \in \text{GRF}_0 , |f| = n \}</math>

where <math>f \in GRF_k</math> means that <math>f: \N^k \rightharpoonup \N</math> is a k-ary GRF and <math>|f|</math> 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 <math>GRF_k</math> inductively based on the following construction rules, start with Atoms and combine them using Combinators.

====== Atoms ======

* Zero: <math>\forall k \in \N, Z^k \in GRF_k</math> is the constant 0 function <math>Z^k(x_1, \dots, x_k) = 0</math>
* Successor: <math>S \in GRF_1</math> is the successor function <math>S(x) = x+1</math>
* Projection: <math>\forall 1 \le i \le k \in \N, P^k_i \in GRF_k</math> is a projection function <math>P^k_i(x_1, \dots x_k) = x_i</math>

===== Combinators =====

* Composition: <math>\forall k,m \in \N, \forall h \in GRF_m, \forall g_1, \dots g_m \in GRF_k, C(h, g_1, \dots g_m) \in GRF_k</math> is the composition or substitution of the ''g''s into ''h'': <math>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))</math>
* Primitive Recursion: <math>\forall k \in \N, \forall g \in GRF_k, \forall h \in GRF_{k+2}, R(g, h) \in GRF_{k+1}</math> is primitive recursion using ''g'' as the base case and ''h'' as the inductive step.
* Minimization / Unlimited Search: <math>\forall k \in \N, \forall f \in GRF_{k+1}, M(f) \in GRF_k</math> is the µ-operator which allows unlimited search.

=== Primitive Recursion ===
<math>R</math> models a typical iterative function definition over ℕ.

Base case: <math>R^k(g, h)(0, x_2, x_3, ..., x_k) = g(x_2, x_3, ..., x_k)</math>

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

<math>R</math> 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 <math>g</math>), then 1, 2, 3, etc. until <math>x_1</math> is reached, each time calling <math>h</math> with the prior iteration count for its first argument and the result of the prior call for its second.

=== Minimization ===
<math>M^k(f)(x_1, ..., x_k) \triangleq \min \{i \in \N: f(i, x_1, ..., x_k) = 0\}</math>

In computational language, when ''M(f)'' is evaluated it can be considered to calculate <math>f(i, x_1, ..., x_k)</math> with <math>i=0</math>, then <math>i=1</math>, then <math>i=2</math> etc. until one of the calls to <math>f</math> returns 0. It returns the value of <math>i</math> which first gave a result of 0. If no first argument causes <math>f</math> to return 0, <math>M(f)</math> 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 <math>f \in GRF_1</math>
{| class="wikitable"
|+
!
!Macro
!arity
!Definition
!Size
!Function
|-
|Plus constant
|<math>Plus[n]</math>
|1
|<math>\begin{array}{lcl}
Plus[1] & := & S \\
Plus[n+1] & := & C(S, Plus[n])
\end{array}</math>
|<math>2n-1</math>
|<math>\lambda x. x+n</math>
|-
|Constant
|<math>K^k[n]</math>
|k
|<math>\begin{array}{lcl}
K^k[0] & := & Z^k \\
K^k[n] & := & C(Plus[n], Z^k)
\end{array}</math>
|<math>2n+1</math>
|<math>\lambda x_1 \dots x_k. n</math>
|-
|Iteration
|<math>Rep[f,n]</math>
|1
|<math>Rep[f,n] := R(K^0[n], C(f, P^2_2))</math>
|<math>|f| + 2n + 4</math>
|<math>\lambda x. f^x(n)</math>
|-
|Iteration of successor
|<math>RepSucc[f]</math>
|2
|<math>RepSucc[f] := R(S, C(f, P^3_2))</math>
|<math>|f| + 4</math>
|<math>\lambda x\ y. f^x(y+1)</math>
|-
|Diagonalization
|<math>RepDiag[f]</math>
|1
|<math>RepDiag[f] := C(RepSucc[f], S, S)</math>
|<math>|f| + 7</math>
|<math>\lambda x. f^{x+1}(x+2)</math>
|-
|Ackermann iteration
|<math>Ack[n,f]</math>
|1
|<math>\begin{array}{lcl}
Ack[0,f] & := & f \\
Ack[n+1,f] & := & Rep[Ack[n,f],1]
\end{array}</math>
|<math>6n + |f|</math>
|
|-
|Knuth base 2 up-arrows
|<math>Knuth2[n]</math>
|1
|<math>\begin{array}{lcl}
Knuth2[0] & := & Rep[Plus[2],0] \\
Knuth2[n+1] & := & Rep[Knuth2[n],1]
\end{array}</math>
|<math>6n+7</math>
|<math>\lambda x. 2 \uparrow^n x</math>
|-
|Ackermann Diagonalization
on Triangular nums
|<math>ADT[n]</math>
|1
|<math>\begin{array}{lcl}
ADT[0] & := & Tri \\
ADT[n+1] & := & RepDiag[ADT[n]]
\end{array}</math>
|<math>7n + 7</math>
|<math>\lambda x. > 10 \uparrow^n (x+1)</math>
|-
|Polygonal
|<math>Poly[n]</math>
|1
|<math>Poly[n] := R(Z^0, R(S, C(Plus[n], P^3_2)))</math>
|<math>2n+5</math>
|<math>\lambda x. \frac{n}{2} x(x-1) + x</math>
|-
|
|<math>Tri</math>
|1
|<math>Tri := Poly[1] = R(Z^0, R(S, C(S, P^3_2)))</math>
|<math>7</math>
|<math>\lambda x. \frac{x(x+1)}{2}</math>
|-
|
|<math>Square</math>
|1
|<math>Square := Poly[2]</math>
|<math>9</math>
|<math>\lambda x. x^2</math>
|}

== Champions ==
{| class="wikitable"
!n
!BBµ(n)
!Champion
!Champion Found
!Holdouts Proven
|-
|1
|= 0
|<math>Z^0</math>
|
|Shawn Ligocki [https://discord.com/channels/960643023006490684/1447627603698647303/1447693296322215976 8 Dec 2025] By hand
|-
|2
|= 0
|<math>M(Z^1), M(P^1_1), C(Z^0)</math>
|
|Shawn Ligocki [https://discord.com/channels/960643023006490684/1447627603698647303/1447693296322215976 8 Dec 2025] By hand
|-
|3
|= 1
|<math>K^0[1]</math>
|
|Shawn Ligocki [https://discord.com/channels/960643023006490684/1447627603698647303/1447693296322215976 8 Dec 2025] By hand
|-
|4
|= 1
|<math>C^0(K^0[1])</math>
|
|Jacob Mandelson [https://mandelson.org/grf/ 3 Apr 2026]
|-
|5
|= 2
|<math>K^0[2]</math>
|
|Jacob Mandelson [https://mandelson.org/grf/ 3 Apr 2026]
|-
|6
|= 2
|<math>C^0(K^0[2])</math>
|
|Jacob Mandelson [https://mandelson.org/grf/ 3 Apr 2026]
|-
|7
|= 3
|<math>K^0[3]</math>
|
|Jacob Mandelson [https://mandelson.org/grf/ 3 Apr 2026]
|-
|9
|≥ 4
|<math>K^0[4]</math>
|
|
|-
|11
|≥ 5
|<math>K^0[5]</math>
|
|
|-
|13
|≥ 6
|<math>K^0[6]</math>
|
|
|-
|14
|≥ 7
|<math>C(RepDiag[S], K^0[2])</math>
|Shawn Ligocki [https://discord.com/channels/960643023006490684/1447627603698647303/1492246885329670184 10 Apr 2026]
|
|-
|16
|≥ 9
|<math>C(RepDiag[S], K^0[3])</math>
|Shawn Ligocki [https://discord.com/channels/960643023006490684/1447627603698647303/1492246885329670184 10 Apr 2026]
|
|-
|17
|≥ 10
|<math>C(Tri, K^0[4])</math>
|Shawn Ligocki 9 Dec 2025
|
|-
|18
|≥ 21
|<math>C(RepDiag[Tri], K^0[1])</math>
|Jacob Mandelson [https://discord.com/channels/960643023006490684/1447627603698647303/1492021428546179182 9 Apr 2026]
|
|-
|20
|≥ 1540
|<math>C(RepDiag[Tri], K^0[2])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|22
|≥ 26'357'430
|<math>C(RepDiag[Tri], K^0[3])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|24
|≥ 64'449'908'476'890'321 > 1016.8
|<math>C(RepDiag[Tri], K^0[4])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|25
|<math> > 10^{10^{10^{6.899}}} > 10 \uparrow\uparrow 3.8388 > 10^{10^{10^{6.8}}}</math>
|<math>C(ADT[2], K^0[1])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|27
|> <math>10 \uparrow\uparrow 6.0834</math>
|<math>C(ADT[2], K^0[2])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|29
|> <math>10 \uparrow\uparrow 8.1944</math>
|<math>C(ADT[2], K^0[3])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|31
|> <math>10 \uparrow\uparrow 10.2800</math>
|<math>C(ADT[2], K^0[4])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|32
|> <math>10 \uparrow\uparrow 10 \uparrow\uparrow 8.1944</math>
|<math>C(ADT[3], K^0[1])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|34
|> <math>10 \uparrow\uparrow\uparrow 4</math>
|<math>C(ADT[3], K^0[2])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|36
|> <math>10 \uparrow\uparrow\uparrow 5</math>
|<math>C(ADT[3], K^0[3])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|38
|> <math>10 \uparrow\uparrow\uparrow 6</math>
|<math>C(ADT[3], K^0[4])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|
|
|
|
|
|-
|7k+11
|> <math>10 \uparrow^k 2</math>
|<math>C(ADT[k], K^0[1])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|7k+13
|> <math>10 \uparrow^k 3</math>
|<math>C(ADT[k], K^0[2])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|7k+15
|> <math>10 \uparrow^k 4</math>
|<math>C(ADT[k], K^0[3])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|7k+17
|> <math>10 \uparrow^k 5</math>
|<math>C(ADT[k], K^0[4])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|
|
|
|
|
|-
|6k+17
|<math>\ge 2 \uparrow^k 4</math>
|<math>C(Knuth2[k], K^0[4])</math>
|Shawn Ligocki [https://discord.com/channels/960643023006490684/1447627603698647303/1447633458510692385 8 Dec 2025]
|
|-
|6k+19
|<math>\ge 2 \uparrow^k 5</math>
|<math>C(Knuth2[k], K^0[5])</math>
|Shawn Ligocki [https://discord.com/channels/960643023006490684/1447627603698647303/1447633458510692385 8 Dec 2025]
|
|-
|6k+21
|<math>\ge 2 \uparrow^k 6</math>
|<math>C(Knuth2[k], K^0[6])</math>
|Shawn Ligocki [https://discord.com/channels/960643023006490684/1447627603698647303/1447633458510692385 8 Dec 2025]
|
|}

== Macro Bounds ==

=== ADT[k] ===

* <math>ADT[0](n) = Tri(n) = \frac{n(n+1)}{2} > \frac{1}{2} n^2</math>
* <math>ADT[0]^k(n) > 2 \left( \frac{n}{2} \right)^{2^k}</math>
* <math>ADT[1](n) = Tri^{n+1}(n+2) > 2 \left(\frac{n+2}{2} \right)^{2^{n+1}} = 2 \left(\frac{(n+2)^2}{4} \right)^{2^n} > A 10^{10^{n/A}}</math> where <math>A = \frac{1}{\log_{10}(2)}</math> (if <math>n \ge 5</math>, for smaller values, this can be calculated directly)
* <math>ADT[1]^k(n) > A (10 \uparrow)^{2k} \frac{n}{A} > 10 \uparrow\uparrow 2k</math> (if <math>n \ge 4</math>)
* <math>ADT[2](n) = ADT[1]^{n+1}(n+2) > 10 \uparrow\uparrow (2n+2) </math> (if <math>n \ge 2</math>)
* <math>ADT[k](n) > 10 \uparrow^k (n+1) </math> (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: <math>BB\mu(6k+17) \ge 2 \uparrow^k 4</math>.

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 [[wikipedia:Pairing_function|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. The smallest known such pairing functions are:
{| class="wikitable"
|+Smallest Pairing Functions
!Macro
!arity
!Definition
!Size
!Function
|-
|Pair
|2
|<math>Pair := C(AddS, C(Tri, Add), P^2_1)</math>
|20
|<math>\lambda xy. \frac{(x+y)(x+y+1)}{2} + x + 1</math>
|-
|Left
|1
|<math>Left := C(RMonus, C(TriP, InvTriCeil), Pred)</math>
|38
|<math>Left(Pair(x,y)) = x</math>
|-
|Right
|1
|<math>Right := C(RMonus, P^1_1, C(Tri, InvTriCeil))</math>
|36
|<math>Right(Pair(x,y)) = y</math>
|}
Where these are based on the following definitions:
{| class="wikitable"
|+Macros
!
!Macro
!arity
!Definition
!Size
!Function
|-
| rowspan="2" |Addition
|Add
|2
|<math>Add := R(P^1_1, C(S, P^3_2))</math>
|5
|<math>\lambda xy. x+y</math>
|-
|AddS
|2
|<math>AddS := R(S, C(S, P^3_2))</math>
|5
|<math>\lambda xy. x+y+1</math>
|-
|[[wikipedia:Primitive_recursive_function#Predecessor|Predecesor]]
|Pred
|1
|<math>Pred := R(Z^0, P^2_1)</math>
|3
|<math>\lambda x. x \dot - 1</math>
|-
|[[wikipedia:Monus#Natural_numbers|Monus]]
|RMonus
|2
|<math>RMonus := R(P^1_1, C(Pred, P^3_2))</math>
|7
|<math>\lambda xy. y \dot - x</math>
|-
| rowspan="2" |Triangular numbers
|Tri
|1
|<math>Tri := R(Z^0, AddS)</math>
|7
|<math>\lambda x. \frac{x(x+1)}{2}</math>
|-
|TriP
|1
|<math>TriP := R(Z^0, Add)</math>
|7
|<math>TriP(x+1) = Tri(x)</math>
|-
| rowspan="2" |Inverting Tri
|RMonusTri
|2
|<math>RMonusTri := C(RMonus, C(Tri, P^2_1), P^2_2)</math>
|18
|<math>\lambda xy. y \dot - Tri(x)</math>
|-
|InvTriCeil
|1
|<math>InvTriCeil := M(RMonusTri)</math>
|19
|<math>\lambda y. \min \{x | Tri(x) \ge y \}</math>
|}

[[Category:functions]]

General Recursive Function

2026-04-11T01:53:08Z

JLM: /* Utilizing Minimization */ Typo for AddS

'''General recursive functions''' ('''GRFs'''), also called '''µ-recursive functions''' or '''partial recursive functions''', are the collection of [[Wikipedia:partial functions|partial functions]] <math>\N^k \rightharpoonup \N</math> 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 <math>\N^k \rightharpoonup \N</math> 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:<math display="block">BB \mu (n) = \max \{ f() | f \in \text{GRF}_0 , |f| = n \}</math>

where <math>f \in GRF_k</math> means that <math>f: \N^k \rightharpoonup \N</math> is a k-ary GRF and <math>|f|</math> 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 <math>GRF_k</math> inductively based on the following construction rules, start with Atoms and combine them using Combinators.

====== Atoms ======

* Zero: <math>\forall k \in \N, Z^k \in GRF_k</math> is the constant 0 function <math>Z^k(x_1, \dots, x_k) = 0</math>
* Successor: <math>S \in GRF_1</math> is the successor function <math>S(x) = x+1</math>
* Projection: <math>\forall 1 \le i \le k \in \N, P^k_i \in GRF_k</math> is a projection function <math>P^k_i(x_1, \dots x_k) = x_i</math>

===== Combinators =====

* Composition: <math>\forall k,m \in \N, \forall h \in GRF_m, \forall g_1, \dots g_m \in GRF_k, C(h, g_1, \dots g_m) \in GRF_k</math> is the composition or substitution of the ''g''s into ''h'': <math>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))</math>
* Primitive Recursion: <math>\forall k \in \N, \forall g \in GRF_k, \forall h \in GRF_{k+2}, R(g, h) \in GRF_{k+1}</math> is primitive recursion using ''g'' as the base case and ''h'' as the inductive step.
* Minimization / Unlimited Search: <math>\forall k \in \N, \forall f \in GRF_{k+1}, M(f) \in GRF_k</math> is the µ-operator which allows unlimited search.

=== Primitive Recursion ===
<math>R</math> models a typical iterative function definition over ℕ.

Base case: <math>R^k(g, h)(0, x_2, x_3, ..., x_k) = g(x_2, x_3, ..., x_k)</math>

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

<math>R</math> 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 <math>g</math>), then 1, 2, 3, etc. until <math>x_1</math> is reached, each time calling <math>h</math> with the prior iteration count for its first argument and the result of the prior call for its second.

=== Minimization ===
<math>M^k(f)(x_1, ..., x_k) \triangleq \min \{i \in \N: f(i, x_1, ..., x_k) = 0\}</math>

In computational language, when ''M(f)'' is evaluated it can be considered to calculate <math>f(i, x_1, ..., x_k)</math> with <math>i=0</math>, then <math>i=1</math>, then <math>i=2</math> etc. until one of the calls to <math>f</math> returns 0. It returns the value of <math>i</math> which first gave a result of 0. If no first argument causes <math>f</math> to return 0, <math>M(f)</math> 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 <math>f \in GRF_1</math>
{| class="wikitable"
|+
!
!Macro
!arity
!Definition
!Size
!Function
|-
|Plus constant
|<math>Plus[n]</math>
|1
|<math>\begin{array}{lcl}
Plus[1] & := & S \\
Plus[n+1] & := & C(S, Plus[n])
\end{array}</math>
|<math>2n-1</math>
|<math>\lambda x. x+n</math>
|-
|Constant
|<math>K^k[n]</math>
|k
|<math>\begin{array}{lcl}
K^k[0] & := & Z^k \\
K^k[n] & := & C(Plus[n], Z^k)
\end{array}</math>
|<math>2n+1</math>
|<math>\lambda x_1 \dots x_k. n</math>
|-
|Iteration
|<math>Rep[f,n]</math>
|1
|<math>Rep[f,n] := R(K^0[n], C(f, P^2_2))</math>
|<math>|f| + 2n + 4</math>
|<math>\lambda x. f^x(n)</math>
|-
|Iteration of successor
|<math>RepSucc[f]</math>
|2
|<math>RepSucc[f] := R(S, C(f, P^3_2))</math>
|<math>|f| + 4</math>
|<math>\lambda x\ y. f^x(y+1)</math>
|-
|Diagonalization
|<math>RepDiag[f]</math>
|1
|<math>RepDiag[f] := C(RepSucc[f], S, S)</math>
|<math>|f| + 7</math>
|<math>\lambda x. f^{x+1}(x+2)</math>
|-
|Ackermann iteration
|<math>Ack[n,f]</math>
|1
|<math>\begin{array}{lcl}
Ack[0,f] & := & f \\
Ack[n+1,f] & := & Rep[Ack[n,f],1]
\end{array}</math>
|<math>6n + |f|</math>
|
|-
|Knuth base 2 up-arrows
|<math>Knuth2[n]</math>
|1
|<math>\begin{array}{lcl}
Knuth2[0] & := & Rep[Plus[2],0] \\
Knuth2[n+1] & := & Rep[Knuth2[n],1]
\end{array}</math>
|<math>6n+7</math>
|<math>\lambda x. 2 \uparrow^n x</math>
|-
|Ackermann Diagonalization
on Triangular nums
|<math>ADT[n]</math>
|1
|<math>\begin{array}{lcl}
ADT[0] & := & Tri \\
ADT[n+1] & := & RepDiag[ADT[n]]
\end{array}</math>
|<math>7n + 7</math>
|<math>\lambda x. > 10 \uparrow^n (x+1)</math>
|-
|Polygonal
|<math>Poly[n]</math>
|1
|<math>Poly[n] := R(Z^0, R(S, C(Plus[n], P^3_2)))</math>
|<math>2n+5</math>
|<math>\lambda x. \frac{n}{2} x(x-1) + x</math>
|-
|
|<math>Tri</math>
|1
|<math>Tri := Poly[1] = R(Z^0, R(S, C(S, P^3_2)))</math>
|<math>7</math>
|<math>\lambda x. \frac{x(x+1)}{2}</math>
|-
|
|<math>Square</math>
|1
|<math>Square := Poly[2]</math>
|<math>9</math>
|<math>\lambda x. x^2</math>
|}

== Champions ==
{| class="wikitable"
!n
!BBµ(n)
!Champion
!Champion Found
!Holdouts Proven
|-
|1
|= 0
|<math>Z^0</math>
|
|Shawn Ligocki [https://discord.com/channels/960643023006490684/1447627603698647303/1447693296322215976 8 Dec 2025] By hand
|-
|2
|= 0
|<math>M(Z^1), M(P^1_1), C(Z^0)</math>
|
|Shawn Ligocki [https://discord.com/channels/960643023006490684/1447627603698647303/1447693296322215976 8 Dec 2025] By hand
|-
|3
|= 1
|<math>K^0[1]</math>
|
|Shawn Ligocki [https://discord.com/channels/960643023006490684/1447627603698647303/1447693296322215976 8 Dec 2025] By hand
|-
|4
|= 1
|<math>C^0(K^0[1])</math>
|
|Jacob Mandelson [https://mandelson.org/grf/ 3 Apr 2026]
|-
|5
|= 2
|<math>K^0[2]</math>
|
|Jacob Mandelson [https://mandelson.org/grf/ 3 Apr 2026]
|-
|6
|= 2
|<math>C^0(K^0[2])</math>
|
|Jacob Mandelson [https://mandelson.org/grf/ 3 Apr 2026]
|-
|7
|= 3
|<math>K^0[3]</math>
|
|Jacob Mandelson [https://mandelson.org/grf/ 3 Apr 2026]
|-
|9
|≥ 4
|<math>K^0[4]</math>
|
|
|-
|11
|≥ 5
|<math>K^0[5]</math>
|
|
|-
|13
|≥ 6
|<math>K^0[6]</math>
|
|
|-
|14
|≥ 7
|<math>C(RepDiag[S], K^0[2])</math>
|Shawn Ligocki [https://discord.com/channels/960643023006490684/1447627603698647303/1492246885329670184 10 Apr 2026]
|
|-
|16
|≥ 9
|<math>C(RepDiag[S], K^0[3])</math>
|Shawn Ligocki [https://discord.com/channels/960643023006490684/1447627603698647303/1492246885329670184 10 Apr 2026]
|
|-
|17
|≥ 10
|<math>C(Tri, K^0[4])</math>
|Shawn Ligocki 9 Dec 2025
|
|-
|18
|≥ 21
|<math>C(RepDiag[Tri], K^0[1])</math>
|Jacob Mandelson [https://discord.com/channels/960643023006490684/1447627603698647303/1492021428546179182 9 Apr 2026]
|
|-
|20
|≥ 1540
|<math>C(RepDiag[Tri], K^0[2])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|22
|≥ 26'357'430
|<math>C(RepDiag[Tri], K^0[3])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|24
|≥ 64'449'908'476'890'321 > 1016.8
|<math>C(RepDiag[Tri], K^0[4])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|25
|<math> > 10^{10^{10^{6.899}}} > 10 \uparrow\uparrow 3.8388 > 10^{10^{10^{6.8}}}</math>
|<math>C(RepDiag[RepDiag[Tri]], K^0[1])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|27
|> <math>10 \uparrow\uparrow 6.0834</math>
|<math>C(RepDiag[RepDiag[Tri]], K^0[2])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|29
|> <math>10 \uparrow\uparrow 8.1944</math>
|<math>C(RepDiag[RepDiag[Tri]], K^0[3])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|31
|> <math>10 \uparrow\uparrow 10.2800</math>
|<math>C(RepDiag[RepDiag[Tri]], K^0[4])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|32
|> <math>10 \uparrow\uparrow 10 \uparrow\uparrow 8.1944</math>
|<math>C(ADT[3], K^0[1])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|34
|> <math>10 \uparrow\uparrow\uparrow 4</math>
|<math>C(ADT[3], K^0[2])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|36
|> <math>10 \uparrow\uparrow\uparrow 5</math>
|<math>C(ADT[3], K^0[3])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|38
|> <math>10 \uparrow\uparrow\uparrow 6</math>
|<math>C(ADT[3], K^0[4])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|
|
|
|
|
|-
|7k+11
|> <math>10 \uparrow^k 2</math>
|<math>C(ADT[k], K^0[1])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|7k+13
|> <math>10 \uparrow^k 3</math>
|<math>C(ADT[k], K^0[2])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|7k+15
|> <math>10 \uparrow^k 4</math>
|<math>C(ADT[k], K^0[3])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|7k+17
|> <math>10 \uparrow^k 5</math>
|<math>C(ADT[k], K^0[4])</math>
|Jacob Mandelson 9 Apr 2026
|
|-
|
|
|
|
|
|-
|6k+17
|<math>\ge 2 \uparrow^k 4</math>
|<math>C(Knuth2[k], K^0[4])</math>
|Shawn Ligocki [https://discord.com/channels/960643023006490684/1447627603698647303/1447633458510692385 8 Dec 2025]
|
|-
|6k+19
|<math>\ge 2 \uparrow^k 5</math>
|<math>C(Knuth2[k], K^0[5])</math>
|Shawn Ligocki [https://discord.com/channels/960643023006490684/1447627603698647303/1447633458510692385 8 Dec 2025]
|
|-
|6k+21
|<math>\ge 2 \uparrow^k 6</math>
|<math>C(Knuth2[k], K^0[6])</math>
|Shawn Ligocki [https://discord.com/channels/960643023006490684/1447627603698647303/1447633458510692385 8 Dec 2025]
|
|}

== Macro Bounds ==

=== ADT[k] ===

* <math>ADT[0](n) = Tri(n) = \frac{n(n+1)}{2} > \frac{1}{2} n^2</math>
* <math>ADT[0]^k(n) > 2 \left( \frac{n}{2} \right)^{2^k}</math>
* <math>ADT[1](n) = Tri^{n+1}(n+2) > 2 \left(\frac{n+2}{2} \right)^{2^{n+1}} = 2 \left(\frac{(n+2)^2}{4} \right)^{2^n} > A 10^{10^{n/A}}</math> where <math>A = \frac{1}{\log_{10}(2)}</math> (if <math>n \ge 5</math>, for smaller values, this can be calculated directly)
* <math>ADT[1]^k(n) > A (10 \uparrow)^{2k} \frac{n}{A} > 10 \uparrow\uparrow 2k</math> (if <math>n \ge 4</math>)
* <math>ADT[2](n) = ADT[1]^{n+1}(n+2) > 10 \uparrow\uparrow (2n+2) </math> (if <math>n \ge 2</math>)
* <math>ADT[k](n) > 10 \uparrow^k (n+1) </math> (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: <math>BB\mu(6k+17) \ge 2 \uparrow^k 4</math>.

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 [[wikipedia:Pairing_function|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. The smallest known such pairing functions are:
{| class="wikitable"
|+Smallest Pairing Functions
!Macro
!arity
!Definition
!Size
!Function
|-
|Pair
|2
|<math>Pair := C(AddS, C(Tri, Add), P^2_1)</math>
|20
|<math>\lambda xy. \frac{(x+y)(x+y+1)}{2} + x + 1</math>
|-
|Left
|1
|<math>Left := C(RMonus, C(TriP, InvTriCeil), Pred)</math>
|38
|<math>Left(Pair(x,y)) = x</math>
|-
|Right
|1
|<math>Right := C(RMonus, P^1_1, C(Tri, InvTriCeil))</math>
|36
|<math>Right(Pair(x,y)) = y</math>
|}
Where these are based on the following definitions:
{| class="wikitable"
|+Macros
!
!Macro
!arity
!Definition
!Size
!Function
|-
| rowspan="2" |Addition
|Add
|2
|<math>Add := R(P^1_1, C(S, P^3_2))</math>
|5
|<math>\lambda xy. x+y</math>
|-
|AddS
|2
|<math>AddS := R(S, C(S, P^3_2))</math>
|5
|<math>\lambda xy. x+y+1</math>
|-
|[[wikipedia:Primitive_recursive_function#Predecessor|Predecesor]]
|Pred
|1
|<math>Pred := R(Z^0, P^2_1)</math>
|3
|<math>\lambda x. x \dot - 1</math>
|-
|[[wikipedia:Monus#Natural_numbers|Monus]]
|RMonus
|2
|<math>RMonus := R(P^1_1, C(Pred, P^3_2))</math>
|7
|<math>\lambda xy. y \dot - x</math>
|-
| rowspan="2" |Triangular numbers
|Tri
|1
|<math>Tri := R(Z^0, AddS)</math>
|7
|<math>\lambda x. \frac{x(x+1)}{2}</math>
|-
|TriP
|1
|<math>TriP := R(Z^0, Add)</math>
|7
|<math>TriP(x+1) = Tri(x)</math>
|-
| rowspan="2" |Inverting Tri
|RMonusTri
|2
|<math>RMonusTri := C(RMonus, C(Tri, P^2_1), P^2_2)</math>
|18
|<math>\lambda xy. y \dot - Tri(x)</math>
|-
|InvTriCeil
|1
|<math>InvTriCeil := M(RMonusTri)</math>
|19
|<math>\lambda y. \min \{x | Tri(x) \ge y \}</math>
|}

[[Category:functions]]

General Recursive Function

2026-04-11T00:42:30Z

JLM: Fix typo in ADT definition and add upper bound to sandwich 10^^3.8388

General Recursive Function

2026-04-10T14:51:06Z

JLM: Rename "RepRepSucc" to "RepDiagS"

General Recursive Function

2026-04-10T07:01:31Z

JLM: /* Champions */ Write in "hyperscientific" notation

General Recursive Function

2026-04-10T06:31:36Z

JLM: Use a closer-to-standard notation

General Recursive Function

2026-04-10T05:34:07Z

JLM: New champions, starting at BBu(18) >= 21

General Recursive Function

2026-04-09T01:18:51Z

JLM: /* Minimization */ Clearer explanation of 'M' operator.

General Recursive Function

2026-04-08T15:06:06Z

JLM: Regularize formatting.

General Recursive Function

2026-04-08T07:08:26Z

JLM: /* Primitive Recursive Functions */ More precise section name

General Recursive Function

2026-04-08T07:02:42Z

JLM: /* Primitive Recursive Functions */ h() receives the prior iter count.

General Recursive Function

2026-04-08T06:59:10Z

JLM: /* Minimization */ Include arguments to M(f) in its definition.

General Recursive Function

2026-04-08T06:56:21Z

JLM: /* Primitive Recursive Functions */ Define the 'R' operator.

General Recursive Function

2026-04-08T06:32:06Z

JLM: /* Minimization */ Define 'M' operator.

General Recursive Function

2026-04-08T06:04:26Z

JLM: /* Champions */ Holdouts for sizes 4-7 proven.