Papers › Turing machines deciders, part I
Turing machines deciders, part I
The bbchallenge Collaboration, Justin Blanchard, Konrad Deka, Nathan Fenner, Tony Guilfoyle, Iijil, Maja Kądziołka, Pavel Kropitz, Shawn Ligocki, Pascal Michel, Mateusz Naściszewski, Tristan Stérin
The archive published only this paper's code-link row. Authors, date and abstract are from arXiv's metadata (CC0), read from the Kaggle arXiv metadata snapshot of 2026-09-12 where its title matched the archive's; the title is the archive's.
The Busy Beaver Challenge (or bbchallenge) aims at collaboratively solving the following conjecture: "S(5) = 47,176,870" [Rad\'o, 1962], [Marxen and Buntrock, 1990], [Aaronson, 2020]. This conjecture says that if a 5-state Turing machine runs for more than 47,176,870 steps without halting, then it will never halt -- starting from the all-0 tape. Proving this conjecture amounts to deciding whether 181,385,789 Turing machines with 5 states halt or not -- starting from the all-0 tape [bbchallenge, 2025]. To do so, we write deciders: programs that take as input a Turing machine and output either HALT, NONHALT, or UNKNOWN. Each decider is specialised in recognising a particular type of non-halting behavior. After two years of work, the Busy Beaver Challenge achieved its goal in July 2024 by delivering a proof of "S(5) = 47,176,870" formalised in Coq [bbchallenge, 2025]. In this document, we present deciders that were developed before the Coq proof and which were mainly not used in the proof; nonetheless, they are relevant techniques for analysing Turing machines. Part II of this work is the decider section of our paper showing "S(5) = 47,176,870" [bbchallenge, 2025], presenting the deciders that were used in the Coq proof.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections