FACT
2021-12-05 12:33:23
In theoretical computer science, the busy beaver game aims at finding a terminating program of a given size that produces the most output possible.[1] 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, binary-alphabet Turing machine 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:
the machine must have two states in addition to the halting state, and
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 ot
In theoretical computer science, the busy beaver game aims at finding a terminating program of a given size that produces the most output possible.[1] 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, binary-alphabet Turing machine 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:
the machine must have two states in addition to the halting state, and
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 ot
Log in to post comments
her possible n-state competing Turing Machines. The BB-2 Turing machine, 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".[1]