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.

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.

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*10^{36,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).

47176870 1012L 2013L 3014L 4011R 5010L 1113R 2112L 3105R 4114R 5101R

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.