Non-halting Turing machine - Revision history

Polygon: /* Translated cycler period */ Added BBP(6)

2026-11-04T12:46:43Z

Translated cycler period: Added BBP(6)

← Older revision		Revision as of 12:46, 4 November 2026
Line 329:		Line 329:
	\|{{TM\|1LC1LE_---1LD_1RD0LD_1LA1RE_0LB0RC\|non_halt}}		\|{{TM\|1LC1LE_---1LD_1RD0LD_1LA1RE_0LB0RC\|non_halt}}
	\|about <math>5.42 \times 10^{51}</math>		\|about <math>5.42 \times 10^{51}</math>
			\|-
			\|BBP(6,2)
			\|<math>> 2.4154\times 10^{2695}</math><ref>https://discord.com/channels/960643023006490684/1239205785913790465/1567517097360363621</ref>
			\|{{TM\|1RB1LC_1LA1RB_1LD0LA_1RE1RD_---1RF_1LB0RF\|non_halt}}, {{TM\|1RB1LA_1LA1RC_1RD0RB_1LE1LD_---1LF_1RA0LF\|non_halt}}
			\|<math>5.8\times 10^{4502} , 4.0\times 10^{1384}</math>
	\|-		\|-
	\|BBP(3,3)		\|BBP(3,3)

Polygon: /* Translated cycler period */ added Skelet 1 for BBP(5)

2026-11-03T14:39:13Z

Translated cycler period: added Skelet 1 for BBP(5)

← Older revision		Revision as of 14:39, 3 November 2026
Line 324:		Line 324:
	\|{{TM\|1RB0LA_0RC1RD_1LD0RB_1LA1RB\|non_halt}}		\|{{TM\|1RB0LA_0RC1RD_1LD0RB_1LA1RB\|non_halt}}
	\|5,248,647,886		\|5,248,647,886
			\|-
			\|BBP(5,2)
			\|≥ 8,468,569,863<ref>Shawn Ligocki, "[https://www.sligocki.com/2023/03/13/skelet-1-infinite.html Skelet #1 is infinite ... we think]". Blog post, March 2023. Accessed 3 November 2026.</ref>
			\|{{TM\|1LC1LE_---1LD_1RD0LD_1LA1RE_0LB0RC\|non_halt}}
			\|about <math>5.42 \times 10^{51}</math>
	\|-		\|-
	\|BBP(3,3)		\|BBP(3,3)

Polygon: /* Translated cycler preperiod */ fixed weird looking reference

2026-11-03T13:21:41Z

Translated cycler preperiod: fixed weird looking reference

← Older revision		Revision as of 13:21, 3 November 2026
Line 296:		Line 296:
	\|≥ 205,770,076,433,044,242,247,860		\|≥ 205,770,076,433,044,242,247,860
	\|{{TM\|1RB2LA1RA1LB_0LB2RB3RB1LA\|non_halt}}		\|{{TM\|1RB2LA1RA1LB_0LB2RB3RB1LA\|non_halt}}
	\|1<ref>[https://discord.com/channels/960643023006490684/1385498968011575366/1450955870971367535]</ref>		\|1<ref>https://discord.com/channels/960643023006490684/1385498968011575366/1450955870971367535</ref>
	\|}		\|}

Loader3229 at 15:52, 29 September 2026

2026-09-29T15:52:10Z

Show changes

Tlonuqbar: mention of independent nonhalting machines

2026-02-27T06:18:32Z

mention of independent nonhalting machines

← Older revision		Revision as of 06:18, 27 February 2026
Line 3:		Line 3:
	The crux of the [[Busy Beaver function\|Busy Beaver]] problem, of finding BB(''n'', ''k'') for a given ''n'' and ''k'', is to prove that all non-halting Turing machines with ''n'' states and ''k'' symbols are, in fact, non-halting.		The crux of the [[Busy Beaver function\|Busy Beaver]] problem, of finding BB(''n'', ''k'') for a given ''n'' and ''k'', is to prove that all non-halting Turing machines with ''n'' states and ''k'' symbols are, in fact, non-halting.

	The zoology of non-halting Turing machines is extremely rich. See [[Translated cycler]], [[Bouncer]], [[Bell]], [[Counter]], [[Fractal]], [[Shift overflow counter]], [[Shift overflow bouncer counter]] for a sample. In this page, we provide a detailed zoology for some low numbers of states and symbols.		The zoology of non-halting Turing machines is extremely rich. See [[Translated cycler]], [[Bouncer]], [[Bell]], [[Counter]], [[Fractal]], [[Shift overflow counter]], [[Shift overflow bouncer counter]], [[Logical independence]] for a sample. In this page, we provide a detailed zoology for some low numbers of states and symbols.

	== Zoology ==		== Zoology ==
Line 243:		Line 243:
	\|style="text-align: center"\|[[File:1RB1LC 1RD0RB 1LA0LC 0LA0RD.png\|frameless\|300x300px]]		\|style="text-align: center"\|[[File:1RB1LC 1RD0RB 1LA0LC 0LA0RD.png\|frameless\|300x300px]]
	\|}		\|}
			Additionally, some machines have been created that are non-halting if and only if certain [[wikipedia:Formal_system\|formal systems]] are consistent. By [[wikipedia:Gödel's_incompleteness_theorems\|Gödel's incompleteness theorems]], if the corresponding theory is consistent, it cannot prove that the machine is non-halting even though it is, and therefore if the machine has length n, the value BB(n) cannot be determined by the formal theory. See [[logical independence]] for more info.

	== Records ==		== Records ==

Polygon: Added Category:Zoology and Category:Functions

2026-02-20T14:49:03Z

Added Category:Zoology and Category:Functions

← Older revision		Revision as of 14:49, 20 February 2026
Line 336:		Line 336:

	== References ==		== References ==

			[[Category:Zoology]]
			[[Category:Functions]]

Polygon: /* Records */ organised champions into tables and added BBS(5,2)

2025-12-28T16:24:45Z

Records: organised champions into tables and added BBS(5,2)

@@ Line 248: / Line 248: @@
 === Translated cycler preperiod ===
 BBS(n,m) = maximum translated cycler preperiod among n-state, m-symbol TMs.
-* BBS(1,m) = 0: {{TM|0RA---}} and {{TM|1RA---}}, note that any transitions other than A0 are unreachable.
-* BBS(2,2) ≥ 9 (status unknown): {{TM|1RB0LB_1LA0RB}}
+BBS(1,m) = 0: {{TM|0RA---}} and {{TM|1RA---}}, note that any transitions other than A0 are unreachable.
-* BBS(3,2) = 101 (proven): {{TM|1RB1LB_0RC0LA_1LC0LA}} (period = 24)
+{| class="wikitable"
-* BBS(4,2) ≥ 119,120,230,102 (current champion): {{TM|1RB1LC_0LA1RD_0RB0LC_1LA0RD}} (period = 966,716)
+|+
-* BBS(2,3) ≥ 165<ref>Nick Drozd. [https://nickdrozd.github.io/2021/02/14/blanking-beavers.html Blanking Beavers]</ref> (current champion): {{TM|1RB0LA---_1LB2LA0RB}} (period = 55)
+!Domain
-* BBS(3,3) > 10 ↑↑ 6 (current champion): {{TM|1RB0LB2LA_1LA0RC0LB_2RC2RB0LC}} (period = 1)
+!Preperiod
-* BBS(4,3) > <math>10 \uparrow^{4} 4</math> (current champion): {{TM|1RB1RD1LC_2LB1RB1LC_1LB1LA1LD_0RB2RA2RD}} (period = 1)
+!Champions
-* BBS(2,4) ≥  205,770,076,433,044,242,247,860 (current champion): {{TM|1RB2LA1RA1LB_0LB2RB3RB1LA}} (period = 1)<ref>[https://discord.com/channels/960643023006490684/1385498968011575366/1450955870971367535]</ref>
+!Period
 === Translated cycler period ===
 BBP(n,m) = maximum translated cycler period among n-state, m-symbol TMs.
-* BBP(1,m) = 1: {{TM|0RA---}} and {{TM|1RA---}}, note that any transitions other than A0 are unreachable.
-* BBP(2,2) > 9 (status unknown): {{TM|1RB0RB_1LB1RA}}
+BBP(1,m) = 1: {{TM|0RA---}} and {{TM|1RA---}}, note that any transitions other than A0 are unreachable.
-* BBP(3,2) = 92 (proven): {{TM|1RB0LA_0RC1LA_1LC0RB}} (preperiod = 0)
+{| class="wikitable"
-* BBP(4,2) ≥ 212,081,736 (current champion): {{TM|1RB0LA_0RC1RD_1LD0RB_1LA1RB}} (preperiod = 5,248,647,886)
+|+
-* BBP(3,3) ≥ 1,195 (current champion): {{TM|1RB2RC1LC_0RC0RB1LA_2LA2RC1LB}} (preperiod = 15)
+!Domain
-* BBP(2,4) ≥ 33,209,131 (current champion): {{TM|1RB0RA3LB1RB_2LA0LB1RA2RB}} (preperiod = 63,141,841)
+!Period
 == References ==

Polygon: /* Translated cycler preperiod */ added BBS(4,3)

2025-12-28T15:39:31Z

Translated cycler preperiod: added BBS(4,3)

← Older revision		Revision as of 15:39, 28 December 2025
Line 254:		Line 254:
	* BBS(2,3) ≥ 165<ref>Nick Drozd. [https://nickdrozd.github.io/2021/02/14/blanking-beavers.html Blanking Beavers]</ref> (current champion): {{TM\|1RB0LA---_1LB2LA0RB}} (period = 55)		* BBS(2,3) ≥ 165<ref>Nick Drozd. [https://nickdrozd.github.io/2021/02/14/blanking-beavers.html Blanking Beavers]</ref> (current champion): {{TM\|1RB0LA---_1LB2LA0RB}} (period = 55)
	* BBS(3,3) > 10 ↑↑ 6 (current champion): {{TM\|1RB0LB2LA_1LA0RC0LB_2RC2RB0LC}} (period = 1)		* BBS(3,3) > 10 ↑↑ 6 (current champion): {{TM\|1RB0LB2LA_1LA0RC0LB_2RC2RB0LC}} (period = 1)
			* BBS(4,3) > <math>10 \uparrow^{4} 4</math> (current champion): {{TM\|1RB1RD1LC_2LB1RB1LC_1LB1LA1LD_0RB2RA2RD}} (period = 1)
	* BBS(2,4) ≥ 205,770,076,433,044,242,247,860 (current champion): {{TM\|1RB2LA1RA1LB_0LB2RB3RB1LA}} (period = 1)<ref>[https://discord.com/channels/960643023006490684/1385498968011575366/1450955870971367535]</ref>		* BBS(2,4) ≥ 205,770,076,433,044,242,247,860 (current champion): {{TM\|1RB2LA1RA1LB_0LB2RB3RB1LA}} (period = 1)<ref>[https://discord.com/channels/960643023006490684/1385498968011575366/1450955870971367535]</ref>

Polygon: Added references section

2025-12-26T12:23:01Z

Added references section

← Older revision		Revision as of 12:23, 26 December 2025
Line 264:		Line 264:
	* BBP(3,3) ≥ 1,195 (current champion): {{TM\|1RB2RC1LC_0RC0RB1LA_2LA2RC1LB}} (preperiod = 15)		* BBP(3,3) ≥ 1,195 (current champion): {{TM\|1RB2RC1LC_0RC0RB1LA_2LA2RC1LB}} (preperiod = 15)
	* BBP(2,4) ≥ 33,209,131 (current champion): {{TM\|1RB0RA3LB1RB_2LA0LB1RA2RB}} (preperiod = 63,141,841)		* BBP(2,4) ≥ 33,209,131 (current champion): {{TM\|1RB0RA3LB1RB_2LA0LB1RA2RB}} (preperiod = 63,141,841)

			== References ==

Polygon: /* Translated cycler preperiod */ added BBS(2,3) champion

2025-12-26T12:22:37Z

Translated cycler preperiod: added BBS(2,3) champion

← Older revision		Revision as of 12:22, 26 December 2025
Line 252:		Line 252:
	* BBS(3,2) = 101 (proven): {{TM\|1RB1LB_0RC0LA_1LC0LA}} (period = 24)		* BBS(3,2) = 101 (proven): {{TM\|1RB1LB_0RC0LA_1LC0LA}} (period = 24)
	* BBS(4,2) ≥ 119,120,230,102 (current champion): {{TM\|1RB1LC_0LA1RD_0RB0LC_1LA0RD}} (period = 966,716)		* BBS(4,2) ≥ 119,120,230,102 (current champion): {{TM\|1RB1LC_0LA1RD_0RB0LC_1LA0RD}} (period = 966,716)
			* BBS(2,3) ≥ 165<ref>Nick Drozd. [https://nickdrozd.github.io/2021/02/14/blanking-beavers.html Blanking Beavers]</ref> (current champion): {{TM\|1RB0LA---_1LB2LA0RB}} (period = 55)
	* BBS(3,3) > 10 ↑↑ 6 (current champion): {{TM\|1RB0LB2LA_1LA0RC0LB_2RC2RB0LC}} (period = 1)		* BBS(3,3) > 10 ↑↑ 6 (current champion): {{TM\|1RB0LB2LA_1LA0RC0LB_2RC2RB0LC}} (period = 1)
	* BBS(2,4) ≥ 205,770,076,433,044,242,247,860 (current champion): {{TM\|1RB2LA1RA1LB_0LB2RB3RB1LA}} (period = 1)<~~sup~~>[https://discord.com/channels/960643023006490684/1385498968011575366/1450955870971367535]</~~sup~~>		* BBS(2,4) ≥ 205,770,076,433,044,242,247,860 (current champion): {{TM\|1RB2LA1RA1LB_0LB2RB3RB1LA}} (period = 1)<ref>[https://discord.com/channels/960643023006490684/1385498968011575366/1450955870971367535]</ref>

	=== Translated cycler period ===		=== Translated cycler period ===