Closing Gap Rule Map

Turing machine · 6 states, 2 symbols · one halt rule, out of reach for at least 4.8 × 10⁴⁸ steps

What each rule in 1RB0RE…0LD1RE does

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.

1RB0RE_1LC0RA_1LA1LD_1LA---_0RF0LB_0LD1RE Compare the BB(6) Champion Rule Map

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.

The rule table, sorted by job

StateReads 0Reads 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.

Carry leftA1 E1 B0 C0
The head carries a packet, 111, leftward through the stripes. A and E erase the packet's first two 1s, B writes one back, and C writes a 1 into the stripe 0 ahead. The packet is now two cells further left and the stripes behind it are as before. Four steps per two cells.
Pass rightE0 F1
E keeps each stripe 0 and F each stripe 1. The head walks right one cell per step and changes nothing. It stops when E reads a 1 or F reads a 0.
Shift rightA0 B1
A writes 1 over each 0 and B writes 0 over each 1, so the stripes ahead move over by one cell. Rare: it runs only when a gap meets a wall or the head reaches a block.
Gap stepA0 B1 A1
A carry that reaches a gap: the packet fills the gap's first two 0s, a new 000 opens two cells to the right, and A1 starts the pass.
TurnE1 B1 A0 B0 C1 D0 A0 B1 · E0 F0 D0
A pass that reaches a marker moves it two cells left and turns back with a packet. A pass that reaches a wall or blank tape turns back with a packet and moves nothing.
HaltD1
D reads a 1 only if a carry finds 1s in the two cells ahead of its packet. A marker supplies one of them, never both.

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.

The marks are the signposts

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.

1end000gap101010101010stripes111packet010101010stripes11marker010101010101stripes00wall101010101stripes…blank

The routines up close

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.

Carry left

A1010101110101step 4,260 A reads 1: write 0, move right, go to E
E1010100110101step 4,261 E reads 1: write 0, move left, go to B
B1010100010101step 4,262 B reads 0: write 1, move left, go to C
C1010101010101step 4,263 C reads 0: write 1, move left, go to A
A1010111010101step 4,264 A reads 1: write 0, move right, go to E

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.

Pass right

E1000101010101step 4,295 E reads 0: write 0, move right, go to F
F1000101010101step 4,296 F reads 1: write 1, move right, go to E
E1000101010101step 4,297 E reads 0: write 0, move right, go to F
F1000101010101step 4,298 F reads 1: write 1, move right, go to E
E1000101010101step 4,299 E reads 0: write 0, move right, go to F

Just after a gap step. E reads the stripe 0s and F the 1s, and nothing on the tape changes.

Gap step

C0010001010101step 4,291 C reads 0: write 1, move left, go to A
A0010011010101step 4,292 A reads 0: write 1, move right, go to B
B0010111010101step 4,293 B reads 1: write 0, move right, go to A
A0010101010101step 4,294 A reads 1: write 0, move right, go to E
E0010100010101step 4,295 E reads 0: write 0, move right, go to F

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.

Wall turn

F1010101010010step 4,672 F reads 1: write 1, move right, go to E
E1010101010010step 4,673 E reads 0: write 0, move right, go to F
F1010101010010step 4,674 F reads 0: write 0, move left, go to D
D1010101010010step 4,675 D reads 0: write 1, move left, go to A
A1010101011010step 4,676 A reads 1: write 0, move right, go to E

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.

Shift right

E1010000101010step 2,808 E reads 0: write 0, move right, go to F
F1010000101010step 2,809 F reads 0: write 0, move left, go to D
D1010000101010step 2,810 D reads 0: write 1, move left, go to A
A1010010101010step 2,811 A reads 0: write 1, move right, go to B
B1010110101010step 2,812 B reads 1: write 0, move right, go to A
A1010100101010step 2,813 A reads 0: write 1, move right, go to B

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.

Marker turn Marker pass A marker turn, step by step

Pass right, last stepF1 keeps the marker's first 1 and moves on.
F010101011010step 4,318 F reads 1: write 1, move right, go to E
Marker turnE1 and B1 erase the marker. A0, B0, C1, D0 and A0 fill its two cells and the 0 on each side with 1s, so six 1s stand in a row, and B1 turns the third of them into a 0. The first two are the marker, now two cells further left, and the last three are a packet.
E010101011010step 4,319 E reads 1: write 0, move left, go to B
B010101010010step 4,320 B reads 1: write 0, move right, go to A
A010101000010step 4,321 A reads 0: write 1, move right, go to B
B010101001010step 4,322 B reads 0: write 1, move left, go to C
C010101001110step 4,323 C reads 1: write 1, move left, go to D
D010101001110step 4,324 D reads 0: write 1, move left, go to A
A010101011110step 4,325 A reads 0: write 1, move right, go to B
B010101111110step 4,326 B reads 1: write 0, move right, go to A
One carry cycleThe packet moves two cells left, up against the marker.
A010101101110step 4,327 A reads 1: write 0, move right, go to E
E010101100110step 4,328 E reads 1: write 0, move left, go to B
B010101100010step 4,329 B reads 0: write 1, move left, go to C
C010101101010step 4,330 C reads 0: write 1, move left, go to A
Marker passWhere a carry would find a stripe 0, C finds the marker's 1. C1 D0 replace the usual C0, and the packet comes out on the far side. The marker has not moved.
A010101111010step 4,331 A reads 1: write 0, move right, go to E
E010101011010step 4,332 E reads 1: write 0, move left, go to B
B010101001010step 4,333 B reads 0: write 1, move left, go to C
C010101101010step 4,334 C reads 1: write 1, move left, go to D
D010101101010step 4,335 D reads 0: write 1, move left, go to A
Carry onThe carry continues toward the gap.
A010111101010step 4,336 A reads 1: write 0, move right, go to E
E010011101010step 4,337 E reads 1: write 0, move left, go to B

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.

Each part of the calculation

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.

Carry left Pass right Shift right Gap step Turn Other fixed sequence

Closing in on a marker

Gap with a marker as the next mark
beforeleft partgap000stripesd cellsmarker11stripesstartnext bounce123456afterleft part+ 2 cellsgap→ 2stripesd − 4 cellsmarker← 2stripes+ 2 cells

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.

  1. passPass right over the stripes to the marker. E0 F1 repeating
  2. turnMarker turn. The marker is rebuilt two cells further left, with a packet 111 just right of it. E1 B1 A0 B0 C1 D0 A0 B1
  3. carryOne carry cycle brings the packet up to the marker. A1 E1 B0 C0
  4. fixedMarker pass: the packet crosses the marker, which stays where it is. A1 E1 B0 C1 D0
  5. carryCarry the packet left over the stripes to the gap. A1 E1 B0 C0 repeating
  6. gap stepGap step. The packet fills the gap and a new 000 opens two cells to the right. A1 hands off to the pass. A0 B1 A1

Closing in on a wall or the end

Gap with a wall or blank tape as the next mark
beforeleft partgap000stripesd cellswall00beyondstartnext bounce1234afterleft part+ 2 cellsgap→ 2stripesd − 2 cellswallsamebeyond

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.

  1. passPass right to the wall. E0 F1 repeating
  2. turnWall turn. E and F read the 00, and D writes a 1 that starts a packet. Nothing on the tape moves. E0 F0 D0
  3. carryCarry the packet left to the gap. A1 E1 B0 C0 repeating
  4. gap stepGap step. A0 B1 A1

Swap

Gap meets a marker with 4k stripe cells between them at the start
beforeleft partgap000marker11stripesup to the next markstartnext mark12345afterleft partmarker11gap000stripes

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.

  1. passWith no stripes left between them, the pass crosses just the gap's last 0 and the marker's first 1. E0 F1
  2. turnMarker turn. Two cells left of the marker is the gap itself, so the rebuilt marker overlaps the gap's last cells. E1 B1 A0 B0 C1 D0 A0 B1
  3. carryTwo carry cycles bring the packet back to what is left of the gap. No marker pass is needed. A1 E1 B0 C0 A1 E1 B0 C0
  4. gap stepGap step. The gap reopens one cell right of where it was, and a marker 11 now sits just left of it. A0 B1 A1
  5. passPass right to whatever mark comes next. E0 F1 repeating

Merge

Gap meets a marker with 4k + 2 stripe cells between them at the start
beforenext gapor left endstripesand old markersgap000stripes2 cellsmarker11stripesstartpass right123456789aftergapmoved or newstripesand old markerswall00stripes

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.

  1. passPass right over the last two stripe cells. E0 F1
  2. turnMarker turn. E1 B1 A0 B0 C1 D0 A0 B1
  3. carryOne carry cycle. A1 E1 B0 C0
  4. fixedMarker pass. Its D0 lands on the gap's last 0, and A0 B1 fill the gap in. The carry goes on and leaves a wall, 00, where the gap and the marker met. A1 E1 B0 C1 D0 A0 B1
  5. carryCarry left. Markers left behind by earlier swaps are in the way. A1 E1 B0 C0 repeating
  6. fixedEach one is crossed with a marker pass. A1 E1 B0 C1 D0
  7. carryCarry on to the next gap. A1 E1 B0 C0 repeating
  8. gap stepGap step at that gap. If there is none, the packet reaches the blank tape at the left end and a new gap starts there. A0 B1 A1
  9. passPass right: the woken gap starts closing in on its next mark. E0 F1 repeating

The gap meets a wall

Gap step lands right next to a wall or the blank right end
beforenext gapor left endstripesand old markersgap000stripes1 cellwall00stripesblankstart1234567891011aftergapmoved or newstripesand old markersstripesgap and wall gonemarkernew end

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.

  1. passThe last bounce: pass right. E0 F1
  2. turnWall turn. E0 F0 D0
  3. carryOne carry cycle. A1 E1 B0 C0
  4. gap stepGap step. The new 000 lands against the wall's 00. A0 B1 A1
  5. fixedE and F read 0 0 again, and D turns the head into a shift. E0 F0 D0
  6. shiftShift right: every stripe moves over by one cell. That fills in the gap and the wall. A0 B1 repeating
  7. fixedAt the blank tape A0, B0 and D0 write three 1s. Two of them stay as the end's new marker, and the tape is one cell longer. A0 B0 C1 D0
  8. carryCarry a packet back to the left. A1 E1 B0 C0 repeating
  9. fixedMarker pass at each marker on the way. A1 E1 B0 C1 D0
  10. carryCarry on to the next gap. A1 E1 B0 C0 repeating
  11. gap stepGap step, or a new gap at the left end. A0 B1 A1

Halt

A carried packet reaches a block 111
beforestripesblock111stripespacket111stripesstarthalt12

The machine stops. This never happened in 3 billion steps.

  1. carryCarry left toward the block. A1 E1 B0 C0 repeating
  2. haltAt the block, C reads one of its 1s and D the next. D has no rule for reading 1. A1 E1 B0 C1 D1

Every meeting, in one table

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 isand reachesWhat happensRules
Carrying a packet lefta gap 000Gap step: the gap moves two cells right and the head turns right.A0 B1 A1
a marker 11Marker pass: the packet crosses and the marker stays put.A1 E1 B0 C1 D0
a wall 00The wall becomes a marker with a gap just right of it, and the head turns right.A0 B1 A1
blank tape at the left endA new gap starts there, and the tape is two cells longer.A0 B1 A1
a block 111Halt. Never seen in the run.A1 E1 B0 C1 D1
Passing righta marker 11Marker 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 tapeWall turn: nothing moves, and the head comes back with a packet.E0 F0 D0
a block 111The block becomes a wall, and a shift starts from there.E1 B1, then A0 B1 repeating
After a gap stepa wall right next to the gapGap and wall run together, and a shift starts from there.A1 E0 F0 D0, then A0 B1 repeating
Shifting righta marker 11The marker is used up. A gap opens where it was, and the head passes right from there.A1, then E0 F1
a wall 00The wall becomes a block, and the head comes back with a packet.A0 B0 C1 D0
blank tape at the right endThe 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 ineach other, 4k stripe cells apart at the startSwap: the marker ends up just left of the gap, which goes on.marker turn, two carry cycles, gap step
each other, 4k + 2 cells apartMerge: 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

A stretch of the run, to scale

4,1804,2154,2924,5954,6184,6574,7001Merge2Carry back over a marker3Gap wakes: 6 bounces4Merge again5Carry to the end: new gap6Closing in on the wallstepstep 4,180tape after step 4,700gapstripesstripesstripes
Steps 4,180 to 4,700, one row per step and one column per cell. Shaded columns are cells holding a 1, so the marks show up as breaks in the stripes. A merge near the right leaves a wall and sends a packet back over a marker to a sleeping gap at the left end. That gap closes in on the marker in six bounces, and they merge too. This packet reaches the left end and starts a new gap, which closes in on the second wall. The band at the bottom marks, left to right, the gap, the packet, and the two walls. Carry left Pass right Shift right Gap step Turn Other fixed sequence

The big picture: halving

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.

43,385153,557259,659364,251475,189577,363679,067779,549step
One full cycle, to scale: about 160 cells across and 36,164 steps down, so every sweep looks almost flat and the bounces blur into grey wedges. The yellow line traces the gap and the pink line the mark it bounces off. Blue lines are packets carried back past the gap to the left, and green lines are shifts. Each numbered band starts when a new gap begins at the left end. The gap Marker, wall or end it bounces off Carry back to the left Shift
  1. From 43,393. The gap meets the end's marker in the middle and swaps (step 49,905). It closes in on the blank end and meets it (53,283). The packet goes back over the middle marker.
  2. From 53,557. Swap with the middle marker at the quarter point (55,269). Merge with the end's marker (59,468) leaves a wall.
  3. From 59,659. Swap at the eighth point (60,123). The gap meets the wall (63,915), and a shift runs 52 cells to the end.
  4. From 64,251. Swap at the sixteenth point (64,379). Swap with the end's marker (71,312). The gap meets the blank end (74,894).
  5. From 75,189. Swap (75,221). Merge with the marker from round 4 (77,260) leaves a wall.
  6. From 77,363. The swap (77,365) puts the marker at the very left end. The gap meets the wall (78,637), and the shift runs to the end.
  7. From 79,067. The packet crossed the marker at the left end, turned it into a wall and started a new gap just beyond it. After one bounce the gap meets that wall (79,078), and a shift crosses the whole tape. The packet comes back, and after step 79,549 the tape is clean with n = 77.

Clean tapes

after stepncells
4528
9131432
33,82959122
43,38562128
79,54977158
95,11780164
116,30986176
155,05995194
178,09798200
245,823110224
…
2,937,038,1872,5465,096
2,994,703,6632,5615,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.

The marks as arithmetic

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.

ReachesWhat happensPositions afterwards
Gap at g moving rightNext mark
a marker p, with d a multiple of 4Swap, after d/4 bouncesmarker → 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 4Merge, after (d − 2)/4 bouncesa wall at g + d/2 + 3; a packet heads back
a wall qGap and wall vanish, and a shift starts at qsee the shift rows
a block rThe block becomes a wall, the gap falls asleep, and a shift startsa wall at r − 1
nothing, only blank tapeA new end marker formsw grows by 3, with the new end marker 2 cells before the new end; a packet heads back
Shift moving rightNext mark
a marker pThe marker becomes the new gapa gap at p, which goes on
a wall qThe wall becomes a blocka block at q; a packet heads back
a block rThe block becomes a walla wall at r + 2; a packet heads back
blank tapeA new end marker formsw 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 hA gap step wakes itgap → h + 2
a wall qThe wall becomes a marker and a gapmarker at q − 1, gap at q + 1
the left endA new round startsevery position + 2, a new gap at 1 (+ 4 if a marker sits at cell 0; it becomes a wall at 5)
a blockThe machine haltsnever 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.

Three rounds, worked through

The run from the clean tape with n = 14. Every list of marks here matches the tape in the step-by-step run.

Round startsEventArithmeticMarks afterwards
Step 921w = 34 · G1 M32the clean tape n = 14Gap 1 closes in on marker 32d = 32 − 1 − 3 = 28 = 4 × 7, so a swap after 7 bouncesM14, G16
Gap 16 has blank tape aheadw = 34 + 3 = 37, end marker at 35M14, M35
The packet crosses M14 and reaches the left endevery position + 2w = 39 · G1 M16 M37
Step 1,749w = 39 · G1 M16 M37Gap 1 closes in on marker 16d = 16 − 1 − 3 = 12 = 4 × 3, so a swap after 3 bouncesM6, G8
Gap 8 closes in on marker 37d = 37 − 8 − 3 = 26 = 4 × 6 + 2, so a merge after 6 bounces, into a wall at 8 + 13 + 3M6, W24
The packet crosses M6 and reaches the left endevery position + 2w = 41 · G1 M8 W26
Step 2,367w = 41 · G1 M8 W26Gap 1 closes in on marker 8d = 8 − 1 − 3 = 4, so a swap after 1 bounceM2, G4
Gap 4 reaches wall 26, and the shift runs to blank tapew = 41 + 2 = 43, end marker at 41M2, M41
The packet crosses M2 and reaches the left endevery position + 2w = 45 · G1 M4 M43, at step 2,915

From one clean tape to the next

Clean tapeNext clean tapeRoundsShare
n oddn + 3235%
n a multiple of 4n + 6314%
n = 26 or 38 (mod 48)n + 9523%
n = 2 (mod 96)n + 125 or 69%
any other nround by round7 to 4319%

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.

How the tape gets set up

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.

0461417222629323438451Write 1112First stripe3Carry4First gap5Pass and wall turn6Carry7Gap step8Gap meets the end9Shift10End marker11Carrystepblank tapetape after step 4510stripes1010marker11
Every step to scale, one row per step and one column per cell. The numbers match the table below. Carry left Pass right Shift right Gap step Turn Other fixed sequence
Every rule, in order
stepspartruleswhat it does
0–3Write 111A0 B0 C1 D0Blank 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–5First stripeA0 B1A 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–13CarryA1 E1 B0 C0 A1 E1 B0 C0Two carry cycles take the packet to the left end.
14–16First gapA0 B1 A1The packet reaches the blank tape at the left end. As at every left end, A0 B1 A1 leave 1 000: the first gap.
17–21Pass and wall turnE0 F1 E0 F0 D0Pass 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–25CarryA1 E1 B0 C0Carry it back to the gap.
26–28Gap stepA0 B1 A1Gap step. The gap moves two cells right and is now next to the blank tape.
29–31Gap meets the endE0 F0 D0The gap meets that wall: E0 F0 D0 again, this time starting a shift.
32–33ShiftA0 B1One shift cycle reaches the blank tape.
34–37End markerA0 B0 C1 D0A0 B0 C1 D0 write three 1s there: the end's marker plus the start of a packet.
38–45CarryA1 E1 B0 C0 A1 E1 B0 C0Carry the packet left. After step 45 the tape holds only stripes and the end marker: 10 1010 11, the first clean tape.

What keeps the right-end cascade going

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 nMeetingsDigits
73,742 mod 2³⁰1030
26,819,166 mod 2³⁵1135
4,321,786,462 mod 2³³1233
363,165,946,702 mod 2⁴¹1441

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.

MeetingsShare of all n
183.3%
214.3%
31.26%
41.16%
59.5 per million
60.83 per million
844 per billion
104.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.

The binary-digit argument, step by step

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.

Does it ever halt?

In brief

  • No halt below n = 2⁶⁵. Every clean tape below 2⁶⁵ was checked through its residue class, so the machine runs at least 6.7 × 10⁵⁵ steps without halting.
  • A halt needs one long run at the right end: about log₂ n meetings in a row. The longest anywhere below 2⁶⁵ is 19.
  • Long runs are one loop, and it is locked. One stretch of it covers at most about two thirds of what a halt needs, and it ends the run. Its ending is now known exactly: the run can reach the end only from at most 176 cells away, with the left countdown in a fixed residue class. So a halt needs the loop to start late, and beyond the checked range later than any run seen by a wide margin.
  • The usual ways into that loop can never lead to a halt. For every way in found within 62 binary digits, which covers all but about eight in ten billion two-marker states, the exact end of the loop alone rules out a halt on any tape wider than 2⁵⁹·² cells, and the checked range covers the rest. The commonest way can't lead to a halt above 2²²·⁴ cells at all.
  • The rules alone do allow a halt. Hand-built tapes with three free numbers halt at every width tried up to 2²⁰⁰: a stretch of a rarer loop, a drop into the locked one, then a stretch of it.
  • The machine's own tapes have too few free numbers. They have one (two for the wider family they sit in), while a halt costs about 2.8 binary conditions per halving. The expected number of halts beyond 2⁵⁵ comes out at 1 in 10²⁴ or less. The machine's own tail looks cheaper for a while, but that stretch is a few lucky lines of states, and lines that line up further are rarer by a binary digit per halving.
  • And the rarer loop is capped outright for them. Each loop has a number of countdowns, two for the locked loop and three for the rarer one, and a family of tapes can follow a loop without a fixed limit only if it has at least that many free numbers. So for the machine's tapes the rarer loop stops after a fixed number of passes for each way in. For the commonest ways in that number is zero or one; among 190,923 ways in built from all routes to 30 binary digits, 81 allow two passes, 8 allow three and none allows four.
  • The closest any clean tape is known to come is about a third of the way. The best found reach 19.7 halvings at 57 binary digits and 29.6 at 94, where a halt needs about 57 and 94.
  • No proof yet. What is left is a statement about binary digits of the same kind as the Collatz problem. The section What is established, and how firmly grades every statement on this page and states the main theorem in full.

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.

StepWidthMarks after the gap at 1
072W7 W30 W39
12474B32 W41
1,89478M16 B61
3,59682M8 W38 W73
4,75084M4 B75
7,22490W5 W44 W85
7,37492B46 W87
9,33296W27 W70 W93
10,06698B72 W95
10,302halts: 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 nBest halvingsNeeded to halt
1710.316.2
3012.429.1
3914.038.5
4514.744.8
best found
5216.551.7
5719.756.7
6820.867.8
7522.174.4
8525.484.5
9429.693.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.

The machine's tail is a staircase of lucky lines

2⁻¹⁵2⁻²⁰2⁻²⁵2⁻³⁰2⁻³⁵2⁻⁴⁰4567891011121314halvings from the full width to the closest meeting, at leastshare of even nline 1 stops at 10.4line 2 stops at 12.5line 3 stops at 14.1the machine's own, all lines
The machine's own: share of even n whose cycle comes within 2⁻ˣ of the end line 1 line 2 line 3
Every two-marker state a class of n reaches is a whole line of states, one for each member of the class. Each of the three lines shown carries most of the machine's share at some depth, and each stops at a fixed reach: line 1, (7138t + 72, 8192t + 93), reached at 11 digits, at 10.4 halvings; line 2, (18t + 8, 512t + 229) at 7 digits, at 12.5, the same from 34 to 70 digits of t; line 3, (13922t + 2004, 524288t + 75497) at 17 digits, at 14.1. Up to its reach a line pays about 6 binary digits per 4 halvings, one pass of the loop. Summed over the 5,141 lines reached within 22 digits, followed to 46 digits in all, the total matches the exact tail of all cycles to within 2% at every x.
The numbers
x at leastAll linesLine 1Line 2Line 3
42-13.52-18.7 (3%)2-18.8 (3%)2-26.9 (0%)
52-16.02-20.5 (4%)2-21.6 (2%)2-27.9 (0%)
62-19.52-23.4 (7%)2-24.0 (4%)2-30.0 (0%)
72-22.02-26.0 (6%)2-25.0 (12%)2-32.0 (0%)
82-23.32-27.0 (8%)2-26.0 (16%)2-33.0 (0%)
92-25.42-27.0 (32%)2-28.0 (16%)2-34.0 (0%)
102-26.72-27.0 (79%)2-30.0 (10%)2-36.0 (0%)
112-29.9none2-31.0 (46%)2-38.0 (0%)
122-30.9none2-32.0 (48%)2-39.0 (0%)
132-38.0nonenone2-40.0 (25%)
142-38.7nonenone2-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 widthRun at the endSteps to halt
7.1 × 10¹⁶53 meetings9.3 × 10³⁴
1.6 × 10⁶⁰197 meetings1.8 × 10¹²²
about 2¹⁰⁰⁰997 meetings4.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.

How far each loop can run
LoopCount­downs2 free numbers (two-marker states)1 free number (a cycle's own states)
Plain2No fixed cap; the lock stops it at ⅔ of the halvingsFixed cap per way in
1 extra wall3Fixed cap per way inFixed cap per way in
k extra walls2 + kFixed cap per way inFixed 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.

The detour refills the countdown

050100150200050100150200meetings in the runbinary digits (log₂)detourone stretch couldgo no furtherleft countdowndistance to the end
Left countdown, the extra-wall loop's L at each pass start Distance from the last wall to the end
The 2²⁰⁰-cell tape from the table, which also passes the mod-3 test every tape reached from blank must pass. Each pass costs the countdown 6 binary digits and the distance 4. A single stretch would have run out of countdown at meeting 137, with the wall still about 2⁶⁰ cells from the end; the one detour pass resets the countdown to full size, and the second stretch carries the wall the rest of the way.
The numbers
Meetinglog₂ of the countdownlog₂ of the distance
0205.8197
4199.8193
8193.8189
12187.8185
16181.8181
20175.8177
24169.8173
28163.8169
32157.8165
36151.8161
40145.8157
44139.8153
48133.8149
52127.8145
56121.8141
60115.8137
64109.8133
68103.8129
7297.8125
7691.8121
8085.8117
8479.8113
8873.8109
9267.8105
9661.8101
100203.297
104197.293
108191.289
112185.285
116179.281
120173.277
124167.273
128161.269
132155.265
136149.261
140143.257
144137.253
148131.249
152125.245
156119.241
160113.237
164107.233
168101.229
17295.225
17689.221
18083.217
18477.213
18871.29
19265.25
19659.21

How the odds of a close approach fall

2⁰2⁻¹⁰2⁻²⁰2⁻³⁰3456789101112halvings from the full width to the closest meeting, at leastshare of statesall two-marker statesthe machine's own
All two-marker states (gap, a marker anywhere, the end marker) The ones the machine reaches (the marker just past half the width)
A billion random states of each kind, about 2⁴⁸ cells wide, run under the mark rules to the next clean tape; the share is out of each billion. Each extra halving costs both about 2.5 binary digits of odds, at every width tried from 2²⁴ to 2⁴⁸. For a single segment from a random two-marker state the odds can also be computed exactly, by following every binary branch to 46 digits: they match a count of all 6.4 billion states 2¹⁷ to 2¹⁸ cells wide, and fall exactly 10 binary digits per 4 halvings, the price of one pass of the plain loop. A halt on a tape of width W needs about log₂W halvings, so with 2.5 digits per halving a family needs more than 2.5 free numbers to keep producing candidates, and more than 17/6 once the lock forces the costlier patterns. The two-marker states have two, the machine's own tapes one.
The numbers
h at leastAll two-marker states, of 10⁹The machine's own, of 10⁹
362,700,051 (2-4.0)25,243,656 (2-5.3)
42,513,659 (2-8.6)86,074 (2-13.5)
5325,335 (2-11.6)15,466 (2-16.0)
686,407 (2-13.5)1,400 (2-19.4)
712,622 (2-16.3)229 (2-22.1)
83,939 (2-17.9)82 (2-23.5)
9306 (2-21.6)18 (2-25.7)
1092 (2-23.4)6 (2-27.3)
1114 (2-26.1)none
123 (2-28.3)none

Each return makes the machine's states more random

2⁻⁶2⁻¹⁰2⁻¹⁴2⁻¹⁸2⁻²²1st2nd3rd4th5th6th7th8th9thsegment of the cycle (between returns to a two-marker state)odds of coming within 2⁻⁴never (proved)a random two-marker statethe machine's own
Cycles from random two-marker states (5 × 10⁷) Cycles from the machine's own clean tapes (2 × 10⁸)
A cycle is a chain of segments, each from one two-marker state to the next or to the clean tape; about a third of segments end in another two-marker state. Shown: among cycles that reach a given segment, the share in which that segment's closest meeting with the end is within 2⁻⁴ of the width. The machine's first two-marker state always lies on the line E = 2m + 7 and its second on one of two lines, so its early segments are tame; only after six or seven returns do its odds catch up with a random state's.
The numbers
SegmentRandom two-marker statesThe machine's own
1st88,116 of 50,000,000 (2-9.1)0 of 200,000,000 (proved never)
2nd24,916 of 17,193,973 (2-9.4)28 of 74,988,389 (2-21.4)
3rd8,588 of 5,814,194 (2-9.4)7,527 of 27,948,937 (2-11.9)
4th2,736 of 1,962,642 (2-9.5)6,152 of 9,161,333 (2-10.5)
5th917 of 663,576 (2-9.5)1,952 of 3,218,753 (2-10.7)
6th313 of 224,867 (2-9.5)882 of 1,090,740 (2-10.3)
7th117 of 75,894 (2-9.3)406 of 380,911 (2-9.9)
8th49 of 25,542 (2-9.0)192 of 125,773 (2-9.4)
9th14 of 8,733 (2-9.3)89 of 42,950 (2-8.9)

What is established, and how firmly

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.

The ledger

GradeStatementWhat it saysHow it was established
From the rule table to the marks
provedThe mark rulesEvery 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.
provedOne round of the machine is one round of the mark modelFrom 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.
checkedThe rules reproduce the machineEvery 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.
provedHow the machine can haltD 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.
provedA halt needs a contactThe 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.
provedEvery halt starts at a two-marker stateA 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
provedOne pass divides the two countdowns exactlyFrom 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.)
provedL is never 0 and at most 280EL ≡ 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.
provedLeaving the loop is shortFrom 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).
provedThe exact end of the loopA 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.
provedThe extra-wall loopsWith 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.
provedThe rules alone allow a haltHand-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.
checkedTwo-marker runs have no shared lockA 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
checkedRoute ceilingsFor 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.
checkedExact candidates: noneFor 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
checkedNo clean tape below 2⁶⁵ haltsEvery 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.
provedA halt needs an open clean tape, and past a loop entry an open pass startIf 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).
checkedThe 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
measuredLate entries need the extra-wall loopWithout 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.
measuredThe pricesEach 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).
measuredThe machine's lines are not specialIts 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.
heuristicOdds 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.

The chain of reductions

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.

rests on the step above
rests on the step above
rests on the step above
rests on the step above
rests on the step above
rests on the step above
rests on the step above

The theorem about the end of the loop, in full

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.

The closing table

R at the last pass startL must beTrailing zeros of L3 log₂R − 2 log₂|L|minRounds to the close
210 mod 141−1.002
410 mod 1412.002
824 mod 563−0.173
16192 mod 22452.005
24416 mod 44853.759
32192 mod 4486−0.178
48640 mod 89670.7511
64640 mod 89672.0010
176640 mod 89676.3813

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

Ways in, worked through

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.

What each computation checks

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.

Where the steps go

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.