General Recursive Function

2026-05-24T20:03:06Z

Racheline6174: /* Champions */ keeping the later champions that have non-discord sources

'''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'' (the number of atoms and combinators in the definition, [[General Recursive Function#Size|see details below]]). In other words, it is the largest number computable via a 0-ary function (a constant) with a limited "program" size. It is more akin to the traditional [[Sigma score]] for a Turing machine rather than the Step function in the sense that it maximizes over the produced value, not the number of steps needed to reach that value.

== Definition ==

=== Structure ===
Define <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^k(h, g_1, \dots g_m) \in GRF_k</math> is the composition or substitution of the ''g''s into ''h'': <math>C^k(h, g_1, \dots g_m)(x_1, \dots x_k) = h(g_1(x_1, \dots x_k), \dots g_m(x_1, \dots x_k))</math>
* Primitive Recursion: <math>\forall k \in \N, \forall g \in GRF_k, \forall h \in GRF_{k+2}, R^{k+1}(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^k(f) \in GRF_k</math> is the µ-operator which allows unlimited search.
The arity superscripts for C, R and M are redundant (except for <math>C^k(h)</math>) and so are sometimes omitted below.

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

* <math>|Z^k| = |P^k_i| = |S| = 1</math>
* <math>|C(h, g_1, \cdots, g_m)| = 1 + |h| + |g_1| + \cdots + |g_m|</math>
* <math>|R(g, h)| = 1 + |g| + |h|</math>
* <math>|M(f)| = 1 + |f|</math>

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

''R'' can be recursively evaluated following its definition directly or it can be simulated as a bounded <code>for</code> loop like this python code:<pre>
# f = R(g,h)
def f(n, *xs):
acc = g(*xs)
for k in range(n):
acc = h(k, acc, *xs)
return acc
</pre>The iterative function ''h'' is passed two synthetic args in the front: (''k'') iteration number (0-indexed) and (''acc'') "accumulator" from previous iterations.
Both the base and iterative cases can be parameterized by values <math>x_2, x_3, ..., x_k</math>.

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

=== Minimization ===
<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_2, g \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[g]</math>
|2
|<math>RepSucc[g] := R(S, C(g, P^3_2))</math>
|<math>|g| + 4</math>
|<math>\lambda x\ y. g^x(y+1)</math>
|-
|Iteration on first arg
|<math>RepFirst[f]</math>
|2
|<math>RepFirst[f] := R^2(S, R^3(f, P^4_2))</math>
|<math>|f| + 4</math>
|<math>\lambda x\ y. (\lambda z. f(z, y))^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>C^0(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
|≥ 32
|<math>M^{0}(C^{1}(R^{2}(P^{1}_{1}, R^{3}(P^{2}_{1}, C^{4}(R^{2}(P^{1}_{1}, P^{3}_{1}), P^{4}_{2}, P^{4}_{1}))), P^{1}_{1}, S))</math>
|Shawn Ligocki [https://discord.com/channels/960643023006490684/1447627603698647303/1499137558695641189 29 Apr 2026]
|
|-
|15
|
|
|
|
|-
|16
|≥ 47
|<math>M(C(R(S, R(P^2_1, R(P^3_2, C(R(S, P^3_1), P^5_3, P^5_2)))), P^1_1, S))</math>
|Shawn Ligocki [https://discord.com/channels/960643023006490684/1447627603698647303/1501347538287067267 5 May 2026]
|
|-
|17
|≥ 2090
|<math>M^0(C^1(R^2(P^1_1, R^3(P^2_1, R^4(R^3(R^2(S, C^3(S, P^3_2)), P^4_1), P^5_2))), P^1_1, S))</math>
|Shawn Ligocki [https://discord.com/channels/960643023006490684/1447627603698647303/1502314241766588468 8 May 2026]
|
|-
|18
|
|
|
|
|-
|19
|
|
|
|
|-
|20
|
|
|
|
|-
|21
|≥ 8,589,934,591
|<math>C(DiagS[RepFirst[DiagRep[RepSucc[S]]]], K[1])</math>
|Shawn Ligocki [https://discord.com/channels/960643023006490684/1447627603698647303/1505396390665130035 16 May 2026]
|
|-
|22
|<math>> 2^{2^{230}}</math>
|<math>C(DiagS[RepFirst[RepSucc[Tri]]], K[1])</math>
|Shawn Ligocki [https://discord.com/channels/960643023006490684/1447627603698647303/1506168696605904946 17 May 2026]
|
|-
|23
|<math>> 2^{2^{2^{81}}}</math>
|<math>C(DiagS[RepFirst[DiagRep[RepSucc[S]]]], K[2])</math>
|Shawn Ligocki 17 May 2026
|
|-
|24
|<math>> 2^{2^{2^{2^{2^{20}}}}}</math>
|<math>C(DiagS[RepFirst[RepSucc[Tri]]], K[2])</math>
|Shawn Ligocki 17 May 2026
|
|-
|...
|
|
|
|
|-
|93
|<math>>f_{\omega+1}(f_\omega(2 \uparrow\uparrow\uparrow 2 \uparrow\uparrow\uparrow 6)) \gg \text{Graham's number}</math>
|
|Shawn Ligocki and Racheline [https://discord.com/channels/960643023006490684/1447627603698647303/1506295959049474068 19 May 2026]
|
|-
|94
|<math>> f_\omega(2 \uparrow\uparrow 2 \uparrow\uparrow 5)</math>
|Omega() from [https://github.com/sligocki/etc/blob/main/gen_rec/mgrf/ack_worm.mgrf ack_worm.mgrf]
|Shawn Ligocki 17 May 2026
|
|-
|95
|
|
|
|
|-
|96
|<math>> f_\omega^2(2 \uparrow\uparrow 2 \uparrow\uparrow 5)</math>
|Omega2() from [https://github.com/sligocki/etc/blob/main/gen_rec/mgrf/ack_worm.mgrf ack_worm.mgrf]
|Shawn Ligocki 18 May 2026
|
|-
|97
|
|
|
|
|-
|98
|<math>> f_\omega^{f_\omega^3(3)}(3) \gg \text{Graham's number}</math>
|Graham() from [https://github.com/sligocki/etc/blob/main/gen_rec/mgrf/ack_worm.mgrf ack_worm.mgrf]
|Shawn Ligocki 17 May 2026
|
|}

== Cryptids ==
So far all [[Cryptids]] have been constructed by hand. None found "in the wild" yet.
{| class="wikitable"
|+Hand Constructed Cryptids
!Size
!Problem
!Authors
!Ref
|-
|49
|[[wikipedia:Brocard's_problem|Brocard's problem]]
|aparker, star and Shawn 3 May 2026
|[https://github.com/sligocki/etc/blob/main/gen_rec/mgrf/brocard.mgrf brocard.mgrf] [https://discord.com/channels/960643023006490684/1447627603698647303/1500605707748245524 Discord]
|-
|56
|5x+1 trajectory of 7
|Shawn Ligocki 2 May 2026
|[https://github.com/sligocki/etc/blob/main/gen_rec/mgrf/collatz.mgrf collatz.mgrf]
|-
|81
|Erdos Ternary Conjecture
|Shawn Ligocki 28 Apr 2026
|[https://github.com/sligocki/etc/blob/main/gen_rec/mgrf/erdos.mgrf erdos.mgrf]
|-
|139
|Antihydra-like problem
|Jacob Mandelson 8 Apr 2026
|[https://discord.com/channels/960643023006490684/1447627603698647303/1491642156295913482 Orig (size 141)] [https://discord.com/channels/960643023006490684/1447627603698647303/1494889866704588983 Size 139]
|}

== Notable Divergent GRF ==

=== Tetrahedral Divisibility ===
The GRF <math>M^{0}(C^{1}(R^{2}(S, R^{3}(P^{2}_{1}, R^{4}(P^{3}_{1}, R^{5}(R^{4}(P^{3}_{3}, P^{5}_{1}), P^{6}_{2})))), S, S))</math> (Size 15) halts iff there exists some n ≥ 1 such that n+3 divides <math>Tetr(n) = \frac{n(n+1)(n+2)}{6}</math>.[https://discord.com/channels/960643023006490684/960643023530762341/1500584497542987776] aparker[https://discord.com/channels/960643023006490684/960643023530762341/1500587569514283098] and star[https://discord.com/channels/960643023006490684/960643023530762341/1500595210919346337] proved that there is no such n, therefore this GRF diverges.

== 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 ==
Most champions are primitive recursive functions. In other words they do not use the minimization combinator M. This fundamentally limits their growth rate. In fact, no primitive recursive function can grow faster than the Ackermann function and we can see that above where the assymtotic growth of the known BBµ bound is Ackermann growth: <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]]

BusyBeaverWiki - User contributions [en]

General Recursive Function