Two oscillators of the rule B37/S2378 that Conway's rule does not sustain

Lax834858.Oscillators · concepts/Lax834858/Oscillators.lean · lax-834858

proven

Loading review…

Sign in with ORCID

Community review

Flags

Each flag is tied to a public ORCID identity and explains why this concept may be incorrect.

No flags have been submitted.

    Community review

    Flag this concept

    State precisely what appears incorrect. This explanation will be public under your ORCID name.

    No source line selected.

    Natural Language Statement

    Theorem

    The outer-totalistic rule B37/S2378B37/S2378 (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 4×44 × 4 box under Conway's B3/S23B3/S23 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 decidedecide: 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
    1 concept
    100%
    Proven claimThis concept
    Evidence

    This concept declares 4 statements. Each proof establishes one of them relative to its assumptions.

    3 p10_period_minimal proven

    Lean source view on GitHub

    1import Mathlib.Logic.Function.Iterate
    2import Mathlib.Data.List.Basic
    3
    4/-!
    5---
    6title: Two oscillators of the rule B37/S2378 that Conway's rule does not sustain
    7type: theorem
    8---
    9The outer-totalistic rule `B37/S2378` (a dead cell is born with 3 or 7 live
    10neighbours; a live cell survives with 2, 3, 7 or 8) admits two oscillators that an
    11exhaustive census of the `4 × 4` box under Conway's `B3/S23` does not produce: one of
    12period 10 with 11 live cells, and one of period 32 with 13. Both are exhibited here
    13as 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
    15after no fewer, the period-32 pattern returns after thirty-two, and under Conway's
    16rule the first pattern does not return to itself within those ten generations. The
    17boards carry a margin wide enough that no phase touches the border, so each statement
    18is also a statement about the pattern on the infinite plane.
    19-/
    20
    21namespace Lax834858.Oscillators
    22
    23/-- A board: a list of rows of cells; `true` is alive. Outside the list everything is
    24dead, so a pattern that never reaches the border evolves as it would on the plane. -/
    25abbrev Board := List (List Bool)
    26
    27/-- The cell at `(y, x)`; out of range it is dead. -/
    28def 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)`. -/
    31def 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
    39set `survive`, on a board of fixed size. -/
    40def 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
    47with 2, 3, 7 or 8. -/
    48def houseStep : Board → Board := step [3, 7] [2, 3, 7, 8]
    49
    50/-- Conway's `B3/S23`. -/
    51def 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
    54enough that no phase of the cycle reaches the border. -/
    55def 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. -/
    71def 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. -/
    94axiom p10_period : houseStep^[10] p10 = p10
    95
    96/-- Ten is its exact period: no smaller positive number of generations works. -/
    97axiom 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. -/
    100axiom p32_period : houseStep^[32] p32 = p32
    101
    102/-- Conway's rule does not sustain `p10`: under `B3/S23` it does not return to itself
    103within ten generations. -/
    104axiom p10_not_conway : ∀ k ∈ [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], conwayStep^[k] p10 ≠ p10
    105
    106end Lax834858.Oscillators
    107
    Show ProofShow ProofShow ProofShow Proof
    Builds on

    none

    Used by

    none

    From Mathlib

    Discussion

    Ask a question or add context. Endorsements and structured flags are kept in the review panel above.

    Loading discussion…