BB(2) - Revision history

Sligocki: Link Tibor Radó

2025-12-04T21:36:15Z

Link Tibor Radó

← Older revision		Revision as of 21:36, 4 December 2025
Line 1:		Line 1:
	The 2-state 2-symbol Busy Beaver problem '''BB(2)''' was solved by Tibor Radó using pencil and paper and announced in his seminal Busy Beaver paper, On Non-Computable Functions.<ref>Rado, T. (1962), On Non-Computable Functions. Bell System Technical Journal, 41: 877-884. <nowiki>https://doi.org/10.1002/j.1538-7305.1962.tb00480.x</nowiki></ref>		The 2-state 2-symbol Busy Beaver problem '''BB(2)''' was solved by [[Tibor Radó]] using pencil and paper and announced in his seminal Busy Beaver paper, On Non-Computable Functions.<ref>Rado, T. (1962), On Non-Computable Functions. Bell System Technical Journal, 41: 877-884. <nowiki>https://doi.org/10.1002/j.1538-7305.1962.tb00480.x</nowiki></ref>

	== Deciders ==		== Deciders ==

Polygon: Added link to "champions"

2025-08-11T10:23:00Z

Added link to "champions"

← Older revision		Revision as of 10:23, 11 August 2025
Line 5:		Line 5:

	== Champions ==		== Champions ==
	S(2)<ref>Same as BB(2).</ref> = 6 and there are 5 shift champions in [[TNF]]:		S(2)<ref>Same as BB(2).</ref> = 6 and there are 5 shift [[champions]] in [[TNF]]:

	* {{TM\|1RB1LB_1LA1RZ\|halt}} leaves 4 ones (the ones champion)		* {{TM\|1RB1LB_1LA1RZ\|halt}} leaves 4 ones (the ones champion)

Polygon: Prepare Category move of BB-domains

2025-08-10T23:41:34Z

Prepare Category move of BB-domains

← Older revision		Revision as of 23:41, 10 August 2025
Line 80:		Line 80:
	== References ==		== References ==
	<references />		<references />
	[[Category:BB ~~Domain~~]]		[[Category:BB Domains]]

Zcy: /* Champions */ Add cite to claim S(2)=BB(2) Origin: S(2)=6 Now:S(2)[Cite: Same as BB(2)]=6.

2025-05-24T04:30:18Z

Champions: Add cite to claim S(2)=BB(2) Origin: S(2)=6 Now:S(2)[Cite: Same as BB(2)]=6.

← Older revision		Revision as of 04:30, 24 May 2025
Line 5:		Line 5:

	== Champions ==		== Champions ==
	S(2) = 6 and there are 5 shift champions in [[TNF]]:		S(2)<ref>Same as BB(2).</ref> = 6 and there are 5 shift champions in [[TNF]]:

	* {{TM\|1RB1LB_1LA1RZ\|halt}} leaves 4 ones (the ones champion)		* {{TM\|1RB1LB_1LA1RZ\|halt}} leaves 4 ones (the ones champion)

Sligocki: Add domain category

2025-02-06T18:27:10Z

Add domain category

← Older revision		Revision as of 18:27, 6 February 2025
Line 80:		Line 80:
	== References ==		== References ==
	<references />		<references />
			[[Category:BB Domain]]

DF476: /* Translated Cyclers */ I ended up using the preperiod definition from the wiki (which should be more genuine from a deciders perspective)

2024-11-18T06:13:42Z

Translated Cyclers: I ended up using the preperiod definition from the wiki (which should be more genuine from a deciders perspective)

← Older revision		Revision as of 06:13, 18 November 2024
Line 21:		Line 21:

	=== Halting TMs ===		=== Halting TMs ===
	The following TMs are ordered by the number of steps before halting and by the number of ones left in the tape (represented by the left and right numbers, respectively).		The following TMs are ordered by the number of steps before halting and by the number of ones left in the tape (represented by the left and right numbers, respectively):

	<pre>		<pre>
Line 42:		Line 42:

	=== Cyclers ===		=== Cyclers ===
	The following TMs are ordered by the period and preperiod (represented by the left and right numbers, respectively).		The following TMs are ordered by the period and preperiod (represented by the left and right numbers, respectively):

	<pre>		<pre>
Line 51:		Line 51:

	=== Translated Cyclers ===		=== Translated Cyclers ===
	<pre>		The following TMs are classified (in order of appereance) by their period, the preperiod and by the offset (in absolute value):<pre>
	1RB1RA_1LA--- Translated Cycler		1RB1RA_1LA--- Translated Cycler 4 4 2
	~~1RB1RA_0LA~~--- Translated Cycler		1RB1LB_0LA--- Translated Cycler 4 3 2
	~~1RB1LB_0LA~~--- Translated Cycler		1RB0RA_1LA--- Translated Cycler 4 0 2
	~~1RB0RA_1LA~~--- Translated Cycler		1RB0LB_0LA--- Translated Cycler 4 0 2
	~~1RB0RA_0LA~~--- Translated Cycler		1RB1RA_0LA--- Translated Cycler 3 1 1
	~~1RB0LB_0LA~~--- Translated Cycler		1RB---_1LB1RB Translated Cycler 3 1 1
	~~1RB0LA_1LA~~--- Translated Cycler		1RB---_0LB1RA Translated Cycler 3 1 1
	~~1RB0LA_0LA~~--- Translated Cycler		1RB---_0LB0LA Translated Cycler 3 0 1
	~~1RB---_1RB~~--- Translated Cycler		1RB0RA_0LA--- Translated Cycler 3 0 1
	~~1RB---_1RA~~--- Translated Cycler		1RB0LA_1LA--- Translated Cycler 3 0 1
	~~1RB~~---~~_1LB1RB~~ Translated Cycler		1RB0LA_0LA--- Translated Cycler 3 0 1
	1RB---~~_1LB1LB~~ Translated Cycler		1RB---_1LB0LA Translated Cycler 3 0 1
	1RB---~~_1LB0RB~~ Translated Cycler		1RB---_0LB0RA Translated Cycler 3 0 1
	1RB---~~_1LB0LB Translated Cycler~~		1RB---_1RA--- Translated Cycler 2 2 2
	~~1RB~~---~~_1LB0LA~~ Translated Cycler		1RB---_0RA--- Translated Cycler 2 1 2
	1RB---~~_0RB~~--- Translated Cycler		1RB---_1LB0RB Translated Cycler 1 5 1
	1RB---~~_0RA~~--- Translated Cycler		1RB---_1LB0LB Translated Cycler 1 4 1
	1RB---~~_0LB1RA~~ Translated Cycler		1RB---_0LB1LB Translated Cycler 1 4 1
	1RB---~~_0LB1LB~~ Translated Cycler		1RB---_1LB1LB Translated Cycler 1 3 1
	1RB---_0LB0RB Translated Cycler		1RB---_0LB0RB Translated Cycler 1 3 1
	1RB---~~_0LB0RA~~ Translated Cycler		1RB---_0LB0LB Translated Cycler 1 3 1
	1RB---~~_0LB0LB~~ Translated Cycler		1RB---_0RB--- Translated Cycler 1 2 1
	1RB---~~_0LB0LA~~ Translated Cycler		1RB---_1RB--- Translated Cycler 1 1 1

	</pre>		</pre>

	== References ==		== References ==
	<references />		<references />

Sligocki: Continue to use consistent distinction between cyclers and TC. Fix preperiod of one TM.

2024-11-15T15:41:51Z

Continue to use consistent distinction between cyclers and TC. Fix preperiod of one TM.

← Older revision		Revision as of 15:41, 15 November 2024
Line 2:		Line 2:

	== Deciders ==		== Deciders ==
	The only ~~decider~~ needed to prove BB(2) is [[~~Translated Cycler~~]]. All 26 infinite TMs listed below are either Translated Cyclers or Cyclers.		The only deciders needed to prove BB(2) are [[cycler]] and [[translated cycler]] deciders. All 26 infinite TMs listed below are either Translated Cyclers or Cyclers.

	== Champions ==		== Champions ==
Line 18:		Line 18:

	== Enumeration ==		== Enumeration ==
	In [[TNF-1RB]] there are exactly 41 2-state, 2-symbol [[TM]]s, of which 15 halt and 26 never halt. The last group can be divided to 3 [[~~Cycler\|cyclers~~]] and 23 [[~~Translated Cycler\|~~translated ~~cyclers~~]].		In [[TNF-1RB]] there are exactly 41 2-state, 2-symbol [[TM]]s, of which 15 halt and 26 never halt. The last group can be divided to 3 [[cycler]]s and 23 [[translated cycler]]s.

	=== Halting TMs ===		=== Halting TMs ===
Line 45:		Line 45:

	<pre>		<pre>
	1RB0RB_0LA--- Cycler 4 1		1RB0RB_0LA--- Cycler 4 0
	1RB1RB_0LA--- Cycler 2 1		1RB1RB_0LA--- Cycler 2 1
	1RB---_0LB1RB Cycler 2 1		1RB---_0LB1RB Cycler 2 1

DF476: /* Enumeration */

2024-11-15T15:03:19Z

Enumeration

← Older revision		Revision as of 15:03, 15 November 2024
Line 2:		Line 2:

	== Deciders ==		== Deciders ==
	The only decider needed to prove BB(2) is [[Translated Cycler]]. All 26 infinite TMs listed below are Translated Cyclers.		The only decider needed to prove BB(2) is [[Translated Cycler]]. All 26 infinite TMs listed below are either Translated Cyclers or Cyclers.

	== Champions ==		== Champions ==
Line 18:		Line 18:

	== Enumeration ==		== Enumeration ==
			In [[TNF-1RB]] there are exactly 41 2-state, 2-symbol [[TM]]s, of which 15 halt and 26 never halt. The last group can be divided to 3 [[Cycler\|cyclers]] and 23 [[Translated Cycler\|translated cyclers]].

	=== Halting TMs ===		=== Halting TMs ===
	~~In [[TNF-1RB]] there~~ are ~~exactly 41 2-state, 2-symbol [[TM]]s, of which 15 halt (the left digit represents~~ the number of steps before halting and ~~the right one~~ the number of ones ~~that are~~ left ~~out~~ in the tape):		The following TMs are ordered by the number of steps before halting and by the number of ones left in the tape (represented by the left and right numbers, respectively).

	<pre>		<pre>
Line 40:		Line 41:
	</pre>		</pre>

	=== ~~Non-Halting TMs~~ ===		=== Cyclers ===
	~~There~~ are ~~also 26 machines that never halt:~~		The following TMs are ordered by the period and preperiod (represented by the left and right numbers, respectively).

	<pre>		<pre>
	1RB1RB_0LA---		1RB0RB_0LA--- Cycler 4 1
	~~1RB1RA_1LA~~---		1RB1RB_0LA--- Cycler 2 1
	~~1RB1RA_0LA~~---		1RB---_0LB1RB Cycler 2 1
	~~1RB1LB_0LA~~---		</pre>
	~~1RB0RB_0LA~~---
	1RB0RA_1LA---		=== Translated Cyclers ===
	1RB0RA_0LA---		<pre>
	1RB0LB_0LA---		1RB1RA_1LA--- Translated Cycler
	1RB0LA_1LA---		1RB1RA_0LA--- Translated Cycler
	1RB0LA_0LA---		1RB1LB_0LA--- Translated Cycler
	1RB---_1RB---		1RB0RA_1LA--- Translated Cycler
	1RB---_1RA---		1RB0RA_0LA--- Translated Cycler
	1RB---_1LB1RB		1RB0LB_0LA--- Translated Cycler
	1RB---_1LB1LB		1RB0LA_1LA--- Translated Cycler
	1RB---_1LB0RB		1RB0LA_0LA--- Translated Cycler
	1RB---_1LB0LB		1RB---_1RB--- Translated Cycler
	1RB---_1LB0LA		1RB---_1RA--- Translated Cycler
	1RB---_0RB---		1RB---_1LB1RB Translated Cycler
	1RB---_0RA---		1RB---_1LB1LB Translated Cycler
	~~1RB---_0LB1RB~~		1RB---_1LB0RB Translated Cycler
	1RB---_0LB1RA		1RB---_1LB0LB Translated Cycler
	1RB---_0LB1LB		1RB---_1LB0LA Translated Cycler
	1RB---_0LB0RB		1RB---_0RB--- Translated Cycler
	1RB---_0LB0RA		1RB---_0RA--- Translated Cycler
	1RB---_0LB0LB		1RB---_0LB1RA Translated Cycler
	1RB---_0LB0LA		1RB---_0LB1LB Translated Cycler
			1RB---_0LB0RB Translated Cycler
			1RB---_0LB0RA Translated Cycler
			1RB---_0LB0LB Translated Cycler
			1RB---_0LB0LA Translated Cycler
	</pre>		</pre>

	== References ==		== References ==
	<references />		<references />

C7X: Confused me for a second, thinking there were 41 TMs that have the behavior of the champion /* Halting TMs */

2024-11-15T00:27:21Z

Confused me for a second, thinking there were 41 TMs that have the behavior of the champion Halting TMs

← Older revision		Revision as of 00:27, 15 November 2024
Line 20:		Line 20:

	=== Halting TMs ===		=== Halting TMs ===
	In [[TNF-1RB]] there are exactly 41 ~~BB(~~2) [[TM]]s of which 15 halt (the left digit represents the number of steps before halting and the right one the number of ones that are left out in the tape):		In [[TNF-1RB]] there are exactly 41 2-state, 2-symbol [[TM]]s, of which 15 halt (the left digit represents the number of steps before halting and the right one the number of ones that are left out in the tape):

	<pre>		<pre>

DF476 at 19:10, 14 November 2024

2024-11-14T19:10:42Z

← Older revision		Revision as of 19:10, 14 November 2024
Line 18:		Line 18:

	== Enumeration ==		== Enumeration ==
	In [[TNF-1RB]] there are exactly 41 BB(2) [[TM]]s of which 15 halt:
			=== Halting TMs ===
			In [[TNF-1RB]] there are exactly 41 BB(2) [[TM]]s of which 15 halt (the left digit represents the number of steps before halting and the right one the number of ones that are left out in the tape):

	<pre>		<pre>
Line 38:		Line 40:
	</pre>		</pre>

	~~and~~ 26 ~~are infinite~~:		=== Non-Halting TMs ===
			There are also 26 machines that never halt:

	<pre>		<pre>