A Followup to Turing's Birthday, with Busy Beavers

In my previous post celebrating the 100^th birthday of Alan Turing, there was an animation of a simple Turing machine in action. I suggested that the reader try to figure out what the machine was doing (I didn't really intend this as a homework exercise!). Here's the answer, and two more Turing machines (but these aren't so simple).

The machine was a clock. Starting at a 0 (blue) on the tape, it writes a string of 1's (red), until it encounters an existing 1, at which point it reverses, erasing all the 1's it wrote, and then it repeats. But it's writing the 1's in a rather inefficient way: it goes to the end of the string, writes a 1, returns to the beginning, and repeats (unless there was already a 1 there, in which case it backs up, writing 0's until it encounters a 0). If it has written N 1's, then it takes O(N) steps to write the next 1 (because it has to move over N times and then move back N times); the total time required to write N+1 1's is therefore O(1+2+…+N) = O(N²). Here it is again, but writing a longer string of 1's, running faster, and without all the irrelevant clutter on the tape:

A Quadratic-Time Turing Clock

You may be wondering what is the point of this clock. Simple: being a clock, it is periodic, lending itself to an infinite-loop animation, which is what I wanted; and it's doing something more interesting than just moving back and forth. That's all. (If you were expecting an automated theorem-proving Turing machine, I'm sorry you were disappointed.) But there's more to be said.

Turing machines can be put into three categories. More accurately, a Turing machine, its initial state, and its initial tape, can be put into three categories: those that run for a while and then stop; those that eventually end up in a periodic loop; and those that do neither. (A simple example of the latter is one that just keeps moving in one direction.) Interestingly, this classification is not computable. In other words, there is no algorithm which can look at (machine, state, tape) and say "halts" or "periodic" or "neither". This question — whether a machine will halt — is the “halting problem”. It's worth emphasizing the “no algorithm”: it's not just that known algorithms are slow, or that any possible algorithm is known to be slow; it's that there simply is no such algorithm. (This is a distinction which is sometimes lost in the popular media, where people say “not computable” when they really mean “not computable in the life of the universe”.)

Let's talk about the clock some more. A really straightforward clock, with period linear in N, would simply write a 1 and move the tape, repeating until it encountered a 1, and then write a 0 and move the tape the other way, repeating until it encountered a 0, and then start all over. This would be an O(N) clock. My clock is more complicated, O(N²). A reasonable question would be, how complicated can you make a clock? In other words, can you make a O(N^k) for k > 2? Maybe even bigger than polynomial, like exponential in N?

I don't know the answers to these questions. However, there is another question which is similar (at least in style if not substance): what is the most complicated behaviour you can get from a Turing machine that halts? This question is known as the “busy beaver” question. There are two versions of the question, both starting with the assumption that the initial tape is blank (all 0's): among all n-state Turing machines with m symbols, how many 1's can you write on the tape before it stops; or, how long can it run before it stops. Neither of these functions (Σ, the number of 1's; or S, the number of steps) is computable; in other words, there's no algorithm that computes these from a Turing machine. (You can't just list all the machines and run them, because some of the machines won't halt, and you don't know which ones those are, because that's not computable.)

Even though the functions aren't computable in the computability sense, it is nevertheless possible to compute some specific values of the functions. (No, this isn't a contradiction; computability requires a single algorithm to compute the value for all inputs, not just a few of them.) How many specific values? Very, very, very few. The answers are known for two-symbol machines with two, three, or four states; and for three-symbol machines with two states. That's it.

It's easy to calculate lower bounds for these functions; just find an (n,m) Turing machine that halts, run it, and count. Based on these lower bounds, we can see how quickly these functions grow. It's really fast. For the two-symbol machines, the maximum number Σ(n,2) of 1's, as a function of the number of states n, is:

• Σ(1,2) = 2
• Σ(2,2) = 4
• Σ(3,2) = 6
• Σ(4,2) = 13
• Σ(5,2) ≥ 4098
• Σ(6,2) ≥ 3.5×10¹⁸²⁶⁷

Wow.

Here's an animation of a three-state two-symbol busy beaver, maximizing the number of 1's, taking 13 steps. (There's a different one that takes 14 steps, the maximum among all machines that generate six 1's. The three-state two-symbol busy beaver that maximizes the number of steps takes 21 steps, but produces only five 1's.)

Three-state busy beaver Turing machine (maximal number of 1's)

The step counter is in the upper-right part of the illustrations.

And here's an animation of a four-state two-symbol busy beaver, writing thirteen 1's in 107 steps. (This one machine, unlike the three-state case, maximizes both the number of 1's and the number of steps.)

Four-state busy beaver Turing machine

Maybe the right way to formulate my clock question is this: given (n,m), and an initial tape which is blank except for a 1 that is N places to the right of the initial position, find the maximal period T(n,m,N) among all (n,m) Turing machines that are periodic with that initial tape. (I don't know the answer, nor do I know if this question is theoretically interesting.)

For those of you who came here looking for a different kind of beaver and were disappointed by all this math stuff, here. And the wacko conservatives in Canada seem to be waging a war on beavers, just like their USA counterparts. And here's a kid-friendly beaver page, complete with an anatomical diagram.