is the largest number of 1's written by a halting -state Turing machine on a tape initially filled with 0's.
The following things come to mind when you look into research in this area, especially the search for BB(5) which was hard but doable:
- it is largely recreational mathematics, i.e. done by non-professionals, a bit like the aperiodic tiling. Humbly, they tend to call their results lemmas
- complex structure emerges from simple rules, leading to a complex classification with a few edge cases, much like the classification of finite simple groups
Bibliography:
Turing machine acceleration refers to using high level understanding of specific properties of specific Turing machines to be able to simulate them much fatser than naively running the simulation as usual.
Acceleration allows one to use simulation to find infinite loops that might be very long, and would not be otherwise spotted without acceleration.
This is for example the case of www.sligocki.com/2023/03/13/skelet-1-infinite.html proof of Skelet machine #1.
Project trying to compute BB(5) once and for all. Notably it has better presentation and organization than any other previous effort, and appears to have grouped everyone who cares about the topic as of the early 2020s.
Very cool initiative!
By 2023, they had basically decided every machine: discuss.bbchallenge.org/t/the-30-to-34-ctl-holdouts-from-bb-5/141
In June 2024 they felt that they had verified the result after a full Coq proof was published:
So now onto BB(6) I guess.
The last value we will likely every know for the busy beaver function! BB(6) is likely completely out of reach forever.
By 2023, it had basically been decided by the The Busy Beaver Challenge as mentioned at: discuss.bbchallenge.org/t/the-30-to-34-ctl-holdouts-from-bb-5/141, pending only further verification. It is going to be one of those highly computational proofs that will be needed to be formally verified for people to finally settle.
As that project beautifully puts it, as of 2023 prior to full resolution, this can be considered the:on the Busy beaver scale.
simplest open problem in mathematics
Best busy beaver machine known since 1989 as of 2023, before a full proof of all 5 state machines had been carried out.
Paper extracted to HTML by Heiner Marxen: turbotm.de/~heiner/BB/mabu90.html
Non formal proof with a program March 2023: www.sligocki.com/2023/03/13/skelet-1-infinite.html Awesome article that describes the proof procedure.
The proof uses Turing machine acceleration to show that Skelet machine #1 is a Translated cycler Turing machine with humongous cycle paramters:
- start between 50-200 M steps, not calculated precisely on the original post
- period: ~8 billion steps
wiki.bbchallenge.org/wiki/Antihydra:
- news.ycombinator.com/item?id=40864949 BB(6), The 6th Busy Beaver Number, is harder than a Collatz-like math problem
- www.reddit.com/r/math/comments/1dubva0/finding_the_6th_busy_beaver_number_%CF%836_aka_bb6_is/ "Finding the 6th busy beaver number (Σ(6), AKA BB(6)) is at least as hard as a hard Collatz-like math problem called Antihydra":
- www.reddit.com/r/compsci/comments/1duc62e/finding_the_6th_busy_beaver_number_%CF%836_aka_bb6_is/
Articles by others on the same topic
There are currently no matching articles.