Non-Triviality of Rule f_star
ProvedReversibleCA.f_star_nontrivialThe conserved-landscape rule is strictly distinct from all 18 trivial single-cell shift and complemented shift rules.
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 trivialRule (u : Nbhd) (e : Bool) : LocalRule :=
fun nbhd => if e then ! (nbhd u) else nbhd u
def is_p_star (nb : Nbhd → Bool) : Bool :=
nb (0, 1) && nb (2, 0) &&
! nb (0, 0) && ! nb (0, 2) && ! nb (1, 0) && ! nb (1, 2) && ! nb (2, 1) && ! nb (2, 2)
def f_star : LocalRule :=
fun nb => Bool.xor (nb (1, 1)) (is_p_star nb)
theorem f_star_nontrivial (u : Nbhd) (e : Bool) : f_star ≠ trivialRule u e := by sorry
end ReversibleCAHuman review
Confirmed by the mission captain (proposal self-audit).