Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

SGL zigzag global correctness

Definition
sgl_zigzag_global

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

complexity-theorysipser-gacs-lautemannturing-machines

This auxiliary module lifts the local zigzag simulator correctness lemmas to complete runs of a two-tape base machine. It proves that the archive-preserving simulator reaches the configuration corresponding to a bounded base-machine run with polynomial overhead.

Definition code
import Definitions.Def_sgl_zigzag_correctness
import Mathlib.Tactic.FinCases

namespace SipserGacsLautemann

theorem zigzagScan_pad
    (initial final : ZigzagScanLocal × Tape)
    (steps bound : Nat)
    (hle : steps ≤ bound)
    (hrun :
      (zigzagScanConfigurationStep^[steps]) initial = final)
    (hfinal : final.1.isDone = true) :
    (zigzagScanConfigurationStep^[bound]) initial = final := by
  obtain ⟨extra, hbound⟩ :=
    Nat.exists_eq_add_of_le hle
  rw [hbound, Nat.add_comm,
    Function.iterate_add_apply, hrun]
  apply Function.iterate_fixed
  rcases final with ⟨state, tape⟩
  cases state <;> simp_all [zigzagScanConfigurationStep,
    ZigzagScanLocal.isDone, zigzagScanLocalStep,
    applyPhysicalAction, Tape.write, Tape.move]

abbrev ZigzagScanProduct :=
  (Fin 2 → ZigzagScanLocal) × (Fin 2 → Tape)

def zigzagScanProductStep
    (configuration : ZigzagScanProduct) :
    ZigzagScanProduct :=
  (fun i =>
      (zigzagScanConfigurationStep
        (configuration.1 i, configuration.2 i)).1,
    fun i =>
      (zigzagScanConfigurationStep
        (configuration.1 i, configuration.2 i)).2)

theorem zigzagScanProductStep_iterate_apply
    (configuration : ZigzagScanProduct)
    (steps : Nat) (i : Fin 2) :
    (((zigzagScanProductStep^[steps])
        configuration).1 i,
      ((zigzagScanProductStep^[steps])
        configuration).2 i) =
      (zigzagScanConfigurationStep^[steps])
        (configuration.1 i, configuration.2 i) := by
  induction steps with
  | zero => rfl
  | succ steps ih =>
      rw [Function.iterate_succ_apply']
      rw [Function.iterate_succ_apply']
      change
        (zigzagScanConfigurationStep
          (((zigzagScanProductStep^[steps])
              configuration).1 i,
            ((zigzagScanProductStep^[steps])
              configuration).2 i)) =
          zigzagScanConfigurationStep
            ((zigzagScanConfigurationStep^[steps])
              (configuration.1 i, configuration.2 i))
      rw [ih]

theorem zigzagScanProductStep_iterate_eq
    (configuration final : ZigzagScanProduct)
    (steps : Nat)
    (hrun :
      ∀ i : Fin 2,
        (zigzagScanConfigurationStep^[steps])
            (configuration.1 i, configuration.2 i) =
          (final.1 i, final.2 i)) :
    (zigzagScanProductStep^[steps]) configuration =
      final := by
  apply Prod.ext
  · funext i
    have hcomponent :=
      zigzagScanProductStep_iterate_apply
        configuration steps i
    rw [hrun i] at hcomponent
    exact congrArg Prod.fst hcomponent
  · funext i
    have hcomponent :=
      zigzagScanProductStep_iterate_apply
        configuration steps i
    rw [hrun i] at hcomponent
    exact congrArg Prod.snd hcomponent

def maxZigzagIndex (positions : Fin 2 → Int) : Nat :=
  max (zigzagIndex (positions 0))
    (zigzagIndex (positions 1))

theorem zigzagIndex_le_maxZigzagIndex
    (positions : Fin 2 → Int) (i : Fin 2) :
    zigzagIndex (positions i) ≤
      maxZigzagIndex positions := by
  fin_cases i
  · exact Nat.le_max_left _ _
  · exact Nat.le_max_right _ _

theorem zigzagScanProduct_physicalTapes
    (archives : Fin 2 → List TapeSymbol)
    (tapes : Fin 2 → Tape)
    (positions : Fin 2 → Int)
    (recordCount : Nat)
    (hroom :
      ∀ i : Fin 2,
        zigzagIndex (positions i) < recordCount) :
    (zigzagScanProductStep^[
        6 * maxZigzagIndex positions + 6])
        (startScanLocals,
          fun i =>
            (zigzagPhysicalTape
              (archives i) (tapes i) (positions i)
              recordCount).move .right) =
      (fun i =>
          .done (tapes i).head
            (ZigzagIndexClass.atIndex
              (zigzagIndex (positions i))),
        fun i =>
          zigzagPhysicalTape
            (archives i) (tapes i) (positions i)
            recordCount) := by
  apply zigzagScanProductStep_iterate_eq
  intro i
  obtain ⟨extra, hcount⟩ :=
    Nat.exists_eq_add_of_le
      (show zigzagIndex (positions i) + 1 ≤
          recordCount by
        exact Nat.succ_le_iff.mpr (hroom i))
  have hscan :=
    zigzagScan_physicalTape
      (archives i) (tapes i) (positions i) extra
  rw [← hcount] at hscan
  apply zigzagScan_pad _ _
      (6 * zigzagIndex (positions i) + 6)
      (6 * maxZigzagIndex positions + 6)
  · exact Nat.add_le_add_right
      (Nat.mul_le_mul_left 6
        (zigzagIndex_le_maxZigzagIndex
          positions i)) 6
  · simpa [startScanLocals] using hscan
  · rfl

abbrev ZigzagUpdateProduct :=
  (Fin 2 → ZigzagUpdateLocal) × (Fin 2 → Tape)

def zigzagUpdateProductStep
    (writes : Fin 2 → TapeSymbol)
    (moves : Fin 2 → HeadMove)
    (configuration : ZigzagUpdateProduct) :
    ZigzagUpdateProduct :=
  (fun i =>
      (zigzagUpdateConfigurationStep
        (writes i) (moves i)
        (configuration.1 i, configuration.2 i)).1,
    fun i =>
      (zigzagUpdateConfigurationStep
        (writes i) (moves i)
        (configuration.1 i, configuration.2 i)).2)

theorem zigzagUpdateProductStep_iterate_apply
    (writes : Fin 2 → TapeSymbol)
    (moves : Fin 2 → HeadMove)
    (configuration : ZigzagUpdateProduct)
    (steps : Nat) (i : Fin 2) :
    ((((zigzagUpdateProductStep writes moves)^[steps])
        configuration).1 i,
      (((zigzagUpdateProductStep writes moves)^[steps])
        configuration).2 i) =
      (zigzagUpdateConfigurationStep
          (writes i) (moves i))^[steps]
        (configuration.1 i, configuration.2 i) := by
  induction steps with
  | zero => rfl
  | succ steps ih =>
      rw [Function.iterate_succ_apply']
      rw [Function.iterate_succ_apply']
      change
        zigzagUpdateConfigurationStep
            (writes i) (moves i)
            ((((zigzagUpdateProductStep writes moves)^[
                steps]) configuration).1 i,
              (((zigzagUpdateProductStep writes moves)^[
                steps]) configuration).2 i) =
          zigzagUpdateConfigurationStep
            (writes i) (moves i)
            (((zigzagUpdateConfigurationStep
                (writes i) (moves i))^[steps])
              (configuration.1 i, configuration.2 i))
      rw [ih]

theorem zigzagUpdateProductStep_iterate_eq
    (writes : Fin 2 → TapeSymbol)
    (moves : Fin 2 → HeadMove)
    (configuration final : ZigzagUpdateProduct)
    (steps : Nat)
    (hrun :
      ∀ i : Fin 2,
        ((zigzagUpdateConfigurationStep
            (writes i) (moves i))^[steps])
            (configuration.1 i, configuration.2 i) =
          (final.1 i, final.2 i)) :
    ((zigzagUpdateProductStep writes moves)^[steps])
        configuration =
      final := by
  apply Prod.ext
  · funext i
    have hcomponent :=
      zigzagUpdateProductStep_iterate_apply
        writes moves configuration steps i
    rw [hrun i] at hcomponent
    exact congrArg Prod.fst hcomponent
  · funext i
    have hcomponent :=
      zigzagUpdateProductStep_iterate_apply
        writes moves configuration steps i
    rw [hrun i] at hcomponent
    exact congrArg Prod.snd hcomponent

theorem zigzagUpdateProduct_physicalTapes
    (archives : Fin 2 → List TapeSymbol)
    (tapes : Fin 2 → Tape)
    (positions : Fin 2 → Int)
    (recordCount : Nat)
    (writes : Fin 2 → TapeSymbol)
    (moves : Fin 2 → HeadMove)
    (hroom :
      ∀ i : Fin 2,
        zigzagIndex (positions i) + 2 < recordCount) :
    ((zigzagUpdateProductStep writes moves)^[
        6 * maxZigzagIndex positions + 23])
        (startUpdateLocals,
          fun i =>
            (zigzagPhysicalTape
              (archives i) (tapes i) (positions i)
              recordCount).move .right) =
      (fun _ => .done,
        fun i =>
          zigzagPhysicalTape
            (archives i)
            (((tapes i).write (writes i)).move
              (moves i))
            ((moves i).updatePosition (positions i))
            recordCount) := by
  apply zigzagUpdateProductStep_iterate_eq
  intro i
  have hupdate :=
    zigzagUpdate_physicalTape
      (archives i) (tapes i) (positions i)
      recordCount (writes i) (moves i) (hroom i)
  apply zigzagUpdate_pad
      (writes i) (moves i) _ _
      (6 * zigzagIndex (positions i) + 23)
      (6 * maxZigzagIndex positions + 23)
  · exact Nat.add_le_add_right
      (Nat.mul_le_mul_left 6
        (zigzagIndex_le_maxZigzagIndex
          positions i)) 23
  · simpa [startUpdateLocals] using hupdate
  · rfl

theorem iterate_embed_until_done
    {α β : Type*}
    (localStep : α → α) (globalStep : β → β)
    (embed : α → β) (done : α → Bool)
    (initial : α) (bound : Nat)
    (hstep :
      ∀ configuration,
        done configuration = false →
          globalStep (embed configuration) =
            embed (localStep configuration))
    (hfinal :
      done ((localStep^[bound]) initial) = true) :
    ∃ steps ≤ bound,
      (globalStep^[steps]) (embed initial) =
          embed ((localStep^[steps]) initial) ∧
        done ((localStep^[steps]) initial) = true := by
  classical
  let terminal : Nat → Prop :=
    fun steps =>
      done ((localStep^[steps]) initial) = true
  have hexists : ∃ steps, terminal steps :=
    ⟨bound, hfinal⟩
  let first := Nat.find hexists
  have hfirst : terminal first :=
    Nat.find_spec hexists
  have hfirstLe : first ≤ bound :=
    Nat.find_min' hexists hfinal
  have hbefore :
      ∀ steps < first,
        done ((localStep^[steps]) initial) = false := by
    intro steps hlt
    apply Bool.eq_false_of_not_eq_true
    intro hterminal
    exact (Nat.find_min hexists hlt) hterminal
  have hembed :
      ∀ steps ≤ first,
        (globalStep^[steps]) (embed initial) =
          embed ((localStep^[steps]) initial) := by
    intro steps hle
    induction steps with
    | zero => rfl
    | succ steps ih =>
        rw [Function.iterate_succ_apply',
          Function.iterate_succ_apply']
        rw [ih (Nat.le_trans (Nat.le_succ steps) hle)]
        apply hstep
        exact hbefore steps (Nat.lt_of_succ_le hle)
  exact
    ⟨first, hfirstLe, hembed first (Nat.le_refl _),
      hfirst⟩

def embedZigzagScanProduct
    {baseStates : Nat} (baseState : Fin baseStates)
    (configuration : ZigzagScanProduct) :
    TypedConfiguration 2
      (ZigzagSimulationState baseStates) :=
  ⟨.scanning baseState configuration.1,
    configuration.2⟩

def embedZigzagUpdateProduct
    {baseStates : Nat} (nextState : Fin baseStates)
    (writes : Fin 2 → TapeSymbol)
    (moves : Fin 2 → HeadMove)
    (configuration : ZigzagUpdateProduct) :
    TypedConfiguration 2
      (ZigzagSimulationState baseStates) :=
  ⟨.updating nextState writes moves configuration.1,
    configuration.2⟩

theorem zigzagSimulation_step_scan_not_done
    {baseStates : Nat}
    (baseMachine : Machine 2 baseStates)
    (baseState : Fin baseStates)
    (configuration : ZigzagScanProduct)
    (hnotDone :
      allScanDone configuration.1 = false) :
    (zigzagSimulationTypedMachine baseMachine).step
        (embedZigzagScanProduct baseState configuration) =
      embedZigzagScanProduct baseState
        (zigzagScanProductStep configuration) := by
  simp only [TypedMachine.step,
    zigzagSimulationTypedMachine,
    embedZigzagScanProduct]
  rw [dif_neg (by simpa using hnotDone)]
  rfl

theorem zigzagSimulation_step_update_not_done
    {baseStates : Nat}
    (baseMachine : Machine 2 baseStates)
    (nextState : Fin baseStates)
    (writes : Fin 2 → TapeSymbol)
    (moves : Fin 2 → HeadMove)
    (configuration : ZigzagUpdateProduct)
    (hnotDone :
      allUpdateDone configuration.1 = false) :
    (zigzagSimulationTypedMachine baseMachine).step
        (embedZigzagUpdateProduct nextState
          writes moves configuration) =
      embedZigzagUpdateProduct nextState writes moves
        (zigzagUpdateProductStep
          writes moves configuration) := by
  simp only [TypedMachine.step,
    zigzagSimulationTypedMachine,
    embedZigzagUpdateProduct]
  rw [dif_neg (by simpa using hnotDone)]
  rfl

theorem zigzagSimulation_scan_reaches_done
    {baseStates : Nat}
    (baseMachine : Machine 2 baseStates)
    (baseState : Fin baseStates)
    (archives : Fin 2 → List TapeSymbol)
    (tapes : Fin 2 → Tape)
    (positions : Fin 2 → Int)
    (recordCount : Nat)
    (hroom :
      ∀ i : Fin 2,
        zigzagIndex (positions i) < recordCount) :
    ∃ steps ≤ 6 * maxZigzagIndex positions + 6,
      (((zigzagSimulationTypedMachine baseMachine).step)^[
          steps])
          (embedZigzagScanProduct baseState
            (startScanLocals,
              fun i =>
                (zigzagPhysicalTape
                  (archives i) (tapes i) (positions i)
                  recordCount).move .right)) =
        embedZigzagScanProduct baseState
          (((zigzagScanProductStep^[steps])
            (startScanLocals,
              fun i =>
                (zigzagPhysicalTape
                  (archives i) (tapes i) (positions i)
                  recordCount).move .right))) ∧
      allScanDone
          (((zigzagScanProductStep^[steps])
            (startScanLocals,
              fun i =>
                (zigzagPhysicalTape
                  (archives i) (tapes i) (positions i)
                  recordCount).move .right))).1 =
        true := by
  apply iterate_embed_until_done
      zigzagScanProductStep
      (zigzagSimulationTypedMachine baseMachine).step
      (embedZigzagScanProduct baseState)
      (fun configuration =>
        allScanDone configuration.1)
  · intro configuration hnotDone
    exact zigzagSimulation_step_scan_not_done
      baseMachine baseState configuration hnotDone
  · rw [zigzagScanProduct_physicalTapes
      archives tapes positions recordCount hroom]
    rfl

theorem zigzagSimulation_update_reaches_done
    {baseStates : Nat}
    (baseMachine : Machine 2 baseStates)
    (nextState : Fin baseStates)
    (archives : Fin 2 → List TapeSymbol)
    (tapes : Fin 2 → Tape)
    (positions : Fin 2 → Int)
    (recordCount : Nat)
    (writes : Fin 2 → TapeSymbol)
    (moves : Fin 2 → HeadMove)
    (hroom :
      ∀ i : Fin 2,
        zigzagIndex (positions i) + 2 < recordCount) :
    ∃ steps ≤ 6 * maxZigzagIndex positions + 23,
      (((zigzagSimulationTypedMachine baseMachine).step)^[
        steps])
        (embedZigzagUpdateProduct nextState writes moves
          (startUpdateLocals,
            fun i =>
              (zigzagPhysicalTape
                (archives i) (tapes i) (positions i)
                recordCount).move .right)) =
        embedZigzagUpdateProduct nextState writes moves
          (((zigzagUpdateProductStep writes moves)^[
            steps])
            (startUpdateLocals,
              fun i =>
                (zigzagPhysicalTape
                  (archives i) (tapes i) (positions i)
                  recordCount).move .right)) ∧
      allUpdateDone
          ((((zigzagUpdateProductStep writes moves)^[
            steps])
            (startUpdateLocals,
              fun i =>
                (zigzagPhysicalTape
                  (archives i) (tapes i) (positions i)
                  recordCount).move .right)).1) =
        true := by
  apply iterate_embed_until_done
      (zigzagUpdateProductStep writes moves)
      (zigzagSimulationTypedMachine baseMachine).step
      (embedZigzagUpdateProduct nextState writes moves)
      (fun configuration =>
        allUpdateDone configuration.1)
  · intro configuration hnotDone
    exact zigzagSimulation_step_update_not_done
      baseMachine nextState writes moves
      configuration hnotDone
  · rw [zigzagUpdateProduct_physicalTapes
      archives tapes positions recordCount
      writes moves hroom]
    rfl

theorem zigzagScanConfigurationStep_fixed_of_done
    (configuration : ZigzagScanLocal × Tape)
    (hdone : configuration.1.isDone = true) :
    zigzagScanConfigurationStep configuration =
      configuration := by
  rcases configuration with ⟨state, tape⟩
  cases state <;>
    simp_all [ZigzagScanLocal.isDone,
      zigzagScanConfigurationStep, zigzagScanLocalStep,
      applyPhysicalAction, Tape.write, Tape.move]

theorem zigzagUpdateConfigurationStep_fixed_of_done
    (write : TapeSymbol) (move : HeadMove)
    (configuration : ZigzagUpdateLocal × Tape)
    (hdone : configuration.1.isDone = true) :
    zigzagUpdateConfigurationStep write move configuration =
      configuration := by
  rcases configuration with ⟨state, tape⟩
  cases state <;>
    simp_all [ZigzagUpdateLocal.isDone,
      zigzagUpdateConfigurationStep, zigzagUpdateLocalStep,
      applyPhysicalAction, Tape.write, Tape.move]

theorem zigzagScanProductStep_fixed_of_done
    (configuration : ZigzagScanProduct)
    (hdone : allScanDone configuration.1 = true) :
    zigzagScanProductStep configuration =
      configuration := by
  have hcomponents :
      ∀ i : Fin 2,
        (configuration.1 i).isDone = true := by
    rw [allScanDone, Bool.and_eq_true] at hdone
    intro i
    fin_cases i
    · exact hdone.1
    · exact hdone.2
  apply Prod.ext
  · funext i
    have hlocal :=
      zigzagScanConfigurationStep_fixed_of_done
        (configuration.1 i, configuration.2 i)
        (hcomponents i)
    exact congrArg Prod.fst hlocal
  · funext i
    have hlocal :=
      zigzagScanConfigurationStep_fixed_of_done
        (configuration.1 i, configuration.2 i)
        (hcomponents i)
    exact congrArg Prod.snd hlocal

theorem zigzagUpdateProductStep_fixed_of_done
    (writes : Fin 2 → TapeSymbol)
    (moves : Fin 2 → HeadMove)
    (configuration : ZigzagUpdateProduct)
    (hdone : allUpdateDone configuration.1 = true) :
    zigzagUpdateProductStep writes moves configuration =
      configuration := by
  have hcomponents :
      ∀ i : Fin 2,
        (configuration.1 i).isDone = true := by
    rw [allUpdateDone, Bool.and_eq_true] at hdone
    intro i
    fin_cases i
    · exact hdone.1
    · exact hdone.2
  apply Prod.ext
  · funext i
    have hlocal :=
      zigzagUpdateConfigurationStep_fixed_of_done
        (writes i) (moves i)
        (configuration.1 i, configuration.2 i)
        (hcomponents i)
    exact congrArg Prod.fst hlocal
  · funext i
    have hlocal :=
      zigzagUpdateConfigurationStep_fixed_of_done
        (writes i) (moves i)
        (configuration.1 i, configuration.2 i)
        (hcomponents i)
    exact congrArg Prod.snd hlocal

theorem iterate_eq_final_of_fixed
    {α : Type*} (step : α → α)
    (initial current final : α)
    (steps bound : Nat)
    (hle : steps ≤ bound)
    (hcurrent :
      (step^[steps]) initial = current)
    (hfixed : step current = current)
    (hfinal :
      (step^[bound]) initial = final) :
    current = final := by
  obtain ⟨extra, hbound⟩ :=
    Nat.exists_eq_add_of_le hle
  rw [hbound, Nat.add_comm,
    Function.iterate_add_apply, hcurrent] at hfinal
  have hiterate :
      (step^[extra]) current = current :=
    Function.iterate_fixed hfixed extra
  rw [hiterate] at hfinal
  exact hfinal

theorem zigzagSimulation_scan_reaches_final
    {baseStates : Nat}
    (baseMachine : Machine 2 baseStates)
    (baseState : Fin baseStates)
    (archives : Fin 2 → List TapeSymbol)
    (tapes : Fin 2 → Tape)
    (positions : Fin 2 → Int)
    (recordCount : Nat)
    (hroom :
      ∀ i : Fin 2,
        zigzagIndex (positions i) < recordCount) :
    ∃ steps ≤ 6 * maxZigzagIndex positions + 6,
      (((zigzagSimulationTypedMachine baseMachine).step)^[
        steps])
        (embedZigzagScanProduct baseState
          (startScanLocals,
            fun i =>
              (zigzagPhysicalTape
                (archives i) (tapes i) (positions i)
                recordCount).move .right)) =
      embedZigzagScanProduct baseState
        (fun i =>
            .done (tapes i).head
              (ZigzagIndexClass.atIndex
                (zigzagIndex (positions i))),
          fun i =>
            zigzagPhysicalTape
              (archives i) (tapes i) (positions i)
              recordCount) := by
  obtain ⟨steps, hsteps, hglobal, hdone⟩ :=
    zigzagSimulation_scan_reaches_done
      baseMachine baseState archives tapes positions
      recordCount hroom
  let initial : ZigzagScanProduct :=
    (startScanLocals,
      fun i =>
        (zigzagPhysicalTape
          (archives i) (tapes i) (positions i)
          recordCount).move .right)
  let current :=
    (zigzagScanProductStep^[steps]) initial
  let final : ZigzagScanProduct :=
    (fun i =>
        .done (tapes i).head
          (ZigzagIndexClass.atIndex
            (zigzagIndex (positions i))),
      fun i =>
        zigzagPhysicalTape
          (archives i) (tapes i) (positions i)
          recordCount)
  have hcurrent :
      (zigzagScanProductStep^[steps]) initial =
        current := rfl
  have hfixed :
      zigzagScanProductStep current = current :=
    zigzagScanProductStep_fixed_of_done
      current hdone
  have hfinal :
      (zigzagScanProductStep^[
        6 * maxZigzagIndex positions + 6]) initial =
          final := by
    exact zigzagScanProduct_physicalTapes
      archives tapes positions recordCount hroom
  have hcanonical :
      current = final :=
    iterate_eq_final_of_fixed
      zigzagScanProductStep initial current final
      steps (6 * maxZigzagIndex positions + 6)
      hsteps hcurrent hfixed hfinal
  refine ⟨steps, hsteps, ?_⟩
  simpa [initial, current, final, hcanonical] using hglobal

theorem zigzagSimulation_update_reaches_final
    {baseStates : Nat}
    (baseMachine : Machine 2 baseStates)
    (nextState : Fin baseStates)
    (archives : Fin 2 → List TapeSymbol)
    (tapes : Fin 2 → Tape)
    (positions : Fin 2 → Int)
    (recordCount : Nat)
    (writes : Fin 2 → TapeSymbol)
    (moves : Fin 2 → HeadMove)
    (hroom :
      ∀ i : Fin 2,
        zigzagIndex (positions i) + 2 < recordCount) :
    ∃ steps ≤ 6 * maxZigzagIndex positions + 23,
      (((zigzagSimulationTypedMachine baseMachine).step)^[
        steps])
        (embedZigzagUpdateProduct nextState writes moves
          (startUpdateLocals,
            fun i =>
              (zigzagPhysicalTape
                (archives i) (tapes i) (positions i)
                recordCount).move .right)) =
      embedZigzagUpdateProduct nextState writes moves
        (fun _ => .done,
          fun i =>
            zigzagPhysicalTape
              (archives i)
              (((tapes i).write (writes i)).move
                (moves i))
              ((moves i).updatePosition (positions i))
              recordCount) := by
  obtain ⟨steps, hsteps, hglobal, hdone⟩ :=
    zigzagSimulation_update_reaches_done
      baseMachine nextState archives tapes positions
      recordCount writes moves hroom
  let initial : ZigzagUpdateProduct :=
    (startUpdateLocals,
      fun i =>
        (zigzagPhysicalTape
          (archives i) (tapes i) (positions i)
          recordCount).move .right)
  let current :=
    ((zigzagUpdateProductStep writes moves)^[steps])
      initial
  let final : ZigzagUpdateProduct :=
    (fun _ => .done,
      fun i =>
        zigzagPhysicalTape
          (archives i)
          (((tapes i).write (writes i)).move
            (moves i))
          ((moves i).updatePosition (positions i))
          recordCount)
  have hcurrent :
      ((zigzagUpdateProductStep writes moves)^[steps])
          initial =
        current := rfl
  have hfixed :
      zigzagUpdateProductStep writes moves current =
        current :=
    zigzagUpdateProductStep_fixed_of_done
      writes moves current hdone
  have hfinal :
      ((zigzagUpdateProductStep writes moves)^[
        6 * maxZigzagIndex positions + 23]) initial =
          final := by
    exact zigzagUpdateProduct_physicalTapes
      archives tapes positions recordCount
      writes moves hroom
  have hcanonical :
      current = final :=
    iterate_eq_final_of_fixed
      (zigzagUpdateProductStep writes moves)
      initial current final steps
      (6 * maxZigzagIndex positions + 23)
      hsteps hcurrent hfixed hfinal
  refine ⟨steps, hsteps, ?_⟩
  simpa [initial, current, final, hcanonical] using hglobal

def zigzagReadyConfiguration
    {baseStates : Nat}
    (configuration : Configuration 2 baseStates)
    (archives : Fin 2 → List TapeSymbol)
    (positions : Fin 2 → Int)
    (recordCount : Nat) :
    TypedConfiguration 2
      (ZigzagSimulationState baseStates) :=
  ⟨.ready configuration.state,
    fun i =>
      zigzagPhysicalTape
        (archives i) (configuration.tape i)
        (positions i) recordCount⟩

theorem Tape.write_head (tape : Tape) :
    tape.write tape.head = tape := by
  cases tape
  rfl

theorem zigzagSimulation_ready_step
    {baseStates : Nat}
    (baseMachine : Machine 2 baseStates)
    (configuration : Configuration 2 baseStates)
    (archives : Fin 2 → List TapeSymbol)
    (positions : Fin 2 → Int)
    (recordCount : Nat)
    (hresult :
      baseMachine.result configuration.state = none) :
    (zigzagSimulationTypedMachine baseMachine).step
        (zigzagReadyConfiguration configuration archives
          positions recordCount) =
      embedZigzagScanProduct configuration.state
        (startScanLocals,
          fun i =>
            (zigzagPhysicalTape
              (archives i) (configuration.tape i)
              (positions i) recordCount).move .right) := by
  unfold TypedMachine.step zigzagReadyConfiguration
    embedZigzagScanProduct
  rw [show
      (zigzagSimulationTypedMachine baseMachine).result
          (.ready configuration.state) =
        none by
      exact hresult]
  simp only [zigzagSimulationTypedMachine]
  congr 1

theorem zigzagSimulation_scan_done_step
    {baseStates : Nat}
    (baseMachine : Machine 2 baseStates)
    (baseState : Fin baseStates)
    (archives : Fin 2 → List TapeSymbol)
    (tapes : Fin 2 → Tape)
    (positions : Fin 2 → Int)
    (recordCount : Nat) :
    let action :=
      baseMachine.transition baseState
        (fun i => (tapes i).head)
    (zigzagSimulationTypedMachine baseMachine).step
        (embedZigzagScanProduct baseState
          (fun i =>
              .done (tapes i).head
                (ZigzagIndexClass.atIndex
                  (zigzagIndex (positions i))),
            fun i =>
              zigzagPhysicalTape
                (archives i) (tapes i) (positions i)
                recordCount)) =
      embedZigzagUpdateProduct action.1
        (fun i => (action.2 i).1)
        (fun i => (action.2 i).2)
        (startUpdateLocals,
          fun i =>
            (zigzagPhysicalTape
              (archives i) (tapes i) (positions i)
              recordCount).move .right) := by
  dsimp only
  unfold TypedMachine.step embedZigzagScanProduct
    embedZigzagUpdateProduct
  simp only [zigzagSimulationTypedMachine,
    allScanDone, ZigzagScanLocal.isDone,
    ZigzagScanLocal.symbol, Bool.true_and,
    ↓reduceDIte, Tape.write_head]

theorem zigzagSimulation_update_done_step
    {baseStates : Nat}
    (baseMachine : Machine 2 baseStates)
    (nextState : Fin baseStates)
    (archives : Fin 2 → List TapeSymbol)
    (tapes : Fin 2 → Tape)
    (positions : Fin 2 → Int)
    (recordCount : Nat)
    (writes : Fin 2 → TapeSymbol)
    (moves : Fin 2 → HeadMove) :
    (zigzagSimulationTypedMachine baseMachine).step
        (embedZigzagUpdateProduct nextState writes moves
          (fun _ => .done,
            fun i =>
              zigzagPhysicalTape
                (archives i)
                (((tapes i).write (writes i)).move
                  (moves i))
                ((moves i).updatePosition (positions i))
                recordCount)) =
      zigzagReadyConfiguration
        ⟨nextState,
          fun i =>
            ((tapes i).write (writes i)).move
              (moves i)⟩
        archives
        (fun i =>
          (moves i).updatePosition (positions i))
        recordCount := by
  unfold TypedMachine.step embedZigzagUpdateProduct
    zigzagReadyConfiguration
  simp only [zigzagSimulationTypedMachine,
    allUpdateDone, ZigzagUpdateLocal.isDone,
    Bool.true_and, ↓reduceDIte, Tape.write_head,
    Tape.move]

def ReachesWithin {α : Type*}
    (step : α → α) (initial final : α)
    (bound : Nat) : Prop :=
  ∃ steps ≤ bound,
    (step^[steps]) initial = final

theorem ReachesWithin.refl
    {α : Type*} (step : α → α) (initial : α)
    (bound : Nat) :
    ReachesWithin step initial initial bound :=
  ⟨0, Nat.zero_le _, rfl⟩

theorem ReachesWithin.mono
    {α : Type*} {step : α → α}
    {initial final : α} {firstBound secondBound : Nat}
    (hreaches :
      ReachesWithin step initial final firstBound)
    (hle : firstBound ≤ secondBound) :
    ReachesWithin step initial final secondBound := by
  rcases hreaches with ⟨steps, hsteps, hrun⟩
  exact ⟨steps, Nat.le_trans hsteps hle, hrun⟩

theorem ReachesWithin.trans
    {α : Type*} {step : α → α}
    {first second third : α}
    {firstBound secondBound : Nat}
    (hfirst :
      ReachesWithin step first second firstBound)
    (hsecond :
      ReachesWithin step second third secondBound) :
    ReachesWithin step first third
      (firstBound + secondBound) := by
  rcases hfirst with
    ⟨firstSteps, hfirstSteps, hfirstRun⟩
  rcases hsecond with
    ⟨secondSteps, hsecondSteps, hsecondRun⟩
  refine
    ⟨firstSteps + secondSteps,
      Nat.add_le_add hfirstSteps hsecondSteps, ?_⟩
  rw [Nat.add_comm, Function.iterate_add_apply,
    hfirstRun, hsecondRun]

theorem ReachesWithin.one
    {α : Type*} (step : α → α) (initial : α) :
    ReachesWithin step initial (step initial) 1 :=
  ⟨1, Nat.le_refl _, rfl⟩

theorem zigzagSimulation_reaches_base_step
    {baseStates : Nat}
    (baseMachine : Machine 2 baseStates)
    (configuration : Configuration 2 baseStates)
    (archives : Fin 2 → List TapeSymbol)
    (positions : Fin 2 → Int)
    (recordCount : Nat)
    (hresult :
      baseMachine.result configuration.state = none)
    (hroom :
      ∀ i : Fin 2,
        zigzagIndex (positions i) + 2 < recordCount) :
    let action :=
      baseMachine.transition configuration.state
        (fun i => (configuration.tape i).head)
    ReachesWithin
      (zigzagSimulationTypedMachine baseMachine).step
      (zigzagReadyConfiguration configuration archives
        positions recordCount)
      (zigzagReadyConfiguration
        (baseMachine.step configuration) archives
        (fun i =>
          (action.2 i).2.updatePosition (positions i))
        recordCount)
      (12 * maxZigzagIndex positions + 32) := by
  dsimp only
  let action :=
    baseMachine.transition configuration.state
      (fun i => (configuration.tape i).head)
  let scanInitial : ZigzagScanProduct :=
    (startScanLocals,
      fun i =>
        (zigzagPhysicalTape
          (archives i) (configuration.tape i)
          (positions i) recordCount).move .right)
  let scanFinal : ZigzagScanProduct :=
    (fun i =>
        .done (configuration.tape i).head
          (ZigzagIndexClass.atIndex
            (zigzagIndex (positions i))),
      fun i =>
        zigzagPhysicalTape
          (archives i) (configuration.tape i)
          (positions i) recordCount)
  let updateInitial : ZigzagUpdateProduct :=
    (startUpdateLocals,
      fun i =>
        (zigzagPhysicalTape
          (archives i) (configuration.tape i)
          (positions i) recordCount).move .right)
  let updateFinal : ZigzagUpdateProduct :=
    (fun _ => .done,
      fun i =>
        zigzagPhysicalTape
          (archives i)
          (((configuration.tape i).write
            (action.2 i).1).move (action.2 i).2)
          ((action.2 i).2.updatePosition (positions i))
          recordCount)
  let globalStep :=
    (zigzagSimulationTypedMachine baseMachine).step
  have hready :
      ReachesWithin globalStep
        (zigzagReadyConfiguration configuration archives
          positions recordCount)
        (embedZigzagScanProduct configuration.state
          scanInitial)
        1 := by
    refine ⟨1, Nat.le_refl _, ?_⟩
    simpa [globalStep, scanInitial] using
      zigzagSimulation_ready_step
        baseMachine configuration archives positions
        recordCount hresult
  have hscanRoom :
      ∀ i : Fin 2,
        zigzagIndex (positions i) < recordCount := by
    intro i
    have := hroom i
    omega
  have hscan :
      ReachesWithin globalStep
        (embedZigzagScanProduct configuration.state
          scanInitial)
        (embedZigzagScanProduct configuration.state
          scanFinal)
        (6 * maxZigzagIndex positions + 6) := by
    obtain ⟨steps, hsteps, hrun⟩ :=
      zigzagSimulation_scan_reaches_final
        baseMachine configuration.state archives
        configuration.tape positions recordCount
        hscanRoom
    exact
      ⟨steps, hsteps,
        by simpa [globalStep, scanInitial, scanFinal]
          using hrun⟩
  have hscanDone :
      ReachesWithin globalStep
        (embedZigzagScanProduct configuration.state
          scanFinal)
        (embedZigzagUpdateProduct action.1
          (fun i => (action.2 i).1)
          (fun i => (action.2 i).2)
          updateInitial)
        1 := by
    refine ⟨1, Nat.le_refl _, ?_⟩
    simpa [globalStep, scanFinal, updateInitial,
      action] using
      zigzagSimulation_scan_done_step
        baseMachine configuration.state archives
        configuration.tape positions recordCount
  have hupdate :
      ReachesWithin globalStep
        (embedZigzagUpdateProduct action.1
          (fun i => (action.2 i).1)
          (fun i => (action.2 i).2)
          updateInitial)
        (embedZigzagUpdateProduct action.1
          (fun i => (action.2 i).1)
          (fun i => (action.2 i).2)
          updateFinal)
        (6 * maxZigzagIndex positions + 23) := by
    obtain ⟨steps, hsteps, hrun⟩ :=
      zigzagSimulation_update_reaches_final
        baseMachine action.1 archives configuration.tape
        positions recordCount
        (fun i => (action.2 i).1)
        (fun i => (action.2 i).2)
        hroom
    exact
      ⟨steps, hsteps,
        by simpa [globalStep, updateInitial, updateFinal]
          using hrun⟩
  let steppedConfiguration : Configuration 2 baseStates :=
    ⟨action.1,
      fun i =>
        ((configuration.tape i).write
          (action.2 i).1).move (action.2 i).2⟩
  have hbaseStep :
      baseMachine.step configuration =
        steppedConfiguration := by
    simp [Machine.step, hresult, steppedConfiguration,
      action]
  have hupdateDone :
      ReachesWithin globalStep
        (embedZigzagUpdateProduct action.1
          (fun i => (action.2 i).1)
          (fun i => (action.2 i).2)
          updateFinal)
        (zigzagReadyConfiguration steppedConfiguration
          archives
          (fun i =>
            (action.2 i).2.updatePosition (positions i))
          recordCount)
        1 := by
    refine ⟨1, Nat.le_refl _, ?_⟩
    simpa [globalStep, updateFinal,
      steppedConfiguration] using
      zigzagSimulation_update_done_step
        baseMachine action.1 archives
        configuration.tape positions recordCount
        (fun i => (action.2 i).1)
        (fun i => (action.2 i).2)
  have htotal :=
    ((((hready.trans hscan).trans hscanDone).trans
      hupdate).trans hupdateDone)
  rw [hbaseStep]
  apply htotal.mono
  simp only [maxZigzagIndex]
  omega

theorem zigzagIndex_updatePosition_le_add_two
    (position : Int) (move : HeadMove) :
    zigzagIndex (move.updatePosition position) ≤
      zigzagIndex position + 2 := by
  have hposition :=
    zigzagIndex_updatePosition position move
  simp only at hposition
  cases hrelocation :
      zigzagRelocation move
        (ZigzagIndexClass.atIndex
          (zigzagIndex position)) with
  | none =>
      rw [hrelocation] at hposition
      omega
  | some relocation =>
      rcases relocation with ⟨direction, distance⟩
      rw [hrelocation] at hposition
      cases direction with
      | inward =>
          simp at hposition
          omega
      | outward =>
          simp at hposition
          have hdistance : distance.val / 3 ≤ 2 := by
            omega
          omega

def zigzagRunPositions
    {baseStates : Nat}
    (baseMachine : Machine 2 baseStates)
    (input : Fin 2 → List Bool) :
    Nat → (Fin 2 → Int)
  | 0 => fun _ => 0
  | steps + 1 =>
      let configuration := baseMachine.run input steps
      match baseMachine.result configuration.state with
      | some _ => zigzagRunPositions baseMachine input steps
      | none =>
          let action :=
            baseMachine.transition configuration.state
              (fun i => (configuration.tape i).head)
          fun i =>
            (action.2 i).2.updatePosition
              (zigzagRunPositions baseMachine input steps i)

theorem zigzagRunPositions_index_bound
    {baseStates : Nat}
    (baseMachine : Machine 2 baseStates)
    (input : Fin 2 → List Bool)
    (steps : Nat) (i : Fin 2) :
    zigzagIndex
        (zigzagRunPositions baseMachine input steps i) ≤
      2 * steps := by
  induction steps with
  | zero =>
      simp [zigzagRunPositions, zigzagIndex]
  | succ steps ih =>
      cases hresult :
          baseMachine.result
            (baseMachine.run input steps).state with
      | some result =>
          simp [zigzagRunPositions, hresult]
          exact Nat.le_trans ih (by omega)
      | none =>
        simp only [zigzagRunPositions, hresult]
        exact
          Nat.le_trans
            (zigzagIndex_updatePosition_le_add_two
              (zigzagRunPositions baseMachine input steps i)
              ((baseMachine.transition
                (baseMachine.run input steps).state
                (fun i =>
                  ((baseMachine.run input steps).tape i).head)
                ).2 i).2)
            (by omega)

theorem maxZigzagIndex_runPositions_bound
    {baseStates : Nat}
    (baseMachine : Machine 2 baseStates)
    (input : Fin 2 → List Bool)
    (steps : Nat) :
    maxZigzagIndex
        (zigzagRunPositions baseMachine input steps) ≤
      2 * steps := by
  unfold maxZigzagIndex
  rw [Nat.max_le]
  constructor
  · exact zigzagRunPositions_index_bound
      baseMachine input steps 0
  · exact zigzagRunPositions_index_bound
      baseMachine input steps 1

theorem zigzagSimulation_reaches_run
    {baseStates : Nat}
    (baseMachine : Machine 2 baseStates)
    (input : Fin 2 → List Bool)
    (archives : Fin 2 → List TapeSymbol)
    (steps horizon : Nat)
    (hsteps : steps ≤ horizon) :
    ReachesWithin
      (zigzagSimulationTypedMachine baseMachine).step
      (zigzagReadyConfiguration
        (baseMachine.run input 0) archives
        (zigzagRunPositions baseMachine input 0)
        (2 * horizon + 3))
      (zigzagReadyConfiguration
        (baseMachine.run input steps) archives
        (zigzagRunPositions baseMachine input steps)
        (2 * horizon + 3))
      (steps * (24 * horizon + 32)) := by
  induction steps with
  | zero =>
      exact ReachesWithin.refl _ _ _
  | succ steps ih =>
      have hstepsLe : steps ≤ horizon := by omega
      have hprevious :=
        ih hstepsLe
      let configuration := baseMachine.run input steps
      let positions :=
        zigzagRunPositions baseMachine input steps
      let recordCount := 2 * horizon + 3
      let macroBound := 24 * horizon + 32
      by_cases hhalted :
          ∃ result,
            baseMachine.result configuration.state =
              some result
      · rcases hhalted with ⟨result, hresult⟩
        have hmachineStep :
            baseMachine.step configuration =
              configuration :=
          by
            simp [Machine.step, hresult]
        have hpositionStep :
            zigzagRunPositions baseMachine input
                (steps + 1) =
              positions := by
          simp [zigzagRunPositions, configuration,
            positions, hresult]
        have hrunStep :
            baseMachine.run input (steps + 1) =
              configuration := by
          rw [Machine.run, hmachineStep]
        have hstay :
            ReachesWithin
              (zigzagSimulationTypedMachine baseMachine).step
              (zigzagReadyConfiguration configuration archives
                positions recordCount)
              (zigzagReadyConfiguration
                (baseMachine.run input (steps + 1))
                archives
                (zigzagRunPositions baseMachine input
                  (steps + 1))
                recordCount)
              macroBound := by
          rw [hrunStep, hpositionStep]
          exact ReachesWithin.refl _ _ _
        have hcombined := hprevious.trans hstay
        simpa [configuration, positions, recordCount,
          macroBound, Nat.succ_eq_add_one,
          Nat.add_mul] using hcombined
      · have hresult :
            baseMachine.result configuration.state =
              none := by
          cases h :
              baseMachine.result configuration.state with
          | none => rfl
          | some result =>
              exact False.elim
                (hhalted ⟨result, h⟩)
        let action :=
          baseMachine.transition configuration.state
            (fun i => (configuration.tape i).head)
        have hpositionStep :
            zigzagRunPositions baseMachine input
                (steps + 1) =
              fun i =>
                (action.2 i).2.updatePosition
                  (positions i) := by
          simp [zigzagRunPositions, configuration,
            positions, action, hresult]
        have hrunStep :
            baseMachine.run input (steps + 1) =
              baseMachine.step configuration := by
          rfl
        have hroom :
            ∀ i : Fin 2,
              zigzagIndex (positions i) + 2 <
                recordCount := by
          intro i
          have hindex :=
            zigzagRunPositions_index_bound
              baseMachine input steps i
          simp only [positions, recordCount]
          omega
        have hone :=
          zigzagSimulation_reaches_base_step
            baseMachine configuration archives positions
            recordCount hresult hroom
        have hmacro :
            12 * maxZigzagIndex positions + 32 ≤
              macroBound := by
          have hmax :=
            maxZigzagIndex_runPositions_bound
              baseMachine input steps
          simp only [positions, macroBound]
          omega
        have hone' := hone.mono hmacro
        have hcombined := hprevious.trans hone'
        rw [hrunStep, hpositionStep]
        simpa [configuration, positions, recordCount,
          macroBound, Nat.succ_eq_add_one,
          Nat.add_mul] using hcombined

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