BB(5): Difference between revisions
Jump to navigation
Jump to search
No edit summary |
|||
| Line 1: | Line 1: | ||
'''BB(5)''' refers to the 5<sup>th</sup> value of the [[Busy Beaver function]]. In 1989, the [[5-state busy beaver winner]] was found: a 5-state [[Turing machine]] halting after 47,176,870 giving the lower bound BB(5) ≥ 47,176,870<ref>H. Marxen and J. Buntrock. Attacking the Busy Beaver 5. Bulletin of the EATCS, 40, pages 247-251, February 1990. https://turbotm.de/~heiner/BB/mabu90.html</ref>. | '''BB(5)''' refers to the 5<sup>th</sup> value of the [[Busy Beaver function]]. In 1989, the [[5-state busy beaver winner]] was found: a 5-state [[Turing machine]] halting after 47,176,870 giving the lower bound BB(5) ≥ 47,176,870<ref name=":0">H. Marxen and J. Buntrock. Attacking the Busy Beaver 5. Bulletin of the EATCS, 40, pages 247-251, February 1990. https://turbotm.de/~heiner/BB/mabu90.html</ref>. | ||
In 2024, BB(5) = 47,176,870 was proven by the [[bbchallenge.org]] massively collaborative research project. | In 2024, BB(5) = 47,176,870 was proven by the [[bbchallenge.org]] massively collaborative research project. | ||
| Line 5: | Line 5: | ||
== History == | == 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]]. | ||
=== Finding the 5-state winner === | |||
* In 1964, Green establishes Σ(5) ≥ 17.<ref>Pascal Michel. (2022). The Busy Beaver Competition: a historical survey. https://bbchallenge.org/~pascal.michel/ha#tm52 </ref> | * In 1964, Green establishes Σ(5) ≥ 17.<ref>Pascal Michel. (2022). The Busy Beaver Competition: a historical survey. https://bbchallenge.org/~pascal.michel/ha#tm52 </ref> | ||
| Line 10: | Line 12: | ||
* In 1973, Weimann establishes S(5) ≥ 556 and Σ(5) ≥ 40. | * In 1973, Weimann establishes S(5) ≥ 556 and Σ(5) ≥ 40. | ||
* In 1983, the [https://docs.bbchallenge.org/other/lud20.pdf Dortmund contest]is organised to find new 5-state champions, winner is Uwe Schult who established S(5) ≥ 134,467 and Σ(5) ≥ 501. | * In 1983, the [https://docs.bbchallenge.org/other/lud20.pdf Dortmund contest]is organised to find new 5-state champions, winner is Uwe Schult who established S(5) ≥ 134,467 and Σ(5) ≥ 501. | ||
=== Proving that the winner is actually the winner === | |||
* In 2003, Georgi Georgiev (Skelet) publishes a list of [[Skelet's 43 holdouts]], based on [[bbfind]], a collection of [[Deciders]] written in Pascal<ref>https://skelet.ludost.net/bb/index.html</ref>. | |||
== References == | == References == | ||
Revision as of 16:39, 14 June 2024
BB(5) refers to the 5th value of the Busy Beaver function. In 1989, the 5-state busy beaver winner was found: a 5-state Turing machine halting after 47,176,870 giving the lower bound BB(5) ≥ 47,176,870[1].
In 2024, BB(5) = 47,176,870 was proven by the bbchallenge.org massively collaborative research project.
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.
Finding the 5-state winner
- In 1964, Green establishes Σ(5) ≥ 17.[2]
- In 1972, Lynn establishes S(5) ≥ 435 and Σ(5) ≥ 22.
- In 1973, Weimann establishes S(5) ≥ 556 and Σ(5) ≥ 40.
- In 1983, the Dortmund contestis organised to find new 5-state champions, winner is Uwe Schult who established S(5) ≥ 134,467 and Σ(5) ≥ 501.
Proving that the winner is actually the winner
- In 2003, Georgi Georgiev (Skelet) publishes a list of Skelet's 43 holdouts, based on bbfind, a collection of Deciders written in Pascal[3].
References
- ↑ H. Marxen and J. Buntrock. Attacking the Busy Beaver 5. Bulletin of the EATCS, 40, pages 247-251, February 1990. https://turbotm.de/~heiner/BB/mabu90.html
- ↑ Pascal Michel. (2022). The Busy Beaver Competition: a historical survey. https://bbchallenge.org/~pascal.michel/ha#tm52
- ↑ https://skelet.ludost.net/bb/index.html