Busy Beaver Function
A function defined as the maximum number of 1s that can appear on the tape when an n-state, two-symbol Turing machine halts; it is uncomputable and grows faster than any computable function.
Timeline (last 90 days)
The busy beaver function BB(n) is defined as the maximum number of 1s that an n-state, two-symbol Turing machine can write when it finally halts.
The busy beaver function is uncomputable; there is no general algorithm to compute BB(n) for arbitrary n.
BB(1)=1, BB(2)=4, BB(3)=6, BB(4)=13。
The value of BB(5) has been determined to be 47176870.
BB(6) is already too large to be written out completely in conventional notation.
If BB(n) could be computed, it could be used to determine whether all n-state Turing machines halt, thereby solving the halting problem.
For any computable function f, there exists some n such that BB(n) > f(n).
BB(10) > Graham's number.
The specific value of BB(10) can never be computed by humans, because computing it would amount to solving an instance of the halting problem.
The core consensus in the HN discussion comments is that BB(10) > Graham's number is a corollary of the standard properties of the busy beaver function, rather than a new unsolved problem.
All Facts (10)
The core consensus in the HN discussion comments is that BB(10) > Graham's number is a corollary of the standard properties of the busy beaver function, rather than a new unsolved problem.
50%UnverifiedThe busy beaver function is uncomputable; there is no general algorithm to compute BB(n) for arbitrary n.
50%UnverifiedBB(1)=1, BB(2)=4, BB(3)=6, BB(4)=13。
50%UnverifiedThe value of BB(5) has been determined to be 47176870.
50%UnverifiedBB(6) is already too large to be written out completely in conventional notation.
50%UnverifiedIf BB(n) could be computed, it could be used to determine whether all n-state Turing machines halt, thereby solving the halting problem.
50%UnverifiedFor any computable function f, there exists some n such that BB(n) > f(n).
50%UnverifiedBB(10) > Graham's number.
50%UnverifiedThe busy beaver function BB(n) is defined as the maximum number of 1s that an n-state, two-symbol Turing machine can write when it finally halts.
50%UnverifiedThe specific value of BB(10) can never be computed by humans, because computing it would amount to solving an instance of the halting problem.
50%