Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

SGL simulator reachability and result adapters

Definition
sgl_simulation_result_adapters

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

complexity-theorysipser-gacs-lautemannturing-machines

This module packages result-readout and reachability adapters for the Sipser--Gács--Lautemann simulator stack. It lifts ReachesWithin proofs through the move-left prefix when the prefixed machine is already in an embedded running state, records that embedded prefixed states have the same result as the underlying typed machine, and records that a completed left-zigzag simulation reads out exactly the result of the simulated base machine run.

These lemmas are intended for the remaining aggregation scheduler: after a loader constructs a ready verifier-query configuration, these adapters let the proof append the verifier simulation phase and recover the Boolean answer with the published polynomial-overhead bound.

Definition code
import Definitions.Def_sgl_move_left_prefix_reaches

namespace SipserGacsLautemann

theorem moveLeftPrefixTypedMachine_iterate_embedded
    {tapes : Nat} {State : Type}
    (machine : TypedMachine tapes State)
    (configuration : TypedConfiguration tapes State)
    (steps : Nat) :
    ((moveLeftPrefixTypedMachine machine).step^[steps])
        (MoveLeftPrefixState.embedConfiguration configuration) =
      MoveLeftPrefixState.embedConfiguration
        ((machine.step^[steps]) configuration) := by
  induction steps with
  | zero => rfl
  | succ steps ih =>
      rw [Function.iterate_succ_apply',
        Function.iterate_succ_apply', ih]
      exact moveLeftPrefixTypedMachine_step_running
        machine ((machine.step^[steps]) configuration)

theorem moveLeftPrefixTypedMachine_reaches_embedded
    {tapes : Nat} {State : Type}
    (machine : TypedMachine tapes State)
    {initial final : TypedConfiguration tapes State}
    {bound : Nat}
    (hreaches :
      ReachesWithin machine.step initial final bound) :
    ReachesWithin
      (moveLeftPrefixTypedMachine machine).step
      (MoveLeftPrefixState.embedConfiguration initial)
      (MoveLeftPrefixState.embedConfiguration final)
      bound := by
  rcases hreaches with ⟨steps, hle, hsteps⟩
  refine ⟨steps, hle, ?_⟩
  rw [moveLeftPrefixTypedMachine_iterate_embedded, hsteps]

theorem moveLeftPrefixTypedMachine_result_embedded
    {tapes : Nat} {State : Type}
    (machine : TypedMachine tapes State)
    (configuration : TypedConfiguration tapes State) :
    (moveLeftPrefixTypedMachine machine).result
        (MoveLeftPrefixState.embedConfiguration configuration).state =
      machine.result configuration.state := by
  rfl

theorem leftZigzagReadyConfiguration_result
    {baseStates : Nat}
    (baseMachine : Machine 2 baseStates)
    (configuration : Configuration 2 baseStates)
    (archives : Fin 2 → List TapeSymbol)
    (positions : Fin 2 → Int)
    (recordCount : Nat) :
    (leftZigzagSimulationTypedMachine baseMachine).result
        (leftZigzagReadyConfiguration
          configuration archives positions recordCount).state =
      baseMachine.result configuration.state := by
  rfl

theorem leftZigzagSimulation_reaches_run_with_result
    {baseStates : Nat}
    (baseMachine : Machine 2 baseStates)
    (input : Fin 2 → List Bool)
    (archives : Fin 2 → List TapeSymbol)
    (steps horizon : Nat)
    (hsteps : steps ≤ horizon) :
    ∃ final : TypedConfiguration 2
        (ZigzagSimulationState baseStates),
      ReachesWithin
        (leftZigzagSimulationTypedMachine baseMachine).step
        (leftZigzagReadyConfiguration
          (baseMachine.run input 0) archives
          (zigzagRunPositions baseMachine input 0)
          (2 * horizon + 3))
        final
        (steps * (24 * horizon + 32)) ∧
      (leftZigzagSimulationTypedMachine baseMachine).result
          final.state =
        baseMachine.result
          (baseMachine.run input steps).state := by
  refine
    ⟨leftZigzagReadyConfiguration
        (baseMachine.run input steps) archives
        (zigzagRunPositions baseMachine input steps)
        (2 * horizon + 3),
      leftZigzagSimulation_reaches_run
        baseMachine input archives steps horizon hsteps,
      ?_⟩
  exact
    leftZigzagReadyConfiguration_result
      baseMachine (baseMachine.run input steps)
      archives (zigzagRunPositions baseMachine input steps)
      (2 * horizon + 3)

end SipserGacsLautemann
Source
Prove2me Sipser--Gács--Lautemann mission; deterministic Turing-machine simulator bookkeeping for the shared aggregation scheduler.

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