Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

sgl_machine_infrastructure

Definition

by Henry Yuen · Jul 24, 2026 · Mathlib c5ea003 (Lean v4.30.0)

complexity-theoryformalizationturing-machine

A typed-state presentation of the mission’s deterministic multitape Turing machines, together with a finite-state relabeling into Fin states and exact preservation theorems for steps, runs, acceptance, rejection, and stable halting.

Definition code
import Definitions.Def_sipser_gacs_lautemann
import Mathlib.Data.Fintype.EquivFin

namespace SipserGacsLautemann

/-- A version of the mission machine whose finite state type has not yet
been relabeled as an initial segment of the natural numbers. -/
structure TypedMachine (tapes : Nat) (State : Type) where
  start : State
  transition :
    State → (Fin tapes → TapeSymbol) →
      State × (Fin tapes → TapeSymbol × HeadMove)
  result : State → Option Bool

structure TypedConfiguration (tapes : Nat) (State : Type) where
  state : State
  tape : Fin tapes → Tape

def TypedMachine.step {tapes : Nat} {State : Type}
    (machine : TypedMachine tapes State)
    (configuration : TypedConfiguration tapes State) :
    TypedConfiguration tapes State :=
  match machine.result configuration.state with
  | some _ => configuration
  | none =>
      let action :=
        machine.transition configuration.state
          (fun i => (configuration.tape i).head)
      { state := action.1
        tape := fun i =>
          Tape.move
            (Tape.write (configuration.tape i) (action.2 i).1)
            (action.2 i).2 }

def TypedMachine.initialConfiguration {tapes : Nat} {State : Type}
    (machine : TypedMachine tapes State)
    (input : Fin tapes → List Bool) :
    TypedConfiguration tapes State :=
  ⟨machine.start, fun i => Tape.ofBits (input i)⟩

def TypedMachine.run {tapes : Nat} {State : Type}
    (machine : TypedMachine tapes State)
    (input : Fin tapes → List Bool) :
    Nat → TypedConfiguration tapes State
  | 0 => machine.initialConfiguration input
  | steps + 1 => machine.step (machine.run input steps)

noncomputable def TypedMachine.toMachine {tapes : Nat} {State : Type}
    [Fintype State] (machine : TypedMachine tapes State) :
    Machine tapes (Fintype.card State) :=
  let encode := Fintype.equivFin State
  { start := encode machine.start
    transition := fun state symbols =>
      let action := machine.transition (encode.symm state) symbols
      ⟨encode action.1, action.2⟩
    result := fun state => machine.result (encode.symm state) }

noncomputable def TypedConfiguration.encode {tapes : Nat}
    {State : Type} [Fintype State]
    (configuration : TypedConfiguration tapes State) :
    Configuration tapes (Fintype.card State) :=
  ⟨Fintype.equivFin State configuration.state, configuration.tape⟩

theorem TypedMachine.toMachine_result_encode {tapes : Nat}
    {State : Type} [Fintype State]
    (machine : TypedMachine tapes State)
    (configuration : TypedConfiguration tapes State) :
    machine.toMachine.result configuration.encode.state =
      machine.result configuration.state := by
  simp [TypedMachine.toMachine, TypedConfiguration.encode]

theorem TypedMachine.toMachine_step_encode {tapes : Nat}
    {State : Type} [Fintype State]
    (machine : TypedMachine tapes State)
    (configuration : TypedConfiguration tapes State) :
    machine.toMachine.step configuration.encode =
      (machine.step configuration).encode := by
  cases hresult : machine.result configuration.state with
  | some result =>
      unfold Machine.step TypedMachine.step
      rw [machine.toMachine_result_encode configuration, hresult]
  | none =>
      unfold Machine.step TypedMachine.step
      rw [machine.toMachine_result_encode configuration, hresult]
      simp [TypedMachine.toMachine, TypedConfiguration.encode]

theorem TypedMachine.toMachine_initial_encode {tapes : Nat}
    {State : Type} [Fintype State]
    (machine : TypedMachine tapes State)
    (input : Fin tapes → List Bool) :
    SipserGacsLautemann.initialConfiguration machine.toMachine input =
      (machine.initialConfiguration input).encode := by
  simp [SipserGacsLautemann.initialConfiguration,
    TypedMachine.initialConfiguration,
    TypedMachine.toMachine, TypedConfiguration.encode]

theorem TypedMachine.toMachine_run_encode {tapes : Nat}
    {State : Type} [Fintype State]
    (machine : TypedMachine tapes State)
    (input : Fin tapes → List Bool) (steps : Nat) :
    machine.toMachine.run input steps =
      (machine.run input steps).encode := by
  induction steps with
  | zero =>
      exact machine.toMachine_initial_encode input
  | succ steps ih =>
      rw [Machine.run, TypedMachine.run, ih]
      exact machine.toMachine_step_encode (machine.run input steps)

theorem TypedMachine.toMachine_acceptsWithin_iff {tapes : Nat}
    {State : Type} [Fintype State]
    (machine : TypedMachine tapes State)
    (input : Fin tapes → List Bool) (steps : Nat) :
    machine.toMachine.acceptsWithin input steps ↔
      machine.result (machine.run input steps).state = some true := by
  unfold Machine.acceptsWithin
  rw [machine.toMachine_run_encode]
  exact
    ⟨fun h => by
      simpa [TypedConfiguration.encode, TypedMachine.toMachine] using h,
      fun h => by
        simpa [TypedConfiguration.encode, TypedMachine.toMachine] using h⟩

theorem TypedMachine.toMachine_rejectsWithin_iff {tapes : Nat}
    {State : Type} [Fintype State]
    (machine : TypedMachine tapes State)
    (input : Fin tapes → List Bool) (steps : Nat) :
    machine.toMachine.rejectsWithin input steps ↔
      machine.result (machine.run input steps).state = some false := by
  unfold Machine.rejectsWithin
  rw [machine.toMachine_run_encode]
  exact
    ⟨fun h => by
      simpa [TypedConfiguration.encode, TypedMachine.toMachine] using h,
      fun h => by
        simpa [TypedConfiguration.encode, TypedMachine.toMachine] using h⟩

theorem TypedMachine.step_eq_self_of_result_some {tapes : Nat}
    {State : Type} (machine : TypedMachine tapes State)
    (configuration : TypedConfiguration tapes State)
    {result : Bool}
    (hresult : machine.result configuration.state = some result) :
    machine.step configuration = configuration := by
  simp [TypedMachine.step, hresult]

theorem TypedMachine.run_add_eq_of_result_run_eq_some {tapes : Nat}
    {State : Type} (machine : TypedMachine tapes State)
    (input : Fin tapes → List Bool)
    (steps extra : Nat) {result : Bool}
    (hresult :
      machine.result (machine.run input steps).state = some result) :
    machine.run input (steps + extra) = machine.run input steps := by
  induction extra with
  | zero => simp
  | succ extra ih =>
      rw [Nat.add_succ, TypedMachine.run, ih]
      exact
        machine.step_eq_self_of_result_some
          (machine.run input steps) hresult

end SipserGacsLautemann
Source
Reusable formal infrastructure for the custom Turing-machine model in the Sipser–Gács–Lautemann mission.

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me