Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

SGL machine halting monotonicity

Definition
sgl_machine_monotone

by Henry Yuen · Jul 24, 2026 · Mathlib c5ea003 (Lean v4.30.0)

complexity-theorysipser-gacs-lautemannturing-machines

This auxiliary module proves basic monotonicity facts for the mission Turing-machine model. Once a machine has reached an accepting or rejecting state, subsequent steps leave it in the same halted configuration, so acceptance and rejection persist under larger time bounds.

These lemmas are runtime-padding infrastructure for polynomial-time simulations in the Sipser--Gacs--Lautemann mission.

Definition code
import Definitions.Def_sipser_gacs_lautemann

namespace SipserGacsLautemann

theorem Machine.step_eq_self_of_result_eq_some
    {tapes states : Nat}
    (machine : Machine tapes states)
    (configuration : Configuration tapes states)
    {result : Bool}
    (hresult : machine.result configuration.state = some result) :
    machine.step configuration = configuration := by
  simp [Machine.step, hresult]

theorem Machine.run_add_of_result_eq_some
    {tapes states : Nat}
    (machine : Machine tapes states)
    (input : Fin tapes → List Bool)
    (steps extra : Nat)
    {result : Bool}
    (hresult :
      machine.result (machine.run input steps).state =
        some result) :
    machine.run input (steps + extra) =
      machine.run input steps := by
  induction extra with
  | zero => simp
  | succ extra ih =>
      rw [Nat.add_succ, Machine.run, ih]
      exact
        machine.step_eq_self_of_result_eq_some
          (machine.run input steps) hresult

theorem Machine.acceptsWithin_mono_steps
    {tapes states : Nat}
    (machine : Machine tapes states)
    (input : Fin tapes → List Bool)
    {earlier later : Nat}
    (hle : earlier ≤ later)
    (haccepts : machine.acceptsWithin input earlier) :
    machine.acceptsWithin input later := by
  obtain ⟨extra, rfl⟩ := Nat.exists_eq_add_of_le hle
  unfold Machine.acceptsWithin at haccepts ⊢
  rw [machine.run_add_of_result_eq_some
    input earlier extra haccepts]
  exact haccepts

theorem Machine.rejectsWithin_mono_steps
    {tapes states : Nat}
    (machine : Machine tapes states)
    (input : Fin tapes → List Bool)
    {earlier later : Nat}
    (hle : earlier ≤ later)
    (hrejects : machine.rejectsWithin input earlier) :
    machine.rejectsWithin input later := by
  obtain ⟨extra, rfl⟩ := Nat.exists_eq_add_of_le hle
  unfold Machine.rejectsWithin at hrejects ⊢
  rw [machine.run_add_of_result_eq_some
    input earlier extra hrejects]
  exact hrejects

theorem Machine.not_accepts_and_rejects_same_time
    {tapes states : Nat}
    (machine : Machine tapes states)
    (input : Fin tapes → List Bool)
    (steps : Nat) :
    ¬ (machine.acceptsWithin input steps ∧
        machine.rejectsWithin input steps) := by
  intro hboth
  rcases hboth with ⟨haccepts, hrejects⟩
  unfold Machine.acceptsWithin at haccepts
  unfold Machine.rejectsWithin at hrejects
  rw [haccepts] at hrejects
  cases hrejects

end SipserGacsLautemann
Source
Auxiliary formalization for the Prove2me mission The Sipser--Gacs--Lautemann Theorem.

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