General Recursive Function - Revision history

Azerty: /* Utilizing Minimization */ Updated because some champions that use minimization have been discovered.

2026-05-01T18:44:47Z

Utilizing Minimization: Updated because some champions that use minimization have been discovered.

← Older revision		Revision as of 18:44, 1 May 2026
Line 432:		Line 432:

	== Utilizing Minimization ==		== 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>.		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:		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:

Sligocki: Add definition of size back

2026-04-30T15:10:42Z

Add definition of size back

← Older revision		Revision as of 15:10, 30 April 2026
Line 5:		Line 5:
	'''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>		'''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.		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 ==		== Definition ==
Line 23:		Line 23:
	* 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.		* 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.		* 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.

			=== 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 ===		=== Primitive Recursion ===

Sligocki: /* Champions */ BBµ(14) ≥ 32!

2026-04-30T02:58:01Z

Champions: BBµ(14) ≥ 32!

← Older revision		Revision as of 02:58, 30 April 2026
Line 201:		Line 201:
	\|-		\|-
	\|14		\|14
	\|≥ 13		\|≥ 32
	\|<math>M^{0}(C^{1}(R^{2}(P^{1}_{1}, R^{3}(P^{2}_{1}, C^{4}(R^{2}(S, P^{3}_{1}), P^{4}_{2}, P^{4}_{4}))), P^{1}_{1}, S))</math>		\|<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]		\|Shawn Ligocki [https://discord.com/channels/960643023006490684/1447627603698647303/1499137558695641189 29 Apr 2026]
	\|		\|

Sligocki: /* Champions */ New BBµ(14) champ again

2026-04-29T23:40:46Z

Champions: New BBµ(14) champ again

← Older revision		Revision as of 23:40, 29 April 2026
Line 201:		Line 201:
	\|-		\|-
	\|14		\|14
	\|≥ 9		\|≥ 13
	\|<math>M(C(R(P^~~1_1~~, R(P^~~2_1~~, C(R(S, P^~~3_1~~), P^~~4_2~~, P^~~4_1~~))), P^~~1_1~~, S))</math>		\|<math>M^{0}(C^{1}(R^{2}(P^{1}_{1}, R^{3}(P^{2}_{1}, C^{4}(R^{2}(S, P^{3}_{1}), P^{4}_{2}, P^{4}_{4}))), P^{1}_{1}, S))</math>
	\|Shawn Ligocki [https://discord.com/channels/960643023006490684/1447627603698647303/1499137558695641189 29 Apr 2026]		\|Shawn Ligocki [https://discord.com/channels/960643023006490684/1447627603698647303/1499137558695641189 29 Apr 2026]
	\|		\|
Line 213:		Line 213:
	\|-		\|-
	\|16		\|16
	\|~~≥ 10~~		\|
	\|~~<math>C(AckDiag[0, Plus[2]], K^0[2])</math>~~		\|
	\|~~Shawn Ligocki [https://discord.com/channels/960643023006490684/1447627603698647303/1492394919728517160 11 Apr 2026]~~		\|
	\|		\|
	\|-		\|-

Sligocki: /* Champions */ New BBµ(14) ≥ 9 champion

2026-04-29T21:16:01Z

Champions: New BBµ(14) ≥ 9 champion

← Older revision		Revision as of 21:16, 29 April 2026
Line 201:		Line 201:
	\|-		\|-
	\|14		\|14
	\|≥ 7		\|≥ 9
	\|<math>C(~~AckDiag[0~~, S], K^~~0[2]~~)</math>		\|<math>M(C(R(P^1_1, R(P^2_1, C(R(S, P^3_1), P^4_2, P^4_1))), P^1_1, S))</math>
	\|Shawn Ligocki [https://discord.com/channels/960643023006490684/1447627603698647303/~~1492246885329670184 10~~ Apr 2026]		\|Shawn Ligocki [https://discord.com/channels/960643023006490684/1447627603698647303/1499137558695641189 29 Apr 2026]
	\|		\|
	\|-		\|-
	\|15		\|15
	\|~~≥ 7~~		\|
	\|~~<math>K^0[7]</math>~~		\|
	\|		\|
	\|		\|

Sligocki: /* Champions */

2026-04-22T18:07:55Z

Champions

← Older revision		Revision as of 18:07, 22 April 2026
Line 308:		Line 308:
	\|		\|
	\|-		\|-
	\|		\|...
	\|		\|
	\|		\|
Line 344:		Line 344:
	\|		\|
	\|-		\|-
	\|		\|...
	\|		\|
	\|		\|
Line 362:		Line 362:
	\|		\|
	\|-		\|-
	\|		\|96
	\|		\|
	\|		\|
Line 374:		Line 374:
	\|		\|
	\|-		\|-
	\|		\|98
	\|		\|
	\|		\|

Sligocki: /* Champions */ Add Omega champions

2026-04-22T18:04:32Z

Champions: Add Omega champions

@@ Line 130: / Line 130: @@
 |2
 |= 0
-|<math>M(Z^1), M(P^1_1), C(Z^0)</math>
+|<math>M^0(Z^1), M^0(P^1_1), C^0(Z^0)</math>
+|
 |Shawn Ligocki [https://discord.com/channels/960643023006490684/1447627603698647303/1447693296322215976 8 Dec 2025] By hand
@@ Line 348: / Line 348: @@
+|
+|
+|
 |-
 |100
-|> Graham's number
+|<math>> f_{\omega+1}(f_\omega^2(10^{13})) \gg \text{Graham's number}</math>
-|See [https://github.com/sligocki/etc/blob/main/gen_rec/src/example_ack.rs example_ack.rs]
+|Graham() from [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]
+|

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

2026-04-18T05:07:05Z

Macros: Fix typos in AckDiag2 macro def'n.

← Older revision		Revision as of 05:07, 18 April 2026
Line 98:		Line 98:
	\|-		\|-
	\| rowspan="2" \|Ackermann iteration		\| rowspan="2" \|Ackermann iteration
	\|<math>AckDiag2[f]</math>		\|<math>AckDiag2[n,f]</math>
	\|2		\|2
	\|<math>\begin{array}{lcl}		\|<math>\begin{array}{lcl}
	AckDiag2[0,f] & := & RepSucc[f] \\		AckDiag2[0,f] & := & RepSucc[f] \\
	AckDiag2[n+1,f] & := & DiagRep[~~Ack~~[n,f]]		AckDiag2[n+1,f] & := & DiagRep[AckDiag2[n,f]]
	\end{array}</math>		\end{array}</math>
	\|<math>5n + 4 + \|f\|</math>		\|<math>5n + 4 + \|f\|</math>

JLM: /* Cryptids */ Shrinkage

2026-04-18T02:46:08Z

Cryptids: Shrinkage

← Older revision		Revision as of 02:46, 18 April 2026
Line 358:		Line 358:

	== Cryptids ==		== Cryptids ==
	Jacob Mandelson constructed a size 141 [[Cryptid]] on 8 Apr 2026.[https://discord.com/channels/960643023006490684/1447627603698647303/~~1491642156295913482~~]		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 ==		== Macro Bounds ==

Sligocki: Add stub about Cryptid

2026-04-17T20:27:21Z

Add stub about Cryptid

← Older revision		Revision as of 20:27, 17 April 2026
Line 356:		Line 356:
	\|		\|
	\|}		\|}

			== Cryptids ==
			Jacob Mandelson constructed a size 141 [[Cryptid]] on 8 Apr 2026.[https://discord.com/channels/960643023006490684/1447627603698647303/1491642156295913482]

	== Macro Bounds ==		== Macro Bounds ==