Reversibility of the 18 Trivial Rules
ProvedReversibleCA.trivialRule_reversibleEach of the 18 trivial single-cell rules (comprising the 9 pure spatial shifts and their 9 point-wise complements on the Moore neighborhood) generates a bijective (reversible) global map .
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
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)
def trivialRule (u : Nbhd) (e : Bool) : LocalRule :=
fun nbhd => if e then ! (nbhd u) else nbhd u
theorem trivialRule_reversible (u : Nbhd) (e : Bool) : IsReversible (trivialRule u e) := by sorry
end ReversibleCAHuman review
Confirmed by the mission captain (proposal self-audit).