Busy Beavers

After spending all this time talking about the different kinds of computing machines and what they can do, I thought it would be fun to talk a little bit about what they can't do.

Back in the early days of this blog, I talked about two things that no computing machine can do:

• the halting problem: determining whether running a given program on a particular input will eventually halt;
  
• minimal complexity: determining whether or not a particular program is the smallest one that can generate a particular result.
  

There's one really fun non-computable, which various nutty people like me still play with to see who can find the best one. It's called the busy beaver problem. There are actually real competitions to see who can build the best busy beaver program.

Here's the question that the simplest version of the busy beaver problem wants to answer: Given a binary turing machine (that is a machine whose tape can have only the characters 0 and 1) with N states, what is the longest string of 1s that can be generated by a halting program?

Based on experimentation, our best guess is for a five-state machine, the answer is: 4098 ones, taking 47,176,870 steps. For a six state machine, it's something on the order of 10^1000 1s.

From wikipedia, here's the state transition function for a six-state busy beaver that will write 1x10^865 ones:

State,Input	Write-Symbol	Next-State	Direction
0,0	1	1	+
0,1	0	5	-
1,0	0	2	+
1,1	0	3	+
2,0	1	3	-
2,1	1	4	+
3,0	0	4	-
3,1	0	3	-
4,0	0	0	+
4,1	1	2	+
5,0	1	0	-
5,1	1	HALT	HALT

(In the original version of this posting, the turing program above had several errors due to an error translating from the wikipedia format to my format.)

I'm not going to go through the proof; this is basically just a fairly typical Godel-esque problem: to compute this, you need to "meta-compute" - that is, to use computation to reason about computation; and any time you reach meta-problems like that, you hit the Godel barrier, and things become uncomputable. This is what we call a Turing complete problem: if it were possible to solve the halting problem, we could solve this; if it were possible to solve this, we could solve the halting problem.

(This is actually a secondary use of the term "Turing complete", and it's definitely awkward, but I'm not aware of a better term. Turing complete is also used to describe programming languages or computing machines to mean that the language/machine can both implement a turing machine, and be implemented by a Turing machine.)

There are numerous variations on the busy beaver problem: versions for turing machines with more symbols on the input tape; versions where the goal is to run for the most execution steps before halting; versions for other computing systems; etc.

(One of the questions that people often come up seeing the busy beaver is: if all computing devices are equivalent, then why would the answer be different for a computing device other than a turing machine? The answer is that the busy beaver problem includes the basic properties of the Turing machine in it - so even if you used a different computing machine to compute the result of a given busy beaver program, the program for that other machine would need to encode the properties of the Turing machine that the BB program was written for.)