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:

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.