BB(3) - Revision history

Sligocki: Link Shen Lin

2025-12-04T17:39:08Z

Link Shen Lin

← Older revision		Revision as of 17:39, 4 December 2025
Line 1:		Line 1:
	The 3-state 2-symbol Busy Beaver problem '''BB(3)''' was proven by Shen Lin in his 1963 doctoral dissertation<ref>Shen Lin. 1963. Computer studies of Turing machine problems. PhD dissertation. Ohio State University. https://etd.ohiolink.edu/acprod/odb_etd/etd/r/1501/10?clear=10&p10_accession_num=osu1486554418657614</ref> and republished in 1965.<ref>Lin, Shen; Radó, Tibor (April 1965). "Computer Studies of Turing Machine Problems". ''Journal of the ACM''. '''12''' (2): 196–212. https://doi.org/10.1145/321264.321270</ref> Allen Brady independently proved it in his 1964 PhD dissertation.<ref>Allen Brady. 1964. Solutions of Restricted Cases of the Halting Problem Applied to the Determination of Particular Values of a Non-Computable Function. PhD dissertation. Oregon State University. https://ir.library.oregonstate.edu/downloads/6q182n74x</ref>		The 3-state 2-symbol Busy Beaver problem '''BB(3)''' was proven by [[Shen Lin]] in his 1963 doctoral dissertation<ref>Shen Lin. 1963. Computer studies of Turing machine problems. PhD dissertation. Ohio State University. https://etd.ohiolink.edu/acprod/odb_etd/etd/r/1501/10?clear=10&p10_accession_num=osu1486554418657614</ref> and republished in 1965.<ref>Lin, Shen; Radó, Tibor (April 1965). "Computer Studies of Turing Machine Problems". ''Journal of the ACM''. '''12''' (2): 196–212. https://doi.org/10.1145/321264.321270</ref> Allen Brady independently proved it in his 1964 PhD dissertation.<ref>Allen Brady. 1964. Solutions of Restricted Cases of the Halting Problem Applied to the Determination of Particular Values of a Non-Computable Function. PhD dissertation. Oregon State University. https://ir.library.oregonstate.edu/downloads/6q182n74x</ref>

	== Techniques ==		== Techniques ==

Int-y1: edit cps link

2025-08-25T08:27:12Z

edit cps link

← Older revision		Revision as of 08:27, 25 August 2025
Line 2:		Line 2:

	== Techniques ==		== Techniques ==
	In order to prove BB(3), Lin discovered [[Translated Cycler]]s (which he called "partial recurrence") and described the first algorithm for proving them infinite. Translated cycler (with cycler) deciders decide all except 63 TNF-1RB BB(3) TMs. Those last 63 are all decided by [[Closed Position Set ~~(CPS)~~]] augmented with fixed history 1 (each symbol remembers the transition which wrote it).		In order to prove BB(3), Lin discovered [[Translated Cycler]]s (which he called "partial recurrence") and described the first algorithm for proving them infinite. Translated cycler (with cycler) deciders decide all except 63 TNF-1RB BB(3) TMs. Those last 63 are all decided by [[Closed Position Set]] augmented with fixed history 1 (each symbol remembers the transition which wrote it).

	== Champions ==		== Champions ==

Polygon: Added link to "champions"

2025-08-11T10:50:00Z

Added link to "champions"

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

	== Champions ==		== Champions ==
	S(3) = 21 and there is only one shift champion (in [[TNF]]):		S(3) = 21 and there is only one shift [[champion]] (in [[TNF]]):

	* {{TM\|1RB1RZ_1LB0RC_1LC1LA\|halt}} leaves 5 ones		* {{TM\|1RB1RZ_1LB0RC_1LC1LA\|halt}} leaves 5 ones

Polygon: Prepare Category move of BB-domains

2025-08-10T23:42:58Z

Prepare Category move of BB-domains

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

Sligocki: /* Techniques */ Note how TC + CPS is all you need for BB(3).

2025-04-29T01:56:35Z

Techniques: Note how TC + CPS is all you need for BB(3).

← Older revision		Revision as of 01:56, 29 April 2025
Line 2:		Line 2:

	== Techniques ==		== Techniques ==
	In order to prove BB(3), Lin discovered [[Translated Cycler]]s (which he called "partial recurrence") and described the first algorithm for proving them infinite.		In order to prove BB(3), Lin discovered [[Translated Cycler]]s (which he called "partial recurrence") and described the first algorithm for proving them infinite. Translated cycler (with cycler) deciders decide all except 63 TNF-1RB BB(3) TMs. Those last 63 are all decided by [[Closed Position Set (CPS)]] augmented with fixed history 1 (each symbol remembers the transition which wrote it).

	== Champions ==		== Champions ==

Sligocki: Add domain category

2025-02-06T18:27:46Z

Add domain category

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

DF376: Updated the templates

2024-08-13T11:10:36Z

Updated the templates

← Older revision		Revision as of 11:10, 13 August 2024
Line 7:		Line 7:
	S(3) = 21 and there is only one shift champion (in [[TNF]]):		S(3) = 21 and there is only one shift champion (in [[TNF]]):

	* {{TM\|1RB1RZ_1LB0RC_1LC1LA}} leaves 5 ones		* {{TM\|1RB1RZ_1LB0RC_1LC1LA\|halt}} leaves 5 ones

	Σ(3) = 6 and there are 5 ones champions (in TNF):		Σ(3) = 6 and there are 5 ones champions (in TNF):

	* {{TM\|1RB1RZ_0RC1RB_1LC1LA}} runs for 14 steps		* {{TM\|1RB1RZ_0RC1RB_1LC1LA\|halt}} runs for 14 steps
	* {{TM\|1RB1RC_1LC1RZ_1RA0LB}} runs for 13 steps		* {{TM\|1RB1RC_1LC1RZ_1RA0LB\|halt}} runs for 13 steps
	* {{TM\|1RB1LC_1LA1RB_1LB1RZ}} runs for 13 steps		* {{TM\|1RB1LC_1LA1RB_1LB1RZ\|halt}} runs for 13 steps
	* {{TM\|1RB1RA_1LC1RZ_1RA1LB}} runs for 12 steps		* {{TM\|1RB1RA_1LC1RZ_1RA1LB\|halt}} runs for 12 steps
	* {{TM\|1RB1LC_1RC1RZ_1LA0LB}} runs for 11 steps		* {{TM\|1RB1LC_1RC1RZ_1LA0LB\|halt}} runs for 11 steps
	BB(3) is notable for being the only known size where none of the shift champions are also ones champions.		BB(3) is notable for being the only known size where none of the shift champions are also ones champions.

Sligocki: /* Champions */ Note no shared champions

2024-07-12T04:17:20Z

Champions: Note no shared champions

← Older revision		Revision as of 04:17, 12 July 2024
Line 7:		Line 7:
	S(3) = 21 and there is only one shift champion (in [[TNF]]):		S(3) = 21 and there is only one shift champion (in [[TNF]]):

	* {{TM\|1RB1RZ_1LB0RC_1LC1LA}}		* {{TM\|1RB1RZ_1LB0RC_1LC1LA}} leaves 5 ones

	Σ(3) = 6 and there are 5 ones champions (in TNF):		Σ(3) = 6 and there are 5 ones champions (in TNF):

	* {{TM\|1RB1RZ_0RC1RB_1LC1LA}}		* {{TM\|1RB1RZ_0RC1RB_1LC1LA}} runs for 14 steps
	* {{TM\|1RB1RC_1LC1RZ_1RA0LB}}		* {{TM\|1RB1RC_1LC1RZ_1RA0LB}} runs for 13 steps
	* {{TM\|1RB1LC_1LA1RB_1LB1RZ}}		* {{TM\|1RB1LC_1LA1RB_1LB1RZ}} runs for 13 steps
	* {{TM\|1RB1RA_1LC1RZ_1RA1LB}}		* {{TM\|1RB1RA_1LC1RZ_1RA1LB}} runs for 12 steps
	* {{TM\|1RB1LC_1RC1RZ_1LA0LB}}		* {{TM\|1RB1LC_1RC1RZ_1LA0LB}} runs for 11 steps
			BB(3) is notable for being the only known size where none of the shift champions are also ones champions.

	== Enumeration ==		== Enumeration ==

Sligocki: Add some longest running halters

2024-07-12T03:43:32Z

Add some longest running halters

@@ Line 1: / Line 1: @@
 The 3-state 2-symbol Busy Beaver problem '''BB(3)''' was proven by Shen Lin in his 1963 doctoral dissertation<ref>Shen Lin. 1963. Computer studies of Turing machine problems. PhD dissertation. Ohio State University. https://etd.ohiolink.edu/acprod/odb_etd/etd/r/1501/10?clear=10&p10_accession_num=osu1486554418657614</ref> and republished in 1965.<ref>Lin, Shen; Radó, Tibor (April 1965). "Computer Studies of Turing Machine Problems". ''Journal of the ACM''. '''12''' (2): 196–212. https://doi.org/10.1145/321264.321270</ref> Allen Brady independently proved it in his 1964 PhD dissertation.<ref>Allen Brady. 1964. Solutions of Restricted Cases of the Halting Problem Applied to the Determination of Particular Values of a Non-Computable Function. PhD dissertation. Oregon State University. https://ir.library.oregonstate.edu/downloads/6q182n74x</ref>
 == Champions ==
@@ Line 14: / Line 17: @@
 * {{TM|1RB1LC_1RC1RZ_1LA0LB}}
-== Deciders ==
+== Enumeration ==
-In order to prove BB(3), Lin discovered [[Translated Cycler]]s (which he called "partial recurrence") and described the first algorithm for proving them infinite.
+In [[TNF-1RB]] there are exactly 4057 BB(3) TMs of which 1379 halt. The top longest running TMs are:<pre>
 == References ==
 <references />

Sligocki: partial recurrence

2024-07-12T03:34:16Z

partial recurrence

← Older revision		Revision as of 03:34, 12 July 2024
Line 15:		Line 15:

	== Deciders ==		== Deciders ==
	In order to prove BB(3), Lin discovered [[Translated Cycler]]s and described the first algorithm for proving them infinite.		In order to prove BB(3), Lin discovered [[Translated Cycler]]s (which he called "partial recurrence") and described the first algorithm for proving them infinite.

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

← Older revision		Revision as of 11:10, 13 August 2024
Line 7:		Line 7:
	S(3) = 21 and there is only one shift champion (in [[TNF]]):		S(3) = 21 and there is only one shift champion (in [[TNF]]):

	* {{TM\|1RB1RZ_1LB0RC_1LC1LA}} leaves 5 ones		* {{TM\|1RB1RZ_1LB0RC_1LC1LA\|halt}} leaves 5 ones

	Σ(3) = 6 and there are 5 ones champions (in TNF):		Σ(3) = 6 and there are 5 ones champions (in TNF):

	* {{TM\|1RB1RZ_0RC1RB_1LC1LA}} runs for 14 steps		* {{TM\|1RB1RZ_0RC1RB_1LC1LA\|halt}} runs for 14 steps
	* {{TM\|1RB1RC_1LC1RZ_1RA0LB}} runs for 13 steps		* {{TM\|1RB1RC_1LC1RZ_1RA0LB\|halt}} runs for 13 steps
	* {{TM\|1RB1LC_1LA1RB_1LB1RZ}} runs for 13 steps		* {{TM\|1RB1LC_1LA1RB_1LB1RZ\|halt}} runs for 13 steps
	* {{TM\|1RB1RA_1LC1RZ_1RA1LB}} runs for 12 steps		* {{TM\|1RB1RA_1LC1RZ_1RA1LB\|halt}} runs for 12 steps
	* {{TM\|1RB1LC_1RC1RZ_1LA0LB}} runs for 11 steps		* {{TM\|1RB1LC_1RC1RZ_1LA0LB\|halt}} runs for 11 steps
	BB(3) is notable for being the only known size where none of the shift champions are also ones champions.		BB(3) is notable for being the only known size where none of the shift champions are also ones champions.