Using your Head is Permitted

July 2012 solution

The turnout for this contest was not as big as I had hoped, but we do have Jin Ruizhang's and Zilin Jiang's impressive 41,710-step machine taking the grand prize (and tying for number of steps with Daniel Bitin).

Interestingly, this contest is not an original idea of mine. It is a running contest known as the Busy Beaver competition. The only difference from the classic Busy Beaver problem is that in BB the winner is the program to output the most "1"s, not necessarily the last to halt. Nevertheless, in practice, both metrics are measured and compared.

Unlike what we saw on this site, the BB is quite a popular contest, and it is perhaps this very reason that caused the low turnout this month, with many solvers having prior familiarity with the problem.

Personally, I see the low turnout this month as an indication that people did not see how to "use their heads" to get a better Turing machine. If so, you are in good company. For my money, this does, indeed, make the competition less interesting, but it is less interesting for highly interesting reasons. Let us consider, briefly, the interesting parts in both the problem and the solution.

The problem

This problem (as well as the problem of writing the most "1"s) was first raised by Tibor Radó in his 1962 paper "On Non-Computable Functions". The number of "1"s written by the best possible program, as well as the number of steps until the most long-lived machine halts, were both shown to be non-computable from the number of states of the machine.

This, in itself, is not very surprising. For example, if one were able to calculate this S(n) function, one could solve the halting problem by simulating the machine in question S(n) steps. There are many known non-computable functions, so one may argue that this is not very impressive. What I personally find most impressive here is that this function is necessarily non-computable by virtue of growing faster than any computable function. Think of the worst you could do with an input n. For example, you could calculate the Ackermann function. And then you can calculate the Ackermann function of the result. And then you can calculate the Ackermann function of that result. Your function will still grow only much more slowly than S(n). Now that is impressive.

By virtue of the function not being computable, it is also clear that there is no algorithm, no formalizable method, of finding the winning program in a Busy-Beaver competition. As such, if you couldn't find a way to "use your head" in this month's riddle, it is because there is none.

The solution

No less fascinating than what we know about the problem is what we know about the solution. The answer is that we don't know it. Not even for a machine with 5 states. There is a construction by Milton Green that gives Turing machines that prove


for k≥2, where "↑" indicates Knuth's up-arrow notation and "A" is the Ackermann function, but even for small n values for which we are able to bound S(n) from below empirically, Green's bound is puny compared to the known bounds.

Interestingly, even by simulating every single n-state machine there is, one cannot determine S(n). The reason for this is that even with n as low as 5, there are plenty of machines for which we cannot tell whether they halt or not.

In fact, a while back I found this interesting review by Pascal Michel (centering on the effects of adding more symbols rather than just more states to the problem). This paper draws several interesting lines demarcating machines where the halting problem is known to be solvable from those where the halting problem is equivalent to a well-known number-theoretic open problem (one of several Collatz-problem like variations), from those where the halting problem is equivalent to the Collatz problem itself, from those known to be universal. It is interesting how well-suited the Collatz problem and its siblings are to simulation on state-and-symbol-limited Turing machines.

The known results for two-symbol machines are

n S(n) Record holder
1 1 Lin and Radó
2 6 Lin and Radó
3 21 Lin and Radó
4 107 Brady
5 ≥47,176,870 Marxen and Buntrock
6 >7.412*1036,534 Pavel Kropitz

Heiner Marxen and Jürgen Buntrock, current holders of the n=5 record (with a machine that attains over 47 million steps), did so with the following machine (given here in the same notation as asked for on the question page).


A full review of how this staggering result was reached is given in the paper "Attacking the Busy Beaver 5" which they co-wrote, and which is available on Heiner Marxen's homepage. Also available there is the current state of the ongoing Busy Beaver competition.

To the best of my knowledge, Pavel Kropitz's unbelievably high S(6) figures are also the result of simulation. However, these are no longer one-to-one simulations. Rather, each simulation step leaps over a large number of steps of the simulated Turing machine.

Back to riddle

Back to main page