The busy beaver game aims to find the terminating program of a given size that produces the most output possible. In particular, the nth busy beaver is the turing machine with n states and alphabet {0,1}, that writes the most 1s to a tape initially containing all zeros.
The busy beaver function BB(n) quantifies the maximum number of 1s that a busy beaver turing machine with n states could write to the tape. This function is noncomputable, as opposed to a computable function where there are explicit, unambiguous steps to compute it. In other words, BB(n) is very difficult to evaluate!
The implications of evaluating this function is that we can use it as a new approach to solve open mathematical problems. For example there is a 27 state turing machine that halts if and only if goldbachs conjecture is false. If we knew what the value of BB(27) was, we can simply run the goldbach machine until either it halts, or the number of 1s on the tape exceeds BB(27). In the first case, Goldbachs Conjecture is false since that is how the machine is constructed. In the second case, we know that BB(27) is an upper bound on the number of 1s a halting turing machine will output, so we know the Goldbach machine will not halt, so Goldbachs conjecture is true!
We can now solve any problem in mathematics provided:
- we can construct an n state turing machine that halts if and only if it is true/false
- we know the value of BB(n)
Thus, we have removed the ‘infinite nature’ of solving these problems.