BB(4) - Revision history

HelpMe: hmm maybe we don't need a table for this one idk

2026-09-25T15:46:36Z

hmm maybe we don't need a table for this one idk

@@ Line 4: / Line 4: @@
 == History ==
-In this Section, we use Radó's original S (number of steps) and Σ (number of ones on the final tape) notations; see [[Busy Beaver Functions]].
+In this section, we use Radó's original S (number of steps) and Σ (number of ones on the final tape) notations; see [[Busy Beaver Functions]].
+{| class="wikitable mw-collapsible"
-* In 1965, Allen Brady proved that S(4) ≥ 84 and Σ(4) ≥ 11.<ref name=":0">Brady, A. H. (1965). Solutions of restricted cases of the halting problem applied to the determination of particular values of a non-computable function. https://ir.library.oregonstate.edu/concern/graduate_thesis_or_dissertations/zk51vk21c</ref> (TODO: the abstract says "or ≥ 12 using a different stopping convention")
+! colspan="6" |Timeline of lower bounds established for Σ(4) and S(4)
-* In 1966, Allen Brady conjectured Σ(4) = 13 and S(4) = 107 (He said S(4) = 106, seemingly basing it upon a slightly different version of S function).<ref name=":1">Brady, A. H. (1966). The Conjectured Highest Scoring Machines for Rado's Σ(k) for the Value k = 4. https://ieeexplore.ieee.org/document/4038890 </ref>
+|-
-* In 1974, Allen Brady proved that S(4) = 107.<ref name=":2">https://www.quantamagazine.org/amateur-mathematicians-find-fifth-busy-beaver-turing-machine-20240702/</ref> (better source needed)
+!Month of discovery
-* In 1983, Allen Brady published the proof that Σ(4) = 13 and S(4) = 107. <ref name=":3">Brady, A. H. (1983). The determination of the value of Rado’s noncomputable function Σ(k) for four-state Turing machines. https://www.ams.org/journals/mcom/1983-40-162/S0025-5718-1983-0689479-6/</ref>  Some holdouts were not rigorously handled by the proof:  ''"All of the remaining holdouts were examined by means of voluminous printouts of their histories along with some program extracted features. It was determined to the author's satisfaction that none of these machines will ever stop."''<ref name=":0" />
+!Machine
 == Champions ==
@@ Line 18: / Line 61: @@
 Σ(4) = 13 and there are 2 ones champions (in TNF):
-* {{TM|1RB1LB_1LA0LC_1RZ1LD_1RD0RA|halt}} runs 107 steps (the steps champion)
+* {{TM|1RB1LB_1LA0LC_1RZ1LD_1RD0RA|halt}} runs for 107 steps (the steps champion)
-* {{TM|1RB0RC_1LA1RA_1RZ1RD_1LD0LB|halt}} runs 96 steps
+* {{TM|1RB0RC_1LA1RA_1RZ1RD_1LD0LB|halt}} runs for 96 steps
 == Top Halters ==

C1: Another minor grammatical change

2026-07-15T06:36:25Z

Another minor grammatical change

← Older revision		Revision as of 06:36, 15 July 2026
Line 7:		Line 7:

	* In 1965, Allen Brady proved that S(4) ≥ 84 and Σ(4) ≥ 11.<ref name=":0">Brady, A. H. (1965). Solutions of restricted cases of the halting problem applied to the determination of particular values of a non-computable function. https://ir.library.oregonstate.edu/concern/graduate_thesis_or_dissertations/zk51vk21c</ref> (TODO: the abstract says "or ≥ 12 using a different stopping convention")		* In 1965, Allen Brady proved that S(4) ≥ 84 and Σ(4) ≥ 11.<ref name=":0">Brady, A. H. (1965). Solutions of restricted cases of the halting problem applied to the determination of particular values of a non-computable function. https://ir.library.oregonstate.edu/concern/graduate_thesis_or_dissertations/zk51vk21c</ref> (TODO: the abstract says "or ≥ 12 using a different stopping convention")
	* In 1966, Allen Brady conjectured Σ(4) = 13 and S(4) = 107 (He said S(4) = 106, seemingly ~~based~~ upon a slightly different version of S function).<ref name=":1">Brady, A. H. (1966). The Conjectured Highest Scoring Machines for Rado's Σ(k) for the Value k = 4. https://ieeexplore.ieee.org/document/4038890 </ref>		* In 1966, Allen Brady conjectured Σ(4) = 13 and S(4) = 107 (He said S(4) = 106, seemingly basing it upon a slightly different version of S function).<ref name=":1">Brady, A. H. (1966). The Conjectured Highest Scoring Machines for Rado's Σ(k) for the Value k = 4. https://ieeexplore.ieee.org/document/4038890 </ref>
	* In 1974, Allen Brady proved that S(4) = 107.<ref name=":2">https://www.quantamagazine.org/amateur-mathematicians-find-fifth-busy-beaver-turing-machine-20240702/</ref> (better source needed)		* In 1974, Allen Brady proved that S(4) = 107.<ref name=":2">https://www.quantamagazine.org/amateur-mathematicians-find-fifth-busy-beaver-turing-machine-20240702/</ref> (better source needed)
	* In 1983, Allen Brady published the proof that Σ(4) = 13 and S(4) = 107. <ref name=":3">Brady, A. H. (1983). The determination of the value of Rado’s noncomputable function Σ(k) for four-state Turing machines. https://www.ams.org/journals/mcom/1983-40-162/S0025-5718-1983-0689479-6/</ref> Some holdouts were not rigorously handled by the proof: ''"All of the remaining holdouts were examined by means of voluminous printouts of their histories along with some program extracted features. It was determined to the author's satisfaction that none of these machines will ever stop."''<ref name=":0" />		* In 1983, Allen Brady published the proof that Σ(4) = 13 and S(4) = 107. <ref name=":3">Brady, A. H. (1983). The determination of the value of Rado’s noncomputable function Σ(k) for four-state Turing machines. https://www.ams.org/journals/mcom/1983-40-162/S0025-5718-1983-0689479-6/</ref> Some holdouts were not rigorously handled by the proof: ''"All of the remaining holdouts were examined by means of voluminous printouts of their histories along with some program extracted features. It was determined to the author's satisfaction that none of these machines will ever stop."''<ref name=":0" />

C1: A minor grammatical optimization

2026-07-15T06:32:18Z

A minor grammatical optimization

← Older revision		Revision as of 06:32, 15 July 2026
Line 7:		Line 7:

	* In 1965, Allen Brady proved that S(4) ≥ 84 and Σ(4) ≥ 11.<ref name=":0">Brady, A. H. (1965). Solutions of restricted cases of the halting problem applied to the determination of particular values of a non-computable function. https://ir.library.oregonstate.edu/concern/graduate_thesis_or_dissertations/zk51vk21c</ref> (TODO: the abstract says "or ≥ 12 using a different stopping convention")		* In 1965, Allen Brady proved that S(4) ≥ 84 and Σ(4) ≥ 11.<ref name=":0">Brady, A. H. (1965). Solutions of restricted cases of the halting problem applied to the determination of particular values of a non-computable function. https://ir.library.oregonstate.edu/concern/graduate_thesis_or_dissertations/zk51vk21c</ref> (TODO: the abstract says "or ≥ 12 using a different stopping convention")
	* In 1966, Allen Brady conjectured Σ(4) = 13 and S(4) = 107 (He said S(4) = 106, ~~but this seemed to be~~ based upon a slightly different version of S function).<ref name=":1">Brady, A. H. (1966). The Conjectured Highest Scoring Machines for Rado's Σ(k) for the Value k = 4. https://ieeexplore.ieee.org/document/4038890 </ref>		* In 1966, Allen Brady conjectured Σ(4) = 13 and S(4) = 107 (He said S(4) = 106, seemingly based upon a slightly different version of S function).<ref name=":1">Brady, A. H. (1966). The Conjectured Highest Scoring Machines for Rado's Σ(k) for the Value k = 4. https://ieeexplore.ieee.org/document/4038890 </ref>
	* In 1974, Allen Brady proved that S(4) = 107.<ref name=":2">https://www.quantamagazine.org/amateur-mathematicians-find-fifth-busy-beaver-turing-machine-20240702/</ref> (better source needed)		* In 1974, Allen Brady proved that S(4) = 107.<ref name=":2">https://www.quantamagazine.org/amateur-mathematicians-find-fifth-busy-beaver-turing-machine-20240702/</ref> (better source needed)
	* In 1983, Allen Brady published the proof that Σ(4) = 13 and S(4) = 107. <ref name=":3">Brady, A. H. (1983). The determination of the value of Rado’s noncomputable function Σ(k) for four-state Turing machines. https://www.ams.org/journals/mcom/1983-40-162/S0025-5718-1983-0689479-6/</ref> Some holdouts were not rigorously handled by the proof: ''"All of the remaining holdouts were examined by means of voluminous printouts of their histories along with some program extracted features. It was determined to the author's satisfaction that none of these machines will ever stop."''<ref name=":0" />		* In 1983, Allen Brady published the proof that Σ(4) = 13 and S(4) = 107. <ref name=":3">Brady, A. H. (1983). The determination of the value of Rado’s noncomputable function Σ(k) for four-state Turing machines. https://www.ams.org/journals/mcom/1983-40-162/S0025-5718-1983-0689479-6/</ref> Some holdouts were not rigorously handled by the proof: ''"All of the remaining holdouts were examined by means of voluminous printouts of their histories along with some program extracted features. It was determined to the author's satisfaction that none of these machines will ever stop."''<ref name=":0" />

C1: Minor grammatical changes

2026-07-15T06:28:44Z

Minor grammatical changes

← Older revision		Revision as of 06:28, 15 July 2026
Line 6:		Line 6:
	In this Section, we use Radó's original S (number of steps) and Σ (number of ones on the final tape) notations; see [[Busy Beaver Functions]].		In this Section, we use Radó's original S (number of steps) and Σ (number of ones on the final tape) notations; see [[Busy Beaver Functions]].

	* In 1965, Allen Brady ~~proves~~ that S(4) ≥ 84 and Σ(4) ≥ 11.<ref name=":0">Brady, A. H. (1965). Solutions of restricted cases of the halting problem applied to the determination of particular values of a non-computable function. https://ir.library.oregonstate.edu/concern/graduate_thesis_or_dissertations/zk51vk21c</ref> (TODO: the abstract says "or ≥ 12 using a different stopping convention")		* In 1965, Allen Brady proved that S(4) ≥ 84 and Σ(4) ≥ 11.<ref name=":0">Brady, A. H. (1965). Solutions of restricted cases of the halting problem applied to the determination of particular values of a non-computable function. https://ir.library.oregonstate.edu/concern/graduate_thesis_or_dissertations/zk51vk21c</ref> (TODO: the abstract says "or ≥ 12 using a different stopping convention")
	* In 1966, Allen Brady ~~conjectures~~ Σ(4) = 13 and S(4) = 107 (He ~~says~~ S(4) = 106, but this ~~seems~~ to be based upon a slightly different version of S function).<ref name=":1">Brady, A. H. (1966). The Conjectured Highest Scoring Machines for Rado's Σ(k) for the Value k = 4. https://ieeexplore.ieee.org/document/4038890 </ref>		* In 1966, Allen Brady conjectured Σ(4) = 13 and S(4) = 107 (He said S(4) = 106, but this seemed to be based upon a slightly different version of S function).<ref name=":1">Brady, A. H. (1966). The Conjectured Highest Scoring Machines for Rado's Σ(k) for the Value k = 4. https://ieeexplore.ieee.org/document/4038890 </ref>
	* In 1974, Allen Brady ~~proves~~ that S(4) = 107.<ref name=":2">https://www.quantamagazine.org/amateur-mathematicians-find-fifth-busy-beaver-turing-machine-20240702/</ref> (better source needed)		* In 1974, Allen Brady proved that S(4) = 107.<ref name=":2">https://www.quantamagazine.org/amateur-mathematicians-find-fifth-busy-beaver-turing-machine-20240702/</ref> (better source needed)
	* In 1983, Allen Brady ~~publishes~~ the proof that Σ(4) = 13 and S(4) = 107. <ref name=":3">Brady, A. H. (1983). The determination of the value of Rado’s noncomputable function Σ(k) for four-state Turing machines. https://www.ams.org/journals/mcom/1983-40-162/S0025-5718-1983-0689479-6/</ref> Some holdouts were not rigorously handled by the proof: ''"All of the remaining holdouts were examined by means of voluminous printouts of their histories along with some program extracted features. It was determined to the author's satisfaction that none of these machines will ever stop."''<ref name=":0" />		* In 1983, Allen Brady published the proof that Σ(4) = 13 and S(4) = 107. <ref name=":3">Brady, A. H. (1983). The determination of the value of Rado’s noncomputable function Σ(k) for four-state Turing machines. https://www.ams.org/journals/mcom/1983-40-162/S0025-5718-1983-0689479-6/</ref> Some holdouts were not rigorously handled by the proof: ''"All of the remaining holdouts were examined by means of voluminous printouts of their histories along with some program extracted features. It was determined to the author's satisfaction that none of these machines will ever stop."''<ref name=":0" />

	== Champions ==		== Champions ==

Polygon: Added Category:BB(4)

2026-02-28T11:50:47Z

Added Category:BB(4)

← Older revision		Revision as of 11:50, 28 February 2026
Line 53:		Line 53:
	<references />		<references />
	[[Category:BB Domains]]		[[Category:BB Domains]]
			[[Category:BB(4)]]

Polygon: Added link to "champions"

2025-08-11T10:33:31Z

Added link to "champions"

← Older revision		Revision as of 10:33, 11 August 2025
Line 12:		Line 12:

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

	* {{TM\|1RB1LB_1LA0LC_1RZ1LD_1RD0RA\|halt}} leaves 13 ones (a ones champion)		* {{TM\|1RB1LB_1LA0LC_1RZ1LD_1RD0RA\|halt}} leaves 13 ones (a ones champion)

Polygon: Prepare Category move of BB-domains

2025-08-10T23:43:45Z

Prepare Category move of BB-domains

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

Fr tho: Updated introduction for consistency and style fixes

2025-05-17T12:38:40Z

Updated introduction for consistency and style fixes

← Older revision		Revision as of 12:38, 17 May 2025
Line 1:		Line 1:
	The 4-state 2-symbol Busy Beaver problem, '''BB(4)''', refers to the 4<sup>th</sup> value of the [[Busy Beaver function]].		The 4-state, 2-symbol Busy Beaver problem, '''BB(4)''', refers to the 4<sup>th</sup> value of the [[Busy Beaver function]]. In 1983, the 4-state busy beaver winner was found: a 4-state [[Turing machine]] halting after 107 steps giving the lower bound BB(4) ≥ 107.

			In 2024, BB(4) = 107 was officially confirmed by the [[bbchallenge.org]] massively collaborative research project, when a proof for the BB(4) case was added to [[Coq-BB5]] and successfully compiled.<ref>https://github.com/ccz181078/Coq-BB5/blob/main/BB42Theorem.v</ref>

	== History ==		== History ==
Line 8:		Line 10:
	* In 1974, Allen Brady proves that S(4) = 107.<ref name=":2">https://www.quantamagazine.org/amateur-mathematicians-find-fifth-busy-beaver-turing-machine-20240702/</ref> (better source needed)		* In 1974, Allen Brady proves that S(4) = 107.<ref name=":2">https://www.quantamagazine.org/amateur-mathematicians-find-fifth-busy-beaver-turing-machine-20240702/</ref> (better source needed)
	* In 1983, Allen Brady publishes the proof that Σ(4) = 13 and S(4) = 107. <ref name=":3">Brady, A. H. (1983). The determination of the value of Rado’s noncomputable function Σ(k) for four-state Turing machines. https://www.ams.org/journals/mcom/1983-40-162/S0025-5718-1983-0689479-6/</ref> Some holdouts were not rigorously handled by the proof: ''"All of the remaining holdouts were examined by means of voluminous printouts of their histories along with some program extracted features. It was determined to the author's satisfaction that none of these machines will ever stop."''<ref name=":0" />		* In 1983, Allen Brady publishes the proof that Σ(4) = 13 and S(4) = 107. <ref name=":3">Brady, A. H. (1983). The determination of the value of Rado’s noncomputable function Σ(k) for four-state Turing machines. https://www.ams.org/journals/mcom/1983-40-162/S0025-5718-1983-0689479-6/</ref> Some holdouts were not rigorously handled by the proof: ''"All of the remaining holdouts were examined by means of voluminous printouts of their histories along with some program extracted features. It was determined to the author's satisfaction that none of these machines will ever stop."''<ref name=":0" />
	* In 2024, S(4) = 107 was confirmed as part of [[Coq-BB5]]. <ref>https://github.com/ccz181078/Coq-BB5/blob/main/BB42Theorem.v</ref>

	== Champions ==		== Champions ==
Line 21:		Line 22:
	* {{TM\|1RB0RC_1LA1RA_1RZ1RD_1LD0LB\|halt}} runs 96 steps		* {{TM\|1RB0RC_1LA1RA_1RZ1RD_1LD0LB\|halt}} runs 96 steps

	== ~~Enumeration~~ ==		== Top Halters ==
	In [[TNF-1RB]] there are exactly 620,261 BB(4) TMs of which 183,983 halt. The top longest running TMs are:<pre>		In [[TNF-1RB]] there are exactly 620,261 BB(4) TMs of which 183,983 halt. The top 20 longest running TMs are:
	1RB1LB_1LA0LC_1RZ1LD_1RD0RA Halt 107 13		<pre>
	1RB1LD_1LC0RB_1RA1LA_1RZ0LC Halt 97 9		Standard Format Status Steps Σ
	1RB0RC_1LA1RA_1RZ1RD_1LD0LB Halt 96 13		1RB1LB_1LA0LC_1RZ1LD_1RD0RA Halt 107 13
	1RB1LB_0LC0RD_1RZ1LA_1RA0LA Halt 96 6		1RB1LD_1LC0RB_1RA1LA_1RZ0LC Halt 97 9
	1RB1LD_0LC0RC_1LC1LA_1RZ0LA Halt 84 11		1RB0RC_1LA1RA_1RZ1RD_1LD0LB Halt 96 13
	1RB1RZ_1LC0RD_1LA1LB_0LC1RD Halt 83 8		1RB1LB_0LC0RD_1RZ1LA_1RA0LA Halt 96 6
	1RB0RD_1LC0LA_1RA1LB_1RZ0RC Halt 78 12		1RB1LD_0LC0RC_1LC1LA_1RZ0LA Halt 84 11
	1RB1LA_0RC0RD_1LC0LA_1RZ0RC Halt 78 9		1RB1RZ_1LC0RD_1LA1LB_0LC1RD Halt 83 8
	1RB0RD_0RC0RA_1LC0LA_0RB1RZ Halt 75 9		1RB0RD_1LC0LA_1RA1LB_1RZ0RC Halt 78 12
	1RB0RC_1LC1RA_1RZ0LD_1RA1LA Halt 74 8		1RB1LA_0RC0RD_1LC0LA_1RZ0RC Halt 78 9
	1RB1LA_0LA1RC_1RA0RD_1RZ0RB Halt 70 8		1RB0RD_0RC0RA_1LC0LA_0RB1RZ Halt 75 9
	1RB1LC_0RC0RB_0LD0LA_1LA1RZ Halt 69 7		1RB0RC_1LC1RA_1RZ0LD_1RA1LA Halt 74 8
	1RB1LA_1LA1RC_1RZ0RD_0LD1RB Halt 69 7		1RB1LA_0LA1RC_1RA0RD_1RZ0RB Halt 70 8
	1RB1RZ_1LC1RA_0RC0LD_1RD0LB Halt 68 10		1RB1LC_0RC0RB_0LD0LA_1LA1RZ Halt 69 7
	1RB0LB_0RC0RD_1LD1LA_0LA1RZ Halt 68 8		1RB1LA_1LA1RC_1RZ0RD_0LD1RB Halt 69 7
	1RB1LB_0RC1RZ_1LC1LD_0RD0LA Halt 68 7		1RB1RZ_1LC1RA_0RC0LD_1RD0LB Halt 68 10
	1RB0RD_0RC1RZ_1LC0LA_0RA0RB Halt 68 7		1RB0LB_0RC0RD_1LD1LA_0LA1RZ Halt 68 8
	1RB0LD_0RC1LD_1LC0RB_0LA1RZ Halt 67 7		1RB1LB_0RC1RZ_1LC1LD_0RD0LA Halt 68 7
	1RB1LA_1RC0LD_0LA0RC_1RZ1LB Halt 66 7		1RB0RD_0RC1RZ_1LC0LA_0RA0RB Halt 68 7
	1RB1RC_1LC1RD_1RZ0LD_1LA0RA Halt 65 7		1RB0LD_0RC1LD_1LC0RB_0LA1RZ Halt 67 7
	</pre>For the top 1000 halting BB(4) TMs, see: https://github.com/sligocki/busy-beaver/blob/main/Machines/bb/4x2.txt		1RB1LA_1RC0LD_0LA0RC_1RZ1LB Halt 66 7
			1RB1RC_1LC1RD_1RZ0LD_1LA0RA Halt 65 7
			</pre>

			For the top 1000 halting BB(4) TMs, see: https://github.com/sligocki/busy-beaver/blob/main/Machines/bb/4x2.txt

	== References ==		== References ==
	<references />		<references />
	[[Category:BB Domain]]		[[Category:BB Domain]]

Sligocki: Add domain category

2025-02-06T18:31:23Z

Add domain category

← Older revision		Revision as of 18:31, 6 February 2025
Line 46:		Line 46:

	== References ==		== References ==
			<references />
			[[Category:BB Domain]]

Tjligocki: Made introduction more consistent with the BB(2) and BB(3) pages.

2024-08-26T02:52:05Z

Made introduction more consistent with the BB(2) and BB(3) pages.

← Older revision		Revision as of 02:52, 26 August 2024
Line 1:		Line 1:
	'''BB(4)''' refers to the 4<sup>th</sup> value of the [[Busy Beaver function]].		The 4-state 2-symbol Busy Beaver problem, '''BB(4)''', refers to the 4<sup>th</sup> value of the [[Busy Beaver function]].

	== History ==		== History ==