Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Preprocess-and-delegate DPT theorem up to observational equivalence, full module

Definition
sgl_preprocess_delegate_obseq_full

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

complexity-theorysipser-gacs-lautemannturing-machines

Full-code module proving a robust preprocess-and-delegate theorem for deterministic polynomial-time machines. The preprocessing phase may reach a base configuration only observationally equivalent to the transformed initial configuration; exact equality of Lean’s concrete tape zipper is unnecessary. This supports machine-construction reductions where scans may leave harmless blank padding.

Definition code
import Definitions.Def_sgl_preprocess_delegate
import Definitions.Def_sgl_tape_observational_equivalence_full

namespace SipserGacsLautemann

/-- Variant of `DecidesInPolynomialTime.of_same_tape_preprocess_delegate`
where the preprocessing phase only has to reach a base configuration
observationally equivalent to the transformed initial configuration.

This is the useful form for concrete Turing-machine transducers: scanning to
the end of a finite input and returning to the origin may leave extra blank
cells in the concrete zipper representation, but those cells are invisible to
all future machine executions. -/
theorem DecidesInPolynomialTime.of_same_tape_preprocess_delegate_obsEq
    {tapes states : Nat} {State : Type}
    [Fintype State]
    {predicate : (Fin tapes → List Bool) → Prop}
    (baseMachine : Machine tapes states)
    (baseTime : Nat → Nat)
    (hbaseTime : PolynomiallyBounded baseTime)
    (hbaseCorrect :
      ∀ input : Fin tapes → List Bool,
        (baseMachine.acceptsWithin input
            (baseTime (totalInputLength input)) ↔
          predicate input) ∧
        (baseMachine.rejectsWithin input
            (baseTime (totalInputLength input)) ↔
          ¬ predicate input))
    (transform :
      (Fin tapes → List Bool) → (Fin tapes → List Bool))
    (preMachine : TypedMachine tapes State)
    (preTime argumentBound : Nat → Nat)
    (hpreTime : PolynomiallyBounded preTime)
    (hargumentBound : PolynomiallyBounded argumentBound)
    (htransformLength :
      ∀ input : Fin tapes → List Bool,
        totalInputLength (transform input) ≤
          argumentBound (totalInputLength input))
    (embed : Configuration tapes states →
      TypedConfiguration tapes State)
    (preConfig :
      (Fin tapes → List Bool) → Configuration tapes states)
    (hpreConfigObsEq :
      ∀ input : Fin tapes → List Bool,
        Configuration.ObsEq (preConfig input)
          (initialConfiguration baseMachine
            (transform input)))
    (hpre :
      ∀ input : Fin tapes → List Bool,
        preMachine.run input
            (preTime (totalInputLength input)) =
          embed (preConfig input))
    (hstep :
      ∀ configuration : Configuration tapes states,
        preMachine.step (embed configuration) =
          embed (baseMachine.step configuration))
    (hresult :
      ∀ configuration : Configuration tapes states,
        preMachine.result (embed configuration).state =
          baseMachine.result configuration.state) :
    DecidesInPolynomialTime
      (fun input : Fin tapes → List Bool =>
        predicate (transform input)) := by
  rcases hbaseTime with
    ⟨coefficient, degree, hbaseBound⟩
  let paddedBaseTime : Nat → Nat :=
    fun n => coefficient * (argumentBound n + 1) ^ degree
  let totalTime : Nat → Nat :=
    fun n => preTime n + paddedBaseTime n
  let machine := preMachine.toMachine
  refine
    ⟨Fintype.card State, machine, totalTime,
      hpreTime.add
        (PolynomiallyBounded.padded_composed_bound
          hargumentBound coefficient degree),
      ?_⟩
  intro input
  let baseInput := transform input
  let inputLength := totalInputLength input
  let exactBaseSteps := baseTime (totalInputLength baseInput)
  let paddedBaseSteps := paddedBaseTime inputLength
  have hbaseStepsLe :
      exactBaseSteps ≤ paddedBaseSteps := by
    dsimp [exactBaseSteps, paddedBaseSteps, paddedBaseTime]
    have hlength :
        totalInputLength baseInput + 1 ≤
          argumentBound inputLength + 1 :=
      Nat.succ_le_succ (htransformLength input)
    exact
      (hbaseBound (totalInputLength baseInput)).trans
        (Nat.mul_le_mul_left coefficient
          (Nat.pow_le_pow_left hlength degree))
  have hbaseCorrectLater :
      (baseMachine.acceptsWithin baseInput paddedBaseSteps ↔
          predicate baseInput) ∧
        (baseMachine.rejectsWithin baseInput paddedBaseSteps ↔
          ¬ predicate baseInput) := by
    exact
      baseMachine.correctness_at_larger_time
        predicate baseInput hbaseStepsLe
        (hbaseCorrect baseInput).1
        (hbaseCorrect baseInput).2
  have hrun :
      preMachine.run input
          (preTime inputLength + paddedBaseSteps) =
        embed
          ((baseMachine.step^[paddedBaseSteps])
            (preConfig input)) := by
    rw [preMachine.run_add_steps]
    rw [hpre]
    exact
      preprocessDelegate_iterate_embed
        preMachine baseMachine embed hstep
        (preConfig input) paddedBaseSteps
  have hbaseResultObs :
      baseMachine.result
          (((baseMachine.step^[paddedBaseSteps])
            (preConfig input)).state) =
        baseMachine.result
          (baseMachine.run baseInput paddedBaseSteps).state := by
    rw [Machine.run_eq_iterate_step_from_initial]
    exact
      baseMachine.result_iterate_eq_of_obsEq
        (hpreConfigObsEq input) paddedBaseSteps
  constructor
  · rw [preMachine.toMachine_acceptsWithin_iff]
    change
      preMachine.result
          (preMachine.run input
            (totalTime (totalInputLength input))).state =
          some true ↔
        predicate (transform input)
    simp only [totalTime, paddedBaseTime]
    rw [hrun]
    rw [hresult]
    rw [hbaseResultObs]
    simpa [Machine.acceptsWithin, baseInput,
      paddedBaseSteps] using hbaseCorrectLater.1
  · rw [preMachine.toMachine_rejectsWithin_iff]
    change
      preMachine.result
          (preMachine.run input
            (totalTime (totalInputLength input))).state =
          some false ↔
        ¬ predicate (transform input)
    simp only [totalTime, paddedBaseTime]
    rw [hrun]
    rw [hresult]
    rw [hbaseResultObs]
    simpa [Machine.rejectsWithin, baseInput,
      paddedBaseSteps] using hbaseCorrectLater.2

end SipserGacsLautemann
Source
Prove2me Sipser--Gács--Lautemann mission; full-code replacement using sgl_tape_observational_equivalence_full.

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