Good Math/Bad Math

Thursday, May 11, 2006

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,InputWrite-SymbolNext-StateDirection
0,011+
0,105-
1,002+
1,103+
2,013-
2,114+
3,004-
3,103-
4,000+
4,112+
5,010-
5,11HALTHALT
(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.)

5 Comments:

  • I tried to understand the 6-state example. If I would start in state 2 and get a 1 as input, I would go to state 4 with a 1 as input and then go back to state 2 with 1 as input. Ad infinitum, right? So it depends on the initial condition?

    By Anonymous Jack, at 3:26 PM  

  • Jack:

    Sorry, I neglection to mention that in the busy beaver machine, it always starts in state 0 with a blank (all 0s) input tape.

    By Blogger MarkCC, at 3:29 PM  

  • Thanks Mark, but from (0,0) I go to (2,1), then to (4,1) and back to (2,1) and I'm stuck in an infinite loop. I'd like to understand. Am I missing something? Finite state dynamical systems always end up on periodic attractors, but for this one it is supposed to take very very very long but I don't see how...

    By Anonymous Jack, at 5:23 PM  

  • Hmmm. I'm confused.

    Start out:

    State: 0
    Head: X
    00000000000000000
    (0,0) so

    State: 2
    Head: X
    00000000001000000
    (2,0) so

    State: 3
    Head: X
    00000000001100000
    (3,1) so

    State: 3
    Head: X
    00000000000100000
    (3,0) so

    State: 4
    Head: X
    00000000000100000
    (4,0) so

    State: 0
    Head: X
    00000000000100000


    And we have seen that from (0,0), given nothing but 0 input, the head will not move forwards (+) more than 1 unit, so all it will see is 0 inputs. So we have an infinite loop writing 1 and heading to the left.

    By Anonymous Anonymous, at 5:33 PM  

  • Sorry. As I said, I grabbed particular busy beaver from Wikipedia, but translated it to my prefered way of presenting turing programs. I managed to botch the translation, and get a few target states wrong.

    I *think* it's right now. I've hand-run it through a couple of passes, and it seems to work the way I expect it to.

    By Blogger MarkCC, at 8:09 PM  

Post a Comment

Links to this post:

Create a Link

<< Home