/-! # MAZE.AI — de kern, bewezen (Lean 4, geen mathlib) De trit als register van één winding, het adres als lijst trits (meest significante eerst), de waarde in gebalanceerd drietallig, en de stellingen die het essay *Where Computation Comes From* (§2, §5.1) als eigenschappen beweert: bereik, uniciteit, en truncatie (idempotent, prefix-stabiel). Alles hieronder wordt door Lean gecontroleerd; niets is een aanname behalve de definities. -/ /-- Eén winding tegen zijn referentie: boven, erop, eronder. -/ inductive Trit where | neg | nul | pos deriving DecidableEq, Repr, Inhabited namespace Trit /-- De waarde van een trit: −1, 0, +1. -/ def toInt : Trit → Int | neg => -1 | nul => 0 | pos => 1 theorem toInt_bound (t : Trit) : -1 ≤ t.toInt ∧ t.toInt ≤ 1 := by cases t <;> simp [toInt] /-- Spiegelen = negatie (essay §2: "negation is a mirror"). -/ def spiegel : Trit → Trit | neg => pos | nul => nul | pos => neg theorem spiegel_toInt (t : Trit) : t.spiegel.toInt = - t.toInt := by cases t <;> simp [spiegel, toInt] theorem spiegel_spiegel (t : Trit) : t.spiegel.spiegel = t := by cases t <;> rfl end Trit /-- Een adres: een pad van windingen, meest significante trit eerst. -/ abbrev Adres := List Trit namespace Adres /-- Het bereik van n trits: (3ⁿ − 1)/2 aan weerszijden van nul. -/ def bereik (n : Nat) : Int := ((3 : Int) ^ n - 1) / 2 /-- De waarde in gebalanceerd drietallig (Horner, meest significante eerst). -/ def waarde : Adres → Int | [] => 0 | t :: rest => t.toInt * 3 ^ rest.length + waarde rest /-- Truncatie tot diepte n: de eerste n trits. -/ def trunc (n : Nat) (a : Adres) : Adres := a.take n /-- Stelling (truncatie is idempotent): tweemaal afkappen is eenmaal afkappen. -/ theorem trunc_idem (n : Nat) (a : Adres) : trunc n (trunc n a) = trunc n a := by simp [trunc, List.take_take] /-- Stelling (prefix-stabiel): het adres op diepte n is de truncatie van élk dieper adres dat het verlengt. "Deeper knowledge refines an address; it never replaces it." -/ theorem trunc_verlenging (a b : Adres) : trunc a.length (a ++ b) = a := by simp [trunc] /-- Stelling: verdieping verandert de prefix niet, op welke diepte ook wordt afgekapt. -/ theorem trunc_prefix (n : Nat) (a b : Adres) (h : n ≤ a.length) : trunc n (a ++ b) = trunc n a := by simp [trunc, List.take_append_of_le_length h] /-- Stelling (spiegelen = negatie op het hele adres). -/ def spiegel (a : Adres) : Adres := a.map Trit.spiegel theorem waarde_spiegel (a : Adres) : waarde (spiegel a) = - waarde a := by induction a with | nil => simp [spiegel, waarde] | cons t rest ih => simp only [spiegel, List.map_cons, waarde, List.length_map, Trit.spiegel_toInt] at * rw [ih] generalize (3 : Int) ^ rest.length = p cases t <;> simp [Trit.toInt] <;> omega /-- 3ⁿ is positief. -/ theorem three_pow_pos (n : Nat) : (0 : Int) < 3 ^ n := by induction n with | zero => simp | succ k ih => rw [Int.pow_succ]; omega /-- Hulp: 2 · bereik n = 3ⁿ − 1 (3ⁿ is oneven). -/ theorem two_mul_bereik (n : Nat) : 2 * bereik n = (3 : Int) ^ n - 1 := by unfold bereik have h : ((3 : Int) ^ n - 1) % 2 = 0 := by induction n with | zero => simp | succ k ih => rw [Int.pow_succ]; omega omega /-- Stelling (bereik): |waarde a| ≤ (3^|a| − 1)/2 — elke lijst van n trits ligt binnen het bereik van n. -/ theorem waarde_bereik (a : Adres) : - bereik a.length ≤ waarde a ∧ waarde a ≤ bereik a.length := by induction a with | nil => simp [waarde, bereik] | cons t rest ih => have hb := two_mul_bereik rest.length have hb' := two_mul_bereik (rest.length + 1) have ht := Trit.toInt_bound t have hp := three_pow_pos rest.length simp only [waarde, List.length_cons] rw [Int.pow_succ] at hb' generalize hpdef : (3 : Int) ^ rest.length = p at * cases t <;> simp [Trit.toInt] <;> omega end Adres namespace Adres /-- Stelling (uniciteit): twee adressen van gelijke diepte met dezelfde waarde zijn hetzelfde adres. Gebalanceerd drietallig stelt elk getal maar op één manier voor — het adres ís de identiteit. -/ theorem waarde_inj (a b : Adres) (hl : a.length = b.length) (h : waarde a = waarde b) : a = b := by induction a generalizing b with | nil => cases b with | nil => rfl | cons _ _ => simp at hl | cons t rest ih => cases b with | nil => simp at hl | cons u rest' => simp only [List.length_cons] at hl have hl' : rest.length = rest'.length := by omega simp only [waarde] at h rw [← hl'] at h have ha := waarde_bereik rest have hb := waarde_bereik rest' rw [← hl'] at hb have h2 := two_mul_bereik rest.length have hp := three_pow_pos rest.length generalize (3 : Int) ^ rest.length = p at * cases t <;> cases u <;> simp [Trit.toInt] at h <;> first | (exfalso; omega) | (rw [ih rest' hl' (by omega)]) /-- Het adres van een getal op diepte n: meest significante trit eerst, per stap de trit die het getal binnen het bereik van de rest brengt. Dit is "the address is calculated from the identity itself". -/ def ofInt : Nat → Int → Adres | 0, _ => [] | n + 1, v => let t : Trit := if v > bereik n then Trit.pos else if v < - bereik n then Trit.neg else Trit.nul t :: ofInt n (v - t.toInt * 3 ^ n) theorem ofInt_length (n : Nat) (v : Int) : (ofInt n v).length = n := by induction n generalizing v with | zero => rfl | succ k ih => simp [ofInt, ih] /-- Stelling (terugkeer): binnen het bereik van n geeft het berekende adres het getal exact terug. Samen met uniciteit: adres ↔ getal is een bijectie op het bereik — geen tabel, geen instantie. -/ theorem waarde_ofInt (n : Nat) (v : Int) (h : - bereik n ≤ v ∧ v ≤ bereik n) : waarde (ofInt n v) = v := by induction n generalizing v with | zero => simp [bereik] at h; simp [ofInt, waarde]; omega | succ k ih => have h2 := two_mul_bereik k have h3 := two_mul_bereik (k + 1) have hp := three_pow_pos k rw [Int.pow_succ] at h3 simp only [ofInt, waarde, ofInt_length] generalize hpdef : (3 : Int) ^ k = p at * split · simp [Trit.toInt]; rw [ih (v - p) (by omega)]; omega · split · simp [Trit.toInt]; rw [ih (v + p) (by omega)]; omega · simp [Trit.toInt]; rw [ih v (by omega)] /-- Prefix-doorgang (essay §6.1): de klasse van een adres is zijn truncatie tot diepte m. -/ def klasse (m : Nat) (a : Adres) : Adres := trunc m a /-- Stelling: de klasse-indeling is een partitie — twee adressen delen een klasse precies als hun truncaties gelijk zijn; en verdieping verandert de klasse niet (m ≤ diepte). -/ theorem klasse_stabiel (m : Nat) (a b : Adres) (h : m ≤ a.length) : klasse m (a ++ b) = klasse m a := trunc_prefix m a b h theorem klasse_length (m : Nat) (a : Adres) : (klasse m a).length ≤ m := by simp [klasse, trunc, List.length_take]; omega end Adres /-- Het trit-register voor gewichten (essay §7, BitNet b1.58): drempel γ/2, uitkomst per type in {−1,0,+1}. Nul is exact nul — geen afronding, geen tekenbit. -/ def kwantiseer (w γ : Int) : Trit := if 2 * w > γ then Trit.pos else if 2 * w < - γ then Trit.neg else Trit.nul theorem kwantiseer_nul (γ : Int) (h : 0 ≤ γ) : kwantiseer 0 γ = Trit.nul := by unfold kwantiseer have hγ : ¬ (γ < 0) := by omega simp [hγ] /-- Stelling (symmetrie van het register): het gewicht spiegelen spiegelt de trit — voor elke niet-negatieve drempel. -/ theorem kwantiseer_spiegel (w γ : Int) (hγ : 0 ≤ γ) : kwantiseer (-w) γ = (kwantiseer w γ).spiegel := by unfold kwantiseer by_cases h1 : 2 * w > γ · have h2 : ¬ (2 * (-w) > γ) := by omega have h3 : 2 * (-w) < -γ := by omega simp [h1, h2, h3, Trit.spiegel] · by_cases h4 : 2 * w < -γ · have h5 : 2 * (-w) > γ := by omega simp [h1, h4, h5, Trit.spiegel] · have h6 : ¬ (2 * (-w) > γ) := by omega have h7 : ¬ (2 * (-w) < -γ) := by omega simp [h1, h4, h6, h7, Trit.spiegel]