Finite Closed Turing Supports and Pointed Renaming
DefinitionMonodromy_FiniteSupportDefines finite control supports containing the distinguished initial state and closed under every transition target. Restricts Turing machines to those supports and renames finite pointed alphabets and controls by Fin types while preserving the blank symbol, initial control, complete configurations and execution.
-- Generated by Lean-fact skeleton subtraction; original source is frozen in imports/monodromy/source.
module
public import Mathlib.Computability.TuringMachine.PostTuringMachine
public import Mathlib.Data.Fintype.EquivFin
public import Mathlib.Data.Fintype.Sets
@[expose] public section
/-!
# Finite support and pointed renaming
A finite support includes the initial label and every reachable transition
target. Restricting to that pointed finite carrier preserves the entire
configuration and execution. Pointed finite enumeration then preserves both
the blank symbol and the distinguished initial control label.
-/
@[expose] public section
namespace Monodromy.FiniteSupport
open Turing
variable {Γ Q : Type*} [Inhabited Γ] [Inhabited Q]
/-- A finite, transition-closed collection of control labels. -/
structure Support (source : TM0.Machine Γ Q) where
labels : Finset Q
closed : TM0.Supports source (labels : Set Q)
namespace Support
variable {source : TM0.Machine Γ Q} (support : Support source)
/-- The finite control retains the source's distinguished initial label. -/
def Control : Type _ := {label : Q // label ∈ support.labels}
instance : Fintype support.Control := by unfold Control; infer_instance
instance : Inhabited support.Control := ⟨⟨default, support.closed.1⟩⟩
/-- Each transition target is already certified to belong to the finite control. -/
def restrict : TM0.Machine Γ support.Control := fun label symbol =>
match transition : source label.val symbol with
| none => none
| some (target, instruction) =>
some (⟨target, support.closed.2 transition label.property⟩, instruction)
/-- Forget only the finite-support certificate; the complete tape is retained. -/
def embed (configuration : TM0.Cfg Γ support.Control) : TM0.Cfg Γ Q :=
⟨configuration.q.val, configuration.Tape⟩
end Support
end Monodromy.FiniteSupport
/-! Pointed finite enumeration preserves the blank symbol, initial label, and complete execution. -/
namespace Monodromy.FiniteRenaming
open Turing
section Enumeration
variable (α : Type*) [Fintype α] [Inhabited α]
/-- Enumerate any finite pointed type with its distinguished element at zero. -/
noncomputable def enumeration : α ≃ Fin (Fintype.card α) :=
(Fintype.equivFin α).trans (Equiv.swap ((Fintype.equivFin α) default) 0)
@[simp] theorem enumeration_default : enumeration α default = 0 := by
simp [enumeration]
noncomputable def toFin : PointedMap α (Fin (Fintype.card α)) :=
⟨enumeration α, enumeration_default α⟩
noncomputable def fromFin : PointedMap (Fin (Fintype.card α)) α :=
⟨(enumeration α).symm, by
apply (enumeration α).injective
simp⟩
end Enumeration
section Machine
variable {Γ Q : Type} [Fintype Γ] [Inhabited Γ] [Fintype Q] [Inhabited Q]
/-- Renaming preserves both the blank symbol and initial control state. -/
noncomputable def machine (source : TM0.Machine Γ Q) :
TM0.Machine (Fin (Fintype.card Γ)) (Fin (Fintype.card Q)) :=
source.map (toFin Γ) (fromFin Γ) (toFin Q) (fromFin Q)
noncomputable def configuration (source : TM0.Cfg Γ Q) :
TM0.Cfg (Fin (Fintype.card Γ)) (Fin (Fintype.card Q)) :=
source.map (toFin Γ) (toFin Q)
end Machine
open Turing
variable {Γ Q : Type} [Fintype Γ] [Inhabited Γ] [Fintype Q] [Inhabited Q]
end Monodromy.FiniteRenaming
Read-back
What the Lean code literally says, in plain math · OpenAI Codex (independent agent)
For arbitrary inhabited symbol and control types and a Turing machine with transitions on a control and a read symbol, a support consists of a finite set containing the distinguished default control and closed under all targets of defined transitions whose source control lies in . Its restricted control type is the subtype , equipped with a finite enumeration type structure and distinguished element given by the original default control with its membership certificate. The restricted machine on returns no transition exactly when does so at the underlying control and read symbol; if returns target and an instruction, it returns that same instruction and target together with the closure certificate . A configuration embedding removes only the membership certificate on the control and retains the complete tape. Separately, for every finite inhabited type , an equivalence is defined by taking the supplied finite equivalence and then swapping its image of the distinguished element with ; the bundle asserts . It defines pointed forward and inverse maps from and . For finite inhabited , the renamed machine uses these forward and inverse pointed maps to convert control labels, read symbols and written symbols to the finite index types, and the renamed configuration maps its control and every tape symbol by the corresponding forward map. The pointed maps preserve the distinguished symbol and control by their defining proofs; neither nor needs a finite-type structure in the earlier support construction, while both do in the renaming construction, and every inhabited finite carrier has positive cardinality.
Confirmed by the mission captain (proposal self-audit).