Bound L4: 33,070,982 <= R for Reversible Binary 2D Moore Rules
OpenReversibleCA.R_ge_33070982combinatoricsformal-verification
There exist at least 33,070,982 pairwise distinct reversible binary 2D cellular automata on the Moore neighborhood. The explicit numbering satisfies and is injective for all .
Preamble
import Lean
Formal statement
namespace ReversibleCA
def Coord : Type := Int × Int
def Config : Type := Coord → Bool
def Bijective {α β : Type} (f : α → β) : Prop := (∀ x y, f x = f y → x = y) ∧ (∀ y, ∃ x, f x = y)
def Nbhd : Type := Fin 3 × Fin 3
deriving BEq, DecidableEq
def LocalRule : Type := (Nbhd → Bool) → Bool
instance : Inhabited LocalRule := ⟨fun _ => false⟩
def globalMap (f : LocalRule) (c : Config) : Config :=
fun z => f (fun ⟨i, j⟩ => c (z.1 + (i.val - 1 : Int), z.2 + (j.val - 1 : Int)))
def IsReversible (f : LocalRule) : Prop := Bijective (globalMap f)
opaque G4 (i : Nat) : LocalRule
theorem R_ge_33070982 :
(∀ i, i < 33070982 → IsReversible (G4 i)) ∧
(∀ i j, i < 33070982 → j < 33070982 → G4 i = G4 j → i = j) := by sorry
end ReversibleCASource
R. G. Mir, How many reversible binary cellular automata have the Moore neighbourhood?
Human review
Confirmed by the mission captain (proposal self-audit).