Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

SGL move-left prefix composition

Definition
sgl_move_left_prefix

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

complexity-theorysipser-gacs-lautemannturing-machines

This auxiliary module defines a generic typed-machine prefix that first moves every tape left once, then runs an arbitrary typed machine from the resulting configuration. It proves that after the prefix step, the composed machine has exactly the same state and tape behavior as the underlying typed machine started from the moved-left initial tapes.

This is scheduler infrastructure for preserving raw input archives before invoking encoded verifier simulations.

Definition code
import Definitions.Def_sgl_raw_archive_machine
import Mathlib.Data.Fintype.Sum

namespace SipserGacsLautemann

inductive MoveLeftPrefixState (State : Type) where
  | moveLeft
  | running : State → MoveLeftPrefixState State
  deriving DecidableEq, Fintype

def moveLeftInitialConfiguration
    {tapes : Nat} {State : Type}
    (machine : TypedMachine tapes State)
    (input : Fin tapes → List Bool) :
    TypedConfiguration tapes State where
  state := machine.start
  tape := fun i => (Tape.ofBits (input i)).move .left

def MoveLeftPrefixState.embedConfiguration
    {tapes : Nat} {State : Type}
    (configuration : TypedConfiguration tapes State) :
    TypedConfiguration tapes (MoveLeftPrefixState State) where
  state := .running configuration.state
  tape := configuration.tape

def moveLeftPrefixTypedMachine
    {tapes : Nat} {State : Type}
    (machine : TypedMachine tapes State) :
    TypedMachine tapes (MoveLeftPrefixState State) where
  start := .moveLeft
  transition state symbols :=
    match state with
    | .moveLeft =>
        (.running machine.start,
          fun i => (symbols i, .left))
    | .running baseState =>
        let action := machine.transition baseState symbols
        (.running action.1, action.2)
  result
    | .moveLeft => none
    | .running baseState => machine.result baseState

theorem moveLeftPrefixTypedMachine_step_running
    {tapes : Nat} {State : Type}
    (machine : TypedMachine tapes State)
    (configuration : TypedConfiguration tapes State) :
    (moveLeftPrefixTypedMachine machine).step
        (MoveLeftPrefixState.embedConfiguration configuration) =
      MoveLeftPrefixState.embedConfiguration
        (machine.step configuration) := by
  cases configuration with
  | mk state tape =>
      cases hresult : machine.result state with
      | some result =>
          simp [TypedMachine.step,
            moveLeftPrefixTypedMachine,
            MoveLeftPrefixState.embedConfiguration,
            hresult]
      | none =>
          simp [TypedMachine.step,
            moveLeftPrefixTypedMachine,
            MoveLeftPrefixState.embedConfiguration,
            hresult]

theorem moveLeftPrefixTypedMachine_run_one
    {tapes : Nat} {State : Type}
    (machine : TypedMachine tapes State)
    (input : Fin tapes → List Bool) :
    (moveLeftPrefixTypedMachine machine).run input 1 =
      MoveLeftPrefixState.embedConfiguration
        (moveLeftInitialConfiguration machine input) := by
  rfl

theorem moveLeftPrefixTypedMachine_run_succ
    {tapes : Nat} {State : Type}
    (machine : TypedMachine tapes State)
    (input : Fin tapes → List Bool)
    (steps : Nat) :
    (moveLeftPrefixTypedMachine machine).run input
        (steps + 1) =
      MoveLeftPrefixState.embedConfiguration
        ((machine.step^[steps])
          (moveLeftInitialConfiguration machine input)) := by
  induction steps with
  | zero =>
      exact moveLeftPrefixTypedMachine_run_one machine input
  | succ steps ih =>
      change
        (moveLeftPrefixTypedMachine machine).run input
            ((steps + 1) + 1) =
          MoveLeftPrefixState.embedConfiguration
            ((machine.step^[steps + 1])
              (moveLeftInitialConfiguration machine input))
      rw [TypedMachine.run, ih]
      rw [moveLeftPrefixTypedMachine_step_running]
      rw [Function.iterate_succ_apply']

theorem moveLeftPrefixTypedMachine_result_run_succ
    {tapes : Nat} {State : Type}
    (machine : TypedMachine tapes State)
    (input : Fin tapes → List Bool)
    (steps : Nat) :
    (moveLeftPrefixTypedMachine machine).result
        ((moveLeftPrefixTypedMachine machine).run input
          (steps + 1)).state =
      machine.result
        (((machine.step^[steps])
          (moveLeftInitialConfiguration machine input)).state) := by
  rw [moveLeftPrefixTypedMachine_run_succ]
  rfl

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