BB(4)
BB(4) refers to the 4th value of the Busy Beaver function.
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 1965, Allen Brady proves that S(4) ≥ 84 and Σ(4) ≥ 11.[1] (TODO: the abstract says "or ≥ 12 using a different stopping convention")
- In 1966, Allen Brady conjectures Σ(4) = 13 and S(4) = 106.[2]
- In 1974, Allen Brady proves that S(4) = 107.[3] (better source needed)
- In 1983, Allen Brady publishes the proof that Σ(4) = 13 and S(4) = 107. [4]
References
- ↑ 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
- ↑ Brady, A. H. (1966). The Conjectured Highest Scoring Machines for Rado's Σ(k) for the Value k = 4. https://ieeexplore.ieee.org/document/4038890
- ↑ https://www.quantamagazine.org/amateur-mathematicians-find-fifth-busy-beaver-turing-machine-20240702/
- ↑ 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/