Determination of the fifth Busy Beaver value
2025/09/15 by The bbchallenge Collaboration, Justin Blanchard, Blanchard, Justin +33 · 20 voices · 2 citations
#cs.LO #cs.FL #math.LO
paper · pdf · doi:10.48550/arxiv.2509.12337
Abstract
The Busy Beaver value S(n) is the maximum number of steps that an n-state 2-symbol Turing machine can perform from the all-zero tape before halting. S was historically introduced by Tibor Radó in 1962 as one of the simplest examples of an uncomputable function. We prove that S(5) = 47,176,870 using the Coq proof assistant. The proof enumerates 181,385,789 Turing machines with 5 states and, for each machine, decides whether it halts or not. Our result marks the first determination of a new Busy Beaver value in over 40 years and the first Busy Beaver value ever to be formally verified, attesting to the effectiveness of massively collaborative online research (bbchallenge.org).
Cited by
Discussions
- Determination of the fifth Busy Beaver value [hn, 288 points, 116 comments]
- New word I learned from the BB(5) paper: "probviously" [bsky, 76 points, 2 comments]
- Determination of the fifth Busy Beaver value [lobsters, 40 points, 6 comments]
- This is very cool. arxiv.org/abs/2509.12337 [bsky, 5 points, 1 comments]
- I missed the news that the bbchallenge collaboration have released a preprint on the determination of BB(5): https://arxiv.org/abs/2509.12337 [bsky, 3 points, 1 comments]
- If I am around to see us calculate the 6th Busy Beaver number, I will buy every quantum state in our light cone a round of drinks. arxiv.org/abs/2509.12337 [bsky, 1 points, 0 comments]
- Determination of the fifth Busy Beaver value View Article | Join the HN Conversation Summary of HN discussion 🧵👇 #hacker-news [bsky, 0 points, 1 comments]
- Determination of the fifth Busy Beaver value https://lobste.rs/s/hrq54n #pdf #compsci [bsky, 0 points, 0 comments]
- Determination of the fifth Busy Beaver value https://arxiv.org/abs/2509.12337 (https://news.ycombinator.com/item?id=45273999) [bsky, 0 points, 0 comments]
- ⚡ Hackernews Top story: Determination of the fifth Busy Beaver value [bsky, 0 points, 0 comments]
- Determination of the fifth Busy Beaver value https://arxiv.org/abs/2509.12337 (http://news.ycombinator.com/item?id=45273999) [bsky, 0 points, 0 comments]
- Determination of the fifth Busy Beaver value https://arxiv.org/abs/2509.12337 (http://news.ycombinator.com/item?id=45273999) [bsky, 0 points, 0 comments]
- https://arxiv.org/abs/2509.12337 この論文は、Busy Beaver問題の5番目の値の決定に関するものです。 Busy Beaver問題は計算理論における未解決問題の一つです。 論文では、具体的な数値の特定方法について解説していると考えられます。 [bsky, 0 points, 0 comments]
- get up, loser, a new busy beaver just dropped: arxiv.org/abs/2509.12337 [bsky, 0 points, 0 comments]
- This research is cool because it has empirical traction on the halting problem. arxiv.org/abs/2509.12337 [bsky, 0 points, 0 comments]
- Determination of the fifth Busy Beaver value https://arxiv.org/abs/2509.12337 (https://news.ycombinator.com/item?id=45273999) [bsky, 0 points, 0 comments]
- Determination of the fifth Busy Beaver value [bsky, 0 points, 0 comments]
- Determination of the fifth Busy Beaver value #HackerNews https://arxiv.org/abs/2509.12337 [bsky, 0 points, 0 comments]
- Determination of the fifth Busy Beaver value https://arxiv.org/abs/2509.12337 https://news.ycombinator.com/item?id=45273999 [bsky, 0 points, 0 comments]
- Determination of the fifth Busy Beaver value https://arxiv.org/abs/2509.12337 [bsky, 0 points, 0 comments]
Related