Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

SGL encoded simulator

Definition
sgl_encoded_simulator

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

complexity-theorysipser-gacs-lautemannturing-machines

This auxiliary module formalizes a fixed two-bit encoding of mission tape symbols and proves that an encoded simulator can reproduce a base multitape machine run with constant-factor overhead. It supplies the low-level encoded-tape correctness lemmas used by the Sipser--Gacs--Lautemann simulator stack.

Definition code
import Definitions.Def_sgl_machine_infrastructure
import Mathlib.Data.Fintype.Pi
import Mathlib.Data.Fintype.Prod
import Mathlib.Data.Fintype.Sum
import Mathlib.Tactic.FinCases

namespace SipserGacsLautemann

def encodeTapeSymbol : TapeSymbol → Bool × Bool
  | .blank => (false, false)
  | .bit false => (false, true)
  | .bit true => (true, false)

def decodeTapeSymbol : Bool × Bool → TapeSymbol
  | (false, false) => .blank
  | (false, true) => .bit false
  | (true, false) => .bit true
  | (true, true) => .blank

@[simp]
theorem decodeTapeSymbol_encodeTapeSymbol (symbol : TapeSymbol) :
    decodeTapeSymbol (encodeTapeSymbol symbol) = symbol := by
  cases symbol with
  | blank => rfl
  | bit value =>
      cases value <;> rfl

def encodedSymbolBits (symbol : TapeSymbol) : List Bool :=
  [(encodeTapeSymbol symbol).1, (encodeTapeSymbol symbol).2]

def encodedLeftSymbols (symbols : List TapeSymbol) :
    List TapeSymbol :=
  symbols.flatMap fun symbol =>
    [.bit (encodeTapeSymbol symbol).2,
      .bit (encodeTapeSymbol symbol).1]

def encodedRightSymbols (head : TapeSymbol)
    (symbols : List TapeSymbol) : List TapeSymbol :=
  .bit (encodeTapeSymbol head).2 ::
    symbols.flatMap fun symbol =>
      [.bit (encodeTapeSymbol symbol).1,
        .bit (encodeTapeSymbol symbol).2]

def encodeTape (tape : Tape) : Tape where
  left := encodedLeftSymbols tape.left
  head := .bit (encodeTapeSymbol tape.head).1
  right := encodedRightSymbols tape.head tape.right

def encodeInputBits (bits : List Bool) : List Bool :=
  match bits with
  | [] => encodedSymbolBits .blank
  | _ => bits.flatMap fun bit => encodedSymbolBits (.bit bit)

theorem encodedSymbols_map_bits (bits : List Bool) :
    (bits.map TapeSymbol.bit).flatMap
        (fun symbol =>
          [.bit (encodeTapeSymbol symbol).1,
            .bit (encodeTapeSymbol symbol).2]) =
      (bits.flatMap fun bit =>
        encodedSymbolBits (.bit bit)).map TapeSymbol.bit := by
  induction bits with
  | nil => rfl
  | cons bit bits ih =>
      simp [encodedSymbolBits, ih]

theorem encodeTape_ofBits (bits : List Bool) :
    encodeTape (Tape.ofBits bits) =
      Tape.ofBits (encodeInputBits bits) := by
  cases bits with
  | nil =>
      simp [encodeTape, Tape.ofBits, encodeInputBits,
        encodedLeftSymbols, encodedRightSymbols,
        encodedSymbolBits, encodeTapeSymbol]
  | cons bit bits =>
      simp [encodeTape, Tape.ofBits, encodeInputBits,
        encodedLeftSymbols, encodedRightSymbols,
        encodedSymbolBits, List.flatMap_cons,
        encodedSymbols_map_bits]

inductive EncodedSimulationState
    (tapes baseStates : Nat) where
  | ready : Fin baseStates →
      EncodedSimulationState tapes baseStates
  | readSecond :
      Fin baseStates → (Fin tapes → Bool) →
      EncodedSimulationState tapes baseStates
  | writeFirst :
      Fin baseStates →
      (Fin tapes → Bool × Bool) →
      (Fin tapes → HeadMove) →
      EncodedSimulationState tapes baseStates
  | moveSecond :
      Fin baseStates → (Fin tapes → HeadMove) →
      EncodedSimulationState tapes baseStates
  | ensureFirst :
      Fin baseStates →
      EncodedSimulationState tapes baseStates
  | ensureSecond :
      Fin baseStates →
      EncodedSimulationState tapes baseStates

def EncodedSimulationState.equivSum
    (tapes baseStates : Nat) :
    EncodedSimulationState tapes baseStates ≃
      Fin baseStates ⊕
        (Fin baseStates × (Fin tapes → Bool)) ⊕
        (Fin baseStates ×
          (Fin tapes → Bool × Bool) ×
          (Fin tapes → HeadMove)) ⊕
        (Fin baseStates × (Fin tapes → HeadMove)) ⊕
        Fin baseStates ⊕ Fin baseStates where
  toFun
    | .ready state => Sum.inl state
    | .readSecond state first =>
        Sum.inr (Sum.inl (state, first))
    | .writeFirst state writes moves =>
        Sum.inr (Sum.inr
          (Sum.inl (state, writes, moves)))
    | .moveSecond state moves =>
        Sum.inr (Sum.inr
          (Sum.inr (Sum.inl (state, moves))))
    | .ensureFirst state =>
        Sum.inr (Sum.inr
          (Sum.inr (Sum.inr (Sum.inl state))))
    | .ensureSecond state =>
        Sum.inr (Sum.inr
          (Sum.inr (Sum.inr (Sum.inr state))))
  invFun
    | Sum.inl state => .ready state
    | Sum.inr (Sum.inl (state, first)) =>
        .readSecond state first
    | Sum.inr (Sum.inr
        (Sum.inl (state, writes, moves))) =>
        .writeFirst state writes moves
    | Sum.inr (Sum.inr
        (Sum.inr (Sum.inl (state, moves)))) =>
        .moveSecond state moves
    | Sum.inr (Sum.inr
        (Sum.inr (Sum.inr (Sum.inl state)))) =>
        .ensureFirst state
    | Sum.inr (Sum.inr
        (Sum.inr (Sum.inr (Sum.inr state)))) =>
        .ensureSecond state
  left_inv state := by
    cases state <;> rfl
  right_inv state := by
    rcases state with
      state | state | state | state | state | state <;>
      rfl

def headMoveEquivFin : HeadMove ≃ Fin 3 where
  toFun
    | .left => 0
    | .stay => 1
    | .right => 2
  invFun
    | ⟨0, _⟩ => .left
    | ⟨1, _⟩ => .stay
    | ⟨2, _⟩ => .right
  left_inv move := by
    cases move <;> rfl
  right_inv i := by
    fin_cases i <;> rfl

instance headMoveFintype : Fintype HeadMove where
  elems := {.left, .stay, .right}
  complete move := by cases move <;> simp

def tapeSymbolEquivFin : TapeSymbol ≃ Fin 3 where
  toFun
    | .blank => 0
    | .bit false => 1
    | .bit true => 2
  invFun
    | ⟨0, _⟩ => .blank
    | ⟨1, _⟩ => .bit false
    | ⟨2, _⟩ => .bit true
  left_inv symbol := by
    cases symbol with
    | blank => rfl
    | bit value => cases value <;> rfl
  right_inv i := by
    fin_cases i <;> rfl

instance tapeSymbolFintype : Fintype TapeSymbol where
  elems := {.blank, .bit false, .bit true}
  complete symbol := by
    cases symbol with
    | blank => simp
    | bit value => cases value <;> simp

noncomputable instance encodedSimulationStateFintype
    (tapes baseStates : Nat) :
    Fintype (EncodedSimulationState tapes baseStates) :=
  Fintype.ofEquiv
    (Fin baseStates ⊕
      (Fin baseStates × (Fin tapes → Bool)) ⊕
      (Fin baseStates ×
        (Fin tapes → Bool × Bool) ×
        (Fin tapes → HeadMove)) ⊕
      (Fin baseStates × (Fin tapes → HeadMove)) ⊕
      Fin baseStates ⊕ Fin baseStates)
    (EncodedSimulationState.equivSum tapes baseStates).symm

def readPhysicalBit : TapeSymbol → Bool
  | .blank => false
  | .bit bit => bit

def preserveOrEncodeBlank (symbol : TapeSymbol) :
    TapeSymbol :=
  .bit (readPhysicalBit symbol)

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

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

noncomputable def encodedSimulationTypedMachine
    {tapes baseStates : Nat}
    (baseMachine : Machine tapes baseStates) :
    TypedMachine tapes
      (EncodedSimulationState tapes baseStates) where
  start := .ready baseMachine.start
  transition state symbols :=
    match state with
    | .ready baseState =>
        (.readSecond baseState
            (fun i => readPhysicalBit (symbols i)),
          fun i =>
            (preserveOrEncodeBlank (symbols i), .right))
    | .readSecond baseState firstBits =>
        let virtualSymbols := fun i =>
          decodeTapeSymbol
            (firstBits i, readPhysicalBit (symbols i))
        let action :=
          baseMachine.transition baseState virtualSymbols
        (.writeFirst action.1
            (fun i => encodeTapeSymbol (action.2 i).1)
            (fun i => (action.2 i).2),
          fun i =>
            (.bit (encodeTapeSymbol (action.2 i).1).2,
              .left))
    | .writeFirst nextState writes moves =>
        (.moveSecond nextState moves,
          fun i =>
            (.bit (writes i).1,
              firstPhysicalMove (moves i)))
    | .moveSecond nextState moves =>
        (.ensureFirst nextState,
          fun i => (symbols i, secondPhysicalMove (moves i)))
    | .ensureFirst nextState =>
        (.ensureSecond nextState,
          fun i =>
            (preserveOrEncodeBlank (symbols i), .right))
    | .ensureSecond nextState =>
        (.ready nextState,
          fun i =>
            (preserveOrEncodeBlank (symbols i), .left))
  result
    | .ready baseState => baseMachine.result baseState
    | _ => none

def encodeTypedConfiguration {tapes baseStates : Nat}
    (configuration : Configuration tapes baseStates) :
    TypedConfiguration tapes
      (EncodedSimulationState tapes baseStates) :=
  ⟨.ready configuration.state,
    fun i => encodeTape (configuration.tape i)⟩

theorem encodedSimulation_initial
    {tapes baseStates : Nat}
    (baseMachine : Machine tapes baseStates)
    (input : Fin tapes → List Bool) :
    (encodedSimulationTypedMachine baseMachine).initialConfiguration
        (fun i => encodeInputBits (input i)) =
      encodeTypedConfiguration
        (initialConfiguration baseMachine input) := by
  unfold TypedMachine.initialConfiguration
    encodeTypedConfiguration initialConfiguration
  congr
  funext i
  exact (encodeTape_ofBits (input i)).symm

theorem encodeTape_write (tape : Tape)
    (symbol : TapeSymbol) :
    encodeTape (tape.write symbol) =
      { encodeTape tape with
        head := .bit (encodeTapeSymbol symbol).1
        right :=
          .bit (encodeTapeSymbol symbol).2 ::
            (encodeTape tape).right.tail } := by
  cases tape
  rfl

theorem encodeTape_move_stay (tape : Tape) :
    encodeTape (tape.move .stay) = encodeTape tape := by
  rfl

def applyTapeAction (tape : Tape)
    (symbol : TapeSymbol) (move : HeadMove) : Tape :=
  Tape.move (Tape.write tape symbol) move

def encodedTapeVirtualStep (tape : Tape)
    (write : TapeSymbol) (move : HeadMove) : Tape :=
  let afterReadFirst :=
    applyTapeAction tape
      (preserveOrEncodeBlank tape.head) .right
  let afterWriteSecond :=
    applyTapeAction afterReadFirst
      (.bit (encodeTapeSymbol write).2) .left
  let afterWriteFirst :=
    applyTapeAction afterWriteSecond
      (.bit (encodeTapeSymbol write).1)
      (firstPhysicalMove move)
  let afterMoveSecond :=
    applyTapeAction afterWriteFirst afterWriteFirst.head
      (secondPhysicalMove move)
  let afterEnsureFirst :=
    applyTapeAction afterMoveSecond
      (preserveOrEncodeBlank afterMoveSecond.head) .right
  applyTapeAction afterEnsureFirst
    (preserveOrEncodeBlank afterEnsureFirst.head) .left

theorem encodedTapeVirtualStep_encodeTape
    (tape : Tape) (write : TapeSymbol)
    (move : HeadMove) :
    encodedTapeVirtualStep (encodeTape tape) write move =
      encodeTape
        (Tape.move (Tape.write tape write) move) := by
  cases tape with
  | mk left head right =>
      cases move with
      | stay =>
          cases write <;>
            simp [encodedTapeVirtualStep, applyTapeAction,
              encodeTape, Tape.move, Tape.write,
              encodedLeftSymbols, encodedRightSymbols,
              preserveOrEncodeBlank, readPhysicalBit,
              firstPhysicalMove, secondPhysicalMove,
              encodeTapeSymbol]
      | right =>
          cases right with
          | nil =>
              cases write <;>
                simp [encodedTapeVirtualStep, applyTapeAction,
                  encodeTape, Tape.move, Tape.write,
                  encodedLeftSymbols, encodedRightSymbols,
                  preserveOrEncodeBlank, readPhysicalBit,
                  firstPhysicalMove, secondPhysicalMove,
                  encodeTapeSymbol]
          | cons next rest =>
              cases write <;> cases next <;>
                simp [encodedTapeVirtualStep, applyTapeAction,
                  encodeTape, Tape.move, Tape.write,
                  encodedLeftSymbols, encodedRightSymbols,
                  preserveOrEncodeBlank, readPhysicalBit,
                  firstPhysicalMove, secondPhysicalMove,
                  encodeTapeSymbol]
      | left =>
          cases left with
          | nil =>
              cases write <;>
                simp [encodedTapeVirtualStep, applyTapeAction,
                  encodeTape, Tape.move, Tape.write,
                  encodedLeftSymbols, encodedRightSymbols,
                  preserveOrEncodeBlank, readPhysicalBit,
                  firstPhysicalMove, secondPhysicalMove,
                  encodeTapeSymbol]
          | cons previous rest =>
              cases write <;> cases previous <;>
                simp [encodedTapeVirtualStep, applyTapeAction,
                  encodeTape, Tape.move, Tape.write,
                  encodedLeftSymbols, encodedRightSymbols,
                  preserveOrEncodeBlank, readPhysicalBit,
                  firstPhysicalMove, secondPhysicalMove,
                  encodeTapeSymbol]

theorem decodeEncodedTapeHead (tape : Tape) :
    decodeTapeSymbol
        (readPhysicalBit (encodeTape tape).head,
          readPhysicalBit
            (applyTapeAction (encodeTape tape)
              (preserveOrEncodeBlank (encodeTape tape).head)
              .right).head) =
      tape.head := by
  cases tape with
  | mk left head right =>
      cases head with
      | blank => rfl
      | bit value =>
          cases value <;> rfl

noncomputable def encodedSimulationSixSteps
    {tapes baseStates : Nat}
    (baseMachine : Machine tapes baseStates)
    (configuration :
      TypedConfiguration tapes
        (EncodedSimulationState tapes baseStates)) :
    TypedConfiguration tapes
      (EncodedSimulationState tapes baseStates) :=
  let machine := encodedSimulationTypedMachine baseMachine
  machine.step
    (machine.step
      (machine.step
        (machine.step
          (machine.step
            (machine.step configuration)))))

theorem encodedSimulationSixSteps_encode
    {tapes baseStates : Nat}
    (baseMachine : Machine tapes baseStates)
    (configuration : Configuration tapes baseStates) :
    encodedSimulationSixSteps baseMachine
        (encodeTypedConfiguration configuration) =
      encodeTypedConfiguration
        (baseMachine.step configuration) := by
  cases configuration with
  | mk state tape =>
      cases hresult : baseMachine.result state with
      | some result =>
          simp [encodedSimulationSixSteps,
            TypedMachine.step,
            encodedSimulationTypedMachine,
            encodeTypedConfiguration,
            Machine.step, hresult]
      | none =>
          have hread :
              (fun i =>
                decodeTapeSymbol
                  (readPhysicalBit (encodeTape (tape i)).head,
                    readPhysicalBit
                      (applyTapeAction
                        (encodeTape (tape i))
                        (preserveOrEncodeBlank
                          (encodeTape (tape i)).head)
                        .right).head)) =
                fun i => (tape i).head := by
            funext i
            exact decodeEncodedTapeHead (tape i)
          simp only [applyTapeAction] at hread
          simp only [encodedSimulationSixSteps,
            encodeTypedConfiguration,
            TypedMachine.step,
            encodedSimulationTypedMachine,
            hresult, Machine.step]
          rw [hread]
          let action :=
            baseMachine.transition state
              (fun i => (tape i).head)
          change
            ({ state := .ready action.1
               tape := fun i =>
                 encodedTapeVirtualStep
                   (encodeTape (tape i))
                   (action.2 i).1 (action.2 i).2 } :
              TypedConfiguration tapes
                (EncodedSimulationState tapes baseStates)) =
              ({ state := .ready action.1
                 tape := fun i =>
                   encodeTape
                     (Tape.move
                       (Tape.write (tape i) (action.2 i).1)
                       (action.2 i).2) } :
                TypedConfiguration tapes
                  (EncodedSimulationState tapes baseStates))
          congr
          funext i
          exact
            encodedTapeVirtualStep_encodeTape
              (tape i) (action.2 i).1 (action.2 i).2

theorem encodedSimulation_run_add_six
    {tapes baseStates : Nat}
    (baseMachine : Machine tapes baseStates)
    (input : Fin tapes → List Bool) (steps : Nat) :
    (encodedSimulationTypedMachine baseMachine).run
        input (steps + 6) =
      encodedSimulationSixSteps baseMachine
        ((encodedSimulationTypedMachine baseMachine).run
          input steps) := by
  simp [encodedSimulationSixSteps, TypedMachine.run,
    Nat.add_assoc]

theorem encodedSimulation_run_encoded
    {tapes baseStates : Nat}
    (baseMachine : Machine tapes baseStates)
    (input : Fin tapes → List Bool) (steps : Nat) :
    (encodedSimulationTypedMachine baseMachine).run
        (fun i => encodeInputBits (input i)) (6 * steps) =
      encodeTypedConfiguration
        (baseMachine.run input steps) := by
  induction steps with
  | zero =>
      simpa [TypedMachine.run, Machine.run] using
        encodedSimulation_initial baseMachine input
  | succ steps ih =>
      have htime : 6 * (steps + 1) = 6 * steps + 6 := by
        omega
      rw [htime,
        encodedSimulation_run_add_six baseMachine,
        ih,
        encodedSimulationSixSteps_encode]
      rfl

theorem encodedSimulation_result_run_encoded
    {tapes baseStates : Nat}
    (baseMachine : Machine tapes baseStates)
    (input : Fin tapes → List Bool) (steps : Nat) :
    (encodedSimulationTypedMachine baseMachine).result
        ((encodedSimulationTypedMachine baseMachine).run
          (fun i => encodeInputBits (input i))
          (6 * steps)).state =
      baseMachine.result
        (baseMachine.run input steps).state := by
  rw [encodedSimulation_run_encoded]
  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