Tier A Kernel-Checked Lower Bound 7,340,048 <= R
ProvedReversibleCA.R_ge_7340048There exist at least 7,340,048 pairwise distinct reversible binary cellular automata on the Moore neighborhood. The explicit numbering satisfies and is injective for all , fully kernel-checked in Lean 4.
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
def nonCtr : List Nbhd := [(0, 0), (0, 1), (0, 2), (1, 0), (1, 2), (2, 0), (2, 1), (2, 2)]
def trivRules : List LocalRule :=
nonCtr.flatMap (fun u => [trivialRule u false, trivialRule u true])
def dflt : LocalRule := trivialRule (0, 0) false
def isCtr (t : Nbhd) : Bool := t.1.val == 1 && t.2.val == 1
def ctr : Nbhd := (1, 1)
def flipRule (mark : (Nbhd → Bool) → Bool) : LocalRule :=
fun x => Bool.xor (x ctr) (mark x)
def codeOf (b0 b1 b2 b3 b4 b5 b6 b7 : Bool) : Nat :=
b0.toNat + 2 * b1.toNat + 4 * b2.toNat + 8 * b3.toNat +
16 * b4.toNat + 32 * b5.toNat + 64 * b6.toNat + 128 * b7.toNat
def code (x : Nbhd → Bool) : Nat :=
codeOf (x (0, 0)) (x (0, 1)) (x (0, 2)) (x (1, 0)) (x (1, 2)) (x (2, 0)) (x (2, 1)) (x (2, 2))
def bitIdx (t : Nbhd) : Nat := 3 * t.1.val + t.2.val - (if 3 * t.1.val + t.2.val > 4 then 1 else 0)
def allNbhd : List Nbhd :=
[(0, 0), (0, 1), (0, 2), (1, 0), (1, 1), (1, 2), (2, 0), (2, 1), (2, 2)]
def subIdx (t v : Nbhd) : Option Nbhd :=
if h1 : v.1.val ≤ t.1.val + 1 ∧ t.1.val + 1 - v.1.val < 3 then
if h2 : v.2.val ≤ t.2.val + 1 ∧ t.2.val + 1 - v.2.val < 3 then
some (⟨t.1.val + 1 - v.1.val, h1.2⟩, ⟨t.2.val + 1 - v.2.val, h2.2⟩)
else none
else none
def compatCode (p q : Nat) : Bool :=
allNbhd.all fun v => isCtr v || allNbhd.any fun t =>
!isCtr t && match subIdx t v with
| some t' => !isCtr t' && (p.testBit (bitIdx t) != q.testBit (bitIdx t'))
| none => false
def famTable : List (List Nat) := [
[17, 25, 29, 48, 49, 52, 56, 57, 61, 93, 125, 153, 157, 217, 221, 176, 177, 180],
[17, 25, 29, 48, 49, 52, 56, 57, 60, 61, 93, 125, 157, 217, 221, 92, 216, 220],
[17, 25, 48, 49, 56, 57, 60, 62, 145, 184, 185, 186, 187, 188, 190, 21, 53, 149],
[17, 25, 48, 49, 56, 57, 62, 145, 153, 184, 185, 186, 187, 188, 190, 30, 154, 158],
[12, 28, 29, 60, 61, 93, 124, 125, 136, 137, 140, 152, 156, 157, 221, 168, 169, 172],
[12, 28, 44, 60, 136, 140, 152, 155, 156, 184, 185, 186, 187, 188, 190, 27, 58, 59],
[12, 28, 44, 136, 140, 152, 153, 155, 156, 184, 185, 186, 187, 188, 190, 13, 45, 141],
[12, 28, 29, 61, 93, 124, 125, 136, 137, 140, 152, 153, 156, 157, 221, 89, 120, 121],
[65, 67, 68, 69, 70, 71, 99, 100, 103, 115, 119, 195, 211, 227, 243, 196, 197, 228],
[65, 67, 68, 69, 70, 71, 99, 100, 102, 103, 115, 119, 211, 227, 243, 114, 210, 242],
[65, 67, 68, 69, 70, 71, 110, 193, 195, 198, 199, 206, 207, 230, 238, 106, 202, 234],
[65, 67, 68, 69, 70, 71, 102, 110, 193, 198, 199, 206, 207, 230, 238, 97, 101, 225],
[34, 98, 99, 102, 103, 115, 118, 119, 130, 131, 162, 194, 226, 227, 243, 134, 135, 166],
[34, 38, 98, 102, 130, 162, 194, 198, 199, 203, 206, 207, 226, 230, 238, 75, 78, 79],
[34, 38, 98, 130, 162, 194, 195, 198, 199, 203, 206, 207, 226, 230, 238, 35, 39, 163],
[34, 98, 99, 103, 115, 118, 119, 130, 131, 162, 194, 195, 226, 227, 243, 83, 86, 87]]
def famCode (g k : Nat) : Nat := (famTable.getD g []).getD k 0
def symS (g r : Nat) (p : Nat) : Bool := (List.range 18).any (fun k => r.testBit k && famCode g k == p)
def symRule (g r : Nat) : LocalRule := flipRule (fun x => symS g r (code x))
def K : Nat := 229376
def NA : Nat := 3670016
def NTotal : Nat := 7340048
def G (i : Nat) : LocalRule :=
if i < NA then symRule (i / K) (32768 + i % K)
else if i < 2 * NA then (fun x => ! symRule ((i - NA) / K) (32768 + (i - NA) % K) x)
else trivRules.getD (i - 2 * NA) dflt
theorem R_ge_7340048 :
(∀ i, i < 7340048 → IsReversible (G i)) ∧
(∀ i j, i < 7340048 → j < 7340048 → G i = G j → i = j) := by sorry
end ReversibleCAHuman review
Confirmed by the mission captain (proposal self-audit).