Theory of computation | Large integers | Computability theory
Busy beaver
In theoretical computer science, the busy beaver game aims at finding a terminating program of a given size that produces the most output possible. Since an endlessly looping program producing infinite output is easily conceived, such programs are excluded from the game. More precisely, the busy beaver game consists of designing a halting Turing machine with alphabet {0,1} which writes the most 1s on the tape, using only a given set of states. The rules for the 2-state game are as follows: 1. * the machine must have two states in addition to the halting state, and 2. * the tape initially contains 0s only. A player should conceive a transition table aiming for the longest output of 1s on the tape while making sure the machine will halt eventually. An nth busy beaver, BB-n or simply "busy beaver" is a Turing machine that wins the n-state Busy Beaver Game. That is, it attains the largest number of 1s among all other possible n-state competing Turing Machines. The , for instance, achieves four 1s in six steps. Determining whether an arbitrary Turing machine is a busy beaver is undecidable. This has implications in computability theory, the halting problem, and complexity theory. The concept was first introduced by Tibor Radó in his 1962 paper, "On Non-Computable Functions". (Wikipedia).
