Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Package polynomial-time deciders as typed result machines

Definition
sgl_dpt_to_result_machine

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

complexity-theoryleansipser-gacs-lautemannturing-machines

This module converts between the mission’s raw finite-state machine model and the typed-machine interface. It defines Machine.toTypedMachine, proves that it preserves initial configurations, steps, runs, and results, and then packages any DecidesInPolynomialTime proof as a finite typed machine whose final result is exactly some (decide (P input)) at the same polynomial clock.

This is the converse interface to sgl_result_machine_dpt: together, the two modules let scheduler proofs move cleanly between Boolean-result machines and the standard polynomial-time decidability predicate.

Definition code
import Definitions.Def_sgl_machine_infrastructure

namespace SipserGacsLautemann

def Machine.toTypedMachine {tapes states : Nat}
    (machine : Machine tapes states) :
    TypedMachine tapes (Fin states) where
  start := machine.start
  transition := machine.transition
  result := machine.result

theorem Machine.toTypedMachine_initialConfiguration
    {tapes states : Nat}
    (machine : Machine tapes states)
    (input : Fin tapes → List Bool) :
    machine.toTypedMachine.initialConfiguration input =
      { state := (initialConfiguration machine input).state
        tape := (initialConfiguration machine input).tape } := by
  rfl

theorem Machine.toTypedMachine_step
    {tapes states : Nat}
    (machine : Machine tapes states)
    (configuration : Configuration tapes states) :
    machine.toTypedMachine.step
        { state := configuration.state
          tape := configuration.tape } =
      { state := (machine.step configuration).state
        tape := (machine.step configuration).tape } := by
  cases hresult : machine.result configuration.state with
  | none =>
      simp [Machine.toTypedMachine, TypedMachine.step,
        Machine.step, hresult]
  | some result =>
      simp [Machine.toTypedMachine, TypedMachine.step,
        Machine.step, hresult]

theorem Machine.toTypedMachine_run
    {tapes states : Nat}
    (machine : Machine tapes states)
    (input : Fin tapes → List Bool)
    (steps : Nat) :
    machine.toTypedMachine.run input steps =
      { state := (machine.run input steps).state
        tape := (machine.run input steps).tape } := by
  induction steps with
  | zero =>
      rfl
  | succ steps ih =>
      rw [TypedMachine.run, Machine.run, ih]
      exact machine.toTypedMachine_step (machine.run input steps)

theorem Machine.toTypedMachine_result_run
    {tapes states : Nat}
    (machine : Machine tapes states)
    (input : Fin tapes → List Bool)
    (steps : Nat) :
    machine.toTypedMachine.result
        (machine.toTypedMachine.run input steps).state =
      machine.result (machine.run input steps).state := by
  rw [machine.toTypedMachine_run]
  rfl

theorem DecidesInPolynomialTime.to_typed_result_decide
    {tapes : Nat}
    {predicate : (Fin tapes → List Bool) → Prop}
    [DecidablePred predicate]
    (hdecides : DecidesInPolynomialTime predicate) :
    ∃ (State : Type) (_ : Fintype State)
      (machine : TypedMachine tapes State)
      (time : Nat → Nat),
      PolynomiallyBounded time ∧
        ∀ input : Fin tapes → List Bool,
          machine.result
              (machine.run input
                (time (totalInputLength input))).state =
            some (decide (predicate input)) := by
  classical
  rcases hdecides with
    ⟨states, machine, time, htime, hcorrect⟩
  refine
    ⟨Fin states, inferInstance, machine.toTypedMachine,
      time, htime, ?_⟩
  intro input
  rw [machine.toTypedMachine_result_run]
  by_cases hp : predicate input
  · have haccept :
        machine.acceptsWithin input
          (time (totalInputLength input)) :=
      (hcorrect input).1.mpr hp
    simpa [Machine.acceptsWithin, hp] using haccept
  · have hreject :
        machine.rejectsWithin input
          (time (totalInputLength input)) :=
      (hcorrect input).2.mpr hp
    simpa [Machine.rejectsWithin, hp] using hreject

end SipserGacsLautemann
Source
Prove2me Sipser--Gács--Lautemann mission finite typed-machine infrastructure.

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