Busy Beaver

The busy beaver game asks, for a Turing machine limited to a fixed number of internal states, how many steps it can run before halting, or how many symbols it can write, given that it is required to eventually stop rather than loop forever. The mathematician Tibor Rado introduced the problem in his 1962 paper On Non-Computable Functions, defining two functions, one for the maximum output and one for the maximum running time, both measured across every possible halting machine of a given size. Both functions grow faster than any function that can itself be computed by an algorithm, which makes them impossible to compute in general, and this connects the busy beaver problem directly to the halting problem at the foundation of computability theory. Because the functions grow so explosively, finding the exact value for even a modestly sized busy beaver machine can, in principle, require settling open mathematical questions such as Goldbach's conjecture or the Riemann hypothesis.