Is it possible to prove which Busy Beaver number is the highest that can be determined?
9
110Ṁ90
2200
37%
chance

Low Busy Beaver numbers can be computed. But at some point we must become unable to determine further BB numbers, since the function is an uncomputable function. (Assuming the physical Church-Turing thesis is true.)

We can get lower bounds on this crossover point by computing low numbers; we know up to BB(4), with some promising progress made on 5. And we can get upper bounds as well; for example Adam Yedidia built a 7918 state Turing machine whose behavior is independent of ZFC. Can we ever know the exact value of the crossover point? A BB(n) such that BB(n) can be known with certainty, but BB(n+1) cannot.

For "can be known with certainty", I'll for now use the definition "we know a specific algorithm that prints the number in binary and then halts". This definition is open to revision as needed.

This market resolves to YES if it's proven possible, and to NO if it's proven impossible. It resolves N/A if it's proven that we can't have such a proof, and if none of those are provable, it stays open forever.

Get
Ṁ1,000
to start trading!
© Manifold Markets, Inc.TermsPrivacy