A glider

What we look at

A localised structure is a small pattern on a calm background that, after some number of steps, reappears identical, possibly shifted. If it moves, it is called a glider.

This one comes from a hidden three-state world, in the blackbox run on seed 11. The agent found it while the scripted reference only searched periods of at most 8 steps. Its period is 16: it was out of the reference’s reach.

Reading the figure step by step

1. The background is state 0, in white. It is calm: a 000 neighbourhood gives 0, so nothing appears out of nowhere.
2. States 1 and 2 are drawn in two ink tones.
3. At the start, the pattern is the block 1110221.
4. For 16 steps it changes shape.
5. At step 16 it has exactly its starting shape again, 8 cells further right. It comes back at no earlier step.
6. So it moves 8 cells every 16 steps: a velocity of 1/2 cell per step. The figure follows it for 48 steps, three periods.

The world’s rule

The table has 27 entries, one per neighbourhood of three cells, in the order of the code 9 × left + 3 × centre + right:

0, 0, 0, 2, 1, 1, 2, 2, 0, 2, 2, 2, 2, 1, 1, 2, 2, 0, 0, 0, 0, 2, 1, 1, 1, 1, 2

The Lean statement

theorem glider : Travels
    (tableCA 3 2 [0, 0, 0, 2, 1, 1, 2, 2, 0,
                  2, 2, 2, 2, 1, 1, 2, 2, 0,
                  0, 0, 0, 2, 1, 1, 1, 1, 2])
    (List.replicate 33 0 ++ [1, 1, 1, 0, 2, 2, 1]
      ++ List.replicate 33 0)
    16 8 := by decide +kernel

• The block is surrounded by 33 background cells on each side, that is 2 × 16 + 1. With this padding nothing wraps around the ring within 16 steps, so the statement on the ring also holds on an infinite line.
• 16 8: after 16 steps, new cell i is old cell i + 8.
• The Lean world reads the same table with a one-cell offset, which adds a slide of one cell to the left at every step, 16 cells over one period. The glider moves 8 cells to the right in the figure’s centred reading: 8 − 16 = −8, hence the shift of 8 in the Lean statement. It is the same motion, read differently.

What it proves

In this world, this block comes back exactly after 16 steps, translated. It is a computation checked by the kernel.

What it does not prove

• That the agent does open-ended discovery. It is a genuine finding for this world, but the agent had read the world’s entire rule in one experiment, then searched blocks with a known method, up to period 16. See A hidden world rebuilt.
• That 16 is the minimal period in the Lean world: the statement only says that the block comes back after 16 steps. The figure and the engine check that it does not come back earlier.