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*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).
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.