The easy fates: halt, cycler, translated cycler, bouncer
Most machines quickly do one of four things, and each one has a look you can learn to spot. They halt, they repeat in place (a cycler), they repeat while sliding along the tape (a translated cycler), or they go back and forth between ends that move apart (a bouncer).
Programs called deciders prove machines like these automatically. A holdout is a machine that every decider failed on.
0The four pictures
Each picture is a real run, simulated in this page: one row per step, time going down, the same scale for all four. The coloured cell is the head (its colour is its state).
Halt
4-state champion, steps 0–107
The run stops. The last row is step 107, the halt.
Cycler
steps 0–107
The same 12 rows again and again, in place (lines at steps 12, 24, …).
Translated cycler
steps 0–107
The same 10 rows again and again, each time 2 cells further right: a straight diagonal.
Bouncer
steps 0–107
Back and forth. Each trip is 4 steps longer, and the left end moves out one cell.
1 0 (visited) never visited · head: A B C D E, halted · 1 cell = 7 px wide, 1 step = 3 px tall
1Halt
Press play. At step 21, A reads a 1, and A1 = 1RZ sends the head to Z, the halt state. The run is over: 21 steps (the halting step counts), five 1s left, never more than 5 cells used.
No 3-state machine runs longer and still halts, so this is the 3-state step champion. The most 1s a 3-state machine can leave is six, from a different machine that halts at step 14.
The 4-state champion in the first picture halts at step 107 with thirteen 1s. For a machine that halts, the run is the proof: simulate it and watch it stop. (Some halt far too late to watch: module 6.)
2Cycler: the same picture comes back
Step to the end. At step 12 the tape is blank again and A is back on cell 0: exactly the picture at step 0. The machine has nothing else to remember, so from step 12 it must do the same 12 steps again, forever.
How it is caught. The Loops decider stores the configurations it has seen (state, head cell, tape) and stops when one comes back. Any machine whose head stays inside a fixed stretch of cells must repeat sooner or later, since only finitely many tapes fit there. So a machine that never halts and never needs a new cell is always a cycler.
3Translated cycler: the same picture, shifted
Watch the right edge. At steps 6, 16 and 26, D steps onto a cell no one has visited yet: cells 2, 4 and 6. Each time, the cells at the head read 1 0 D> (D reading the cell after the 1 0) with blank tape to the right: the same picture, 2 cells further right.
That gives a rule: from 1 0 D> followed by n blank pairs 00, 10n steps carry the 1 0 D> across them. The box below runs it for n = 1 to 7. The head never goes more than 2 cells left of D, so nothing further left can ever change what happens.
How it is caught. Loops also compares the moments when the head reaches a new cell. Here are two of them:
Same state D, and the same 3 cells 1 0 0 ending at the head, with blank tape to the right. Between steps 6 and 16 the head never went left of cell 0, so those 3 cells are all the run looked at. So steps 16 to 26 repeat steps 6 to 16, 2 cells further right, and so on forever.
The bbchallenge wiki says 95% of all non-halting 6-state machines are translated cyclers that have cycled at least once within their first 1,000 steps.
4Bouncer: trips that keep getting longer
Every trip has the same shape. A writes a 1 on a new cell at the left. A single 0, the hole, walks right through the 1s. At the right end the head turns and runs left over the whole block onto the next new cell.
Here is one trip, step by step. Watch the bracket: it is the hole.
The hole moves one cell right every 3 steps (A0, B1, C1). So each 1 in the block costs 4 steps per trip: 3 for the hole to pass it and 1 on the run back (A1).
The block grows by one cell per trip, so each trip takes 4 steps more than the last: new cells on the left at steps 3, 10, 21, 36, 55. That is why it is not a translated cycler: the picture never comes back, not even shifted.
Why it never halts, from the table
The only halt is C reading 0 (red dashes). C is entered only by B1, and B only by A0.
A0 writes a 1 and moves right; if B then reads a 1, B1 moves straight back onto the 1 that A0 just wrote. So C always reads a 1, and the halt C0 can never happen. (Simulation agrees: C0 is never used in 106 steps.)
How it is caught. Those three lines are already a proof. Deciders find a different one: a list of tape shapes. Every tape is a block of 1s with at most one hole in it, and the head is in one of four spots:
One step from any tape of these four shapes gives a tape of these four shapes again, and C appears only in the first, standing on a 1. So no run that starts on the blank tape (A on the hole) can ever reach C reading 0.
Pattern deciders (CTL, FAR and their relatives) search for shape lists like this one. Dedicated Bouncers deciders look instead for new-cell moments whose gaps grow by a constant (7, 11, 15, 19 here).
5What the deciders catch, and what is left
Three words first:
- STF
- Standard Text Format, the machine string that names every machine on this page.
1RB1LA_0LA0LC_---1RAis the bouncer's table above: one group per state (A, B, C), and in each group what to do on a 0 and on a 1 (write, move, next state).---is undefined, and reaching it halts. - TNF
- Tree Normal Form, how machines are listed. A transition is filled in only when the run first needs it, and machines that differ only by renamed states (a permutation) are listed once.
- holdout list
- The community's list of machines that every step below failed on. Each one needs its own proof, by hand or by a new tool.
The deciders, one line each:
- simulation
- Run the machine. If it halts, that run is the proof (section 1).
- Loops
- Remember earlier tapes. One that comes back, in place or shifted at a new cell, proves a cycler or a translated cycler (sections 2 and 3).
- n-gram CPS
- Keep only short pieces of the tape (n cells each) and show that the set of pieces the run can produce stops growing without ever allowing a halt.
- RepWL
- Write the tape as repeated words, but count copies only up to a cap ("1, 2, … or many"), and show that these rough tapes close up without a halt.
- CTL / FAR
- Search for a tape pattern that the start fits, that one step keeps, and that can never halt, like the bouncer's four shapes in section 4.
- inductive deciders
- Find rules that hold for every n, like the slide rule in section 3, prove them by induction, and chain them.
Why does a holdout escape? Usually for one of three reasons:
The proof needs a fact like "this block is shorter than that one". A pattern can count a block's length modulo a fixed number, but it cannot compare two lengths that both grow. Module 5.
The rules are about rules: a counter inside a bell, a cycle inside a cycle. That goes beyond what the inductive deciders try. Modules 3 and 4.
A proof would settle an open number problem, like Collatz. No cheap pattern can exist unless that problem is easy after all. Module 7.
W5-8: a bouncer that every decider missed
1RB1LD_0RC1RC_1LA1RE_---1LE_1RF0RC_0RB0LF, line 214 of the 740 list, listed in the class "Bouncer + Chaotic Edge". At heart it is a bouncer: the head runs back and forth, and the two ends move apart. Our Coq proof that it never halts passes all our kill checks (its only undefined cell is D0).
What it adds to a plain bouncer: the fixed gadget at the left end, and five blocks of 1s with four short words, the particles, between them. This is the real tape at the start of one trip, with each block of 1s drawn as one bar:
Read the table. Every 12 trips the first block grows by 48, the second shrinks by 8, the third and fifth grow by 4, and the fourth stays at 45.
At the last row the second block is down to 2. Then the particles collide: 147 trips later the tape has the same shape again, with lengths (2739, 38, 96, 35, 18).
Nine more collisions follow, of four kinds, in no regular order. From step 153,126,993 on, only two kinds are left, and they alternate forever.
Why every decider missed it: reason 2 above, a cycle inside a cycle. From step 153,126,993 the 12-trip step of the table repeats 26 times, then a collision, then 20 times, then a collision; then 30 and 24; then 34 and 28. Each round the counts grow by 4, so the proof needs one induction (the 12-trip step, repeated) inside another (the rounds).
Inside each trip the head crosses the long blocks with shift rules like this one, which turns 11 pairs into 10 pairs, 2 steps per pair:
W5-8 machine page (with its write-up)W5-8's new-cell rows in the explorer
Recap
- Halt: it stops. Cycler: the same rows repeat in place. Translated cycler: they repeat, shifted. Bouncer: back and forth, each trip a little longer.
- Simulation proves halts; Loops catches both kinds of cycler; pattern deciders (CTL, FAR, …) catch simple bouncers.
- A holdout escapes because its proof compares two growing sizes, needs induction nested deeper than the deciders go, or would settle an open number problem (a cryptid).