= Busy beaver scale
The <Busy beaver scale> allows us to gauge the difficulty of proving certain (yet unproven!) mathematical <conjectures>!
To to this, people have reduced certain mathematical problems to deciding the <halting problem> of a specific <Turing machine>.
A good example is perhaps the <Goldbach's conjecture>. We just make a <Turing machine> that successively checks for each even number of it is a sum of two primes by naively looping down and trying every possible pair. Let the machine halt if the check fails. So this machine halts <iff> the <Goldbach's conjecture> is false! See also <Conjecture reduction to a halting problem>.
Therefore, if we were able to compute $BB(n)$, we would be able to prove those conjectures automatically, by letting the machine run up to $BB(n)$, and if it hadn't halted by then, we would know that it would never halt.
Of course, in practice, $BB$ is generally <uncomputable>, so we will never know it. And furthermore, even if it were computable, it would take a lot longer than the age of the universe to compute any of it, so it would be useless.
However, philosophically speaking at least, the number of states of the equivalent <Turing machine> gives us a philosophical idea of the complexity of the problem.
The <busy beaver scale> is likely mostly useless, since we are able to prove that many non-trivial <Turing machines> do halt, often by reducing problems to simpler known cases. But still, it is cute.
But maybe, just maybe, reduction to Turing machine form could be useful. E.g. <The Busy Beaver Challenge> and other attempts to solve <BB(5)> have come up with large number of automated (usually parametrized up to a certain threshold) <Turing machine decider> programs that automatically determine if certain (often large numbers of) Turing machines run forever.
So it it not impossible that after some reduction to a standard <Turing machine> form, some conjecture just gets automatically brute-forced by one of the deciders, this is a path to
Back to article page