Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Machine correctness is preserved under larger time bounds

Definition
sgl_machine_time_padding

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

complexity-theorypolynomial-timeturing-machines

This module proves a standard padding lemma for the mission Turing-machine model. If a deterministic machine decides a predicate correctly at an exact time bound T(x)T(x)T(x), then it also decides the same predicate correctly at any larger time bound T′(x)≥T(x)T\prime(x)\ge T(x)T′(x)≥T(x).

The proof uses the published monotonicity lemmas for accepting and rejecting halting states, together with the fact that a deterministic machine cannot accept and reject at the same time. This is needed by scheduler constructions, which usually run submachines for a uniform polynomial upper bound rather than their exact stopping time.

Definition code
import Definitions.Def_sgl_machine_monotone

namespace SipserGacsLautemann

theorem Machine.correctness_at_larger_time
    {tapes states : Nat}
    (machine : Machine tapes states)
    (predicate : (Fin tapes → List Bool) → Prop)
    (input : Fin tapes → List Bool)
    {exact later : Nat}
    (hle : exact ≤ later)
    (hacceptExact :
      machine.acceptsWithin input exact ↔ predicate input)
    (hrejectExact :
      machine.rejectsWithin input exact ↔ ¬ predicate input) :
    (machine.acceptsWithin input later ↔ predicate input) ∧
      (machine.rejectsWithin input later ↔
        ¬ predicate input) := by
  constructor
  · constructor
    · intro hacceptLater
      by_contra hnot
      have hrejectExact := hrejectExact.mpr hnot
      have hrejectLater :=
        machine.rejectsWithin_mono_steps
          input hle hrejectExact
      exact
        machine.not_accepts_and_rejects_same_time
          input later ⟨hacceptLater, hrejectLater⟩
    · intro hpredicate
      exact
        machine.acceptsWithin_mono_steps input hle
          (hacceptExact.mpr hpredicate)
  · constructor
    · intro hrejectLater hpredicate
      have hacceptExact := hacceptExact.mpr hpredicate
      have hacceptLater :=
        machine.acceptsWithin_mono_steps
          input hle hacceptExact
      exact
        machine.not_accepts_and_rejects_same_time
          input later ⟨hacceptLater, hrejectLater⟩
    · intro hnot
      exact
        machine.rejectsWithin_mono_steps input hle
          (hrejectExact.mpr hnot)

theorem Machine.correctness_package_at_larger_time
    {tapes states : Nat}
    (machine : Machine tapes states)
    (predicate : (Fin tapes → List Bool) → Prop)
    (exact later : (Fin tapes → List Bool) → Nat)
    (hle : ∀ input, exact input ≤ later input)
    (hcorrect :
      ∀ input : Fin tapes → List Bool,
        (machine.acceptsWithin input (exact input) ↔
          predicate input) ∧
        (machine.rejectsWithin input (exact input) ↔
          ¬ predicate input)) :
    ∀ input : Fin tapes → List Bool,
      (machine.acceptsWithin input (later input) ↔
        predicate input) ∧
      (machine.rejectsWithin input (later input) ↔
        ¬ predicate input) := by
  intro input
  exact
    machine.correctness_at_larger_time
      predicate input (hle input)
      (hcorrect input).1 (hcorrect input).2

end SipserGacsLautemann
Source
Standard deterministic-machine time padding argument for the Prove2me Sipser--Gács--Lautemann scheduler formalization.

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