General Recursive Function - Revision history

HelpMe: elaborate

2026-10-06T17:25:29Z

elaborate

← Older revision		Revision as of 17:25, 6 October 2026
Line 376:		Line 376:

	== Cryptids ==		== Cryptids ==
	So far all [[Cryptids]] have been constructed by hand~~. None~~ found "in the wild" yet.		So far all [[Cryptids]] have been constructed by hand; no GRFs found in the wild have been categorized as Cryptids yet.
	{\| class="wikitable"		{\| class="wikitable"
	\|+Hand Constructed Cryptids		\|+Hand Constructed Cryptids
Line 395:		Line 395:
	\|-		\|-
	\|81		\|81
	\|~~Erdos Ternary Conjecture~~		\|Erdős ternary conjecture
	\|Shawn Ligocki 28 Apr 2026		\|Shawn Ligocki 28 Apr 2026
	\|[https://github.com/sligocki/etc/blob/main/gen_rec/mgrf/erdos.mgrf erdos.mgrf]		\|[https://github.com/sligocki/etc/blob/main/gen_rec/mgrf/erdos.mgrf erdos.mgrf]
Line 404:		Line 404:
	\|[https://discord.com/channels/960643023006490684/1447627603698647303/1491642156295913482 Orig (size 141)] [https://discord.com/channels/960643023006490684/1447627603698647303/1494889866704588983 Size 139]		\|[https://discord.com/channels/960643023006490684/1447627603698647303/1491642156295913482 Orig (size 141)] [https://discord.com/channels/960643023006490684/1447627603698647303/1494889866704588983 Size 139]
	\|}		\|}
	There is also a size 133 GRF that ~~halts iff there was a counter-example~~ to Fermat's Last Theorem (~~Technically not a Cryptid~~ since FLT has been proven): [https://github.com/sligocki/etc/blob/main/gen_rec/mgrf/fermat.mgrf fermat.mgrf]		There is also a size 133 GRF that searches for counterexamples to Fermat's Last Theorem, halting iff it ever found one (however, since FLT has been [https://www.jstor.org/stable/2118559 proven], this GRF can be shown to be non-terminating, and is therefore not considered a Cryptid): [https://github.com/sligocki/etc/blob/main/gen_rec/mgrf/fermat.mgrf fermat.mgrf]

	== Notable GRF ==		== Notable GRF ==

Sligocki: /* Cryptids */ Fix mistaken typo

2026-10-06T17:00:48Z

Cryptids: Fix mistaken typo

← Older revision		Revision as of 17:00, 6 October 2026
Line 404:		Line 404:
	\|[https://discord.com/channels/960643023006490684/1447627603698647303/1491642156295913482 Orig (size 141)] [https://discord.com/channels/960643023006490684/1447627603698647303/1494889866704588983 Size 139]		\|[https://discord.com/channels/960643023006490684/1447627603698647303/1491642156295913482 Orig (size 141)] [https://discord.com/channels/960643023006490684/1447627603698647303/1494889866704588983 Size 139]
	\|}		\|}
	There is also a size 133 GRF that halts iff there am a counter-example to Fermat's Last Theorem (Technically not a Cryptid since FLT has been proven): [https://github.com/sligocki/etc/blob/main/gen_rec/mgrf/fermat.mgrf fermat.mgrf]		There is also a size 133 GRF that halts iff there was a counter-example to Fermat's Last Theorem (Technically not a Cryptid since FLT has been proven): [https://github.com/sligocki/etc/blob/main/gen_rec/mgrf/fermat.mgrf fermat.mgrf]

	== Notable GRF ==		== Notable GRF ==

HelpMe: notable mathematical functions do not exist in my opinion. mathematics is irrelevant.

2026-10-06T16:59:13Z

notable mathematical functions do not exist in my opinion. mathematics is irrelevant.

← Older revision		Revision as of 16:59, 6 October 2026
Line 404:		Line 404:
	\|[https://discord.com/channels/960643023006490684/1447627603698647303/1491642156295913482 Orig (size 141)] [https://discord.com/channels/960643023006490684/1447627603698647303/1494889866704588983 Size 139]		\|[https://discord.com/channels/960643023006490684/1447627603698647303/1491642156295913482 Orig (size 141)] [https://discord.com/channels/960643023006490684/1447627603698647303/1494889866704588983 Size 139]
	\|}		\|}
	There is also a size 133 GRF that halts iff there ~~was~~ a counter-example to Fermat's Last Theorem (Technically not a Cryptid since FLT has been proven): [https://github.com/sligocki/etc/blob/main/gen_rec/mgrf/fermat.mgrf fermat.mgrf]		There is also a size 133 GRF that halts iff there am a counter-example to Fermat's Last Theorem (Technically not a Cryptid since FLT has been proven): [https://github.com/sligocki/etc/blob/main/gen_rec/mgrf/fermat.mgrf fermat.mgrf]

	== Notable GRF ==		== Notable GRF ==
Line 410:		Line 410:
	=== Unsolved GRFs ===		=== Unsolved GRFs ===
	* Size 16: <code>M(C(R(S, R(C(S, P(2,1)), C(R(P(1,1), P(3,1)), P(4,2), P(4,1)))), P(1,1), S))</code>[https://discord.com/channels/960643023006490684/1447627603698647303/1501444301245382707 Discord] [https://discord.com/channels/960643023006490684/1447627603698647303/1504211320864505947 Discord]		* Size 16: <code>M(C(R(S, R(C(S, P(2,1)), C(R(P(1,1), P(3,1)), P(4,2), P(4,1)))), P(1,1), S))</code>[https://discord.com/channels/960643023006490684/1447627603698647303/1501444301245382707 Discord] [https://discord.com/channels/960643023006490684/1447627603698647303/1504211320864505947 Discord]
			** It is known that if this function returns a value, it must be greater than 499 quadrillion. [https://discord.com/channels/960643023006490684/1447627603698647303/1546666535911821413 Discord]

	=== Solved GRFs ===		=== Solved GRFs ===

Sligocki: /* Primitive Recursive Functions */ Fix typo in function

2026-08-17T16:36:06Z

Primitive Recursive Functions: Fix typo in function

← Older revision		Revision as of 16:36, 17 August 2026
Line 185:		Line 185:
	\|16		\|16
	\|= 10		\|= 10
	\|<code>C(DiagS[RepSucc[Plus[2]]], K[1])</code>		\|<code>C(DiagS[RepSucc[Plus[2]]], K[2])</code>
	\|Shawn Ligocki [https://discord.com/channels/960643023006490684/1447627603698647303/1492394919728517160 11 Apr 2026]		\|Shawn Ligocki [https://discord.com/channels/960643023006490684/1447627603698647303/1492394919728517160 11 Apr 2026]
	\|0		\|0

Sligocki: /* Notable GRF */ Add "hardest min_prf 12" and reclassify Triangular Divisibility as "hardest min_prf 13"

2026-07-18T23:03:35Z

Notable GRF: Add "hardest min_prf 12" and reclassify Triangular Divisibility as "hardest min_prf 13"

@@ Line 413: / Line 413: @@
 === Solved GRFs ===
-==== Triangular Divisibility ====
+==== Hardest Size 12 ====
-The GRF <code>M(C(R(S, R(P(2,1), R(R(P(2,2), P(4,1)), P(5,2)))), P(1,1), P(1,1)))</code> (Size 13) halts iff there exists some n ≥ 1 such that n+2 divides <math>Tri(n) = \frac{n(n+1)}{2}</math>. There is no such n,<sup>[https://discord.com/channels/960643023006490684/1447627603698647303/1527405134857113650]</sup> therefore this GRF diverges.
+This is subjective of course, but it seems like the hardest size 12 M(PRF) holdout is <code>M(R(C(S, Z0), R(S, R(R(S, P(3,1)), P(4,2)))))</code>. Proving it seems requires noticing the pattern that d(x) = x-2 for all x ≥ 3 and proving that it inductively follows that pattern for all future values.<sup>[https://discord.com/channels/960643023006490684/1447627603698647303/1508151420258484354]</sup><pre>
 ==== Tetrahedral Divisibility ====

Sligocki: /* Cryptids */ Mention fermat.mgrf

2026-07-17T17:40:10Z

Cryptids: Mention fermat.mgrf

← Older revision		Revision as of 17:40, 17 July 2026
Line 404:		Line 404:
	\|[https://discord.com/channels/960643023006490684/1447627603698647303/1491642156295913482 Orig (size 141)] [https://discord.com/channels/960643023006490684/1447627603698647303/1494889866704588983 Size 139]		\|[https://discord.com/channels/960643023006490684/1447627603698647303/1491642156295913482 Orig (size 141)] [https://discord.com/channels/960643023006490684/1447627603698647303/1494889866704588983 Size 139]
	\|}		\|}
			There is also a size 133 GRF that halts iff there was a counter-example to Fermat's Last Theorem (Technically not a Cryptid since FLT has been proven): [https://github.com/sligocki/etc/blob/main/gen_rec/mgrf/fermat.mgrf fermat.mgrf]

	== Notable GRF ==		== Notable GRF ==

Sligocki: /* M(PRF) */ All min_prf 13 holdouts proven by hand

2026-07-16T20:12:33Z

M(PRF): All min_prf 13 holdouts proven by hand

← Older revision		Revision as of 20:12, 16 July 2026
Line 252:		Line 252:
	\|-		\|-
	\|12		\|12
	\|5		\|= 5
	\|<code>C(K[5])</code>		\|<code>C(K[5])</code>
	\|		\|
Line 258:		Line 258:
	\|-		\|-
	\|13		\|13
	\|≥ 6		\|= 6
	\|<code>K[6]</code>		\|<code>K[6]</code>
	\|		\|
	\|15		\|Deciders: 15
			All proven by hand
	\|-		\|-
	\|14		\|14

Sligocki: /* Solved GRFs */ Add Triangular Divisibility (size 13) example

2026-07-16T20:07:47Z

Solved GRFs: Add Triangular Divisibility (size 13) example

← Older revision		Revision as of 20:07, 16 July 2026
Line 410:		Line 410:

	=== Solved GRFs ===		=== Solved GRFs ===

			==== Triangular Divisibility ====
			The GRF <code>M(C(R(S, R(P(2,1), R(R(P(2,2), P(4,1)), P(5,2)))), P(1,1), P(1,1)))</code> (Size 13) halts iff there exists some n ≥ 1 such that n+2 divides <math>Tri(n) = \frac{n(n+1)}{2}</math>. There is no such n,<sup>[https://discord.com/channels/960643023006490684/1447627603698647303/1527405134857113650]</sup> therefore this GRF diverges.

	==== Tetrahedral Divisibility ====		==== Tetrahedral Divisibility ====

Sligocki: /* Chaotic size 15 */ Define %<

2026-07-09T20:41:00Z

Chaotic size 15: Define %<

← Older revision		Revision as of 20:41, 9 July 2026
Line 439:		Line 439:
	e := R(P(1,1), d) [arity 2, size 11, PRF, used={1,2}]		e := R(P(1,1), d) [arity 2, size 11, PRF, used={1,2}]
	M(C(e, S, P(1,1))) [arity 0, size 15]		M(C(e, S, P(1,1))) [arity 0, size 15]
	</pre>Racheline proved this diverges.<sup>[https://discord.com/channels/960643023006490684/1447627603698647303/1508961266490937536]</sup> The key here is that <code>e(n+1, n) = d(n, y, n)</code> for some y (the last step of the recursion) and for all y <code>d(n, y, n) ≠ 0</code> since:<pre>		</pre>(where <code>a %< b</code> is <code>a</code> if a ≥ 0 and <code>a % b</code> if a < 0)

			Racheline proved this diverges.<sup>[https://discord.com/channels/960643023006490684/1447627603698647303/1508961266490937536]</sup> The key here is that <code>e(n+1, n) = d(n, y, n)</code> for some y (the last step of the recursion) and for all y <code>d(n, y, n) ≠ 0</code> since:<pre>
	d(n, 0, n) = 1		d(n, 0, n) = 1
	d(n, y+1, n) = y+1		d(n, y+1, n) = y+1

Sligocki: /* M(PRF) */ BBµ(17) ≥ 58471

2026-07-08T03:29:16Z

M(PRF): BBµ(17) ≥ 58471

← Older revision		Revision as of 03:29, 8 July 2026
Line 282:		Line 282:
	\|-		\|-
	\|17		\|17
	\|≥ ~~2090~~		\|≥ 58,471
	\|<~~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~~>		\|<code>M(C(R(P(1,1),R(R(S,R(R(S,R(Z2,P(4,1))),P(4,2))),P(4,2))),S,P(1,1)))</code>
	\|Shawn Ligocki [https://discord.com/channels/960643023006490684/1447627603698647303/~~1502314241766588468 8 May~~ 2026]		\|Shawn Ligocki [https://discord.com/channels/960643023006490684/1447627603698647303/1521327240732737536 29 Jun 2026]
	\|19,862		\|19,862
	\|-		\|-
	\|18		\|18
	\|~~≥ 2090~~		\|
	\|~~C^0(size 17 champ)~~		\|
	\|		\|
	\|93,738		\|93,738
	\|-		\|-
	\|19		\|19
	\|~~≥ 13,867~~		\|
	\|~~<code>M(R(C(S, Z0), R(C(S, S), R(P(2,1), C(R(S, R(P(2,1), P(4,1))), P(4,4), P(4,2))))))</code>~~		\|
	\|~~Shawn Ligocki [https://discord.com/channels/960643023006490684/1447627603698647303/1519579483617755316 25 Jun 2026]~~		\|
	\|1,419,487		\|1,419,487
	\|-		\|-