The Busy Beaver Problem

This page is in the early stages of development.

How many marks can a Turing machine write on its tape, and still halt? Say M is a binary (i.e., its alphabet consists of just blank and 1) Turing machine. Its score is the number of 1's it leaves on an initially blank tape, when it halts. (If it never halts, then it never receives a score -- it's disqualified.)

For each n, there are only finitely many n-state binary Turing machines and some of them halt. So there is sure to be some highest possible score. Call the highest possible score Sigma(n). What is it?

In 1962 Rado introduced this "busy beaver competition." In more detail, the ground rules for the competition are as follows. Consider a Turing machine with n states (plus an additional halting state) and two symbols, blank and 1. At each step the machine can write, move one space right or left, and change state. To be a valid entry in the competition, the machine must eventually halt when started on a blank two-way tape. Its score in the competition is the number of 1's on the tape when the machine halts. Thus the machine tries to writes as many 1's on the tape as it can, but it must halt. Let Sigma(n) the maximum possible score for a valid n-state entry.

The theoretical interest in this competition stems from the fact that, although Sigma(n) is simply the maximum of a certain finite set, the function Sigma is non-computable. Furthermore, Sigma is eventually greater than any given computable functions. The proof is easy. In fact, if you want to start from scratch and construct a specific non-computable function, this is the one to use.

Links: Click here for Heiner Marxen's own web page on the busy beaver problem. And another page.

So Sigma is non-computable. What are its values? The values of Sigma(n) is known for n = 1, 2, 3, 4. Beyond that, some lower bounds are known.

n = 1

n = 2

n = 3

n = 4

n = 5

n = 6

Herbert Enderton