Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Same-tape preprocessing delegate for polynomial-time machines

Definition
sgl_preprocess_delegate

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

This module proves a reusable same-tape preprocessing/delegation theorem for the Sipser--Gács--Lautemann machine model. If a finite typed preprocessing machine rewrites an input into the exact initial configuration of a base deterministic multitape machine, then delegates every later step and result to that base machine, the transformed predicate is decidable in polynomial time. The theorem includes polynomial padding for an externally supplied polynomial bound on the transformed input length.

Definition code
import Definitions.Def_sgl_machine_time_padding
import Definitions.Def_sgl_machine_infrastructure
import Definitions.Def_sgl_polynomial_closures

namespace SipserGacsLautemann

theorem TypedMachine.run_add_steps
    {tapes : Nat} {State : Type}
    (machine : TypedMachine tapes State)
    (input : Fin tapes → List Bool)
    (first extra : Nat) :
    machine.run input (first + extra) =
      (machine.step^[extra]) (machine.run input first) := by
  induction extra with
  | zero => simp
  | succ extra ih =>
      rw [Nat.add_succ, TypedMachine.run, ih]
      rw [Function.iterate_succ_apply']

theorem Machine.run_eq_iterate_step_from_initial
    {tapes states : Nat}
    (machine : Machine tapes states)
    (input : Fin tapes → List Bool)
    (steps : Nat) :
    machine.run input steps =
      (machine.step^[steps])
        (initialConfiguration machine input) := by
  induction steps with
  | zero => rfl
  | succ steps ih =>
      rw [Machine.run, ih]
      rw [Function.iterate_succ_apply']

theorem preprocessDelegate_iterate_embed
    {tapes states : Nat} {State : Type}
    (preMachine : TypedMachine tapes State)
    (baseMachine : Machine tapes states)
    (embed : Configuration tapes states →
      TypedConfiguration tapes State)
    (hstep :
      ∀ configuration : Configuration tapes states,
        preMachine.step (embed configuration) =
          embed (baseMachine.step configuration))
    (configuration : Configuration tapes states)
    (steps : Nat) :
    (preMachine.step^[steps]) (embed configuration) =
      embed ((baseMachine.step^[steps]) configuration) := by
  induction steps generalizing configuration with
  | zero => rfl
  | succ steps ih =>
      rw [Function.iterate_succ_apply]
      rw [hstep]
      rw [Function.iterate_succ_apply]
      exact ih (baseMachine.step configuration)

theorem preprocessDelegate_run_after_preprocess
    {tapes states : Nat} {State : Type}
    (preMachine : TypedMachine tapes State)
    (baseMachine : Machine tapes states)
    (transform :
      (Fin tapes → List Bool) → (Fin tapes → List Bool))
    (preTime : Nat → Nat)
    (embed : Configuration tapes states →
      TypedConfiguration tapes State)
    (hpre :
      ∀ input : Fin tapes → List Bool,
        preMachine.run input (preTime (totalInputLength input)) =
          embed (initialConfiguration baseMachine
            (transform input)))
    (hstep :
      ∀ configuration : Configuration tapes states,
        preMachine.step (embed configuration) =
          embed (baseMachine.step configuration))
    (input : Fin tapes → List Bool)
    (baseSteps : Nat) :
    preMachine.run input
        (preTime (totalInputLength input) + baseSteps) =
      embed (baseMachine.run (transform input) baseSteps) := by
  rw [preMachine.run_add_steps]
  rw [hpre]
  rw [preprocessDelegate_iterate_embed
    preMachine baseMachine embed hstep]
  rw [← Machine.run_eq_iterate_step_from_initial]

theorem PolynomiallyBounded.padded_composed_bound
    {argument : Nat → Nat}
    (hargument : PolynomiallyBounded argument)
    (coefficient degree : Nat) :
    PolynomiallyBounded
      (fun n => coefficient * (argument n + 1) ^ degree) := by
  exact
    PolynomiallyBounded.const_mul coefficient
      ((PolynomiallyBounded.succ hargument).pow_const degree)

/-- If a finite preprocessing machine rewrites an input into the exact
initial configuration of a base machine and thereafter delegates each step and
result to that base machine, then the transformed predicate is polynomial-time
decidable. The time bound pads the base machine by a polynomial upper bound on
the transformed input length, so the final clock depends only on the original
input length. -/
theorem DecidesInPolynomialTime.of_same_tape_preprocess_delegate
    {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)
    (hpre :
      ∀ input : Fin tapes → List Bool,
        preMachine.run input
            (preTime (totalInputLength input)) =
          embed (initialConfiguration baseMachine
            (transform 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.run baseInput paddedBaseSteps) := by
    simpa [baseInput, inputLength, paddedBaseSteps] using
      preprocessDelegate_run_after_preprocess
        preMachine baseMachine transform preTime embed hpre
        hstep 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]
    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]
    simpa [Machine.rejectsWithin, baseInput,
      paddedBaseSteps] using hbaseCorrectLater.2

end SipserGacsLautemann
Source
Prove2me Sipser--Gács--Lautemann mission internal machine-composition 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