# Reverse busy beaver problem

In this challenge, Turing machines operate on a zero-initialized binary tape that is infinite in both directions.

You are given an integer $$\N\$$, where $$\1 \le N \le 20000\$$. Your program has to output a Turing machine that takes exactly $$\N\$$ steps to halt, including the final step. Alternatively, you can write a program that outputs all 20000 machines.

Your program should complete within 2 hours for all 20000 inputs, when tested on my computer (AMD Ryzen 2600 12-thread CPU). If your program solves all test cases on the same thread, sequentially and independently, your program's running time is divided by 4.

Your score is the total number of states in all 20000 outputs of your program. The lowest-scoring program wins.

## Output

Below is described the (recommended) output format for a single test case.

In the first line, output a number $$\M\$$, the number of states of the machine. In the next $$\M\$$ lines, output the transitions from the states, in order from the first to the last, if the cell under the pointer is zero. In the next $$\M\$$ lines, output the corresponding transitions, if the cell under the pointer is one.

The output format for transitions is movement newval newstate, where movement stands for either L - move left, R - move right, S - do not move, or H - halt, newval is the new value of the cell under the pointer (it can be equal to the original one), and newstate is an integer from $$\1\$$ to $$\M\$$, the state the machine will be in in the next step.

Python 3 checker that inputs in the format described above and outputs the number of steps the Turing machine takes to halt. If you use a different output format, please include a link to a program that can be used to simulate your Turing machines (it's likely a good idea to simply modify my checker).

• Deleted sandbox post – the default. May 23 '20 at 7:47
• – Arnauld May 23 '20 at 10:17
• @Arnauld re: the oeis seq, is the machine in this question 3-tuple? Is it similarly difficult to compute min required states for larger numbers? – Jonah May 23 '20 at 14:18
• @Jonah I should add that I'm not familiar with Turing Machine notations and that this 5-tuple Turing machine in the OEIS definition puzzled me as well. I don't quite understand why they put it in there. The fact that it's a 2-symbol machine is all that should matter here. – Arnauld May 23 '20 at 15:08
• I feel like any competitive program for this would just be a long precomputed list of optimal Turing machines. Iterate through a bunch of small machines, running them for 1000 steps each, recording for each N the smallest machine that runs for exactly N steps. Doesn't matter if it takes more than an hour to compile the list of machines, once the list is hardcoded into a program it's trivial and fast to output list[N] given N. – Magma May 23 '20 at 18:11

# Python 3, 275,467 255,540 states

Thanks @mypronounismonicareinstate for suggesting to add $$\I\$$ into the $$\B \rightarrow C\$$ loop, which ultimately saves about $$\20k\$$ states.

def print_machine(states):
print(len(states))
for i in 0,1:
for s in states[i]:
# if s is None (state unused), puts dummy value in there
move, new_val, new_state = s or ["H", 0, 0]
print(move, new_val, new_state+1)

# simple machine that uses ceil(step/2) states
# used for small cases
def generate_simple_machine(steps):
n_states = (steps+1)//2
# states[cur_char][state_id]
states = [[], []]
for i in range(n_states):
states.append(["S", 1, i])
states.append(["S", 0, i+1])
states[-1] = "H"
if steps%2==1: states[-1] = "H"
return states

BASE_STEPS = [(1<<i+2)-i-3 for i in range(20)]
BASE_STEPS = -999

def generate_counter_machine(steps, do_print=True):
# how many bits/states needed?
for n_bits, max_steps in enumerate(BASE_STEPS):
if max_steps > steps:
break
n_bits -= 1
n_states = n_bits + 2
extra = steps - BASE_STEPS[n_bits]
if extra >= (1 << (n_bits+1)):
n_states += 1

# if small number of steps, use simple machine
n_states_simple = (steps+1)//2
if not do_print:
return min(n_states_simple, n_states)
if n_states >= n_states_simple :
states = generate_simple_machine(steps)
print_machine(states)
return n_states_simple

# states[cur_char][state_id]
# use 0 indexed state
states = [[None]*n_states, [None]*n_states]

# state indices
I_STATE  = 0
B_STATE  = 1
E_STATE  = n_states - 1
C_STATES = [i+2 for i in range(n_bits)]

# initial state
states[I_STATE] = ["R", 1, C_STATES]
states[I_STATE] = ["H", 0, 0]  # not used initially

# go back state
states[B_STATE] = ["L", 0, B_STATE]
states[B_STATE] = ["R", 1, C_STATES]

# ith-digit check states
for i in C_STATES:
states[i] = ["L", 1, B_STATE]
states[i] = ["R", 0, i+1]
states[C_STATES[-1]] = "H"

# dealing with extras
# first, figure out how many half-state
# goes between B_1 -> C1_x
t = 1<<n_bits
q1 = t - 1
q2 = q1 + t
q3 = q2 + t
if  extra < q1:
extra_state = I_STATE
elif extra < q2:
# connect B_1 -> I_0 -> C1_?
states[B_STATE] = ["S", 0, I_STATE]
extra -= q1
extra_state = I_STATE
elif extra < q3:
# connect B_1 -> I_0 -> I_1 -> C1_x
states[B_STATE] = ["S", 0, I_STATE]
states[I_STATE] = ["S", 1, I_STATE]
states[I_STATE] = ["R", 1, C_STATES]
extra -= q2
extra_state = E_STATE
else:
# connect B_1 -> I_0 -> I_1 -> E_0 -> C1_x
states[B_STATE] = ["S", 0, I_STATE]
states[I_STATE] = ["S", 1, I_STATE]
states[I_STATE] = ["S", 0, E_STATE]
states[E_STATE] = ["R", 1, C_STATES]
extra -= q3
extra_state = E_STATE

# then put a half-state between Cx_0 -> B
# if needed
if extra > 0:
states[extra_state] = ["L", 1, B_STATE]
for i in reversed(C_STATES):
if extra%2==1:
states[i] = ["S", 1, extra_state]
extra //= 2
print_machine(states)
return n_states


### Big idea

We want to construct a Turing machine that has a large time complexity compared to the number of states. In this answer, I used a binary counter to count all integers with $$\n\$$ bits, which has a time complexity of $$\O(2^n)\$$. The binary counter was chosen because it is very simple to construct, easy to scale, and flexible enough to add any small number of steps.

### Binary counter

Let's say we want to count all integers with 4 bits. The tape layout will be as follows:

1 x x x x
e.g.
1 0 0 0 0
1 1 0 0 0
....
1 0 1 1 1
1 1 1 1 1


where the left most 1 is used to mark the start of the number, and xxxx is the current number in binary, in reverse order (the least significant bit first). We start with 10000, and end with 11111.

At each cycle, we increase the number by 1 as follows:

• Find the left most 0. E.g.
1 1 1 0 1
^

• Set that digit to 1, and all previous digits to 0. The previous example becomes 1 0 0 1 1.

We then repeat these steps until the tape is 1 1 1 1 1.

### Binary counter Turing machine

The counter machine for $$\b\$$-bit integers will have $$\b+2\$$ states: the initial state $$\I\$$, $$\b\$$ digit check states $$\C_1\$$ to $$\C_b\$$, and the "go back" state $$\B\$$:

• The initial state $$\I\$$ simply sets the left most cell to 1: R 1 C1 / x x x.

• The $$\i^{th}\$$ digit check state $$\C_i\$$ is only called if all previous digits are 1, and the pointer is currently on the $$\i^{th}\$$ left most digit.

• If the current digit is 0, then we've found the left most 0. Set the current digit to 1, and enter "go back" state: L 1 B.
• If the current digit is 1, set that digit to 0 and enter the next digit check state: R 0 C(i+1). If this is the last digit check state ($$\C_b\$$), then halts, since this means the current number is 111..1.
• "Go back" state $$\B\$$ is called after the number is incremented, to reset the pointer to the unit digit and start a new cycle. This state simply moves left until it sees the 1 that marks the start of the number. It then moves one step right to the unit digit, and calls the first digit check state $$\C_1\$$: L 0 B / R 1 C1. ### Time complexity

With $$\n\$$ states (counting $$\n-2\$$ bit integers), a counter machine runs for $$\2^n-n-1\$$ steps.

states  steps
3      4
4     11
5     26
6     57
7    120
8    247
9    502
10   1013
11   2036
12   4083
13   8178
14  16369
15  32752


### Bridging the gap

The above scheme only allows us to generate machines with the exact number of steps in the table above. This means that we are stuck if the number of steps falls in the "gaps" between the above numbers. Thankfully, there is a simple scheme that allow us to add some extra steps to a machine, at the cost of at most 1 state.

For example, from the above table, we know that a counter with 6 states runs for 57 steps, and a machine with 7 states runs for 120 steps. There are 62 numbers in the gap between them (58 to 119). This means that we need to be able to extend a 6-state machine to have 1 to 62 extra steps. (In general, we need a scheme to extend an $$\n\$$-states machine by 1 to $$\2^n-2\$$ steps).

First, some notation: let's $$\S^0\$$ and $$\S^1\$$ be the "half-states" of $$\S\$$, aka $$\S\$$ when the current cell is 0 or 1.

Let's look at how many time each half-state is called in an original 6-state counter machine:

                I    B   C1   C2   C3   C4
cur_char = 0    1   11    8    4    2    1
cur_char = 1    0   15    8    4    2    1


Observation 1

The number of times each digit check half-state is called is always a power of 2. Furthermore, the transition afterward is always $$\C_i^0 \rightarrow B^x\$$ (refer to the state transition diagram above). This means that we can add an extra half-state in between (aka $$\C_i^0 \rightarrow X \rightarrow B^x\$$). The extra half-state simply wastes a step before transitioning to $$\B\$$. The number of extra steps gained is equal to the number of times $$\C_i^0\$$ is called.

By selecting which $$\C_i^0\$$ are connected to this extra half-state $$\X\$$, we can add any number of extra steps from 1 to 15 (since $$\15=8+4+2+1\$$), at the cost of 1 extra half-state. For example, in the modified counter above, $$\C_1^0\$$ and $$\C_3^0\$$ transitions through $$\X\$$ before reaching $$\B\$$. Since $$\C_1^0\$$ is called 8 times and $$\C_3^0\$$ is called 2 times, $$\X\$$ is called 10 times in total, adding an extra 10 steps to the machine.

Observation 2:

Both $$\B^1\$$ and $$\I^0\$$ transitions to state $$\C_1\$$. Furthermore, both $$\B^1\$$ and $$\I^0\$$ sets the current cell to 1, then moves right. Thus, we can have $$\B^1 \rightarrow I^0 \rightarrow C_1^x\$$. This gives us an extra 15 steps for free.

Furthermore, for each additional half-state inserted between $$\I^0\$$ and $$\C_1^x\$$, the machine runs for 16 extra steps. For example, using 2 extra half-state, we can gain $$\15+16+16=47\$$ extra steps.

By combining the 2 observations, we can reach any number of extra steps between 1 and 62 inclusive, using at most 3 extra half-states (1 half-state in observation 1, 2 in observation 2, which gives at most $$\15 + 47 = 62\$$ extra steps). For example, in the machine above, $$\I^0\$$ and 2 extra half-states are added between $$\B^1\$$ and $$\C_1^x\$$, adding $$\15+16+16 = 47\$$ extra steps. Another extra half-state is added between the digit checks and $$\B\$$, adding 10 extra steps. In total, this machine has 57 extra steps compared to the base machine.

This process can be generalized to any $$\n\$$-state counter machine.

Note that since $$\I^1\$$ is unused in the base machine, we already start with a free half-state. This means that we only need at most 1 extra state $$\E\$$ (aka 2 half-states $$\E^0\$$ and $$\E^1\$$).

### Code explanation

If you want to take a look at the code, the states are ordered as follow:

• Initial state $$\I\$$
• Go back state $$\B\$$
• Digit check states from $$\C_1\$$ to $$\C_b\$$
• Extra state $$\E\$$ (if needed)
• I get the same total number of states, and this does not even time out on TIO, and I also tested some machines to confirm they are correct; this seems valid to me. – the default. May 24 '20 at 11:28
• I can't wait to see this explanation. I had a go at this but for instance 19996 takes me 28 states instead of 15. – Neil May 25 '20 at 0:26
• @Neil I have added an explanation, hopefully it makes sense. Feel free to suggest improvements if you think it's still confusing. – Surculose Sputum May 25 '20 at 3:29
• Is it possible to use the initial state as the first extra state? (e.g. C1 notices a zero and depending on the "delay" needed it either proceeds to B or sets to 1, proceeds to I, then I sets to 0 and proceeds to B; I'm not sure whether this would work) – the default. May 25 '20 at 4:35
• @mypronounismonicareinstate Turn out having $C_i \rightarrow B \rightarrow I \rightarrow C_1$ adds a ton of extra steps for free, which completely eliminate the need for the $2^{nd}$ extra state. – Surculose Sputum May 25 '20 at 13:54

# Python 2, 265426 255462 states

t = 0
for i in range(1, 20001):
b = bin(i + 3)[2:]
if i < 5: t += -~i / 2
else: t += len(b) - (not int(b[1:])) - (not int(b))
print t
print
n = input()
if n < 5:
m = -~n / 2
print m
for i in range(m): print "S" if i * 2 < n - 1 else "H", 1, i + 1
for i in range(m): print "S" if i * 2 < n - 2 else "H", 0, -~i % m + 1
else:
b = bin(n + 3)[2:]
e1 = int(b[1:]) and 2
e2 = int(b) and 3
m = len(b) - (not e1) - (not e2)
print m
for i in range(m):
if i == e2 - 1:
if int(b): print "S", 1, 3
else: print "R", 1, 4
elif i == e1 - 1: print "L", 0, 1
elif i:
if int(b[i - m]): print "S", 0, 2
else: print "L", 0, 1
elif int(b[1:3]): print "S", 1, 2
else: print "R", 1, 1 + max(1, e1)
for i in range(m):
if i == m - 1: print "H", 0, 1
elif i == e2 - 1: print "R", 1, 4
elif i == e1 - 1:
if e2: print "S", 0, 3
else: print "R", 1, 3
elif i: print "R", 0, i + 2
else: print "L", 1, 1


Try it online! I was trying to come up with a different binary counter that didn't need @SurculoseSputum's initial state, but I then forgot about it, which is why this post is so late. Thanks to his help I was able to remove 9964 states so it's now actually slightly better than his answer. It's based on a basic machine of $$\ m \$$ states that takes $$\ 2 ^ { m + 1 } - 3 \$$ steps. The following states are created:

1. A "go back" state.
2. An optional state that is divided into two half states:
• An extra half state to drop into state 1 more slowly so that up to $$\ 2 ^ { m - 1 } - 1 \$$ extra steps can be added.
• An extra half state before the first digit state which adds $$\ 2 ^ { m - 1 } \$$ extra steps.
3. An optional state that is divided into two half states, one or both of which are inserted before the first digit state to add a further $$\ 2 ^ { m - 1 } \$$ or $$\ 2 ^ m \$$ extra steps.
4. A number of bit counter states.

Note: It's technically possible to save a further state for values of the form $$\ 3 \left ( 2 ^ m - 1 \right ) \$$ but as it only saves 11 states I haven't bothered to code this up yet.

• Nice approach! You can get $227,290$ states: The base machine with $n$ states runs in $2^{n+1}-3$ steps. Hooking an extra half-state after the bit counter states (when char = 0) gets us from 0 to $2^{n-1}-1$ extra steps. Hooking a half-state after the go back state, when char = 0 gets us $2^{n-1}$ extra steps. Thus, 1 extra state adds from 0 to $2^n$ extra steps (1 half state after go back, and 1 half state after go back or bit counter states). 2 extra states add $2^n+1$ to $2^{n+1}-1$ steps (2 or 3 half-states after go back, and 1 half-state after the bit counters). – Surculose Sputum Jun 1 '20 at 18:03
• @SurculoseSputum I think I broke something when I added the extra states; I should be able to do 29 steps in 4 states, shouldn't I... – Neil Jun 1 '20 at 18:45
• (Correcting the code saved me 46 states.) – Neil Jun 1 '20 at 18:52
• @SurculoseSputum I was already toying with the idea of handling $0$ to $2 ^ {n - 1} - 1$ extra steps using half a state, as that would save on the extra state for odd numbers, but it didn't occur to me to adapt it to include for all extra steps like that! I love it, I just need to work out how to code it now. – Neil Jun 1 '20 at 19:01
• @SurculoseSputum I've tried to implemented your suggestion, and so far it does now undercut your score slightly, but it's nowhere near your suggestion. Have I missed something? – Neil Jun 1 '20 at 22:46

# Python 2, 75012500 states

n = input()
m, l = n / 8, n & 7
print m * 3 + [0, 1, 1, 2, 2, 3, 2, 3][l]
for i in range(m):
print "L", 1, i * 3 + 2
print "R", 1, i * 3 + 1
if l or i + 1 < m:print "R", 0, i * 3 + 4
else:print "H", 0, i * 3 + 3
if l == 7:
print "L", 1, m * 3 + 2
print "R", 1, m * 3 + 1
print "H", 0, m * 3 + 3
elif l == 6:
print "L", 1, m * 3 + 2
print "R", 1, m * 3 + 1
else:
for i in range(-~l / 2):
if i * 2 < l - 1: print "S", 1, m * 3 + i + 1
else: print "H", 1, m * 3 + i + 1
for i in range(m):
print "R", 1, i * 3 + 2
print "R", 0, i * 3 + 3
print "R", 0, i * 3 + 3
if l == 7:
print "R", 1, m * 3 + 2
print "R", 0, m * 3 + 3
print "H", 0, m * 3 + 3
elif l == 6:
print "R", 1, m * 3 + 2
print "H", 0, m * 3 + 3
else:
for i in range(-~l / 2):
if i * 2 < l - 2: print "S", 0, m * 3 + i + 2
else: print "H", 0, m * 3 + i + 1


Try it online! Uses a six-step two-state busy beaver for n=6, then anonther state to clear enough tape in two steps to be able to run the busy beaver again. This handles all numbers whose remainder (modulo 8) is 0, 6 or 7; any remaining steps are handled by some probably suboptimal states.

# C++, score need testing

#include <stdio.h>
#include <thread>
#include <chrono>
#include <random>
#include <bitset>
#include <atomic>
#include <string.h>
#include <map>
// N = space of each buf, D = Amount of threads - 2, TIME = allowed time(ms), W = MaxOut
const int N = 50, D = 16, TIME = 7200 * 999, W=20000;
struct strat {int n, w, m;} mem[D][W+1][N];
int res[D][W+1], spl[W+1];
std::atomic_ullong cnt;
volatile bool timeout;

void putStrat(int i, int det=0, int then=-1) { //fprintf (stderr, "%6d%5d%4d%6d\n", i, det, then, spl[i]);
// printf ()
if (spl[i] && then<0) { //printf ("(%d=%d+%d)", i, spl[i], i-spl[i]);
putStrat(spl[i], det, det + res[spl[i]]); //fprintf (stderr, "a");
putStrat(i-spl[i], det + res[spl[i]], then); //fprintf (stderr, "b");
return;
}
int n = res[then==-1][i]; //fprintf (stderr, "c");
strat (*x) = mem[then==-1][i];
if (n>9999) {
printf ("Not Found(%d,%d,%d)",i,det,then);
} else
for (int i=0; i<n; ++i) {
int d0 = x[i].n<0 ? then : x[i].n+det;
int d1 = x[i].n<0 ? then : x[i].n+det;
printf ("[%2d %c %c|%2d %c %c]",
d0, "01"[x[i].w], "LSR"[x[i].m],
d1, "01"[x[i].w], "LSR"[x[i].m]);
}
}
int run(strat (*A)) {
int p = W+4, i=0;
int cur_state = 0;
std::bitset<W*2+8> Q;
for (i=0; ++i<W+1; ) { //fprintf (stderr, "%d %d %d%d%d%d%d%d%d%d\n", cur_state, p, (int)Q, (int)Q, (int)Q, (int)Q, (int)Q, (int)Q, (int)Q, (int)Q, (int)Q);

auto& o = A[cur_state][Q[p]];
cur_state = o.n;
if (cur_state == -1) break;
Q[p] = o.w;
p += o.m-1;
}
return i;
}
void fallbackGen(int k, int v) {
strat A;
A = {4,1,2};  A = {3,1,2};
A = {2,1,0};  A = {3,0,2};
A = {-1,0,2}; A = {1,1,0};
A = {1,0,0};  A = {0,1,2};
//A = {5,1,2};
//A = {6,1,2};
//A = {1,1,2};
for (int i=4; i<k; ++i) {
A[i] = {i+1, i%2?1:1&(v>>(k-i)/2), 2};
A[i] = {-1,0,2};
}
A[k-1].n = 1;
int r = run(A);
for (int i=3; i<k; ++i) {
if (r>W) return;
if (k<res[r]) {
res[r] = k;
memcpy (mem[r], A, k*sizeof(*A));
}
++r;
if (i==3) {
A.n = 4;
} else {
A[i].n = i+1;
}
}
{ r+=2;
if (r>W) return;
A[k] = {-1,0,0};
A[k] = {k-1,0,2};
++k;
if (k<res[r]) {
res[r] = k;
memcpy (mem[r], A, k*sizeof(*A));
}
}
}
void fallbackGene() {
mem = {-1,0,0}; res = 1;
mem = {0,1,1}; mem = {-1,0,0}; res = 1;
for (int k=5; k<32; k+=2) {
for (int v=0; v<std::min(W,1<<(k-1)/2); ++v) {
fallbackGen(k, v);
}
}
}
void f(int d) {
std::mt19937 R(d);
for (; !timeout; ++cnt) {
strat A[N];
static const int Coll[] = {1,2,3,4,4,5,5,5,5,6,6,6,10};
int n = Coll[(unsigned)R()%13];
for (int i=0; i<n; ++i) {
for (int j=0; j<2; ++j) {
A[i][j].n = (unsigned)R() % n;
A[i][j].w = (unsigned)R() % 2;
A[i][j].m = (unsigned)R() % 8 ? (unsigned)R() % 2 * 2 : 1;
}
}
int halt_state = (unsigned)R() % N;
int halt_bin = (unsigned)R() % 2;
A[halt_state][halt_bin].n = -1;
int i = run(A);
if (i<W+1 && res[d][i]>n) {
res[d][i] = n;
memcpy (mem[d][i], A, n * sizeof(*A));
}
}
}
int main() {
freopen ("unBB.txt", "w", stdout);
memset(res, 1, sizeof(res));
std::thread A[D];
A = std::thread(fallbackGene);
for (int i=2; i<D; ++i) A[i] = std::thread([i](){f(i);});
std::this_thread::sleep_for(std::chrono::milliseconds(TIME));
timeout = 1;
for (int i=1; i<D; ++i) A[i].join();
printf ("%llu Tries\n", (unsigned long long)cnt);

int s=0;
setvbuf (stdout, 0, _IONBF, 0);
for (int i=1; i<W+1; ++i) {
int m=0x7fffffff; strat (*x); //fprintf (stderr, "p");
for (int j=0; j<D; ++j) {
if (res[j][i] < m) {
m = res[j][i];
x = mem[j][i];
}
}//fprintf (stderr, "q");

if (mem[i] != x && m<9999) {
res[i] = m;//fprintf (stderr, "%d", m);
memcpy (mem[i], x, m*sizeof(*x));
}//fprintf (stderr, "r");
for (int j=1; j<i; ++j) {
if (res[j] + res[i-j] < res[i]) {
res[i] = res[j] + res[i-j];
spl[i] = j;
}
}//fprintf (stderr, "s");
printf ("%6d %6d ", i, res[i], res[i]);
putStrat(i);
puts("");
}
return s;
}


Build with blocks that run some steps leaving the tape empty

• From my testing with heavily reduced maximal time, this only finds solutions for some very small numbers (the largest number found is 118 and the second largest is 71, in 2.5 million tries), so I don't think this finds significantly more solutions in the full 2 hours. – the default. May 24 '20 at 3:51
• In ten times as much time (12 minutes, 31M tries), the largest number found is still less than 200. – the default. May 24 '20 at 4:06
• @mypronounismonicareinstate Tested running for 2s(but outputting cost more time), score is 1446775 – l4m2 May 24 '20 at 10:02
• 10s, 1318414, actual time 49.768s – l4m2 May 24 '20 at 10:09
• Seems to be some bugs when building – l4m2 May 24 '20 at 10:14

# C (gcc), Score 622410 442766 states

Now ported from bash to C so it's much faster! (The program constructs all 20,000 Turing machines on TIO in about 10 seconds total.)

Note that this version of the program always computes all 20,000 Turing machines (saving them in 20,000 separate files). This is handy if you download the program and run it on your own computer. (TIO appears to delete all files as soon as the program halts, so the 20,000 files aren't very useful in that environment.)

It also displays one of the Turing machines on stdout (as determined by an argument you pass to it). This is practical for TIO.

Thanks to Surculose Sputum for pointing out that state t+3 in the original version was superfluous. Taking it out reduced the total number of states considerably!

Other changes: Reduced the base cases from 6 to 4. Fixed a few typos in the documentation, and improved the explanation a bit.

This program is based on a recursive construction: the idea is to construct an $$\n\$$-step Turing machine by taking a previously constructed $$\\frac{n}{2}\$$-step Turing machine and running it twice (except that this is adjusted a bit to take overhead into account).

I like this construction because it's easy to understand.

The program computes the Turing machines for 1 up to 20000, and it writes each Turing machine to a separate file.

It also accepts an argument $$\n,\$$ and displays the $$\n\$$-step Turing machine that was constructed on stdout (the default value for $$\n\$$ is 20000).

The score is correct for the challenge even if you request one of the smaller Turing machines, since, no matter what you pass as an argument, it always computes all 20,000 Turing machines and prints the correct codegolf challenge score for all 20,000 machines total.

If you run this on your own computer, run it in a directory by itself, because it will create files T1, T2, T3, ..., T20000 in the directory it's run in (one for each Turing machine).

/**********

INTRODUCTION

For each n from 1 to 20000, this program computes a Turing
machine Tn which takes exactly n steps when it runs.

The program writes all the computed Turing machines to
files T1, T2, T3, ..., T20000.

The total number of states for all 20000 machines is then
displayed.  (This is the score for the codegolf challenge.)

Also, one argument n is accepted on the command line; if provided,
it must be a number between 1 and 20000.  Turing machine Tn is
displayed on stdout.

If no argument is provided, the default is 20000.

Note that all 20000 machines are always computed and written
to the files on disk, but only the one you specify is written
to stdout.

Total time taken is about 10 seconds on TIO.

**********/

/**************

HOW TO COMPILE AND RUN

Save this file as tm.c, and compile it with the command

gcc -O3 -o tm tm.c

or, if you prefer,

gcc -O3 -Wall -Werror -W -o tm tm.c

Run it with a command like

./tm

or

./tm 50

This will display the Turing machine requested (T20000 or T50, in
the two examples above).

But you can look at all 20000 Turing machines in any case, since
they're all saved in files T1, T2, T3, ..., T20000.

(On TIO, the system will delete the saved files as soon as the
program finishes running, so they're not very useful in that
environment.)

**************/

/***************

FUNDAMENTAL IDEA

The idea is to compute a Turing machine which takes n steps to
run, by doing something as close as possible to the following:

Recursively take a machine that takes about n/2 steps to halt,
and run it twice.  (The base case for the recursion will be
n <= 4.)

This needs to be adjusted slightly because there are 3 steps
needed for overhead, so we need to use a machine that takes
(n-3)/2 steps to halt, instead of n/2 steps.

Also, if n is even, this leaves us one step short, so we
need to add an extra step in that case.

Since the challenge is to compute a machine for each n up to
20,000, there's no need to implement this using recursion in
the code.  Instead we just run through a loop, computing a
Turing machine for each n in turn.  But each computation
uses the previous results, just as the recursion suggests.

***************/

/***************

PROPERTIES OF THE CONSTRUCTED TURING MACHINES

These Turing machines never move to the left of position 0
(the starting position of the tape head).

If the all the cells from the starting position to the right
are initially 0, then Tn will take exactly n steps to run.

Each Turing machine leaves everything exactly as it found it
(tape cell data and tape head position).

Output format:
The program will write Turing machine Tn to a file called Tn
(where n is replaced by the actual number).

During execution, the Turing machine Tn is divided into 3 separate pieces:
The array element stateCountArray[n]  holds the number of states.
The file An holds tuples in the form   movement newval newstate  for when
the tape head is looking at a 0.
The file Bn holds tuples in the form   movement newval newstate  for when
the tape head is looking at a 1.

An and Bn have one tuple for each state, in order from
state 1 to the number of states.

The eventual machine Tn will consist of stateCountArray[n], An, and Bn, in that order.

***************/

#include <stdlib.h>
#include <stdio.h>
#include <unistd.h>

#define MAXn (20000)

int stateCountArray[MAXn + 1];
char filenameTemplate[] = "X99999";
int score = 0;

void openTupleFiles(int n, FILE **file0, FILE **file, char *fileMode);
void createOnePrecomputedTuringMachine(int n, int numberOfStates, char *tuplesFor0, char *tuplesFor1);

void adjustStates(int firstUnusedState, FILE *oldFile, FILE *file);
/**********
The routine adjustStates takes a previously computed Turing
machine and makes the changes necessary to incorporate it into the
Turing machine currently being computed.
**********/

void basis(void);

void invalidArgument(void);

int getNumericalArgument(int argc, char **argv);

void openTupleFiles(int n, FILE **file0, FILE **file1, char *fileMode)
/**********
Given n, opens the two files An and Bn, and returns them in the file
descriptors file1 and file2.  The two files are opened in the indicated
mode: "r", "w", ....
**********/
{
sprintf(filenameTemplate, "A%d", n);
*file0 = fopen(filenameTemplate, fileMode);
*filenameTemplate = 'B';
*file1 = fopen(filenameTemplate, fileMode);
}

void createOnePrecomputedTuringMachine(int n, int numberOfStates, char *tuplesFor0, char *tuplesFor1)
/**********
Used by the function basis.

Sets up stateCountArray[n], An, and Bn as specified,
and updates score.
**********/
{
FILE *theFile;

stateCountArray[n] = numberOfStates;

sprintf(filenameTemplate, "A%d", n);
theFile = fopen(filenameTemplate, "w");
fputs(tuplesFor0, theFile);
fclose(theFile);

sprintf(filenameTemplate, "B%d", n);
theFile = fopen(filenameTemplate, "w");
fputs(tuplesFor1, theFile);
fclose(theFile);

score += numberOfStates;
} // createOnePrecomputedTuringMachine

void adjustStates(int firstUnusedState, FILE *oldFile, FILE *file)
/**********
The routine adjustStates takes a previously computed Turing
machine and makes the changes necessary to incorporate it into the
Turing machine currently being computed.

oldFile should already be open for reading, and file should be open for writing.

Reads tuples from oldFile, writes tuples to file.

All states are shifted up by 1.

Each halting state is changed to a tuple which moves left and changes the state
to firstUnusedState.
**********/
{
char movement;
int newValue;
int newState;

while (3 == fscanf(oldFile, "%c%d%d%*c", &movement, &newValue, &newState))
{
if ('H' == movement)
{
movement = 'L';
newState = firstUnusedState;
}
else
newState++;

fprintf(file, "%c %d %d\n", movement, newValue, newState);
} // while
} // void adjustStates

void basis(void)
/**********
This handles values of n from 1 through 4, which form the basis of the recursion.

These Turing machines are precomputed.
**********/
{
createOnePrecomputedTuringMachine(1, 1, "H 0 1\n", "H 0 1\n");
createOnePrecomputedTuringMachine(2, 1, "S 1 1\n", "H 0 1\n");
createOnePrecomputedTuringMachine(3, 2, "S 1 1\nH 0 1\n", "S 1 2\nH 0 1\n");
createOnePrecomputedTuringMachine(4, 2, "S 1 1\nS 1 2\n", "S 0 2\nH 0 1\n");
} // basis

void invalidArgument(void)
{
printf("Usage: tm\n   or: tm n\nwhere n is a number between 1 and 20000\n(default is 20000).\n");
exit(1);
}

int getNumericalArgument(int argc, char **argv)
{
char * arg;
char *p;
int k = 0;

if (argc < 2)
return 20000;

if (argc > 2)
invalidArgument();

arg = argv;

if (0 == *arg)
return 20000;

for (p = arg; *p; p++)
{
if ((*p < '0') || ('9' < *p))
invalidArgument();

k = 10 * k + *p - '0';

if (k > 20000)
invalidArgument();
}

return k;
}

#define BUFFERSIZE (4096)

int main(int argc, char **argv)
{
int n;
int m;
FILE *An;
FILE *Bn;
int t;
FILE *Am;
FILE *Bm;

FILE *TuringMachineFile;
char byteArray[BUFFERSIZE];
int numberOfBytesRead;
int argument;

if (argc > 2)
invalidArgument();

argument = getNumericalArgument(argc, argv);

// For each values of n, we compute stateCountArray[n] and the two files An and Bn.

// First take care of the basis, n = 1 through 4.
basis();

// Now start the main loop for n = 5 and up:
for (n = 5; n <= MAXn; n++)
{

// We'll go through 2 runs of the machine Tm that we
// computed earlier, where m = floor((n-3)/2).

// There are 3 steps of overhead, and we add in one
// extra step if n happens to be even, because in that
// case, 2 * floor((n-3)/2) + 3 is n-1, not n.
// This will get us to exactly n steps.

m = (n - 3)/2;

// Open files An and Bn for writing.
openTupleFiles(n, &An, &Bn, "w");

// Go through two runs of machine Tm.
// The cell at position 0 will keeep track of which run
// we're on (0 for the first run, 1 for the second).

// At the beginning, position 0 holds a 0, so we
// move right to position 1 and go to state 2.
fputs("R 0 2\n", An);

// For even n, at the end of the entire run of Tn, we'll
// find ourselves back in state 1 at position 0, but the
// contents of that cell will be 0, and we'll halt.
// (For odd n, the machine will halt without going back
// to state 1.)
fputs("H 0 1\n", Bn);

// Compute the number of states in the new machine Tn.
// It's two more than the number if states in Tm.
t = stateCountArray[m] + 2;

// Open files Am and Bm for reading.
openTupleFiles(m, &Am, &Bm, "r");

// The two calls below to the function adjustStates copy machine Tm
// into the Turing machine that we're building, with the following
// modifications:
//   - Use states 2 through t+1 instead of 1 through t.
//   - Halt tuples (H) get altered to tuples that don't halt
//       but instead move left (L) and change to state t+2.

adjustStates(t, Am, An);
fclose(Am);

adjustStates(t, Bm, Bn);
fclose(Bm);

// Since we're in state 2 at position 1, we're all set to run
// the altered copy of Tm, so that happens next.

// After running the altered copy of Tm, we're back at position 0,
// since the original Tm would have left us at position 1, but the
// altered version changed every H to an L, causing the tape head
// to move left one position, to position 0.

// If the tape head is looking at 0 in position 0,
// we just finished the first of the two runs of Tm.
// In that case, write a 1 to position 0 to indicate
// that we're on the second run now.
// Move right to position 1 and change to state 2.
// That will start the second run of Tm.

fputs("R 1 2\n", An);
fclose(An);

// If the tape head is looking at a 1 in position 0,
// we just finished our second run of Tm.  We're ready
// to halt, except that if n is even, we need to add
// one extra step.
if (n % 2)
{  // n is odd, so halt.
fputs("H 0 1\n", Bn);
}
else
{ // n is even, so change to state 1 (which
// will take the extra step we need).
// State 1 will then halt because it's
// looking at a 1.
fputs("S 1 1\n", Bn);
}

fclose(Bn);

// Store the number of states for Tn in stateCountArray,
// and update the score..
stateCountArray[n] = t;
score += t;
} // for n

// Print the codegolf challenge score (the total number of
// states in all 20000 Turing machines).

printf("Score (up to 20000) = %d\n\n", score);

// Write each Turing machine Tn to the file called Tn (where
// n is the actual number).
// First write stateCountArray[n], then copy file An, and
// after that copy file Bn.

// Also delete the files An and Bn.

for (n = 1; n <= MAXn; n++)
{
openTupleFiles(n, &An, &Bn, "r");

sprintf(filenameTemplate, "T%d", n);
TuringMachineFile = fopen(filenameTemplate, "w");

fprintf(TuringMachineFile, "%d\n", stateCountArray[n]);

numberOfBytesRead = fread(byteArray, sizeof(char), BUFFERSIZE, An);
fwrite(byteArray, sizeof(char), numberOfBytesRead, TuringMachineFile);
fclose(An);

numberOfBytesRead = fread(byteArray, sizeof(char), BUFFERSIZE, Bn);
fwrite(byteArray, sizeof(char), numberOfBytesRead, TuringMachineFile);
fclose(Bn);

fclose(TuringMachineFile);

*filenameTemplate = 'A';
unlink(filenameTemplate);

*filenameTemplate = 'B';
unlink(filenameTemplate);
} // for n

// Finally print the requested Turing machine to stdout.

(void) printf("Turing machine which halts after exactly %d steps:\n", argument);
sprintf(filenameTemplate, "T%d", argument);
TuringMachineFile = fopen(filenameTemplate, "r");
numberOfBytesRead = fread(byteArray, sizeof(char), BUFFERSIZE, TuringMachineFile);
fwrite(byteArray, sizeof(char), numberOfBytesRead, stdout);
fclose(TuringMachineFile);

exit(0);
} // main



Try it online!

• I think the ideas of the C++ answer can be used to compute more/better base cases (I'm not sure how much exactly that will help). Is the current first step necessary? (I think it can be avoided by relabeling states). – the default. May 31 '20 at 8:47
• @mypronounismonicareinstate Thanks, I'll take a look at the C++ answer (I haven't really looked at the other answers, except to see Surculose Sputum's impressive score). More base cases would certainly help; the difficulty with that is that the method seems to require machines which leave everything the same at the end as at the beginning, so I couldn't simply use most machines I'd find elsewhere. (I looked a bit at using known Busy Beaver champions as base cases, but they didn't seem to be directly applicable for that reason.) – Mitchell Spector May 31 '20 at 8:52
• @mypronounismonicareinstate As for relabeling states, it could be that there's some way to do it. I tried a version where I used the cell in position -1 to keep track of which of the two runs it was on. The idea was that I could then run the smaller Turing machine in its original place, getting the overhead down from 5 steps to 3 steps. But this doesn't work because each recursive call needs to have its own copy of the run-counter (like a stack frame in traditional function calls). .... (continued) – Mitchell Spector May 31 '20 at 9:00
• ...(continued) The working version solves that by essentially shifting every recursive call one step to the right. I didn't pursue the other approach because I thought that handling this issue would probably take more than the 2 steps I was saving. (One could use a bunch of cells on the negative side to keep track of the various run counters, but I think that would add far too many steps to be useful.) – Mitchell Spector May 31 '20 at 9:00
• I think you can get rid of state $t+3$ with the following modification: (1) states 1 moves to position 1 to start $T_m$: R 0 2 (2) The halt state of $T_m$ moves back to position 0 and call state $t+2$: L 0 t+2 (3) State $t+2$ sees a zero, and thus calls $T_m$ again, and sets position 0 to one: R 1 2 (4) $T_m$ goes another round, then calls $t+2$ at position 0 (5) State $t+2$ sees a one, and thus halts. (5b) In the wrong parity case, state $t+2$ sees a one, and calls state 1: S 1 1 (6b) state 1 halts. – Surculose Sputum May 31 '20 at 16:31

# Python 2, 100010000 states

n = input()
m = -~n / 2
print m
for i in range(m): print "S" if i * 2 < n - 1 else "H", 1, i + 1
for i in range(m): print "S" if i * 2 < n - 2 else "H", 0, -~i % m + 1


Try it online! Just to get the ball rolling.

• Because of issues mentioned in the comments of the main post, I had to increase the upper bound on N. Could you update your score accordingly? – the default. May 23 '20 at 18:20