Turing machine · 6 states, 2 symbols · one halt rule, out of reach for at least 4.8 × 10⁴⁸ steps
From a blank tape this machine fills the tape with stripes, 1010…, and keeps a few marks in them: a gap of three 0s, markers of two 1s, and walls of two 0s. The head bounces between the gap and the next mark to its right. Each bounce moves the gap two cells right and a marker two cells left, so the two meet halfway. The eleven rules split into three ways of moving along the tape and a handful of short fixed sequences, and the mark the head reaches decides which one runs next.
Hover over or tap any rule name, such as D1, to see what it does. The Rules button in the corner opens the full table.
| State | Reads 0 | Reads 1 |
|---|---|---|
| A | write 1, →, Bshiftgap stepturn | write 0, →, Ecarrygap step |
| B | write 1, ←, Ccarryturn | write 0, →, Ashiftgap stepturn |
| C | write 1, ←, Acarry | write 1, ←, Dfixedturn |
| D | write 1, ←, Afixedturn | halt (no rule)halt |
| E | write 0, →, Fpassturn | write 0, ←, Bcarryturn |
| F | write 0, ←, Dturn | write 1, →, Epass |
Each entry says what to write, which way to move and the next state, so the last letter of one rule names the state of the next. Every sequence on this page is written in that firing order. D1 has no entry: it is the halt.
Every routine works in pairs of cells. The stripes repeat every two cells, and each cycle covers exactly two: a carry cycle moves the packet two cells, a pass cycle crosses one 0 and one 1, and a shift cycle rewrites one of each. Anything that breaks the 1010 rhythm stops the cycle, and that is what makes the marks signposts.
One read in each cycle checks the tape. On the way right, E1 instead of E0 means a marker or a block, and F0 instead of F1 means a wall. On the way left, A0 instead of A1 means a gap, a wall or the blank end, and C1 instead of C0 means a marker, or a block.
This is the whole tape at step 4,264, with the head on the packet's first cell. Everywhere else it is plain stripes. Each mark is a break in the 1010 rhythm, and the routines stop at them.
Real steps from the run. The outlined cell is under the head, the letter is the head's state, and the text says which rule fires next. 0s are dark.
The packet 111 starts under A. A and E erase two 1s, B writes one back, and C fills the stripe 0 ahead. Four steps later the packet sits two cells further left.
Just after a gap step. E reads the stripe 0s and F the 1s, and nothing on the tape changes.
The carry's last C0 writes a 1 into the gap's last 0, and A0 writes one into its middle 0. B1 and A1 then clear the next two cells, so the gap now starts two cells further right. E begins the pass.
E and F read the wall's 00, and D writes a 1 into its first cell. A starts a carry on that 1 and the stripe 1 before it. One cycle later they are a packet and the wall is 00 again.
A gap has just run into a wall, leaving four 0s in a row. E0 F0 D0 turn the head, and the shift starts: each A0 writes 1 over a 0 and each B1 writes 0 over a 1.
Every step from 4,318 to 4,337. By the end the marker sits two cells further left, the packet has crossed it, and the carry is heading back to the gap.
The head's path through each part, drawn against the tape. Time runs down the page. A carry takes two steps per cell, so carry segments are drawn twice as steep as passes and shifts. Region widths are schematic, and the numbers match the list beside each drawing.
The gap moves two cells right and the marker two cells left, so the stripes between them lose four cells.
About three steps per cell between them: one going out, two coming back. This bounce is most of the run.
The gap moves two cells right and the wall stays put, so the stripes between them lose two cells.
The same three steps per cell as a marker bounce, but the distance shrinks half as fast.
The marker ends up just left of the gap, and the gap goes on to the next mark.
Ends a run of marker bounces. The last bounce has no stripes left to cross.
The gap and the marker become a wall where they met, and the packet heads on to the next gap to the left.
Mostly the long carry back, two steps per cell.
Gap and wall disappear. A shift carries the change to the next mark, here the right end, which gains a marker. The packet heads back left.
One step per cell for the shift, two per cell for the carry back.
The machine stops. This never happened in 3 billion steps.
What happens depends only on how the head is moving and which mark it reaches. In the first 3 billion steps the run uses nothing but the three cycles and the short sequences listed here.
| The head is | and reaches | What happens | Rules |
|---|---|---|---|
| Carrying a packet left | a gap 000 | Gap step: the gap moves two cells right and the head turns right. | A0 B1 A1 |
| a marker 11 | Marker pass: the packet crosses and the marker stays put. | A1 E1 B0 C1 D0 | |
| a wall 00 | The wall becomes a marker with a gap just right of it, and the head turns right. | A0 B1 A1 | |
| blank tape at the left end | A new gap starts there, and the tape is two cells longer. | A0 B1 A1 | |
| a block 111 | Halt. Never seen in the run. | A1 E1 B0 C1 D1 | |
| Passing right | a marker 11 | Marker turn: the marker moves two cells left and the head comes back with a packet. | E1 B1 A0 B0 C1 D0 A0 B1 |
| a wall 00, or blank tape | Wall turn: nothing moves, and the head comes back with a packet. | E0 F0 D0 | |
| a block 111 | The block becomes a wall, and a shift starts from there. | E1 B1, then A0 B1 repeating | |
| After a gap step | a wall right next to the gap | Gap and wall run together, and a shift starts from there. | A1 E0 F0 D0, then A0 B1 repeating |
| Shifting right | a marker 11 | The marker is used up. A gap opens where it was, and the head passes right from there. | A1, then E0 F1 |
| a wall 00 | The wall becomes a block, and the head comes back with a packet. | A0 B0 C1 D0 | |
| blank tape at the right end | The end gains a marker, and the head comes back with a packet. | A0 B0 C1 D0, or A1 E0 F0 D0 A0 B1 A0 B0 C1 D0 | |
| Gap and marker closing in | each other, 4k stripe cells apart at the start | Swap: the marker ends up just left of the gap, which goes on. | marker turn, two carry cycles, gap step |
| each other, 4k + 2 cells apart | Merge: they become a wall, and the packet goes on to the next gap to the left. | marker turn, carry cycle, A1 E1 B0 C1 D0 A0 B1 |
Every so often the tape is clean: nothing but stripes and the end's marker, 1 0 (10)ⁿ 1 1, while the head carries one last packet to the left end. The run below starts from the clean tape with n = 62 at step 43,385 and ends at the next one, n = 77, at step 79,549.
The packet starts a gap at the left end, and the gap closes in on the end's marker. Gap and marker move at the same speed, so they meet in the middle and swap. The gap goes on to the blank right end, which it can only reach two cells at a time, and the meeting there sends a packet back to start the next gap.
Each new gap first meets the marker the previous one left behind, at half the distance, and swaps with it. So the markers on the left sit at about 1/2, 1/4, 1/8, 1/16 … of the way along. After the swap the gap goes on to meet whatever lies beyond: a marker (swap or merge), a wall, or the end.
After about log₂ n rounds the newest marker lands at the left end. The next packet to cross it turns it into a wall and starts a new gap just beyond. The gap meets the wall almost at once, and the shift runs over the whole tape to the right end. That clears the last marks and leaves a clean tape again, a few cells longer.
| after step | n | cells |
|---|---|---|
| 45 | 2 | 8 |
| 913 | 14 | 32 |
| 33,829 | 59 | 122 |
| 43,385 | 62 | 128 |
| 79,549 | 77 | 158 |
| 95,117 | 80 | 164 |
| 116,309 | 86 | 176 |
| 155,059 | 95 | 194 |
| 178,097 | 98 | 200 |
| 245,823 | 110 | 224 |
| … | ||
| 2,937,038,187 | 2,546 | 5,096 |
| 2,994,703,663 | 2,561 | 5,126 |
The tape only grows at its ends: two cells on the left each time a new gap starts there, and a few on the right each time a gap or a shift reaches the right end. By step 2,994,703,663, the last clean tape in the first 3 billion steps, n is 2,561 and the tape is 5,126 cells long.
A cycle's step count grows with the square of the tape length, since each round's bouncing covers a stretch comparable to the tape. Meanwhile n goes up by about 9 per cycle on average, from 2 to 2,561 over 283 cycles. Together that makes the total grow like the cube of the tape length: between 0.022 × (cells)³ and 0.024 × (cells)³ at every clean tape once n passes 100.
Every n is 2 more than a multiple of 3. Count the 1s on the tape, and add 1 when the head is in C, D, E or F, or 2 when it is in B. No rule changes this total mod 3. For example, A0 writes a 1 and switches to B, adding 1 + 2, and E1 erases a 1 and switches from E to B, adding −1 + 2 − 1. The blank tape starts at 0. When the last carry of a clean tape reaches the left end, the head is in A on 1 1 (10)ⁿ 1 1, which holds n + 4 ones. So n + 4 is always a multiple of 3, and n can only grow by multiples of 3: by 3 most often, and by as much as 57 in the first 3 billion steps. The next section works out the exact amount.
Everything the head does is decided by where the marks are, so the run can be followed without its steps. Keep a list of the marks and update it with a few rules. Each rule replaces thousands or millions of steps.
Count cells from the leftmost 1, which is cell 0, and let w be the number of cells up to the right end of the tape. A mark is named by its first cell: G g is a gap at cells g to g + 2, M p a marker at p and p + 1, W q a wall and B r a block. A round starts when a packet reaches the left end and opens a gap at cell 1. Right after the clean tape with n, the marks are G1 and M(2n + 4), and w = 2n + 6.
For a gap and the marker ahead of it, the number that matters is d = p − g − 3, the count of stripe cells between them. It is always even. Each bounce moves the gap two cells right and the marker two cells left, so d drops by 4 per bounce. What is left over at the end decides the meeting: 0 cells gives a swap and 2 cells a merge.
| Reaches | What happens | Positions afterwards |
|---|---|---|
| Gap at g moving rightNext mark | ||
| a marker p, with d a multiple of 4 | Swap, after d/4 bounces | marker → g + d/2 − 1, gap → g + d/2 + 1, and the gap goes on |
| a marker p, with d 2 more than a multiple of 4 | Merge, after (d − 2)/4 bounces | a wall at g + d/2 + 3; a packet heads back |
| a wall q | Gap and wall vanish, and a shift starts at q | see the shift rows |
| a block r | The block becomes a wall, the gap falls asleep, and a shift starts | a wall at r − 1 |
| nothing, only blank tape | A new end marker forms | w grows by 3, with the new end marker 2 cells before the new end; a packet heads back |
| Shift moving rightNext mark | ||
| a marker p | The marker becomes the new gap | a gap at p, which goes on |
| a wall q | The wall becomes a block | a block at q; a packet heads back |
| a block r | The block becomes a wall | a wall at r + 2; a packet heads back |
| blank tape | A new end marker forms | w grows by 2, with the new end marker 2 cells before the new end; a packet heads back |
| Packet moving leftFirst mark that isn't a marker | ||
| a sleeping gap h | A gap step wakes it | gap → h + 2 |
| a wall q | The wall becomes a marker and a gap | marker at q − 1, gap at q + 1 |
| the left end | A new round starts | every position + 2, a new gap at 1 (+ 4 if a marker sits at cell 0; it becomes a wall at 5) |
| a block | The machine halts | never happens within these rules |
A gap or shift only ever deals with the nearest mark to its right, and a packet crosses markers until it finds something else. Each rule also has an exact step count. For example, k bounces of a gap toward a marker, ending with m stripe pairs still between them, take 6km + 6k² + 24k steps.
The run from the clean tape with n = 14. Every list of marks here matches the tape in the step-by-step run.
| Round starts | Event | Arithmetic | Marks afterwards |
|---|---|---|---|
| Step 921w = 34 · G1 M32the clean tape n = 14 | Gap 1 closes in on marker 32 | d = 32 − 1 − 3 = 28 = 4 × 7, so a swap after 7 bounces | M14, G16 |
| Gap 16 has blank tape ahead | w = 34 + 3 = 37, end marker at 35 | M14, M35 | |
| The packet crosses M14 and reaches the left end | every position + 2 | w = 39 · G1 M16 M37 | |
| Step 1,749w = 39 · G1 M16 M37 | Gap 1 closes in on marker 16 | d = 16 − 1 − 3 = 12 = 4 × 3, so a swap after 3 bounces | M6, G8 |
| Gap 8 closes in on marker 37 | d = 37 − 8 − 3 = 26 = 4 × 6 + 2, so a merge after 6 bounces, into a wall at 8 + 13 + 3 | M6, W24 | |
| The packet crosses M6 and reaches the left end | every position + 2 | w = 41 · G1 M8 W26 | |
| Step 2,367w = 41 · G1 M8 W26 | Gap 1 closes in on marker 8 | d = 8 − 1 − 3 = 4, so a swap after 1 bounce | M2, G4 |
| Gap 4 reaches wall 26, and the shift runs to blank tape | w = 41 + 2 = 43, end marker at 41 | M2, M41 | |
| The packet crosses M2 and reaches the left end | every position + 2 | w = 45 · G1 M4 M43, at step 2,915 |
| Clean tape | Next clean tape | Rounds | Share |
|---|---|---|---|
| n odd | n + 3 | 2 | 35% |
| n a multiple of 4 | n + 6 | 3 | 14% |
| n = 26 or 38 (mod 48) | n + 9 | 5 | 23% |
| n = 2 (mod 96) | n + 12 | 5 or 6 | 9% |
| any other n | round by round | 7 to 43 | 19% |
Share: how often each case comes up among the first 10,000 clean tapes of the run. The rules in the first four rows hold for every n up to 200,000.
Odd n takes two rounds. The first gap starts at 1 and the end marker sits at 2n + 4, so d = 2n. For odd n that is 2 more than a multiple of 4, so they merge into a wall at 1 + n + 3 = n + 4. The new round shifts it to n + 6. In the second round the gap meets that wall, and the shift runs off the right end, where it adds an end marker and 2 cells. That leaves only stripes and the end marker, now at 2n + 8: the clean tape with n + 3.
Other n take longer. For even n the first meeting is a swap, and the marker lands in the middle at cell n. The next gap meets it with d = n − 2, so a multiple of 4 merges here and any other even n swaps again. Each further round halves the distance once more, so the outcome depends on more and more of the low binary digits of n, until a merge or a wall breaks the pattern. A multiple of 4 is settled in 3 rounds. n = 14 needs 24 rounds to reach 59, and n = 302 needs 23 to reach 341.
For 29 n in 32, the last five binary digits decide the next clean tape. Running the rules on whole residue classes of n gives the next clean tape exactly: n + 3 for odd n, n + 6 for n a multiple of 4, n + 9 for n that leave 6 or 10 when divided by 16, and n + 12 for n that leave 2 when divided by 32. Only n that leave 14, 18 or 30 when divided by 32 need more digits, and every right-end run of more than two meetings happens there. Each further digit settles about a quarter of what is still open.
Each rule is proved from the rule table. I ran the machine on each rule's starting pattern with the stripe lengths left as symbols and the tape around it unknown. So each rule holds for every length and whatever surrounds it, with an exact step count. A simulation that uses nothing but these rules, starting from a blank tape, reproduces every round and clean tape of the 3 billion step run.
The rules carry the run much further. That simulation reached step 16,470,069,173,330,669,103, about 1.6 × 10¹⁹, and the clean tape with n = 4,529,102, without meeting an arrangement of marks the rules don't cover. A fast program that applies the same rules to the list of marks then followed the machine's clean tapes to n = 14,874,910,607, roughly 6 × 10²⁹ steps. No two marks ever came closer than they already had by n = 302. The deepest cycles along the way, replayed with the certified simulation, give the same results.
Then by residue class. From there the jump to each next clean tape was looked up from the residue classes of n described in Does it ever halt?, and only the few n whose class is still open were simulated. Every millionth looked-up step was simulated again as a check, and all 103,032 checks agreed. That carried the clean tapes to n = 10¹², after 110,250,943,952 cycles and roughly 2 × 10³⁵ steps.
The clean tapes follow a fixed track. For almost every n the jump depends only on the last few dozen binary digits of n. So modulo 2ᵏ the clean tapes run around a fixed cycle of residues. Each lap of 3 · 2ᵏ visits a third of them, and consecutive laps share more than 99%. A residue class is either visited once per lap or never. That is why the 10-meeting cascades in the run come exactly 3 · 2²⁸ apart. The track also favours the residues where cascades start: along it, deep cascades are about 2.3 times as common as for n picked at random. That is no special property of the machine's own n: a third of its clean tapes are odd, and the rest land on residues with exactly the frequencies of a Markov chain on residues built from random n, which visits n that leave 2 when divided by 16 about three times as often as a random sequence would.
There is no separate setup code. From a blank tape the same routines build the first stripes, gap and end marker in 45 steps, and the tape is clean for the first time with n = 2.
| steps | part | rules | what it does |
|---|---|---|---|
| 0–3 | Write 111 | A0 B0 C1 D0 | Blank tape. A, B and C write 111, the same sequence that ends a shift at the blank end, and D turns the head left. |
| 4–5 | First stripe | A0 B1 | A finds blank tape where a stripe 0 should be. A0 B1 write 1 0 in front of the 111, so the head can start carrying. |
| 6–13 | Carry | A1 E1 B0 C0 A1 E1 B0 C0 | Two carry cycles take the packet to the left end. |
| 14–16 | First gap | A0 B1 A1 | The packet reaches the blank tape at the left end. As at every left end, A0 B1 A1 leave 1 000: the first gap. |
| 17–21 | Pass and wall turn | E0 F1 E0 F0 D0 | Pass right to the end of the tape. The blank tape there works as a wall: E0 F0 D0 turn the head with a new packet. |
| 22–25 | Carry | A1 E1 B0 C0 | Carry it back to the gap. |
| 26–28 | Gap step | A0 B1 A1 | Gap step. The gap moves two cells right and is now next to the blank tape. |
| 29–31 | Gap meets the end | E0 F0 D0 | The gap meets that wall: E0 F0 D0 again, this time starting a shift. |
| 32–33 | Shift | A0 B1 | One shift cycle reaches the blank tape. |
| 34–37 | End marker | A0 B0 C1 D0 | A0 B0 C1 D0 write three 1s there: the end's marker plus the start of a packet. |
| 38–45 | Carry | A1 E1 B0 C0 A1 E1 B0 C0 | Carry the packet left. After step 45 the tape holds only stripes and the end marker: 10 1010 11, the first clean tape. |
Each meeting between a gap and the end marker moves the action near the right end about halfway closer to the end. Call the distance at a meeting d. The next distance follows from the binary digits of d + 2. If they end in 00, the meeting is a merge and d + 2 loses its last digit. If they end in 10, it is a swap: d + 2 loses its last digit and gains 5. On its own this rule would carry on to the end of the tape. What stops it is the supply of feeds from the left.
The feed is a halving clock at the left end. During a long cascade the leftmost mark is usually a marker that halves its cell number every round. Each round it swaps with the gap, the gap goes on to the middle and right of the tape, and roughly every second round that produces a meeting. When the marker merges into a wall near the left end, that run of fuel is over.
New fuel comes from blocks. Suppose a round starts with the gap facing a block at cell r. If r has one trailing zero in binary, the next round starts with a wall at r/2 + 4, which feeds the next round directly. If r has k ≥ 2 trailing zeros, it starts with a marker at r/2 that halves for k − 2 rounds. This held in all 4,471 cases checked. The first halving after a clean tape follows the same rule: the marker starts at 2(n + 2), swaps once for each trailing zero of n + 2, and merges into a wall at (n + 2 without its trailing zeros) + 4.
Each block forms at an average. On the main path, a block at r, with the wall near the right end at R and a tape w cells long, leads two rounds later to a block at (r + R + 11)/2, a right-end wall at (R + w + 11)/2 and a tape w + 6 cells long. The right wall's distance to the end goes from D to (D + 1)/2.
| Class of n | Meetings | Digits |
|---|---|---|
| 73,742 mod 2³⁰ | 10 | 30 |
| 26,819,166 mod 2³⁵ | 11 | 35 |
| 4,321,786,462 mod 2³³ | 12 | 33 |
| 363,165,946,702 mod 2⁴¹ | 14 | 41 |
Every large n in each class has exactly this many meetings. Digits: how many binary digits of n the class fixes. The deepest cascades spend 1.5 to 2 trailing zeros of the halving runs' starting cells per meeting.
| Meetings | Share of all n |
|---|---|
| 1 | 83.3% |
| 2 | 14.3% |
| 3 | 1.26% |
| 4 | 1.16% |
| 5 | 9.5 per million |
| 6 | 0.83 per million |
| 8 | 44 per billion |
| 10 | 4.1 per billion |
Exact shares from every residue class of n up to 44 binary digits. They match the counts over 2 billion consecutive n.
Each meeting costs two to three binary digits. Running the rules on whole residue classes of n, explained in Does it ever halt?, settles the cascade length of every n whose cycle depends on at most 44 binary digits. After four meetings the cascades fall off a cliff, and each further meeting is 4 to 10 times rarer. The fewest binary digits of n that fix a cascade grow by about 3 per meeting: 8 digits for 4 meetings, 28 for 8, 33 for 12 and 41 for 14.
The longest cascade in a whole class is 16 meetings. Up to 54 digits no settled class has more than 14, and every large n ≡ 363,165,946,702 (mod 2⁴¹) has exactly 14. Classes with 16 first settle at 56 digits, and the first with 17 at 60. Longer ones belong to single integers that read all their digits: below 2⁵⁹ the longest is 19, first reached by n = 114,928,805,503,523,374 (16 by n = 3,617,714,363,521,582 and n = 30,335,806,016,335,582), and following lucky lines gives 23 at 84 digits and 28 at 94. The family built earlier from its ending, every n ending in the 33 binary digits 100000001100110010011101001011110, has exactly 12. The machine's own clean tapes reached 14 meetings at n = 391,305,139,022.
The 13-meeting record from the sweeps is different. n = 6,151,594,450 owes 11 of its 13 meetings to the zeros above its top binary digit; changing any digit above bit 33 leaves 3 to 6. Most n whose cycle runs past their top digit gain nothing from it.
The simplest feed stops within 3 meetings. With only the gap, a wall near the left and a wall near the right on the tape, the right side needs d ≡ 2 (mod 4) to keep merging and the left needs the right wall at a multiple of 4. Each meeting moves that wall by d/2 + 7, so the two conditions clash by the second meeting. Every residue class checked ends within 3 meetings.
Every long cascade runs the same loop. Every cascade of 9 or more meetings that settles within 33 digits spends at least 4 of them in one 8-round loop, and all 256 with 13 or 14 meetings below 2⁴⁹ spend 7 to 9 there. The loop makes 4 meetings per pass. Its rounds start with three walls; a block and a wall; a halving marker and a block; the marker and two walls; the marker and a block; the marker and two walls; three walls; a block and a wall. Call the walls at the start of a pass a, b and c, and the end E. Another pass needs two things. E − c − 1 must have 4 more trailing zeros in binary: that is the end countdown above. And b must keep a fixed relation to the end, which in the limit is b = 16E/21 + 62/49 read as 2-adic numbers, to about 6 more binary digits. Counted exactly, each pass costs 10 binary digits, 2.5 per meeting.
Nothing cheaper keeps a cascade going. Starting from a block, a wall and an end in general position, I followed every branch of the rules exactly, splitting the possible positions in half at each test. From the sixth meeting on, the chance of reaching each further 4 meetings falls by exactly 1024, the cost of the loop. 20 million random starts give the same chances for the first 8 meetings. The loop itself has no built-in end: solving its conditions for 12 passes gives a block, wall and end that make 50 meetings in a row.
A clean tape can't hold the loop for long. On a clean tape every position depends on the one number n, so the two conditions become two targets for the binary digits of n. The left side, through its halving markers, reads about 1.5 new digits of n per meeting and the end countdown only 1. So the end only ever reads digits that the left side has already fixed. Once the left side is satisfied, whether the right end keeps merging is already decided, and the cascade lasts only as long as the two targets agree. For 100 cascades I fixed the digits that lead to the first meeting and followed every continuation for 40 to 45 more digits. Each has a longest possible cascade, reached by exactly one choice of digits, and no later digits go past it. All 256 cascades of 13 or 14 meetings enter the loop the same way, finish one or two passes, and leave when the end runs out of trailing zeros.
The loop is two countdowns, and one of them always runs out. Put R = E − c − 1 and L = 147b + 280E − 392c − 578. One pass turns R into exactly R/16 and L into exactly L/64, so the loop goes on while R keeps 4 and L keeps 6 trailing zeros per pass. L is always 3 more than a multiple of 7, so it is never 0, and it is at most 280E in size. So any one run of the loop makes at most log₆₄ 280E passes, about a sixth of the tape's binary length. Each pass brings the right end 16 times closer to the end, so the loop alone can cover at most about two thirds of the halvings a halt needs.
The two countdowns are one fixed point seen two ways. R = L = 0 is the fixed point of the pass, b = 16E/21 + 62/49 and c = E − 1. As ordinary numbers each pass pulls the walls toward it, so after a pass or two b sits near 16/21 of the way to the end on every tape. As 2-adic numbers each pass pushes away from it, so staying in the loop needs the walls ever closer to it in binary digits. L is the one integer that measures both, and it can't be 0. The card at the end of this section spells the argument out step by step.
Leaving the loop is short, and it never comes back. Starting from the loop's three-wall state with every position free, I followed every branch of one pass, with no limit on binary digits. The search is finite: 356 ways out. A pass completes with probability exactly 1/1024. Otherwise the run ends within 8 meetings and never returns to the loop. Every comparison it makes comes out the same for any spacing of the walls. So a run that reaches the loop makes 4 meetings per pass and at most 8 more.
There is a rarer second loop with the same lock. With one more wall near the end, the same 8 rounds can repeat. Each pass costs 14 binary digits instead of 10. Its left countdown is −441b + 735c − 2156d + 1652E − 179, again 3 more than a multiple of 7, so it is never 0 either. In fact the loop runs with any number k of extra walls, each costing 4 more binary digits per pass. Its pass map has a simple general form: the right walls are smoothed by 1, 4, 6, 4, 1 sixteenths each pass. For every k up to 2500 the left countdown's variable coefficients are multiples of 7 while its constant is 6·3ᵏ mod 7, never 0. Every loop in the family is locked the same way, though each lock only bounds one unbroken stretch: a run that switches pass types escapes it, as the hand-built tapes in Does it ever halt? show.
1. Closeness in binary digits. Read a number's binary digits from the right. Two numbers are close in this sense, called 2-adic, when they agree in many of their last digits, that is, when their difference is divisible by a high power of 2. A number is 2-adically small when it has many trailing zeros. This has nothing to do with ordinary size: 2⁶⁰ is huge but 2-adically tiny, while 2⁶⁰ − 1, just as huge, is odd and so not 2-adically small at all.
2. A run at the right end reads binary digits. Each meeting between the gap and the end marker looks at the distance d modulo 4, which decides swap or merge, and then the distance roughly halves. Halving shifts the binary expansion right by one place, so the next meeting's test reads the next digit. A run of k meetings reads about k binary digits of the positions, from the bottom up, and a halt needs a single run that reads about log₂ of the tape width of them without breaking off.
3. Each pass of the loop uses up trailing zeros. In the loop's three-wall state the two countdowns are R = E − c − 1 and L = 147b + 280E − 392c − 578. One pass divides R by exactly 16 and L by exactly 64. Both must stay whole numbers, so p passes need R divisible by 16ᵖ and L by 64ᵖ: each pass spends 4 trailing zeros of R and 6 of L. When either runs out, the run breaks off.
4. L can't be 0. Its coefficients 147, 280 and 392 are multiples of 7, while 578 is 4 more than a multiple of 7. So L is always 3 more than a multiple of 7, on every tape, and never 0. Dividing by 64 keeps that remainder, since 64 is one more than 63 = 7 × 9. The 7 is no accident. L = 0 would mean sitting exactly on the loop's fixed point, and finding that point divides by 1 − 1/64, which brings in 63, so the point has 7s in its denominators (b = 16E/21 + 62/49). A wall sits on a whole cell, so no tape is ever exactly there.
5. Small, yet divisible by a large power of 64: the lock. A nonzero whole number divisible by 64ᵖ is at least 64ᵖ in size. But L is built from positions on the tape, so it is at most 280E. So 64ᵖ ≤ 280E, and one stretch of the loop makes at most log₆₄(280E) passes. At 4 meetings per pass that covers about two thirds of the halvings a halt needs. If L could be 0, nothing but R would stop the loop, and R alone allows all of them. That is why L ≠ 0 is the heart of the matter.
6. The same fact as a fixed point. As ordinary numbers, each pass pulls the walls toward that fixed point. In binary digits it pushes them away: staying in the loop means agreeing with the fixed point in 6 more binary digits per pass. L is the tape's offset from the point. As an ordinary number it shrinks 64-fold per pass, and in binary it must gain 6 trailing zeros per pass, and a whole number can't do both for long.
Seen on a real run. Take the closest approach found below 2⁵⁹, the clean tape n = 114,928,805,503,523,374, whose tape is about 2⁵⁷·⁷ cells wide. At three successive pass starts of its run, R has 12, 8 and 4 trailing zeros and L has 21, 15 and 9: exactly 4 and 6 fewer each pass. As ordinary numbers R goes from 2⁵³ to 2⁴⁹ to 2⁴⁵ and L from 2⁵⁸·⁷ to 2⁵²·⁷ to 2⁴⁶·⁷, 16 and 64 times smaller each pass, and L stays 3 more than a multiple of 7 throughout. Another full pass needs at least 5 trailing zeros of R, so after the third pass start the run leaves the loop, with L still holding 9. On this tape the end countdown ran out first, and the cycle got within 2⁻¹⁹·⁷ of the end, where a halt needs about 2⁻⁵⁷. All nine record runs up to 84 digits end the same way, with R down to 3 or 4 trailing zeros while L still has enough for another pass or runs out at the same time; L never gets near its size limit, so what stops them is the line-up, not the lock.
7. How many numbers you get to choose. On a tape with two free numbers, such as the marker position and the width of a two-marker state, both conditions can be met by choosing digits of both numbers: 10 digits per pass, 2.5 per halving. On the machine's own tapes everything depends on the one number n, and the two conditions become n ≡ a (mod 2⁴ᵖ) and n ≡ b (mod 2⁶ᵖ), with a and b fixed by the way the cycle came into the loop. Both can hold only if a and b already agree in their last 4p binary digits. That line-up is settled by digits of n read before the loop starts, so it can't be chosen as the loop goes. Each way in allows a fixed number of passes. Up to that number, passes are cheap, 6 digits each; beyond it, none.
8. Lucky lines, and why the odds come back to 2.5. The chart "The machine's tail is a staircase of lucky lines", further down, shows exactly this. A few ways in whose line-up happens to be long carry the machine's near misses at each depth, each at 1.5 digits per halving, and then stop. A line-up of g digits is about as likely as a random number having g trailing zeros, 1 in 2ᵍ, so going deeper costs another digit per halving: 2.5 again on average. That is measured, not assumed: the line-up of a way in can be read straight off its two countdowns by solving congruences, and over 693,518 of the machine's own lines each extra loop meeting a line allows is rarer by 0.85 to 0.99 binary digits, out to 20 meetings. That average gives the odds quoted below, and the closest approaches found stay about a third of the way to a halt.
9. Why this is not yet a proof. Every step above is exact except one: that line-ups keep behaving like the trailing zeros of random numbers. That is measured out to 20 loop meetings, but a halt needs about as many meetings as n has binary digits, and there are infinitely many ways into the loop, each with its own line-up. To rule out that one of them has an enormous run of trailing zeros is a statement about the binary digits of particular whole numbers. Such statements are easy to weigh and, so far, impossible to prove, which is the situation of the Collatz problem.
D1 is the only missing rule, so the question is whether D ever reads a 1. D runs after F0 or C1. After F0 it always lands on the 0 that E wrote two steps before, as in every wall turn. C runs only after B0, and tracing back from there, D can read a 1 in just one way: a carry cycle starting with A1 E1 when the two cells ahead of its packet both hold 1. In the stripes the first of those is a 0, which gives C0 and the carry goes on. At a marker the first is a 1 and the second a 0, which gives C1 D0, the marker pass. Two 1s in a row ahead of the packet needs a block, 111, or a longer run of 1s.
Blocks do form: a shift that runs into a wall turns the wall into one. But a shift stops at the first mark it meets, so the stretch just left of a new block is plain stripes. The next time the head arrives there it is passing right from a gap, and the pass shifts the block away. In the first 3 billion steps a pass reached a block 68 times, and no carry ever did.
The rules in The marks as arithmetic make this exact. Within them a block always lies to the right of the gap or the packet: a block appears only where a shift stops, the packet then heads left from it, and the next pass or shift to arrive removes it. So within the rules a carry never reaches a block.
That still isn't a proof that the machine never halts. The rules assume the marks never touch in a few odd ways, and the ones that lead to a halt end the same way: a new marker is made directly against a 1, fuses with it into a block left of the head, and the next carry halts on it. That happens when a carry reaches a wall with a marker directly before it or exactly two stripe cells after it, and also when a long run's last meeting is a swap right at the end, as in the hand-built tapes below.
The only route to either that I have found needs the activity at the right end to halve its distance to the end about log₂ n times in a row: a wall near the end is turned into a block, passed, and remade closer to the end, once for each meeting between a gap and the end marker. That run of meetings is short, as What keeps the right-end cascade going shows. The longest below 2⁶⁵ is 19 meetings, reached only by rare single clean tapes, and along the machine's own clean tapes, followed to n = 10¹², the longest is 14.
On a tape built by hand, that route really does halt the machine. I set the loop's two countdowns by hand on a 72-cell tape: gap at 1, walls at 7, 30 and 39, head on the gap in state E, tape 100010100101010101010101010101001010101001010101010101010101010101010101. The meetings at the end run 30, 14, 6, 2, 0, and the machine halts after 10,302 steps: state D reads the first 1 of a 111 next to the end. A 16,000-cell version follows the mark rules exactly for 17 rounds and then halts at step 759,437,834. On a 17,652-cell tape the last wall can start 8,192 cells from the end, mid-tape, and the machine halts at step 1,258,643,838. I also ran every three-wall round start of width 40 to 130, 423,775 of them, on the real machine. It halted only when the mark rules' right-end run got within 2 cells of the end, or when marks touched. Every clean tape below 5,000 run directly on the machine reaches the next one. Nothing suggests these tapes can be reached from blank. The lock keeps the plain loop from doing this on big tapes: from about 2¹⁷ cells on, one run of the loop can't start from mid-tape, and the machine's own tapes are now longer than 2⁵⁶ cells. A run that switches loops gets around the lock, though, and the last part of this section builds tapes of any size that halt that way.
| Step | Width | Marks after the gap at 1 |
|---|---|---|
| 0 | 72 | W7 W30 W39 |
| 124 | 74 | B32 W41 |
| 1,894 | 78 | M16 B61 |
| 3,596 | 82 | M8 W38 W73 |
| 4,750 | 84 | M4 B75 |
| 7,224 | 90 | W5 W44 W85 |
| 7,374 | 92 | B46 W87 |
| 9,332 | 96 | W27 W70 W93 |
| 10,066 | 98 | B72 W95 |
| 10,302 | halts: D reads a 111 | |
The hand-built 72-cell tape, round by round on the real machine. The distance from the last wall to the end halves: 33, 17, 9, 5, 3 cells. The machine halts when the carry reaches the block that then forms next to the end.
The two countdowns are visible in the table. The wall nearest the end gains on it each pass, and the halving marker on the left runs M16, M8, M4 before it is spent. Planting both countdowns with enough trailing zeros is all it takes to make the machine halt on a small tape. On the machine's own tapes the left countdown is too short, by the lock, and runs that switch between loops have not been seen.
No clean tape below 2⁶⁵ leads to a halt. For most n the cycle to the next clean tape depends only on the last few binary digits of n. Write n = 2ᵏj + ρ and leave j as a symbol. Then the rules can run on a whole residue class at once, and the class splits only when a step needs another digit. A class is settled when its cycle reaches the next clean tape.
For a whole class, each comparison of two positions is a linear condition on j. I recorded every one, and in every class that settles within 64 digits, each n with at least one 1-bit above those digits follows the class exactly.
Each n below 2⁶⁵ is then either covered by such a class or is the only member, with that many digits, of a class still open, which I ran directly. That makes 204,860,486,855 classes and 661,842,319,825 direct runs, and none of them halts. Two separate programs did this: one re-runs every open class from the clean tape at each digit, and was taken to 2⁵¹; the other carries each class's state forward as it splits, agrees with the first at every one of those levels, and went on to 2⁶¹, matching its own earlier runs to 2⁵⁵, 2⁵⁷ and 2⁵⁹ at every shared level; a 128-bit copy of it took the check to 2⁶⁵, matching the run to 2⁶¹ at every shared level. In all those cycles no two marks come closer than in cycles the certified simulation has checked.
That rules out a halt for at least 6.7 × 10⁵⁵ steps. The clean tapes below 2⁶⁵ are never more than 375 apart. Each cycle from the clean tape with n starts with ⌊n/2⌋ bounces, at least 1.5(n − 1)² steps. So the machine needs at least 6.7 × 10⁵⁵ steps to get past 2⁶⁵. At its actual pace it needs about 9 × 10⁵⁷. Certified cycles near n = 10¹² keep the pace of the first clean tapes, about 0.022 × (cells)³ steps in total.
| Digits of n | Best halvings | Needed to halt |
|---|---|---|
| 17 | 10.3 | 16.2 |
| 30 | 12.4 | 29.1 |
| 39 | 14.0 | 38.5 |
| 45 | 14.7 | 44.8 |
| best found | ||
| 52 | 16.5 | 51.7 |
| 57 | 19.7 | 56.7 |
| 68 | 20.8 | 67.8 |
| 75 | 22.1 | 74.4 |
| 85 | 25.4 | 84.5 |
| 94 | 29.6 | 93.6 |
Up to 45 digits: over every n with that many binary digits, the most halvings of the distance between a gap and the end marker. A halt needs the distance to reach 2. Below the line: the closest found, so lower bounds for the best. The 52-digit one, n = 3,617,714,363,521,582, turned up in the exhaustive check; the others come from following the luckiest lines of two-marker states (for example n = 114,928,805,503,523,374 and n = 14,690,414,442,211,083,106,227,634,386), and the 55-digit one was predicted that way before the exhaustive check reached it. Each was confirmed by a certified run of the real machine.
A halt would need an n whose cycle runs past its own top digit. Within a residue class every distance keeps growing with the higher digits of n, so it can never shrink to the 2 cells a halt needs. Only an n whose cycle reads all of its binary digits can do that. Below 2⁴⁵ even the best of them fall further short with every digit, and the best found up to 94 digits get only about a third of the way: the shallowest class that comes within 2⁻ˣ of the end has about 3.3x binary digits, so an n with b digits can be expected to reach only about b/3.3 halvings, against the b a halt needs. Each record run is one lead-in meeting, one stretch of the loop (26 of the 28 meetings at 94 digits) and an exit of at most 3. How long the stretch lasts is set by how far that line lines up, not by the loop's own limit, which at 94 digits would allow about 67 meetings. Every one of them enters the loop through one of the routes excluded below.
The odds of a halt beyond 2⁵⁵ look like 1 in 10²⁴ or less. For the machine's own family the odds can be computed exactly, not sampled: follow every even clean tape's whole cycle on classes of n, splitting a class whenever a step needs another binary digit, to 48 digits (369 million classes, exactly the classes the exhaustive check settled through 49 digits). The share of n whose cycle comes within 2⁻ˣ of the end is about 1 in 12,000 for x = 4, 1 in 11 million for x = 8 and 1 in 2 billion for x = 12. From 4 to 8 halvings that falls 2.5 binary digits per halving, like a single two-marker segment, but from 8 to 12 only about 1.9. The chart below shows why. Every two-marker state that a class of n reaches is a whole line of states, one per member of the class, and on a line the loop costs only 6 digits per pass, 1.5 per halving, for as long as the line's line-up lasts. At each depth a few lucky lines carry almost all of the tail, each until its line-up runs out. Lines that line up further are rarer by about a digit per halving: of the machine's 64,665 lines up to 28 digits deep, 15% come within 2⁻¹⁰ in one segment and 0.02% within 2⁻¹⁹, and against random lines of the same shape they line up no more often. So the 1.9 digits per halving cannot last, and the average price is the plane's 2.5. With it, the expected number of halts over all clean tapes beyond 2⁵⁵ comes out at about 10⁻²⁷ from the machine's own tail and 10⁻²⁵ to 10⁻²⁴ from random two-marker states, before taking out the routes now excluded. And the machine's actual sequence of clean tapes is a typical one: its residues mod 2ᵏ follow exactly the frequencies of a Markov chain built from random n, so it visits any class of n at most about 3 times as often as a random sequence would.
That extrapolates tails measured out to about 20 halvings, so it is an estimate, not a proof. The rules also assume the marks never touch in the ways described above, which every certified cycle bears out but which is not proved for all n.
| x at least | All lines | Line 1 | Line 2 | Line 3 |
|---|---|---|---|---|
| 4 | 2-13.5 | 2-18.7 (3%) | 2-18.8 (3%) | 2-26.9 (0%) |
| 5 | 2-16.0 | 2-20.5 (4%) | 2-21.6 (2%) | 2-27.9 (0%) |
| 6 | 2-19.5 | 2-23.4 (7%) | 2-24.0 (4%) | 2-30.0 (0%) |
| 7 | 2-22.0 | 2-26.0 (6%) | 2-25.0 (12%) | 2-32.0 (0%) |
| 8 | 2-23.3 | 2-27.0 (8%) | 2-26.0 (16%) | 2-33.0 (0%) |
| 9 | 2-25.4 | 2-27.0 (32%) | 2-28.0 (16%) | 2-34.0 (0%) |
| 10 | 2-26.7 | 2-27.0 (79%) | 2-30.0 (10%) | 2-36.0 (0%) |
| 11 | 2-29.9 | none | 2-31.0 (46%) | 2-38.0 (0%) |
| 12 | 2-30.9 | none | 2-32.0 (48%) | 2-39.0 (0%) |
| 13 | 2-38.0 | none | none | 2-40.0 (25%) |
| 14 | 2-38.7 | none | none | 2-40.0 (40%) |
A halt would need a run that enters the loop late. A run's first meeting is usually within about 4 halvings of the full width, however close the run before it got (29 million runs checked), and every run seen is a short lead-in, at most one stretch of the loop and a short exit (147 million runs; among 5.8 billion runs from random 60-bit cycles, 3 million contain a stretch of the loop and none contains two). That alone caps a run at about two thirds of log₂ n plus a constant. Counted run by run it is sharper. At a run's first pass start, say the end is 2⁻ˢ of the width W away and L is 2^λ times W. A pass divides R by 16 and L by 64, so 3s + 2λ stays the same at every pass start of the stretch, and what matters is the last one. I searched the end of the loop exactly: from a pass start with the end distance R fixed and the other positions free, every way the run can go, for every even R up to 4096, in two independent implementations, one of which decides every comparison of positions symbolically and reports when it cannot (it never had to). The run gets within 2 cells of the end marker only from R = 2, 4, 8, 16, 24, 32, 48, 64 or 176, and each of these needs L in a fixed residue class. For R = 176, L must be a multiple of 128, so it is at least 256 in size. Together that proves (within the mark rules) that a run that halts through the loop has 3s + 2λ of at least log₂W − 6.4. Counting halvings alone had given log₂W − 24. Over a million loop entries, in random two-marker states, in the deepest classes of the exhaustive check and in the record cycles, 3s + 2λ never exceeds 32.2, which allows a halt only on tapes narrower than 2³⁹. The latest of those entries come from a staircase of short runs, a 7-round pattern that pushes run starts out to 5.6 halvings. Its own affine map pulls the last wall toward a fixed point 0.0084 of the width from the end, so like the loop it can't creep up on the end. It can still make the next run enter the loop late: from a staircase run all the way to its limit, exactly 1/32 of the ways out enter at 3s + 2λ = 36.4 (every branch from the limit followed, to 40 binary digits), and that is the latest exit from any of the 118 plateau limits that uses no round of the extra-wall loop; it allows a halt only below width 2⁴³, far inside the checked range. Exits that do pass through extra-wall rounds reach 47.3 from those limits, at measures below 10⁻¹¹, and the route tree's deep lead-ins reach 52.9. A halt beyond the checked range (tapes up to 2⁶² cells) through the loop would need 3s + 2λ ≥ 55.6, which means entering the loop at least 12 halvings below the width. The rest of the way would have to come from the extra-wall loop. Following every branch from an extra-wall state shows there is no ceiling: each meeting a run makes before it enters the plain loop adds 3 to 3s + 2λ and costs about 3.4 binary digits, against 2.5 per halving inside the loop. Among the machine's own two-marker segments, chains through the extra-wall loop found within 46 binary digits already enter 18.9 halvings below the width; all of them were checked and none halts. So the lock doesn't close the gap on its own. What it does is make about a third of the halvings a halt needs cost 3.4 digits instead of 2.5.
The rarer loops leave a gap. In the loop with an extra wall, a pass whose halving marker runs two rounds longer works as a detour. The pattern can resume after it, or the run can drop the extra wall and carry on in the plain loop. Each new stretch starts with a fresh left countdown, about 50 times E in size, while the right end keeps closing in. So the lock limits each stretch but not a run made of several. These chains are no cheaper: each further 4 meetings still costs 10 binary digits. In clean cycles the extra-wall states have a share of only about 4 in 10⁸. Among every residue class settled within 40 digits, 631 runs use the extra-wall loop, all of them short, and no run contains two stretches of any loop. A proof would need to rule chains out some other way, and the hand-built tapes below show that the rules alone can't.
Why one loop is locked and a mixture isn't. A pattern of rounds that repeats is an affine map, and over the ordinary numbers it pulls the state toward its fixed point. That point is a fraction with a fixed denominator, and when it isn't a whole-number state, the state's distance to it is a nonzero multiple of 1/D that shrinks every pass. So the pattern can only repeat a bounded number of times. The mod-7 lock is this, with the 7 coming from 63 = 64 − 1. The detour is a second 8-round pass whose map has irrational eigenvalues, (13 ± √153)/256. So no linear countdown locks the detour, but a quadratic one does: the product of its two eigenforms is an integer quadratic, never 0, that every detour divides by 4096, so a stretch of detours, like the plain loop, covers at most two thirds of the halvings. Every repeating word of standard passes and detours has a lock of this kind (checked for all 747 words up to length 12), and none covers more than 4/5 of the halvings. Each different order of standard passes and detours has its own fixed point, with its own denominator, so a long mixture has no single point to be held away from, and no lock for every mixture can exist: the hand-built tapes below halt at every width by a mixture. What the locks still say is that such a halt has to change words at least once, and each change starts a fresh lock. Such mixtures cost 16 to 18 binary digits per pass, against 10 for the plain loop.
Every other repeating pattern parks short of the end. I scanned the machine's runs for any sequence of rounds that repeats, in 4 × 10⁸ random two-marker states and about 200,000 of the machine's own cycles, and found 125 kinds. For each I read off its affine map and the point it pulls the marks toward. Only the plain loop and two-round pieces of the plain and extra-wall loops pull a mark onto the end; the pieces never repeat more than three times, and the extra-wall loop never ran two whole passes in these samples (its own pass map also pulls a mark onto the end, and it has a lock too). The other 118 settle a fixed fraction of the width short of the end, at most 7.9 halvings away, the staircase being the latest. So the only repetitions that can carry the right end toward a halt are the ones with a lock.
| Tape width | Run at the end | Steps to halt |
|---|---|---|
| 7.1 × 10¹⁶ | 53 meetings | 9.3 × 10³⁴ |
| 1.6 × 10⁶⁰ | 197 meetings | 1.8 × 10¹²² |
| about 2¹⁰⁰⁰ | 997 meetings | 4.2 × 10⁶⁰⁴ |
Hand-built round starts with a gap and four walls, at 0.65%, 12.5%, 46% and 87% of the width. The run is a stretch of the extra-wall loop, one detour, and a second stretch. Each halt is reached through the proven rules alone, and each width is 3 more than a multiple of 6, so the tapes pass the mod-3 test from The big picture that every tape reached from blank must pass.
With one detour the machine halts on tapes of any size. I wrote the congruences that make a run follow the extra-wall loop for m passes, then one detour, then m more passes, and solved them as a lattice of starting tapes. Lattice reduction then finds one with the right proportions at any width. At 2²⁰⁰ cells one stretch of either loop is limited to about 35 passes and a halt needs about 50, so two stretches of 24 do it. The same recipe gives a halting tape at every width from 2¹⁶ to 2⁴⁰⁰ cells, each checked one by one, while the loop alone stops producing them above 2²⁷. On the two smallest, 67,431 and 131,487 cells wide, I also ran the bare transition table with no rules at all: it halts at steps 15,940,135,477 and 61,437,118,279, exactly as predicted. The machine then halts the same way every time: the meetings at the end run …, 14, 6, 2, 0, the last one is a swap that fuses the end marker into a block, and the carry halts on it.
To run these tapes I used the proven rules themselves, checking the tape against each rule's pattern before applying it, so the step counts are exact. The same simulator matches direct simulation on 550 random small tapes and reproduces the 72-cell tape's 10,302 steps.
So a proof has to use where the tapes come from. Nothing in the rules stops a long run. What has kept every run short so far is that the machine's own tapes are not chosen freely. Each run starts from a family with a single free number, n, and a long run needs that one number to satisfy about two and a half binary conditions per meeting. A tape built by hand has four free positions, enough to satisfy them all. Nor does a conserved count rule these tapes out: they pass the mod-3 count of 1s, and a search for other counts of the same kind, weighting each cell by its value and its position modulo up to 6 and the head by its state, with moduli 2, 3, 5 and 7, finds none.
A halt needs at least three free numbers; the machine's runs have two. One stretch of the plain loop covers at most about two thirds of the meetings a halt needs, and it always ends the run. So at least the first third has to come from a pattern the lock does not cover: the extra-wall loop, at 14 binary conditions per 4 meetings, then a drop into the plain loop that keeps the progress made, then the plain stretch at 10 per 4. That averages 17/6, about 2.83 conditions per meeting. A family of tapes with d free numbers at width W can meet about d·log₂W conditions, and a halt needs about log₂W meetings, so it needs d above 2.83: at least three free numbers. Three do suffice. With one combination of the hand-built tapes' walls held fixed, so that three free numbers remain, the same lattice method finds a 2¹²⁰-cell tape on which the machine halts after ten extra-wall passes, a drop and eighteen plain passes, and tapes that halt the same way at every width tried, 2²⁴, 2³², 2⁴⁰, 2⁴⁸, 2⁶⁴, 2⁸⁰, 2⁹⁶, 2¹²⁸, 2¹⁶⁰ and 2²⁰⁰, while words made only of extra-wall passes and detours find nothing in that family at 2¹²⁰. On a 129,963-cell tape built the same way (one extra-wall pass, the drop, two plain passes), the bare transition table halts at step 75,047,708,436, exactly as the rules predict. The drops are picky: right after an extra-wall pass the simplest one is impossible, and most of the others leave the last wall between a half and a seventeenth of the tape from the end, losing all the progress. And every cycle from an even clean tape is, one round in, at a state with just the gap, one marker and the end marker, so everything after depends on two numbers (really one, n). And for such states the extra-wall loop is capped outright, not just made unlikely. Each of its passes has to keep three countdowns divisible by growing powers of 2, where the plain loop has two. A family with three free numbers can do that for as many passes as its size allows; in a two-number family the third countdown is tied to the other two by a fixed number, which then needs four more binary digits to line up for every pass. Random two-number families never allowed two passes in my tests, random three-number families allowed every word of five, and the 144 ways from a two-marker state into that loop within 30 binary digits allow at most one pass, decided by their position alone. Rarer ways in allow more, each extra pass about ten times rarer than the last: there are two-marker states about 2³⁵ cells wide whose segments run three extra-wall passes in a row, and they still come no closer to the end than 2⁻¹⁵ of the width. Even a chain that keeps its progress falls further behind as it goes: after two extra-wall passes and a drop, each further plain pass needs about 5 more binary digits of width before any two-marker state follows it, and buys only 4 halvings; the first state that adds 8 plain passes is 2⁷⁷ cells wide and stops 38 halvings short. Two-marker states in general have odds of ending within 2⁻ʰ of the width that fall by about 2.5 binary digits for each extra halving, at every width, and the machine's own tapes, a one-number line inside that family, have odds 20 to 30 times smaller still.
| Loop | Countdowns | 2 free numbers (two-marker states) | 1 free number (a cycle's own states) |
|---|---|---|---|
| Plain | 2 | No fixed cap; the lock stops it at ⅔ of the halvings | Fixed cap per way in |
| 1 extra wall | 3 | Fixed cap per way in | Fixed cap per way in |
| k extra walls | 2 + k | Fixed cap per way in | Fixed cap per way in |
Checked on random families of tapes for 0 to 3 extra walls: with fewer free numbers than countdowns, every family stopped after one pass (3 of 40 managed a second); with as many or more, every family ran every pass tried.
None of this depends on where the marks sit. Every rule places a new mark at the midpoint of two neighbouring marks, give or take a few cells, or moves marks by a few cells. Measure each mark by its distances to the marks that started out on the tape: if two neighbours are ordered in every one of those measures, so is their midpoint. So the left-to-right order of the marks is the same whatever the starting distances are, as long as they are large. For a two-marker state that means the whole tree of cases is the same wherever the marker sits; built at nine positions from 1/64 to 63/64 of the width, it came out identical, and none of its 250 million comparisons of two positions depends on the ratio. The same fact settles a loose end in the earlier analysis: the searches that fixed one geometry for convenience give the same answer for every geometry. It also bears on the touching marks the rules can't handle. Along every branch decided within 42 binary digits, the only two neighbouring marks that ever sit a fixed distance apart, rather than a distance that grows with the tape, are the end marker and the end itself: of 69 million neighbouring pairs checked, 13 million are that pair and no other pair ever is. So on a large tape, marks can touch only on a branch that needs more digits than that.
Every halt would have to start from a two-marker state. A cycle reaches its first two-marker state after one round (odd n go straight to the next clean tape in two fixed rounds), and from then on it is a chain of segments, each depending only on where its marker and end marker sit. So from any clean tape the machine can halt only by reaching a two-marker state whose own segment halts, a question about one fixed two-number family rather than about the states the machine happens to visit. I ran every two-marker state up to 262,143 cells wide through its segment, 8.6 billion of them, but left out the marker's last position, three cells before the end marker: only 7, all between 11 and 29 cells wide, get within 2 cells of the end or let marks touch, and on the real machine exactly one of those halts. It is 13 cells wide with the marker touching the gap, and its end meetings run 6, 2, 0. The last position holds two more halting states, 9 and 17 cells wide; at every other width up to 262,143 it reaches the clean tape, and the other narrowest gaps add no new halt. No cycle passes through any of the three: the narrowest two-marker state the machine reaches is 15 cells wide, and its segment leads to one 27 cells wide. The odds measured on random two-marker states predict about one halting state below 2¹⁶ (there are three, all tiny) and about 0.014 beyond 2¹⁸. For the commonest way into the loop, the one 230 of the 256 longest cascades below 2⁴⁹ take, the question can be settled at every size. That route always starts at a two-marker state, and a halt through it needs both of its countdowns to be divisible by large powers of 2, which pins the width to a residue of −38423/1225 and then the marker to one residue. Counted with two halvings to spare, that leaves 332,846 candidate states between 2¹⁷ and 2⁶¹ and none beyond, since the lock forbids it there. None of them halts, so within the mark rules no cycle can ever halt through that route. The best candidate, about 2⁴⁶ cells wide, runs the loop for 8 passes and gets to 1,030 cells from the end, within 2⁻³⁶ of the width, before its left countdown runs out, much closer than the machine's own record of about 2⁻¹⁵: that is what a second free number buys. The same argument works for any fixed way into the loop. Following every branch of a two-marker segment exactly gives 759,918 ways in that are decided within 46 binary digits (2,767 within 30). Of 1,020 random segments that come within 2⁻⁸ of the width, every one whose deepest run uses the loop, 1,019 of them, enters it by one of these, and already by one decided within 34 digits. Together they leave 866,445 candidates, and none of them halts either. (A first pass at this asked for a quarter pass too many at some widths, because a meeting can do slightly better than halve the distance; it was redone with two halvings to spare.) Chains fare no better: of the 31,048 first ways from a two-marker state into the extra-wall loop within those 46 digits, 1,635 allow one pass of it, 226 two, 21 three and one four, and the 1,989 ways those passes can drop back into the plain loop, 346 of them keeping their progress, leave no candidate state at any size. So within the mark rules, a run that enters the loop by any of these ways can never halt, at any size. The exact end of the loop now does this without any search. At each way in, 3s + 2λ depends only on where the marker sits as a fraction of the width, so each way has a ceiling, and a halt through it needs a tape narrower than 2 to the power of the ceiling plus 6.4. The commonest way has a ceiling of 16.0, so it can't lead to a halt on any tape wider than 2²²·⁴ cells. Following every branch to 62 binary digits, no way in has a ceiling above 52.9, so no two-marker state decided within 62 digits can halt on a tape wider than 2⁵⁹·² cells, which is still inside the checked range, though only just. The highest ceilings come from long lead-ins through pieces of the extra-wall loop; the top one enters the loop 15.1 halvings below the width, and I checked it and three others on rebuilt integer states. For that top route I also listed every state whose two countdowns line up exactly as a halt would need, at tape widths from 2⁴⁰ to 2⁶²: there are none. The same exact listing over all 232,456 ways in found within 46 digits, at every width from 2¹⁷ up to each one's lock limit, finds no state at all; the earlier version of that check had 866,445 looser candidates to run. The first way in past the threshold, found at 64 digits with a ceiling of 54.2, turns out to have R fixed at 12 more than a multiple of 16 by its own route, so it can neither pass nor close at any width. What stays open is the segments that need more than 62 digits to decide, about eight in ten billion of all two-marker states, a share that shrinks by 0.71 with each further digit; none of the deep runs sampled was among them. A halt of the machine also needs its own sequence to land on such a state; if its two-marker states hit them like random points, the expected number of halts beyond 2⁵⁵ is around 10⁻²⁵ to 10⁻²⁴, inside the range above, and that is before taking out the routes now excluded.
The machine's own states start out special. A cycle is a chain of segments, each running from one two-marker state to the next or to the clean tape, and each segment ends in another two-marker state with odds of about a third. Starting from a random two-marker state, any segment gets within 2⁻⁴ of the width with odds of about 1.5 in 1,000. On the machine's own tapes the first segment never does: following every residue class through it proves that its meetings stay at least 2−1.6 of the width from the end. The second segment does so about 3 times in 10 million, and the odds then climb, reaching the random level only by the seventh to ninth segment. The reason is how few kinds of state come first. With the marker at cell m and the width E, the first two-marker state of every cycle lies on the line E = 2m + 7; the second lies on one of just two lines, E = 8m + 13 or 13E = 16m + 127; the third on dozens, the fourth on hundreds. Each return also brings about 3.5 new binary digits of n into the marker's position, while the width's low digits stay the few that the history allows. The record 14-meeting cycle below 2⁴⁹ has its long run in its eighth segment. The same returns are what make the exhaustive check expensive: the digits a class needs grow by about 3.5 per return, whether or not the cycle comes close to the end.
On the machine's own tapes, each gap is a count of binary zeros. There every position is λN + κ with N = 2n + 6, and λ and κ are fractions over the same power of 2. At a loop pass start, the difference between the two countdowns' targets, scaled by their slopes, is a number Δ: in all 878 pass starts reached from long-cascade clean tapes it is below 800. Each gap is the number of trailing zeros Δ has when written to as many binary places as λ. So for one stretch to finish the job, Δ must be a whole number, or nearly, with about as many trailing binary zeros as n still has unread digits at the pass start, give or take the few halvings the exit adds. With Δ below 800, that allows at most about 16 unread digits. The 256 longest cascades below 2⁴⁹ reach their first pass start with 2 to 19 digits unread, but their Δ's are far from whole: written out in binary they run to within 8 places of λ's, some 25 places past the point. Ruling out such a Δ for every n is a statement about binary digits of the same kind as the open questions about Collatz-type maps, where the odds are easy to estimate and no proof method is known.
The commonest way into the loop has a ceiling. Of all pass starts on the machine's tapes up to 38 binary digits, 90% come in by the same four rounds: a halving marker and the end marker, then three markers, then two markers and a wall, then a marker and two walls. For those the gap has a closed form, and it depends only on the tape's width W at the first of the four rounds: it is 3 less than the number of binary digits in which W agrees with the 2-adic number −38423/1225. (Every mark's line passes through the same 2-adic point, W itself, to as many digits as the class has read, and the halving marker's slope then cancels out.) On every such line up to 39 digits, all 308,333 of them, W agrees in at least 5 digits and never in 12, so this route's gap never exceeds 8. The route occurs only at particular stages of the cycle, each with a fixed growth g of the width since the clean tape: g = 23, 95, 119, 191, 215, 287 and 383 among all those found, with a search that follows the longest-lived residue classes out to 80 binary digits. At each stage the low digits a clean tape needs in order to get there stay a few places away from the digits of the 2-adic number (−38423/1225 − 6 − g)/2, and the best stage's gap is still 8. 230 of the 256 longest cascades below 2⁴⁹ come in this way, all at exactly that ceiling, which is why they stop after one or two passes. The larger gaps, up to 12 by 43 digits, come from rarer routes.
| Meeting | log₂ of the countdown | log₂ of the distance |
|---|---|---|
| 0 | 205.8 | 197 |
| 4 | 199.8 | 193 |
| 8 | 193.8 | 189 |
| 12 | 187.8 | 185 |
| 16 | 181.8 | 181 |
| 20 | 175.8 | 177 |
| 24 | 169.8 | 173 |
| 28 | 163.8 | 169 |
| 32 | 157.8 | 165 |
| 36 | 151.8 | 161 |
| 40 | 145.8 | 157 |
| 44 | 139.8 | 153 |
| 48 | 133.8 | 149 |
| 52 | 127.8 | 145 |
| 56 | 121.8 | 141 |
| 60 | 115.8 | 137 |
| 64 | 109.8 | 133 |
| 68 | 103.8 | 129 |
| 72 | 97.8 | 125 |
| 76 | 91.8 | 121 |
| 80 | 85.8 | 117 |
| 84 | 79.8 | 113 |
| 88 | 73.8 | 109 |
| 92 | 67.8 | 105 |
| 96 | 61.8 | 101 |
| 100 | 203.2 | 97 |
| 104 | 197.2 | 93 |
| 108 | 191.2 | 89 |
| 112 | 185.2 | 85 |
| 116 | 179.2 | 81 |
| 120 | 173.2 | 77 |
| 124 | 167.2 | 73 |
| 128 | 161.2 | 69 |
| 132 | 155.2 | 65 |
| 136 | 149.2 | 61 |
| 140 | 143.2 | 57 |
| 144 | 137.2 | 53 |
| 148 | 131.2 | 49 |
| 152 | 125.2 | 45 |
| 156 | 119.2 | 41 |
| 160 | 113.2 | 37 |
| 164 | 107.2 | 33 |
| 168 | 101.2 | 29 |
| 172 | 95.2 | 25 |
| 176 | 89.2 | 21 |
| 180 | 83.2 | 17 |
| 184 | 77.2 | 13 |
| 188 | 71.2 | 9 |
| 192 | 65.2 | 5 |
| 196 | 59.2 | 1 |
| h at least | All two-marker states, of 10⁹ | The machine's own, of 10⁹ |
|---|---|---|
| 3 | 62,700,051 (2-4.0) | 25,243,656 (2-5.3) |
| 4 | 2,513,659 (2-8.6) | 86,074 (2-13.5) |
| 5 | 325,335 (2-11.6) | 15,466 (2-16.0) |
| 6 | 86,407 (2-13.5) | 1,400 (2-19.4) |
| 7 | 12,622 (2-16.3) | 229 (2-22.1) |
| 8 | 3,939 (2-17.9) | 82 (2-23.5) |
| 9 | 306 (2-21.6) | 18 (2-25.7) |
| 10 | 92 (2-23.4) | 6 (2-27.3) |
| 11 | 14 (2-26.1) | none |
| 12 | 3 (2-28.3) | none |
| Segment | Random two-marker states | The machine's own |
|---|---|---|
| 1st | 88,116 of 50,000,000 (2-9.1) | 0 of 200,000,000 (proved never) |
| 2nd | 24,916 of 17,193,973 (2-9.4) | 28 of 74,988,389 (2-21.4) |
| 3rd | 8,588 of 5,814,194 (2-9.4) | 7,527 of 27,948,937 (2-11.9) |
| 4th | 2,736 of 1,962,642 (2-9.5) | 6,152 of 9,161,333 (2-10.5) |
| 5th | 917 of 663,576 (2-9.5) | 1,952 of 3,218,753 (2-10.7) |
| 6th | 313 of 224,867 (2-9.5) | 882 of 1,090,740 (2-10.3) |
| 7th | 117 of 75,894 (2-9.3) | 406 of 380,911 (2-9.9) |
| 8th | 49 of 25,542 (2-9.0) | 192 of 125,773 (2-9.4) |
| 9th | 14 of 8,733 (2-9.3) | 89 of 42,950 (2-8.9) |
Four grades of statement appear on this page, and it matters which is which. proved means derived from the rule table and holding for every size, by symbolic runs or by a finite search that covers every branch. checked means a finite computation that covers every case up to a stated bound, and nothing beyond it. measured means seen in every case examined, sampled or exhaustive, with no argument that it continues. heuristic means odds estimated from the measured prices. Everything in the first two grades is a statement about the mark model: the tape read as stripes and marks, with the rules applied where their patterns match. The model is exact wherever marks stay far enough apart for the patterns to be unambiguous, which is itself checked for every clean tape below 2⁵⁹ and measured beyond; for the certified theorem about the end of the loop the distance needed is known exactly, 447 cells.
| Grade | Statement | What it says | How it was established |
|---|---|---|---|
| From the rule table to the marks | |||
| proved | The mark rules | Every routine (carry, pass, shift, gap step, the turns) does a fixed thing to the marks, with an exact step count, for stripes of any length and whatever lies beyond. | The machine was run on each starting pattern with the stripe lengths left as symbols and the surroundings unknown; proofs.py prints ALL PROVED. Machine-checked in Lean 4 (core only): the transition table and step semantics are defined, and all 21 rules, the three cycle lemmas and the repeated bounces are theorems whose proofs follow the Python prover's trace, with no axioms beyond propext and Quot.sound. |
| proved | One round of the machine is one round of the mark model | From the tape of any well-formed mark state (marks in order, every stripe of the right parity, the width the first cell of the blank tail), the machine reaches the next round start the mark model computes, or halts exactly where the model says halt; from blank tape it follows the model for as many rounds as the model covers. The model declines ("uncovered") only where no proven rule applies. | Proved in Lean 4: every event of a round as a theorem about positions with arbitrary marks on both sides, the packet phase and the gap phase as functions with their machine theorems, and the induction over events and rounds (no sorry, standard axioms). The comparison with the checkers' simulator found one slip in it, the trailing wall: a shift reaching a block that ends the tape leaves a wall past the width, which a later shift turns into a block where the machine forms an end marker. The slip is now fixed in the checkers, the C engines in current use and the stepper, and a differential test runs every one of them against the proved model on 20,000 random starts of 12 rounds with no disagreement. With the fixed programs the certificates check with unchanged output and the exhaustive check to 54 digits reproduces its result line for line, the corrected case never occurring; earlier instrumented reruns had shown the same to 46 digits. |
| checked | The rules reproduce the machine | Every round and clean tape of the first 3 billion steps; the certified simulation (rules applied to the real tape, every precondition checked) to 1.6 × 10¹⁹ steps; the mark list to n = 1.5 × 10¹⁰; residue lookup to n = 10¹² with 103,032 spot checks. | Direct comparison. |
| proved | How the machine can halt | D reads a 1 only when a carry finds two 1s ahead of its packet, which among far-apart marks means a packet reaching a block; the only block the rules make is an end marker swapped onto the stripes' last 1 at distance 0. So a halt is the end of a right-end run that reaches distance d ≤ 2. | Traced backward from D1 through the rule table; a run of 1.2 million random small tapes confirms the signature. |
| proved | A halt needs a contact | The mark model never halts by itself, so every halt of the machine passes through a configuration the model leaves uncovered: two marks touching. Each such contact is either a close at the right end (the gap touching the last mark, which is the meeting at distance 0, or a block) or an interior contact (two or more marks still to the right, or one the packet meets on its way left). So if no interior contact is ever reached, a halt needs a close. After any stretch of rounds the model covers, such as those of the exit and endgame theorems below, a halt has to come from a contact after the stretch ends. | Proved in Lean 4 about the machine, from any well-formed state and from blank tape, over any number of rounds (no fuel). Not proved: that interior contacts are unreachable on the machine's own tapes, which is the third open family below. |
| proved | Every halt starts at a two-marker state | A cycle is a chain of segments, each starting from a gap, one marker and the end marker, so the machine halts only if it reaches a two-marker state (m, E) whose own segment halts. | From the rules. Every two-marker state below width 2¹⁸ was run: only (4, 9), (4, 13) and (12, 17) halt, and no cycle passes through them. |
| The loop and its lock | |||
| proved | One pass divides the two countdowns exactly | From a three-wall pass start, R = E − c − 1 becomes R/16 and L = 147b + 280E − 392c − 578 becomes L/64. | Symbolic pass map, read off and verified on traced runs. In Lean it is part of the end event of the endgame theorem, checked as identities of forms at every leaf of the endgame trees that comes back to three walls, along with the loop's two other steps: a half pass (R → R/2, only ever as the first step) and a chain break at round 7, where the right end is set again by the width (R′ = (4E + 4R − b + 110)/32). Lean follows a halting run through all three. (A first Lean statement for R ≥ 4097 claimed the map only where its tree chose to stop, so it never said that a pass happens; it was withdrawn.) |
| proved | L is never 0 and at most 280E | L ≡ 3 (mod 7) on every tape, so one stretch of the loop makes at most log₆₄(280E) passes, about a sixth of the tape's binary length. | Arithmetic: the coefficients are multiples of 7 and the constant is not; the bound is the extreme of a linear form over the tape. |
| proved | Leaving the loop is short | From any loop state, in either phase, a run makes at most 8 end meetings before it breaks off, closes, or arrives at a phase-0 pass start; the plain loop is never re-entered without a new run. | Exhaustive symbolic search of every branch, in two implementations; the second decides every comparison of positions on the cone of large gaps and never had to fall back on a geometry. Written out as a certificate of 358 residue classes and re-derived by an independent checker (below); every class also checks through the Lean-verified symbolic model (cone threshold 390), and a coordinate re-split of the whole start class is proved in Lean as a theorem about the machine: every loop state with stripes above 390 cells runs without halting or closing until its end meetings break the halving chain, the tape is clean, or it has completed a pass (358 classes; tree check by the Lean kernel). |
| proved | The exact end of the loop | A run through the loop closes only from end distance R ∈ {2, 4, 8, 16, 24, 32, 48, 64, 176} at its last pass start, with L in a fixed class for each; a pass needs R ≡ 0 (mod 64) and L ≡ 0 (mod 256). Hence log₂W ≤ 3s + 2λ + 6.38 at any pass start of a halting run, and the constant is attained. | Same two searches, every even R to 4096, no cut; the table is below. Certified: 40,991 residue classes (83,699 for starts in either phase), each re-derived from the rules by an independent checker, which also verifies that the classes partition every start class. Exact for pass starts whose stripes exceed 447 cells. All 40,991 classes also check through the Lean-verified symbolic model at the same threshold. Independently, Lean re-splits every start class by coordinates (coverage by construction) and proves the result as a theorem about the machine: for every even R (one split tree with R a free coordinate for every R ≥ 178, one tree for each smaller R), a phase-0 pass start with stripes above 448 cells closes before it leaves phase 0, breaks the end-meeting chain or reaches the next pass start only if R is in the closing set and L is in its class (the classes of the table; L ≡ 3 mod 7 always), and otherwise runs on to one of those ends without halting or closing (the tree checks are evaluated by the Lean kernel). By strong induction on R through the pass starts whose stripes stay above 448 cells, the same holds through the whole loop at any width: in Lean, a run through the loop can close only from a pass start whose R is in the closing set and whose L is in the class of that R. With the pass map checked at every pass start the induction goes through, R³/L² is the same at every one of them, and the bound log₂W ≤ σ + 6.38 is a Lean theorem too: a close through the loop needs R³/L² ≤ 176³/256² at the first pass start. |
| proved | The extra-wall loops | With k extra walls the pass costs 10 + 4k binary digits and has its own never-zero countdown (k ≤ 2500 checked), so each unbroken stretch is bounded the same way. With one extra wall, the detour pass Q has irrational eigenvalues and so no linear countdown, but it has a quadratic one: the norm form D_Q of its two eigenforms is an integer, never 0, and divided by 4096 by every Q pass, so a stretch of detours covers at most two thirds of the halvings, like the plain loop. Every periodic word in the pass P and the detour Q up to length 12 (747 words) has such a lock and covers at most 4/5 of the halvings, so a halt carried by these passes alone has to change words at least once. Mixtures have no lock, and there is no finite endgame. | Symbolic pass maps and the same kind of search. The maps of P and Q are theorems about the machine in Lean (checked by the Lean kernel alone); that D_Q is divided by 4096 and is never 0 (impossible mod 409) is proved in core Lean. The locks of longer words are exact algebra on the composed maps. |
| proved | The rules alone allow a halt | Hand-built tapes with four walls (three free numbers) halt at every width tried, 2¹⁶ to 2¹⁰⁰⁰, by a stretch of the extra-wall loop, a detour and a drop into the plain loop; two were run on the bare rule table to the halt. | Construction by lattice reduction; direct simulation. |
| checked | Two-marker runs have no shared lock | A run from one two-marker state to the next is one of about 14,000 return pieces, each an exact affine map of (m, E) on its residue class. Pieces that only halve the marker's gap are bounded by m; every other piece has its own never-zero countdown, the scaled distance to a fixed line with no integer point. The lines differ from piece to piece, so a change of piece renews the countdown, and the classes of chains of returns multiply 1.66-fold per binary digit: no lock settles a class. | Exact maps read off the route tree's leaves at 30 digits. The eight largest pieces, 39/128 of all two-marker states, and their countdowns are theorems about the machine in Lean (checked by the kernel), for both gaps at least 32. |
| Ways into the loop | |||
| checked | Route ceilings | For a two-marker state following a fixed route, R and L at the entry are affine in (m, E), so 3s + 2λ depends only on m/E and has a ceiling. The commonest route has ceiling 16.0: no two-marker state can halt through it above width 2²²·⁴. Every route decided within 62 digits has ceiling ≤ 52.86, so none can halt above width 2⁵⁹·²; at 64 digits the only entry above the threshold, 54.25, has R ≡ 12 (mod 16) fixed by its own route and cannot close at any width. | Exact symbolic tree over (m, E), 2-adic cosets, order decided at the asymptotic point and identical at four other ratios; entries replayed on the integer engine agree to three decimals. The trees to 36 and 40 digits (946,207 and 3,949,190 leaves) are certified leaf by leaf by an independent checker that reproduces their entry measures in every ceiling bucket; the deeper trees are the same program run further. The route tree is also a theorem about the machine in Lean, at every depth: it is built from the proved model by an explorer proved to build only trees that pass the check, so nothing is evaluated (standard axioms only). From every two-marker state whose two gaps exceed the cone constant, the machine runs whole rounds without halting to the next clean tape, except on the cut classes; evaluated at 36 and 40 digits, these are the Python certificate's leaves (measure 5.92 × 10⁻⁶ and 1.53 × 10⁻⁶). The ceilings themselves are not in Lean, and the loop entries the Lean tree reaches do not need them: a second tree stops a path at the first pass start from which no member of its class can close through the loop at any width (L bounded against R on the class, each candidate left solved for and shown off the integer points), which leaves a quarter of the cut classes at 36 digits (1.48 × 10⁻⁶) and a fifth at 40 (3.25 × 10⁻⁷); a halt from such an entry needs the loop's chain to end without a close first. |
| checked | Exact candidates: none | For all 232,456 routes decided within 46 digits, at every width from 2¹⁷ up to each route's lock limit, no two-marker state has R = 16ᵖ·r and L in r's class; the same for the 5,983,365 entries of ceiling ≥ 20 at 64 digits. | Lattice enumeration on the pinned lines; agrees with brute force on a 2³⁴ box. In Lean, proved at every width for the loop entries the route tree reaches within 36 and 40 digits (all but 94 pass starts at 36 digits, where a gap of 448 is not decided): a window bound on L against R, then Cramer's rule for the candidates left. |
| The machine itself | |||
| checked | No clean tape below 2⁶⁵ halts | Every n < 2⁶⁵ reaches the next clean tape without a halt and without two marks coming nearer than in certified cycles; the machine runs at least 6.7 × 10⁵⁵ steps. | Residue classes of n followed symbolically by two independent engines (the second to 64 digits: 205 billion settled classes, 662 billion direct runs), agreeing at every shared level. Rerun to 60 digits with the trailing-wall fix, the result is identical line for line; the 64-digit run used the fixed engine. |
| proved | A halt needs an open clean tape, and past a loop entry an open pass start | If the machine halts from blank tape, it first reaches a clean tape of width at least 2⁴¹ that lies, at every depth, in a cut class of the clean-tape tree (the class tree over n of the exhaustive check, with cone W ≥ 2⁴¹), and halts from it. Those classes are exactly the exhaustive check's open classes: 1,660,024 at 36 digits (measure 2.4 × 10⁻⁵), 9,188,898 at 40 digits (8.4 × 10⁻⁶). With the loop entries, the tree also stops at the pass starts from which no member of the class can close through the loop at any width; it then cuts 1,255,963 of those classes at 36 digits (1.83 × 10⁻⁵), and the other 404,061 meet such a loop entry, after which the loop's chain ends without a close where the run leaves three walls. Past that point the pass-start trees follow the run to the next landing or a wider clean tape. So a halt needs a clean tape that both trees leave open at every depth, from which the mark model reaches a contact, or a clean tape that only the first leaves open, followed along the loop's chain from its loop entry by a pass start wider than 2⁴¹ with right end R ≥ 178 that the pass-start tree for R ≥ 178 leaves open at every depth (3.8% of a start class at 20 splits, all of it where the depth ran out), from which the machine halts. The pass starts with R < 178, some of which do halt, are not where that chain ends: past a loop entry from which no run of full passes ends below 178 (every entry at 36 digits is one), the loop's chain ends at R ≥ 178. Those that halt include every pass start that the mark model takes to a close at distance 0, which is a halt 54 steps later: eight classes by residues of b and W, which make up all of R = 2, 3/8 of R = 4, 1/8 of R = 6 and 1/32 to 1/256 of R = 8, 16, 32 and 48, and are the only halts the trees for R < 178 find at 20 splits; and every pass start whose loop chain reaches one of them. Pass starts with R ≥ 178 that the tree for R ≥ 178 leaves open at every depth halt too, at every width: a family with R = 178 whose run leaves the loop, enters it again through an end meeting at 254 and closes in round 19, and seven more families like it (an exhaustive scan of the widths 2,048 to 3,072 finds eleven placements of the walls that close, seven of which repeat at every width); and the loop's chain can land on one after a full pass (from R = 2,976 to R = 186 at width 13,400). That route repeats at every scale: the end is met at R − 2, then off the chain at 2ʲ − 2 when W − b = 2ʲ⁺² − 2R − 22, and the meetings halve from there to 0; for each j from 10 to 30 a family with R = 178 there halts, open at every depth, and at each scale exactly one class of the middle wall halts for each R ≡ 2 (mod 4), fixed by about 1.5j + 2 of its binary digits, of which only those with R ≡ 2 (mod 8) are open at every depth. So the second case is about whether the run from blank tape reaches such a pass start, not whether one halts. Followed from the loop entries themselves, in the clean tape's own coordinate, 1.5% of the entries' measure is still open 16 splits past the entry. | Proved in Lean 4 about the machine. The clean-tape tree is built by an explorer proved to build only trees that pass the check, so it holds at every depth with nothing evaluated; where the edge of the cone leaves a comparison undecided only at a class's smallest member, that member is run directly, as in the exhaustive check. The run from blank tape to the clean tape of width 2³² (1.2 × 10⁹ rounds) and the 26.5 million clean tapes below 2⁴¹ in the cut classes, each run to a wider one, are evaluated by native_decide; from width 2²⁰ the same statement, with the same cut classes, is checked by Lean's kernel alone. The tree with loop entries is built by a proved explorer too, and the loop entries are excluded from closing on the whole class, as in the route tree. The pass-start trees are built by a proved explorer as well. The two clean-tape trees split alike until the second stops at a loop entry, where the first goes on, so the chain over clean tapes takes the first tree's step wherever that tree resolves the clean tape. The small-end check at the loop entries is part of the proved explorer's entry test, decided exactly on each entry's class, and R³/L₁² keeps the loop's chain above 178 through full passes and through round-7 breaks from a width of at least 2³⁷. The halts with R = 6 are a theorem too: Lean's kernel runs the mark model six rounds on the whole class, to a round start whose only mark is a block three cells before the width, and from there the machine halts within the width plus 65 steps, proved step by step. So are the eight classes: every event of the mark model is proved to be a run of the machine, the last 54 steps of the close are checked by evaluation for any tape to their left, and Lean's kernel runs the model on each whole class to the close. In 600,000 random pass starts with R < 178, every run the model takes to a close passes through one of the classes; past the end of the loop's chain a run reached a class only by entering the loop again, three times in twelve million starts with R from 50 to 176 (at width 2¹²), and with R from 178 to 376 23 times in 100 million at widths 2¹¹ and 2¹² and never in 75 million at 2²⁰, 2³⁰ and 2⁴¹ (untrusted). The family with R = 178 (any first wall, the rest moved by multiples of 2¹⁴) is a theorem: Lean's kernel runs the model on it symbolically, 18 round starts none of which could be a landing or a clean tape, then the close. So are the other seven families (six from the scan and the one of the landing at 13,400), and the family with R = 178 at each scale j from 10 to 30; the classes for other right ends and the further halting full-pass landings (at width 29,404, and nine near 235,000 that are not open) come from a symbolic search, each landing checked by running the model (untrusted). |
| checked | The two-marker family below 2¹⁸ | Only the states (4, 9), (4, 13) and (12, 17) halt, and the machine reaches none of them. | Direct run of every state: in the mark model to width 2¹⁸, on the proved round model to width 16,001. The first scan left out the marker's last position, m = E − 5, and found only (4, 13). |
| Measured, not proved | |||
| measured | Late entries need the extra-wall loop | Without any extra-wall shape, ways into the loop stop at ceiling 33.6 (to 64 digits; every ceiling above 41.6 has at least 8 extra-wall rounds on its route, the top ones about 20) and plateau patterns park a fixed fraction short of the end; every higher ceiling has an extra-wall piece before it. From the 118 plateau limits, followed exactly to 40 digits, the latest exit without an extra-wall round is the staircase's 36.45, on exactly 1/32 of its class; with extra-wall rounds their exits reach 47.3, at measures below 10⁻¹¹. | Split of the route tree; census of 125 repeating patterns and their affine maps (the census itself comes from sampled runs, which is why the row is measured); the exits from the limits are exact trees. |
| measured | The prices | Each halving before the loop entry costs about 3.4 binary digits through the extra-wall loop and 2.5 inside the plain loop; the share of routes with ceiling ≥ c falls 1.35 binary digits per unit of c. | Exact trees from extra-wall states to 56 digits; the route-tree tail to 42 (converged). |
| measured | The machine's lines are not special | Its two-marker states hit routes, line-ups and depths at the rates random states of the same shape would; separations between marks grow with depth; the extra-wall loop is capped per way in on its two-number families (0 to 4 passes seen). | Comparisons over the exhaustive classes, random lines and random states. |
| heuristic | Odds of a halt beyond 2⁵⁹ | Of order 10⁻³² to 10⁻³⁷ expected halts, depending on how the lead-in is priced; the lock leaves of order one entry it permits in the machine's whole future, each needing about 100 further binary digits of agreement. | The measured prices applied to the exact requirements. |
Each step turns the halting question into a narrower one. The grade on a step is the grade of that reduction, given the steps above it.
Six states, one missing rule, D1. Everything below is derived from it.
The tape is stripes plus a few marks, and each routine moves the marks by a fixed amount. A round is one gap's trip from the left end to the right and the packet's return. Holds for every size.
The only halting configuration is a packet meeting a block, and the only block comes from the end marker swapped onto the last stripe at distance 0. So a halt needs a chain of meetings between the gap and the end marker whose distance halves about log₂W times without breaking.
Every long run uses the 8-round loop. The loop never restarts once left (8 meetings at most follow), and the extra-wall family is capped per way in on two-number families.
Inside the loop σ = 3s + 2λ is the same at every pass start. The lock (L ≠ 0, |L| ≤ 280E) and the exact closing table together give log₂W ≤ σ + 6.38: a halting run must enter the loop late and with L small.
Along any fixed route σ at the entry depends only on m/E, so each route caps the width at which it can halt. Every route decided within 62 digits caps it inside the exhaustive range, with no candidate to run.
Every clean tape below 2⁶⁵ reaches the next without a halt: at least 6.7 × 10⁵⁵ steps.
Three questions remain, each about an infinite family of coincidences in binary digits: routes deeper than the tree, halts carried by the extra-wall loop alone, and marks touching. Their prices are measured; none can be finished by enumeration.
Setting. A round starts with the gap at cell 1, three walls at a < b < c and the tape ending at E, and the next two rounds have shapes gap-block-wall and gap-marker-block: a phase-0 pass start. Put R = E − c − 1, the end countdown, and L = 147b + 280E − 392c − 578, the left countdown. Write s = log₂(E/R) for how late the run is, λ = log₂(|L|/E) for how large L is, and σ = 3s + 2λ.
Statement. If the right-end run through this state ever brings the gap within 2 cells of the end marker, then at the pass start where the loop was last entered, R is one of 2, 4, 8, 16, 24, 32, 48, 64 or 176 and L lies in the class in the table. Working back through the passes, at any pass start of the run R = 16ᵖ·r for one of those r, with r a multiple of 4 if p ≥ 1, and L ≡ 64ᵖ·cr modulo 64ᵖ·Mr. Because a pass divides R by 16 and L by 64, σ is the same at every pass start of the stretch, and the table's worst row gives log₂E ≤ σ + 6.38. The constant is sharp: for R = 176 and L = −256 there are pass-start tapes that halt, at every width, though none the machine reaches.
Why it holds. From a pass start with R fixed, every way the rules can go is a finite tree once the tests are read as conditions on the binary digits of a, b and E: each test either follows from the digits already fixed or splits the class in two. I followed every branch for every even R up to 4096, in two separate programs. One orders the marks by a concrete far-apart geometry and was rerun in five geometries and with walls brought close together; the other decides every comparison of positions on the cone of large gaps and counts any comparison it cannot decide that way. There were none, in 6.7 million comparisons. Both find the same nine closing values, the same densities, and the same classes. For R above 4096 nothing new can happen: at most 8 end meetings follow a loop state without a new pass, and 8 halvings from more than 4096 cannot reach 2.
How it is certified. The search's result is written out as a list of residue classes of (a, b, E) with the claimed outcome of each, and a separate program, which shares no code with either search, re-derives every outcome from the mark rules on symbolic positions: each digit test must be decided by the class, each comparison of positions by the signs of its gap coefficients alone, and the classes of each R must partition the start class. The checker also records, for every comparison it decides, how far apart the marks must be for the decision to be the true one. The answer is 447 cells: for every pass start whose three stripes exceed that, the theorem holds as stated; a pass start with a shorter stripe is a tape with two marks a few hundred cells apart, which is the third of the three open families below. The same checker on the exit certificate (R free) shows its decisions exact once R + 1 exceeds 241, so the two certificates overlap on 242 ≤ R ≤ 4096 and together cover every R.
In Lean. The statement with the table's classes of L, without the bound 4096, is a theorem about the machine in Lean 4, within the loop: from a phase-0 pass start whose stripes exceed 448 cells, the run closes before it leaves the loop only from a pass start whose R is in the closing set and whose L is in that R's class (one split tree with R a free coordinate for every R ≥ 178, one tree for each smaller R, and induction on the halting time through every pass start the run lands on: after a full pass, a half pass or a chain break at round 7, each with its exact map on E, R and L). The bound below is a Lean theorem as well: a close through the loop needs R³/L² ≤ 176³/256², which is log₂E ≤ σ + 6.38, at the start of the run's last stretch of full passes. A chain break at round 7 can be followed by a close only when E < 2²⁴, so from wider pass starts that is the first pass start, or the one after a single half pass. From E ≥ 2¹³ every landing is again a pass start with stripes over 448 cells, except after a half pass whose middle wall is within 896 cells of the end, so from wider pass starts the run leaves the loop only at a round start that is not three walls. Past that point a tree for each class of pass starts follows the run on to the next landing or a wider clean tape, at every depth with nothing evaluated, so a halt through a pass start needs a closing class, a pass start the tree leaves open at every depth, or a clean tape after it. Some of the open ones are real halts, and that is a theorem as well: one pass start in eight with R = 6 (those with b ≡ 2 mod 8 and W ≡ 2 mod 4) leaves the loop at round 2 and meets the end at distance 0 in round 7, and the machine halts there (from walls 743, 1,802 and 3,319, width 3,326, after 11,362,209 steps). More generally, a close at distance 0 that the mark model reaches is proved to be a halt, 54 steps later: every pass start in the trees that the model takes to a close halts, eight classes by residues of b and W with R in (2, 4, 6, 8, 16, 32, 48).
What it buys. A run that halts on a tape of width 2ᵏ must enter the loop with σ ≥ k − 6.38. Since |L| ≤ 280E, λ ≤ 8.13 and so s ≥ (k − 22.6)/3: the loop must be entered at least that many halvings below the width. Everything seen in the machine's own runs has σ ≤ 32.2; without the extra-wall loop the latest entry any mechanism produces is 36.45 (exact, from the staircase plateau's limit); with pieces of the extra-wall loop the route tree's ceilings reach 52.86 by 62 digits. For the exhaustive frontier, widths up to 2⁶², a halt needs σ ≥ 55.6.
| R at the last pass start | L must be | Trailing zeros of L | 3 log₂R − 2 log₂|L|min | Rounds to the close |
|---|---|---|---|---|
| 2 | 10 mod 14 | 1 | −1.00 | 2 |
| 4 | 10 mod 14 | 1 | 2.00 | 2 |
| 8 | 24 mod 56 | 3 | −0.17 | 3 |
| 16 | 192 mod 224 | 5 | 2.00 | 5 |
| 24 | 416 mod 448 | 5 | 3.75 | 9 |
| 32 | 192 mod 448 | 6 | −0.17 | 8 |
| 48 | 640 mod 896 | 7 | 0.75 | 11 |
| 64 | 640 mod 896 | 7 | 2.00 | 10 |
| 176 | 640 mod 896 | 7 | 6.38 | 13 |
The last column is the number of rounds from the pass start to the meeting at distance 2 or 0. The class for R = 176 is reached by seven rounds of the loop and two of the short piece gap-block, gap-wall-wall. A pass itself is the coset L ≡ 1536 (mod 1792), that is L ≡ 0 (mod 256) on top of L ≡ 3 (mod 7), and it happens only from R ≡ 0 (mod 64).
A route is a residue class. Start a segment from a two-marker state with the marker at m and the end at E, both free. Each test the rules make reads a binary digit of a position, which is an affine form in m and E, so the states that follow one sequence of rounds form a coset of a lattice in the (m, E) plane, of index 2 to the power of the digits read. The route tree follows every such coset until the segment ends or reaches a phase-0 pass start. Order comparisons between marks are decided at the asymptotic point, and the tree is the same at m/E = 1/2, 1/64, 63/64 and 5/16, so the branching holds for every ratio.
At the entry, R and L are affine in m and E. Dividing by E, σ depends only on t = m/E, a smooth function on (0, 1) whose maximum is the route's ceiling. The commonest route, gap-marker-marker-marker, then gap-marker-marker-wall, gap-marker-wall-wall, gap-wall-wall-wall, has R = (3E − m + 13)/8 and L = (854E − 343m − 1030)/16, so σ(t) = 3 log₂(8/(3 − t)) + 2 log₂((854 − 343t)/16), which runs from 15.72 to 15.99. By the theorem, no two-marker state entering by this route can halt on a tape wider than 2²²·⁴ cells, whatever its gaps and line-ups; the empirical ceiling of 8 on its gap, found earlier, is a shadow of this.
The deep routes. The highest ceilings come from long lead-ins through pieces of the extra-wall loop. The top entry at 62 digits (ceiling 52.86, a 41-round route with two detour-type passes and one standard pass) enters the plain loop 15.1 halvings below the width; rebuilt as an integer state 2⁶⁴ cells wide it enters with σ = 52.854, as predicted. Its ceiling allows a halt only below 2⁵⁹·²⁴, inside the exhaustive range by 0.76 of a binary digit. At 64 digits one entry crosses the threshold, with ceiling 54.25; its own tests fix R ≡ 12 (mod 16), and no closing value or pass is compatible with that, so it is excluded at every width without any enumeration. The 64-digit tree was rerun with every addition on a position form checked in 128-bit arithmetic, after the first run's deepest paths had overflowed 64-bit integers: the rerun has the same 5,983,365 entries of ceiling ≥ 20 and the same ceilings, and drops 113,555 overflowing paths, 10⁻¹⁴ of the measure, as undecided.
Below the ceiling, the candidates are explicit. On a route's coset, R = 16ᵖ·r is one linear equation, a line of lattice points; L's class thins the line to an arithmetic progression. For every route decided within 46 digits and every width from 2¹⁷ to its lock limit, that progression is empty: 11,305 routes fix R in a class that contains no closing value at all, 7,915 more have L's class inconsistent on every pinned line, and the remaining 213,236 have consistent congruences but no lattice point in the window the lock leaves. The older version of this check had 866,445 looser candidates to run; the exact one has none.
The class tree over n (the exhaustive check) follows every residue class of n from its clean tape to the next, splitting a class when a test needs another digit, and records every comparison of positions so that each settled class is a proof for all its members. Two engines wrote independently agree at every shared level, and the minima of all separations are logged, which is how contacts are excluded below 2⁵⁹.
The route tree over (m, E) does the same for two-marker states with both numbers free, and records at every phase-0 pass start the forms of R and L. Its results were replayed on the integer engine for the top entries at 40, 58, 62 and 64 digits, and the trees to 36 and 40 digits are certified: every one of their 946,207 and 3,949,190 leaves is written out with its meeting outcomes and round shapes, a separate checker replays each from the start state with its own implementation of the rules, imposing a recorded outcome only where the class does not decide it, and the split sequences of all leaves are verified to form a complete prefix code, which is the partition of the start class. The checker's own count of pass starts agrees with the explorer's in every ceiling bucket.
The endgame search starts from a pass start with R fixed and a, b, E free, and is the finite search behind the theorem. The certificates are its leaves written out (three files: the phase-0 starts, the starts in either phase, and the loop state with R free), and the checkers are two short programs that accept a certificate only if every leaf follows from the rules and the leaves partition the start class; all three are accepted with no failure, no undecided digit and no uncovered configuration. What a reader of the checkers has to trust is the rule table under "How the rules give the round recurrence", exact rational arithmetic, and the bookkeeping itself: that a class on which every digit test is decided and every comparison has a fixed sign follows one sequence of rules. The Lean formalization re-proves the mark rules inside Lean 4 from a definition of the machine: a rule is a theorem about `steps n` on a configuration whose surroundings are variables, single steps are checked by evaluation, repeats are crossed by the three cycle lemmas, and the file of 21 rules is generated from the Python prover's traces, so the two proofs are the same proof in two checkers. On top of the rules it proves the round theorem (from the tape of any well-formed mark state the machine reaches the next round start the mark model computes, or halts where the model says halt; from blank tape it follows the model for as many rounds as the model covers), and it runs the model on symbolic positions with every decision checked, proved sound against the concrete model: every leaf of the endgame, any-phase and exit certificates checks through it, which makes each non-closing leaf a statement about the machine. Re-splitting the start classes by coordinates in Lean gives coverage by construction, and two results are proved as theorems about the machine, each run followed to a stated end (its end meetings break the halving chain, the tape is clean, the run leaves phase 0, or it reaches the next pass start): every loop state with large gaps runs to such an end without halting or closing, and so does every phase-0 pass start unless its R is in the closing set and its L in R's class (the tree checks are evaluated by the Lean kernel). Two more theorems carry this to every width and to the halt itself: by induction over the passes, a run through the loop closes only from a pass start whose R is in the closing set and whose L is in its class, and since each pass divides R by 16 and L by 64, only if log₂E ≤ σ + 6.38 at its first pass start; and a halt needs a contact, a close at the right end unless an interior contact comes first. The route tree, at every depth, and the pass maps of the extra-wall loop are theorems in Lean too, and an end-to-end theorem puts the pieces together from blank tape: a halt needs a clean tape of width at least 2⁴¹ that the clean-tape tree leaves open at every depth. From width 2²⁰ the same statement is checked by the Lean kernel alone, with no compiled evaluation. Comparing the proved model with the simulator used by the checkers and explorers found one slip in the simulator (the trailing wall: a shift reaching a block that ends the tape); it is fixed, a differential test checks every simulator against the proved model, and the certificates and the exhaustive check to 54 digits give the same results with the fixed programs. The candidate solver turns a route's forms and the closing table into explicit lattice points and was tested against brute force. The invariant search looked for any conserved quantity with weights on patterns of up to 7 cells and positions modulo up to 8, modulo 2, 3, 5, 7 and over the rationals: the count of 1s mod 3 is the only one, so no conservation law separates the halting configurations from the reachable ones.
What none of them can do is finish an infinite family. Beyond the frontier a halt needs a route about 1.2k digits deep at width 2ᵏ, more digits than n has, and then about 2.5(k − s) further binary digits of agreement. Each such requirement is a statement about the binary digits of particular whole numbers, which is where the question rests.
In the first 3 billion steps, 66.4% are carry steps and 33.2% are pass steps. The last 0.4% are turns (0.18%), gap steps (0.10%), other fixed sequences (0.09%) and shifts (0.03%).
The 2-to-1 split comes from the bounce: the head crosses the same stripes once each way, at one step per cell going right and two coming back. In that stretch there were 522,285 marker turns, 441,791 wall turns, 807 swaps and 647 merges. Every swap started with a multiple of 4 stripe cells between the gap and the marker, and every merge with 2 more than a multiple of 4.