Busy Beaver Task

A Busy Beaver Task is a Task that requires the determination the largest finite number of ones that a Turing Machine starting with a tape initialized to all zeros, which reads a binary Alphabet, can write to the tape?

• AKA: Busy Beaver Problem.
• See: Algorithm, Turing Machine.

---

---

References

• (Wikipedia, 2009) ⇒ http://en.wikipedia.org/wiki/Busy_beaver
  • In computability theory, a busy beaver (from the colloquial expression for "industrious person") is a Turing machine which, when started on an empty tape, runs as long as possible, but eventually halts. This machine attains the limits on the amount of time and space that a halting Turing machine of the same class can consume.
  • The busy beaver function quantifies those limits and is an example of a non-computable function. In fact, it can be shown to grow faster than any computable function. The concept was first introduced by Tibor Radó as the "busy beaver game" in his 1962 paper, "On Non-Computable Functions"
• http://www.cs.rpi.edu/~kelleo/busybeaver/problem.html
  • Consider a binary alphabet Turing Machine which is given an infinite, blank tape as input. If this machine halts, we define its productivity as the number of 1's left on the tape after the machine is run to completion. If it does not halt, the machine is given a productivity value of zero. Now consider all of the binary alphabet Turing Machines that have n states. The machine in this set which has the highest productivity is called a Busy Beaver, and its productivity is the result of the Busy Beaver function BB(n). Alternatively, the productivity score can be defined as the number of transitions made before halting.

---