Built on Facts

Sunday Function

So I spent two weeks in Wyoming, participated in a wedding in Louisiana, moved two apartments worth of stuff, visited Louisiana again to get a marriage license for myself (20 days left!), collected data for an experiment demonstrating a new result we’re trying to get published quickly (hot topic, lots of competition), and so forth. Blogging is fun, but in terms of priority it has been taking a backseat.

For some reason, I feel the Busy Beaver function might be a good topic for this Sunday…

Ok, consider a Turing machine. I’ve embedded a video of a guy who’s actually built one, but so you’ll understand it here’s a little background. A Turing machine is a generalized model that mathematicians use to think about computation abstractly. It consists of a tape with a string of symbols printed on it, in this case 0s and 1s. There’s a read/write head situated at a fixed position, and the tape runs under it. The read/write head itself has a number associated with it, which is called a state. The state can be any of the numbers {1, 2, 3,… n}, where the specific n is up to you. The read/write head reads the number under it on the tape, and depending on the number on the tape and the state of the head it 1) changes (or leaves alone) the number of the tape, 2) shifts the tape one position to the left or right according to its program for that state and tape value, and 3) the state changes according to whatever rules you’ve programmed into the machine. The process then repeats. Crucially, one of those programmed instructions needs to cause the machine to stop, otherwise it just runs forever. Here’s such a machine in action:

In an abstract mathematical Turing machine the tape is infinite in length, but this physical version gets the gist across pretty well. So to take the simplest possible example, imagine a machine with just one possible state on the read/write head (so n = 1), programmed in the following way. “If the symbol under the head is a 0, write the number 1 to that position, move the tape one position to the right, and halt the program. If the symbol under the head is a 1, halt the program.” If you feed it a tape containing an infinite string of 0, the program will print one number 1 and then quit.

Which is about as boring as it’s possible for a program to be. But if you let n be higher, then you can make more complicated rule sets and get more interesting behavior. So here’s the important part. Imagine you’re trying to make a Turing machine that prints out the most possible 1s for a particular n. It’s easy to make a machine that prints out an infinite number of 1s, but the rules of the contest state that you’re looking for the largest finite n – the machine is required to finish its program.

So the Busy Beaver function is defined as the maximum finite number of 1s that an n-state program can print to the tape. It’s generally denoted Σ(n). Here’s the first few values:

i-a385bff570712df95e4671efbf5bacaf-bb.png

Now here’s the catch. There’s provably no algorithm that can determine whether or not an arbitrary program on a Turing machine does in fact halt. In the general case, you just have to run it and see. But of course this means that you can never be sure that a particular Turing machine program doesn’t halt unless you cleverly manage to prove it by other means, because it could just be that you haven’t let the program run long enough. And there’s no general method for doing that. It’s possible to extend this argument to show that if you have any computable function f(n), no matter how quickly growing, eventually Σ(n) will catch up and surpass it for high enough n. (In this context, “computable function” means a function whose value you can calculate with an algorithm in a finite number of steps.)

The Σ(n) I’ve plotted doesn’t seem to be growing all that fast. But that’s all the values that are known, the next few are not known precisely but we have managed to prove that Σ(5) is greater than 4098 and Σ(6) is known to be no less than a staggering 10^18267. The 6-state Turing machine that prints the most 1s before halting is a very busy beaver indeed.

Comments

  1. #1 Joshua Zelinsky
    August 15, 2010

    Generally, when I’m explaining Busy Beaver I use the slightly different normalization that just cares about how many steps a machine can run and then halt. This is more intuitive than the number of 1s printed and it is more immediately obvious why the function grows too fast to be computable.

  2. #2 Rob
    August 15, 2010

    A fascinating discussion of large numbers, computability, and the busy beaver function is at:

    http://www.scottaaronson.com/writings/bignumbers.html

    I heartily recommend it for anyone interested in this blog.

  3. #3 GrayGaffer
    August 16, 2010

    And if anybody wants to bring their PC to its knees, they can try programming it up on vturing.exe.

    (Note: be careful with which vturing.exe you get. I hear there are some recent versions running around with viruses in them. I’ve had my copy since Windows 95 days and I believe it to be clean. There is also a more recent attempt on sourceforge.net by a different author)

  4. #4 Paul Murray
    August 25, 2010

    Perhaps it isn’t necessarily the case that no function grows faster than sigma(n), but rather that no function can be *proved* to grow faster than it.