A394183 Maximum number of steps before halting among all 2-state 2-symbol Turing machines on an n-cell circular tape, over all binary starting tapes and starting head positions.

4, 7, 11, 13, 21, 23, 36, 35, 55, 47, 78, 59, 105, 81, 136, 108, 171, 139, 210

Offset

1,1

Comments

There are two working states A and B, one halt state H, and two symbols 0 and 1. For each pair (state, symbol), a transition writes 0 or 1, moves left or right on the circular tape, and enters A, B, or H, giving 12^4 = 20736 transition tables. The initial state is A. The maximum is taken over all transition tables, all binary starting tapes of length n, and all starting head positions.

By circular rotation symmetry it suffices to check starting head position 0 and all 2^n binary tapes.

A nonhalting run is detected once a running configuration (state, head position, tape contents) repeats. There are n*2^(n+1) running configurations, so every halting run halts within that many steps.

Terms a(1) through a(19) were verified by exhaustive enumeration.

The tape cells are arranged cyclically: a move from cell i goes to i-1 or i+1 modulo n. Thus for n = 1 both moves return to the same cell, for n = 2 both left and right moves go to the other cell, and for n >= 3 the cells form the cycle graph C_n.

Links

Table of n, a(n) for n=1..19.

Formula

Empirically, for odd n = 5, 7, ..., 19, a(n) = (n+1)*(n+2)/2.

Example

For n = 1, all 20736 transition tables and 2 starting tapes are checked; the maximum halting time is 4.
For n = 19, 20736*2^19 = 10871635968 runs were checked. The maximum halting time is a(19) = 210; 7728597856 runs halt and 3143038112 runs loop.

Prog

(Python)
def A(n):
    def decode(m):
        T = []
        for _ in range(4):
            c = m % 12
            m //= 12
            T.append((c % 2, 1 if (c // 2) % 2 else -1, c // 4))
        return T
    best = 0
    step_limit = n * (1 << (n + 1))
    # By circular symmetry it suffices to start the head at position 0.
    for m in range(12**4):
        T = decode(m)
        for tape0 in range(1 << n):
            tape = tape0
            pos = 0
            state = 0
            steps = 0
            while state != 2 and steps < step_limit:
                sym = (tape >> pos) & 1
                write, move, state = T[2*state + sym]
                if write:
                    tape |= 1 << pos
                else:
                    tape &= ~(1 << pos)
                pos = (pos + move) % n
                steps += 1
            if state == 2 and steps > best:
                best = steps
    return best
print([A(n) for n in range(1, 5)])

Crossrefs

Cf. A386859.

Sequence in context: A308199 A310722 A092403 * A219051 A376355 A310723

Adjacent sequences: A394180 A394181 A394182 * A394184 A394185 A394186

Keyword

nonn,hard,more

Author

Reed Silverstein, May 04 2026

Status

approved