Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Encoded simulator correctness under padded time bounds

Definition
sgl_encoded_padded_correctness

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

complexity-theorypolynomial-timeturing-machines

This module combines two published ingredients: correctness of the encoded simulator on encoded inputs, and preservation of machine correctness under larger time bounds. If a base machine decides a logical predicate on input xxx after exactly ttt simulated steps, then the ordinary relabeled encoded simulator decides the same predicate on encodeInputBits of xxx after any physical time bound at least 6t6t6t.

This is directly used by the remaining Sipser--Gács--Lautemann scheduler: a scheduler normally reserves a uniform polynomial number of physical steps for each verifier call, rather than running exactly the verifier stopping time for each query.

Definition code
import Definitions.Def_sgl_encoded_to_machine_adapters
import Definitions.Def_sgl_machine_time_padding

namespace SipserGacsLautemann

theorem encodedSimulation_toMachine_correctness_at_larger_time
    {tapes baseStates : Nat}
    (baseMachine : Machine tapes baseStates)
    (predicate : (Fin tapes → List Bool) → Prop)
    (input : Fin tapes → List Bool)
    {exact later : Nat}
    (hle : 6 * exact ≤ later)
    (hacceptExact :
      baseMachine.acceptsWithin input exact ↔ predicate input)
    (hrejectExact :
      baseMachine.rejectsWithin input exact ↔ ¬ predicate input) :
    (((encodedSimulationTypedMachine baseMachine).toMachine
          ).acceptsWithin
        (fun i => encodeInputBits (input i)) later ↔
        predicate input) ∧
      (((encodedSimulationTypedMachine baseMachine).toMachine
          ).rejectsWithin
        (fun i => encodeInputBits (input i)) later ↔
        ¬ predicate input) := by
  let encodedMachine :=
    (encodedSimulationTypedMachine baseMachine).toMachine
  have hacceptEncoded :
      encodedMachine.acceptsWithin
          (fun i => encodeInputBits (input i))
          (6 * exact) ↔
        predicate input := by
    exact
      (encodedSimulation_toMachine_acceptsWithin_encoded
        baseMachine input exact).trans hacceptExact
  have hrejectEncoded :
      encodedMachine.rejectsWithin
          (fun i => encodeInputBits (input i))
          (6 * exact) ↔
        ¬ predicate input := by
    exact
      (encodedSimulation_toMachine_rejectsWithin_encoded
        baseMachine input exact).trans hrejectExact
  exact
    encodedMachine.correctness_at_larger_time
      (fun _ : Fin tapes → List Bool => predicate input)
      (fun i => encodeInputBits (input i))
      hle hacceptEncoded hrejectEncoded

theorem encodedSimulation_toMachine_correctness_package_at_larger_time
    {tapes baseStates : Nat}
    (baseMachine : Machine tapes baseStates)
    (predicate : (Fin tapes → List Bool) → Prop)
    (exact : (Fin tapes → List Bool) → Nat)
    (later : (Fin tapes → List Bool) → Nat)
    (hle : ∀ input, 6 * exact input ≤ later input)
    (hcorrect :
      ∀ input : Fin tapes → List Bool,
        (baseMachine.acceptsWithin input (exact input) ↔
          predicate input) ∧
        (baseMachine.rejectsWithin input (exact input) ↔
          ¬ predicate input)) :
    ∀ input : Fin tapes → List Bool,
      (((encodedSimulationTypedMachine baseMachine).toMachine
            ).acceptsWithin
          (fun i => encodeInputBits (input i)) (later input) ↔
          predicate input) ∧
        (((encodedSimulationTypedMachine baseMachine).toMachine
            ).rejectsWithin
          (fun i => encodeInputBits (input i)) (later input) ↔
          ¬ predicate input) := by
  intro input
  exact
    encodedSimulation_toMachine_correctness_at_larger_time
      baseMachine predicate input (hle input)
      (hcorrect input).1 (hcorrect input).2

end SipserGacsLautemann
Source
Prove2me Sipser--Gács--Lautemann mission; consequence of the published encoded simulator and deterministic time-padding lemmas.

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