Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

SGL zigzag simulator machine

Definition
sgl_zigzag_simulator

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

complexity-theorysipser-gacs-lautemannturing-machines

This auxiliary module defines the finite-state zigzag simulator used to run a two-tape mission machine inside encoded work regions while preserving archive data on the physical tapes. It includes the simulator states, local scan and update procedures, mirroring operations, and the mirrored left-zigzag simulator.

Definition code
import Definitions.Def_sgl_encoded_simulator
import Mathlib.Data.Fintype.Pi
import Mathlib.Data.Fintype.Prod
import Mathlib.Data.Fintype.Sigma
import Mathlib.Data.Fintype.Sum
import Mathlib.Tactic.DeriveFintype

namespace SipserGacsLautemann

inductive ZigzagIndexClass where
  | zero
  | positiveOne
  | positive
  | negative
  deriving DecidableEq, Fintype

def ZigzagIndexClass.next : ZigzagIndexClass →
    ZigzagIndexClass
  | .zero => .positiveOne
  | .positiveOne => .negative
  | .positive => .negative
  | .negative => .positive

inductive ZigzagDirection where
  | inward
  | outward
  deriving DecidableEq, Fintype

def ZigzagDirection.headMove : ZigzagDirection → HeadMove
  | .inward => .left
  | .outward => .right

structure ZigzagRelocation where
  direction : ZigzagDirection
  distance : Fin 7
  deriving DecidableEq, Fintype

def zigzagRelocation (move : HeadMove)
    (indexClass : ZigzagIndexClass) :
    Option ZigzagRelocation :=
  match move, indexClass with
  | .stay, _ => none
  | .right, .zero =>
      some ⟨.outward, ⟨3, by decide⟩⟩
  | .right, .positiveOne =>
      some ⟨.outward, ⟨6, by decide⟩⟩
  | .right, .positive =>
      some ⟨.outward, ⟨6, by decide⟩⟩
  | .right, .negative =>
      some ⟨.inward, ⟨6, by decide⟩⟩
  | .left, .zero =>
      some ⟨.outward, ⟨6, by decide⟩⟩
  | .left, .positiveOne =>
      some ⟨.inward, ⟨3, by decide⟩⟩
  | .left, .positive =>
      some ⟨.inward, ⟨6, by decide⟩⟩
  | .left, .negative =>
      some ⟨.outward, ⟨6, by decide⟩⟩

inductive ZigzagScanLocal where
  | atFlag : ZigzagIndexClass → ZigzagScanLocal
  | atSymbolFirst :
      ZigzagIndexClass → Bool → ZigzagScanLocal
  | atSymbolSecond :
      ZigzagIndexClass → Bool → Bool → ZigzagScanLocal
  | returning :
      TapeSymbol → ZigzagIndexClass → ZigzagScanLocal
  | done :
      TapeSymbol → ZigzagIndexClass → ZigzagScanLocal
  deriving DecidableEq, Fintype

def ZigzagScanLocal.isDone : ZigzagScanLocal → Bool
  | .done _ _ => true
  | _ => false

def ZigzagScanLocal.symbol : ZigzagScanLocal → TapeSymbol
  | .done symbol _ => symbol
  | _ => .blank

def ZigzagScanLocal.indexClass :
    ZigzagScanLocal → ZigzagIndexClass
  | .atFlag indexClass => indexClass
  | .atSymbolFirst indexClass _ => indexClass
  | .atSymbolSecond indexClass _ _ => indexClass
  | .returning _ indexClass => indexClass
  | .done _ indexClass => indexClass

def zigzagScanLocalStep
    (scanState : ZigzagScanLocal) (symbol : TapeSymbol) :
    ZigzagScanLocal × (TapeSymbol × HeadMove) :=
  match scanState with
  | .atFlag indexClass =>
      (.atSymbolFirst indexClass
          (readPhysicalBit symbol),
        (preserveOrEncodeBlank symbol, .right))
  | .atSymbolFirst indexClass headFlag =>
      (.atSymbolSecond indexClass headFlag
          (readPhysicalBit symbol),
        (preserveOrEncodeBlank symbol, .right))
  | .atSymbolSecond indexClass headFlag firstBit =>
      let decoded :=
        decodeTapeSymbol (firstBit, readPhysicalBit symbol)
      if headFlag then
        (.returning decoded indexClass,
          (preserveOrEncodeBlank symbol, .left))
      else
        (.atFlag indexClass.next,
          (preserveOrEncodeBlank symbol, .right))
  | .returning cached indexClass =>
      match symbol with
      | .blank =>
          (.done cached indexClass, (.blank, .stay))
      | .bit bit =>
          (.returning cached indexClass, (.bit bit, .left))
  | .done cached indexClass =>
      (.done cached indexClass, (symbol, .stay))

inductive ZigzagUpdateLocal where
  | atFlag : ZigzagIndexClass → ZigzagUpdateLocal
  | skipSymbolFirst : ZigzagIndexClass → ZigzagUpdateLocal
  | skipSymbolSecond : ZigzagIndexClass → ZigzagUpdateLocal
  | writeSymbolFirst :
      ZigzagIndexClass → ZigzagUpdateLocal
  | writeSymbolSecond :
      ZigzagIndexClass → ZigzagUpdateLocal
  | returnToFlag :
      ZigzagIndexClass → ZigzagUpdateLocal
  | relocate :
      ZigzagDirection → Fin 7 → ZigzagUpdateLocal
  | setHead
  | ensureSymbolFirst
  | ensureSymbolSecond
  | returning
  | done
  deriving DecidableEq, Fintype

def ZigzagUpdateLocal.isDone : ZigzagUpdateLocal → Bool
  | .done => true
  | _ => false

def finPredSeven (remaining : Fin 7)
    (hpositive : 0 < remaining.val) : Fin 7 :=
  ⟨remaining.val - 1, by omega⟩

def zigzagUpdateLocalStep
    (write : TapeSymbol) (move : HeadMove)
    (updateState : ZigzagUpdateLocal) (symbol : TapeSymbol) :
    ZigzagUpdateLocal × (TapeSymbol × HeadMove) :=
  match updateState with
  | .atFlag indexClass =>
      if readPhysicalBit symbol then
        (.writeSymbolFirst indexClass,
          (.bit false, .right))
      else
        (.skipSymbolFirst indexClass,
          (preserveOrEncodeBlank symbol, .right))
  | .skipSymbolFirst indexClass =>
      (.skipSymbolSecond indexClass,
        (preserveOrEncodeBlank symbol, .right))
  | .skipSymbolSecond indexClass =>
      (.atFlag indexClass.next,
        (preserveOrEncodeBlank symbol, .right))
  | .writeSymbolFirst indexClass =>
      (.writeSymbolSecond indexClass,
        (.bit (encodeTapeSymbol write).1, .right))
  | .writeSymbolSecond indexClass =>
      (.returnToFlag indexClass,
        (.bit (encodeTapeSymbol write).2, .left))
  | .returnToFlag indexClass =>
      match zigzagRelocation move indexClass with
      | none =>
          (.setHead, (preserveOrEncodeBlank symbol, .left))
      | some relocation =>
          (.relocate relocation.direction relocation.distance,
            (preserveOrEncodeBlank symbol, .left))
  | .relocate direction remaining =>
      if hzero : remaining.val = 0 then
        (.setHead, (preserveOrEncodeBlank symbol, .stay))
      else
        (.relocate direction
            (finPredSeven remaining
              (Nat.pos_of_ne_zero hzero)),
          (preserveOrEncodeBlank symbol,
            direction.headMove))
  | .setHead =>
      (.ensureSymbolFirst, (.bit true, .right))
  | .ensureSymbolFirst =>
      (.ensureSymbolSecond,
        (preserveOrEncodeBlank symbol, .right))
  | .ensureSymbolSecond =>
      (.returning,
        (preserveOrEncodeBlank symbol, .left))
  | .returning =>
      match symbol with
      | .blank => (.done, (.blank, .stay))
      | .bit bit => (.returning, (.bit bit, .left))
  | .done => (.done, (symbol, .stay))

def allScanDone (locals : Fin 2 → ZigzagScanLocal) : Bool :=
  (locals 0).isDone && (locals 1).isDone

def allUpdateDone
    (locals : Fin 2 → ZigzagUpdateLocal) : Bool :=
  (locals 0).isDone && (locals 1).isDone

inductive ZigzagSimulationState (baseStates : Nat) where
  | ready : Fin baseStates →
      ZigzagSimulationState baseStates
  | scanning :
      Fin baseStates → (Fin 2 → ZigzagScanLocal) →
      ZigzagSimulationState baseStates
  | updating :
      Fin baseStates →
      (Fin 2 → TapeSymbol) →
      (Fin 2 → HeadMove) →
      (Fin 2 → ZigzagUpdateLocal) →
      ZigzagSimulationState baseStates

def ZigzagSimulationState.equivSum (baseStates : Nat) :
    ZigzagSimulationState baseStates ≃
      Fin baseStates ⊕
        (Fin baseStates × (Fin 2 → ZigzagScanLocal)) ⊕
        (Fin baseStates ×
          (Fin 2 → TapeSymbol) ×
          (Fin 2 → HeadMove) ×
          (Fin 2 → ZigzagUpdateLocal)) where
  toFun
    | .ready state => Sum.inl state
    | .scanning state locals =>
        Sum.inr (Sum.inl (state, locals))
    | .updating state writes moves locals =>
        Sum.inr (Sum.inr
          (state, writes, moves, locals))
  invFun
    | Sum.inl state => .ready state
    | Sum.inr (Sum.inl (state, locals)) =>
        .scanning state locals
    | Sum.inr (Sum.inr
        (state, writes, moves, locals)) =>
        .updating state writes moves locals
  left_inv state := by
    cases state <;> rfl
  right_inv state := by
    rcases state with state | state | state <;> rfl

noncomputable instance zigzagSimulationStateFintype
    (baseStates : Nat) :
    Fintype (ZigzagSimulationState baseStates) :=
  Fintype.ofEquiv
    (Fin baseStates ⊕
      (Fin baseStates × (Fin 2 → ZigzagScanLocal)) ⊕
      (Fin baseStates ×
        (Fin 2 → TapeSymbol) ×
        (Fin 2 → HeadMove) ×
        (Fin 2 → ZigzagUpdateLocal)))
    (ZigzagSimulationState.equivSum baseStates).symm

def startScanLocals : Fin 2 → ZigzagScanLocal :=
  fun _ => .atFlag .zero

def startUpdateLocals : Fin 2 → ZigzagUpdateLocal :=
  fun _ => .atFlag .zero

noncomputable def zigzagSimulationTypedMachine
    {baseStates : Nat}
    (baseMachine : Machine 2 baseStates) :
    TypedMachine 2 (ZigzagSimulationState baseStates) where
  start := .ready baseMachine.start
  transition state symbols :=
    match state with
    | .ready baseState =>
        (.scanning baseState startScanLocals,
          fun i => (symbols i, .right))
    | .scanning baseState locals =>
        if hdone : allScanDone locals = true then
          let virtualSymbols :=
            fun i => (locals i).symbol
          let action :=
            baseMachine.transition baseState virtualSymbols
          (.updating action.1
              (fun i => (action.2 i).1)
              (fun i => (action.2 i).2)
              startUpdateLocals,
            fun i => (symbols i, .right))
        else
          let actions :=
            fun i => zigzagScanLocalStep (locals i) (symbols i)
          (.scanning baseState (fun i => (actions i).1),
            fun i => (actions i).2)
    | .updating nextState writes moves locals =>
        if hdone : allUpdateDone locals = true then
          (.ready nextState, fun i => (symbols i, .stay))
        else
          let actions :=
            fun i =>
              zigzagUpdateLocalStep
                (writes i) (moves i) (locals i) (symbols i)
          (.updating nextState writes moves
              (fun i => (actions i).1),
            fun i => (actions i).2)
  result
    | .ready baseState => baseMachine.result baseState
    | _ => none

def mirrorHeadMove : HeadMove → HeadMove
  | .left => .right
  | .stay => .stay
  | .right => .left

@[simp]
theorem mirrorHeadMove_involutive (move : HeadMove) :
    mirrorHeadMove (mirrorHeadMove move) = move := by
  cases move <;> rfl

def mirrorTape (tape : Tape) : Tape where
  left := tape.right
  head := tape.head
  right := tape.left

@[simp]
theorem mirrorTape_involutive (tape : Tape) :
    mirrorTape (mirrorTape tape) = tape := by
  cases tape
  rfl

@[simp]
theorem mirrorTape_write (tape : Tape)
    (symbol : TapeSymbol) :
    mirrorTape (tape.write symbol) =
      (mirrorTape tape).write symbol := by
  cases tape
  rfl

@[simp]
theorem mirrorTape_move (tape : Tape) (move : HeadMove) :
    mirrorTape (tape.move move) =
      (mirrorTape tape).move (mirrorHeadMove move) := by
  cases tape with
  | mk left head right =>
      cases move <;> cases left <;> cases right <;> rfl

def mirrorTapeAction :
    TapeSymbol × HeadMove → TapeSymbol × HeadMove :=
  fun action => (action.1, mirrorHeadMove action.2)

def mirrorTypedMachine {tapes : Nat} {State : Type}
    (machine : TypedMachine tapes State) :
    TypedMachine tapes State where
  start := machine.start
  transition state symbols :=
    let action := machine.transition state symbols
    (action.1, fun i => mirrorTapeAction (action.2 i))
  result := machine.result

def mirrorTypedConfiguration {tapes : Nat} {State : Type}
    (configuration : TypedConfiguration tapes State) :
    TypedConfiguration tapes State :=
  ⟨configuration.state, fun i => mirrorTape (configuration.tape i)⟩

@[simp]
theorem mirrorTypedConfiguration_involutive
    {tapes : Nat} {State : Type}
    (configuration : TypedConfiguration tapes State) :
    mirrorTypedConfiguration
        (mirrorTypedConfiguration configuration) =
      configuration := by
  cases configuration
  simp [mirrorTypedConfiguration]

theorem mirrorTypedMachine_step
    {tapes : Nat} {State : Type}
    (machine : TypedMachine tapes State)
    (configuration : TypedConfiguration tapes State) :
    (mirrorTypedMachine machine).step
        (mirrorTypedConfiguration configuration) =
      mirrorTypedConfiguration (machine.step configuration) := by
  cases configuration with
  | mk state tape =>
      cases hresult : machine.result state with
      | some result =>
          simp [TypedMachine.step, mirrorTypedMachine,
            mirrorTypedConfiguration, hresult]
      | none =>
          simp only [TypedMachine.step, mirrorTypedMachine,
            mirrorTypedConfiguration, hresult]
          let action :=
            machine.transition state (fun i => (tape i).head)
          change
            ({ state := action.1
               tape := fun i =>
                 Tape.move
                   (Tape.write (mirrorTape (tape i))
                     (action.2 i).1)
                   (mirrorHeadMove (action.2 i).2) } :
              TypedConfiguration tapes State) =
            ({ state := action.1
               tape := fun i =>
                 mirrorTape
                   (Tape.move
                     (Tape.write (tape i) (action.2 i).1)
                     (action.2 i).2) } :
              TypedConfiguration tapes State)
          congr 1
          funext i
          simp

noncomputable def leftZigzagSimulationTypedMachine
    {baseStates : Nat}
    (baseMachine : Machine 2 baseStates) :
    TypedMachine 2 (ZigzagSimulationState baseStates) :=
  mirrorTypedMachine
    (zigzagSimulationTypedMachine baseMachine)

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