Two oscillators of the rule B37/S2378 that Conway's rule does not sustain
Lax834858.Oscillators · concepts/Lax834858/Oscillators.lean · lax-834858
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Theorem
The outer-totalistic rule (a dead cell is born with 3 or 7 live neighbours; a live cell survives with 2, 3, 7 or 8) admits two oscillators that an exhaustive census of the box under Conway's does not produce: one of period 10 with 11 live cells, and one of period 32 with 13. Both are exhibited here as explicit finite boards, and every statement is a finite computation closed by : the period-10 pattern returns to itself after exactly ten generations and after no fewer, the period-32 pattern returns after thirty-two, and under Conway's rule the first pattern does not return to itself within those ten generations. The boards carry a margin wide enough that no phase touches the border, so each statement is also a statement about the pattern on the infinite plane.
Concept map
Evidence
Lean source view on GitHub
| 1 | import Mathlib.Logic.Function.Iterate |
| 2 | import Mathlib.Data.List.Basic |
| 3 | |
| 4 | /-! |
| 5 | --- |
| 6 | title: Two oscillators of the rule B37/S2378 that Conway's rule does not sustain |
| 7 | type: theorem |
| 8 | --- |
| 9 | The outer-totalistic rule `B37/S2378` (a dead cell is born with 3 or 7 live |
| 10 | neighbours; a live cell survives with 2, 3, 7 or 8) admits two oscillators that an |
| 11 | exhaustive census of the `4 × 4` box under Conway's `B3/S23` does not produce: one of |
| 12 | period 10 with 11 live cells, and one of period 32 with 13. Both are exhibited here |
| 13 | as explicit finite boards, and every statement is a finite computation closed by |
| 14 | `decide`: the period-10 pattern returns to itself after exactly ten generations and |
| 15 | after no fewer, the period-32 pattern returns after thirty-two, and under Conway's |
| 16 | rule the first pattern does not return to itself within those ten generations. The |
| 17 | boards carry a margin wide enough that no phase touches the border, so each statement |
| 18 | is also a statement about the pattern on the infinite plane. |
| 19 | -/ |
| 20 | |
| 21 | namespace Lax834858.Oscillators |
| 22 | |
| 23 | /-- A board: a list of rows of cells; `true` is alive. Outside the list everything is |
| 24 | dead, so a pattern that never reaches the border evolves as it would on the plane. -/ |
| 25 | abbrev Board := List (List Bool) |
| 26 | |
| 27 | /-- The cell at `(y, x)`; out of range it is dead. -/ |
| 28 | def get (b : Board) (y x : Nat) : Bool := (b.getD y []).getD x false |
| 29 | |
| 30 | /-- The number of live cells among the eight neighbours of `(y, x)`. -/ |
| 31 | def neighbours (b : Board) (y x : Nat) : Nat := |
| 32 | let idx : List (Int × Int) := [(-1,-1),(-1,0),(-1,1),(0,-1),(0,1),(1,-1),(1,0),(1,1)] |
| 33 | idx.foldl (fun acc p => |
| 34 | let yy : Int := (y : Int) + p.1 |
| 35 | let xx : Int := (x : Int) + p.2 |
| 36 | if 0 ≤ yy ∧ 0 ≤ xx then acc + (if get b yy.toNat xx.toNat then 1 else 0) else acc) 0 |
| 37 | |
| 38 | /-- One generation of the outer-totalistic rule with birth set `birth` and survival |
| 39 | set `survive`, on a board of fixed size. -/ |
| 40 | def step (birth survive : List Nat) (b : Board) : Board := |
| 41 | (List.range b.length).map fun y => |
| 42 | (List.range ((b.getD 0 []).length)).map fun x => |
| 43 | let n := neighbours b y x |
| 44 | if get b y x then survive.contains n else birth.contains n |
| 45 | |
| 46 | /-- `B37/S2378`: a dead cell is born with 3 or 7 live neighbours, a live cell survives |
| 47 | with 2, 3, 7 or 8. -/ |
| 48 | def houseStep : Board → Board := step [3, 7] [2, 3, 7, 8] |
| 49 | |
| 50 | /-- Conway's `B3/S23`. -/ |
| 51 | def conwayStep : Board → Board := step [3] [2, 3] |
| 52 | |
| 53 | /-- The period-10 oscillator, 11 live cells, on a `13 × 14` board: the margin is wide |
| 54 | enough that no phase of the cycle reaches the border. -/ |
| 55 | def p10 : Board := |
| 56 | [[false,false,false,false,false,false,false,false,false,false,false,false,false,false], |
| 57 | [false,false,false,false,false,false,false,false,false,false,false,false,false,false], |
| 58 | [false,false,false,false,false,false,false,false,false,false,false,false,false,false], |
| 59 | [false,false,false,false,false,false,false,false,false,false,false,false,false,false], |
| 60 | [false,false,false,false,false,true ,false,false,true ,false,false,false,false,false], |
| 61 | [false,false,false,false,true ,false,false,false,true ,false,false,false,false,false], |
| 62 | [false,false,false,false,true ,false,true ,false,false,true ,false,false,false,false], |
| 63 | [false,false,false,false,true ,false,false,false,true ,false,false,false,false,false], |
| 64 | [false,false,false,false,false,true ,false,false,true ,false,false,false,false,false], |
| 65 | [false,false,false,false,false,false,false,false,false,false,false,false,false,false], |
| 66 | [false,false,false,false,false,false,false,false,false,false,false,false,false,false], |
| 67 | [false,false,false,false,false,false,false,false,false,false,false,false,false,false], |
| 68 | [false,false,false,false,false,false,false,false,false,false,false,false,false,false]] |
| 69 | |
| 70 | /-- The period-32 oscillator, 13 live cells in the phase shown, on an `18 × 20` board. -/ |
| 71 | def p32 : Board := |
| 72 | [[false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false], |
| 73 | [false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false], |
| 74 | [false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false], |
| 75 | [false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false], |
| 76 | [false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false], |
| 77 | [false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false], |
| 78 | [false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false], |
| 79 | [false,false,false,false,false,false,false,false,false,true ,true ,false,false,false,false,false,false,false,false,false], |
| 80 | [false,false,false,false,false,false,false,false,true ,false,false,true ,true ,false,false,false,false,false,false,false], |
| 81 | [false,false,false,false,false,false,false,true ,false,false,false,true ,true ,false,false,false,false,false,false,false], |
| 82 | [false,false,false,false,false,false,false,false,true ,true ,true ,true ,true ,false,false,false,false,false,false,false], |
| 83 | [false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false], |
| 84 | [false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false], |
| 85 | [false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false], |
| 86 | [false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false], |
| 87 | [false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false], |
| 88 | [false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false], |
| 89 | [false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false]] |
| 90 | |
| 91 | |
| 92 | |
| 93 | /-- Under `B37/S2378` the pattern `p10` returns to itself after ten generations. -/ |
| 94 | axiom p10_period : houseStep^[10] p10 = p10 |
| 95 | |
| 96 | /-- Ten is its exact period: no smaller positive number of generations works. -/ |
| 97 | axiom p10_period_minimal : ∀ k ∈ [1, 2, 3, 4, 5, 6, 7, 8, 9], houseStep^[k] p10 ≠ p10 |
| 98 | |
| 99 | /-- Under `B37/S2378` the pattern `p32` returns to itself after thirty-two generations. -/ |
| 100 | axiom p32_period : houseStep^[32] p32 = p32 |
| 101 | |
| 102 | /-- Conway's rule does not sustain `p10`: under `B3/S23` it does not return to itself |
| 103 | within ten generations. -/ |
| 104 | axiom p10_not_conway : ∀ k ∈ [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], conwayStep^[k] p10 ≠ p10 |
| 105 | |
| 106 | end Lax834858.Oscillators |
| 107 |
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments