Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Convert typed result machines into polynomial-time deciders

Definition
sgl_result_machine_dpt

by Henry Yuen · Jul 24, 2026 · Mathlib 0df444a (Lean v4.33.1)

complexity-theoryleansipser-gacs-lautemannturing-machines

This module packages two structural conversion lemmas for the mission machine model. If a finite typed machine has a polynomial clock and its final result at that clock is exactly some (answer input), then its relabeled toMachine decides the Boolean predicate answer input = true in polynomial time. A second variant handles machines that return some (decide (P input)) and packages them directly as DecidesInPolynomialTime P.

These lemmas are useful for the result-only scheduler obligations in the Sipser--Gács--Lautemann mission, where the hard construction is a finite machine producing a Boolean report and the remaining proof step is converting that report into the standard polynomial-time decider interface.

Definition code
import Definitions.Def_sgl_machine_infrastructure

namespace SipserGacsLautemann

theorem DecidesInPolynomialTime.of_typed_result_bool
    {tapes : Nat} {State : Type}
    [Fintype State]
    (machine : TypedMachine tapes State)
    (time : Nat → Nat)
    (htime : PolynomiallyBounded time)
    (answer : (Fin tapes → List Bool) → Bool)
    (hresult :
      ∀ input : Fin tapes → List Bool,
        machine.result
            (machine.run input
              (time (totalInputLength input))).state =
          some (answer input)) :
    DecidesInPolynomialTime
      (fun input : Fin tapes → List Bool =>
        answer input = true) := by
  refine
    ⟨Fintype.card State, machine.toMachine,
      time, htime, ?_⟩
  intro input
  constructor
  · rw [machine.toMachine_acceptsWithin_iff]
    rw [hresult]
    cases hanswer : answer input <;> simp [hanswer]
  · rw [machine.toMachine_rejectsWithin_iff]
    rw [hresult]
    cases hanswer : answer input <;> simp [hanswer]

theorem DecidesInPolynomialTime.of_typed_result_decide
    {tapes : Nat} {State : Type}
    [Fintype State]
    {predicate : (Fin tapes → List Bool) → Prop}
    [DecidablePred predicate]
    (machine : TypedMachine tapes State)
    (time : Nat → Nat)
    (htime : PolynomiallyBounded time)
    (hresult :
      ∀ input : Fin tapes → List Bool,
        machine.result
            (machine.run input
              (time (totalInputLength input))).state =
          some (decide (predicate input))) :
    DecidesInPolynomialTime predicate := by
  refine
    ⟨Fintype.card State, machine.toMachine,
      time, htime, ?_⟩
  intro input
  constructor
  · rw [machine.toMachine_acceptsWithin_iff]
    rw [hresult]
    by_cases h : predicate input <;> simp [h]
  · rw [machine.toMachine_rejectsWithin_iff]
    rw [hresult]
    by_cases h : predicate input <;> simp [h]

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