Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

The simulation invariant and the packaged track update

Definition
sgl_step_pieces

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

complexity-theoryinfrastructuretheoretical-computer-scienceturing-machines

Pieces of the per-step theorem: the simulation invariant, the symbol-view identification, and the packaged track update.

MergeInv is the full simulation invariant. The physical tapes below the host index are the corresponding virtual tapes (identity-mapped, so the simulated machine's writes and moves apply to them directly); the host tape carries the remaining two virtual tapes as a parked two-track region with an all-blank ghost; and the two tracks satisfy HostsPair.

hostSyms_eq is the identification that makes the execute phase correct: the symbol view the step program assembles equals the simulated machine's true view k↦(virt.tape k).headk \mapsto (\mathrm{virt.tape}\ k).\mathrm{head}k↦(virt.tape k).head. Below the host index the physical head is the virtual head by identity-mapping; at the two hosted indices, the symbols the read phases learned are the virtual heads by HostsPair.head_eq. So the transition the program applies is the transition the simulated machine would take.

updateTrack_step packages all of module D's and the invariant layer's case analysis into one uniform fact. Given the invariant and a write-and-move for one track, the update halts within 100∣blocks∣+300100|{\rm blocks}| + 300100∣blocks∣+300 steps, leaves the host tape parked on a new region, and re-establishes MergeInv with that track's virtual tape written and moved and the other untouched. Internally it selects among the five bounded specifications and pairs each with its matching HostsPair preservation — three head-moves, two of which split at the region's edges. The per-step theorem therefore sees a single fact per track rather than a five-way case analysis, and the nine-case product across two tracks never arises.

Formalization note. virtTape_update_apply transports an update at a hosted virtual index through the two-track view; stated pointwise rather than as a function equality, it rewrites under binders and keeps the preservation proofs to two lines each.

Definition code
import Definitions.Def_sgl_bounded_specs

/-!
# Pieces of the per-step theorem

Module E3b of the merge_empty plan, first part: the small facts the per-step
theorem needs, isolated and proved before the large composition depends on
them.

The two with real content:

* `hostSyms_eq` — the symbol view the step program assembles equals the
  simulated machine's *true* view.  The identity-mapped tapes contribute
  their physical heads (they are literally the virtual tapes), and the two
  hosted tracks contribute the symbols the read phases learned, which
  `HostsPair.head_eq` identifies with the virtual heads.
* `MergeInv` — the full simulation invariant, and its head-symbol corollary.
-/

namespace SipserGacsLautemann

/-! ## Track sides as virtual indices -/

@[simp] theorem hostIdx_A_val (tapes' : Nat) :
    (hostIdx tapes' TrackSide.A).val = tapes' := rfl

@[simp] theorem hostIdx_B_val (tapes' : Nat) :
    (hostIdx tapes' TrackSide.B).val = tapes' + 1 := rfl

/-! ## The full invariant -/

/-- The simulation invariant: the identity-mapped physical tapes *are* the
corresponding virtual tapes, the host tape carries the other two as a parked
two-track region, and the control carries the simulated state. -/
structure MergeInv {states : Nat} (tapes' : Nat)
    (virt : Configuration (tapes' + 2) states)
    (phys : Fin (tapes' + 1) → Tape) (blocks : List Block)
    (G : List TapeSymbol) : Prop where
  ident : ∀ j : Fin (tapes' + 1), j.val < tapes' →
    phys j = virt.tape ⟨j.val, by omega⟩
  parked : phys (Fin.last tapes') = ParkedTape blocks G
  ghost : AllBlank G
  hosts : HostsPair blocks
    (fun side => virt.tape (hostIdx tapes' side))

/-- The symbol view the step program assembles is the simulated machine's true
view.  Below `tapes'` the physical head *is* the virtual head; at the two
hosted indices the learned symbols are the virtual heads by `HostsPair`. -/
theorem hostSyms_eq {states : Nat} {tapes' : Nat}
    {virt : Configuration (tapes' + 2) states}
    {phys : Fin (tapes' + 1) → Tape} {blocks : List Block}
    {G : List TapeSymbol} (h : MergeInv tapes' virt phys blocks G)
    {preA : List Block} {curA : Block} {postA : List Block}
    (hA : SplitAtFlag TrackSide.A blocks preA curA postA)
    {preB : List Block} {curB : Block} {postB : List Block}
    (hB : SplitAtFlag TrackSide.B blocks preB curB postB) :
    hostSyms tapes' (fun j => (phys j).head)
        (TrackSide.A.pick curA) (TrackSide.B.pick curB) =
      fun k => (virt.tape k).head := by
  funext k
  rw [hostSyms]
  by_cases hk : k.val < tapes'
  · rw [dif_pos hk, h.ident ⟨k.val, by omega⟩ hk]
  · rw [dif_neg hk]
    by_cases hk2 : k.val = tapes'
    · rw [if_pos hk2, h.hosts.head_eq TrackSide.A hA]
      exact congrArg (fun t : Tape => t.head)
        (congrArg virt.tape (Fin.ext (by simp [hostIdx, hk2])))
    · rw [if_neg hk2, h.hosts.head_eq TrackSide.B hB]
      have hval : k.val = tapes' + 1 := by omega
      exact congrArg (fun t : Tape => t.head)
        (congrArg virt.tape (Fin.ext (by simp [hostIdx, hval])))

/-! ## The execute step's tape effect -/

/-- The execute action leaves the host tape alone. -/
theorem execAction_host {states : Nat} (tapes' : Nat)
    (M : Machine (tapes' + 2) states) (q : Fin states) (sA sB : TapeSymbol)
    (syms : Fin (tapes' + 1) → TapeSymbol) :
    execAction tapes' M q sA sB syms (Fin.last tapes') =
      (syms (Fin.last tapes'), HeadMove.stay) := by
  rw [execAction, dif_neg (by simp)]

/-- …so applying it preserves the host tape exactly. -/
theorem applyAction_execAction_host {states : Nat} (tapes' : Nat)
    (M : Machine (tapes' + 2) states) (q : Fin states) (sA sB : TapeSymbol)
    (tape : Fin (tapes' + 1) → Tape) :
    applyAction tape (execAction tapes' M q sA sB) (Fin.last tapes') =
      tape (Fin.last tapes') := by
  rw [applyAction, execAction_host]
  simp [Tape.write_head_self, Tape.move]

/-- On an identity-mapped tape the execute action applies the simulated
machine's own action. -/
theorem applyAction_execAction_ident {states : Nat} (tapes' : Nat)
    (M : Machine (tapes' + 2) states) (q : Fin states) (sA sB : TapeSymbol)
    (tape : Fin (tapes' + 1) → Tape) (j : Fin (tapes' + 1))
    (hj : j.val < tapes') :
    applyAction tape (execAction tapes' M q sA sB) j =
      Tape.move
        (Tape.write (tape j)
          ((M.transition q (hostSyms tapes' (fun l => (tape l).head) sA sB)).2
            ⟨j.val, by omega⟩).1)
        ((M.transition q (hostSyms tapes' (fun l => (tape l).head) sA sB)).2
          ⟨j.val, by omega⟩).2 := by
  rw [applyAction, execAction, dif_pos hj]

/-! ## The simulated step, unfolded -/

/-- While the simulated machine is live, its step applies its transition. -/
theorem Machine.step_of_result_none {n states : Nat}
    (M : Machine n states) (c : Configuration n states)
    (h : M.result c.state = none) :
    M.step c =
      { state := (M.transition c.state (fun i => (c.tape i).head)).1
        tape := fun i =>
          Tape.move
            (Tape.write (c.tape i)
              ((M.transition c.state (fun i => (c.tape i).head)).2 i).1)
            ((M.transition c.state (fun i => (c.tape i).head)).2 i).2 } := by
  unfold Machine.step
  rw [h]


theorem hostIdx_ne {tapes' : Nat} {side side' : TrackSide} (h : side' ≠ side) :
    hostIdx tapes' side' ≠ hostIdx tapes' side := by
  cases side <;> cases side' <;>
    first
      | exact absurd rfl h
      | (intro hcon; have := congrArg Fin.val hcon; simp [hostIdx] at this)

/-- Updating a virtual tape at a hosted index, viewed through the two tracks. -/
@[simp] theorem virtTape_update_apply (tapes' : Nat)
    (vt : Fin (tapes' + 2) → Tape) (side side' : TrackSide) (X : Tape) :
    Function.update vt (hostIdx tapes' side) X (hostIdx tapes' side') =
      Function.update (fun s' => vt (hostIdx tapes' s')) side X side' := by
  by_cases hss : side' = side
  · subst hss; simp
  · rw [Function.update_of_ne hss, Function.update_of_ne (hostIdx_ne hss)]

/-! ## The single-track update, packaged

One theorem covering all three head-moves and both edges: given the invariant
and a write-and-move for one track, the update halts within an affine bound and
re-establishes the invariant with that track's virtual tape written and moved,
the other untouched.  The five bounded specifications and the five `HostsPair`
preservations are matched up here, once, so the per-step theorem sees a single
uniform fact. -/

theorem updateTrack_step {states : Nat} {tapes' : Nat}
    {virt : Configuration (tapes' + 2) states}
    {phys : Fin (tapes' + 1) → Tape} {blocks : List Block}
    {G : List TapeSymbol} (h : MergeInv tapes' virt phys blocks G)
    (side : TrackSide) (s : TapeSymbol) (mv : HeadMove) :
    ∃ (cost : Nat) (blocks' : List Block) (G' : List TapeSymbol),
      cost ≤ 100 * blocks.length + 300 ∧
      HaltsExactly (updateTrack side (Fin.last tapes') s mv)
        ((updateTrack side (Fin.last tapes') s mv).startCfg phys) cost false ∧
      (((updateTrack side (Fin.last tapes') s mv).step^[cost])
        ((updateTrack side (Fin.last tapes') s mv).startCfg phys)).tape =
        Function.update phys (Fin.last tapes') (ParkedTape blocks' G') ∧
      MergeInv tapes'
        { state := virt.state
          tape := Function.update virt.tape (hostIdx tapes' side)
            (Tape.move (Tape.write (virt.tape (hostIdx tapes' side)) s) mv) }
        (Function.update phys (Fin.last tapes') (ParkedTape blocks' G'))
        blocks' G' := by
  classical
  obtain ⟨pre, cur, post, hsplit, -⟩ := h.hosts side
  have hblocks := hsplit.eq
  subst hblocks
  -- the invariant's non-host components are untouched by every variant
  have hident : ∀ (bl : List Block) (Gx : List TapeSymbol),
      ∀ j : Fin (tapes' + 1), j.val < tapes' →
        (Function.update phys (Fin.last tapes') (ParkedTape bl Gx)) j =
          (Function.update virt.tape (hostIdx tapes' side)
            (Tape.move (Tape.write (virt.tape (hostIdx tapes' side)) s) mv))
            ⟨j.val, by omega⟩ := by
    intro bl Gx j hj
    have hne : j ≠ Fin.last tapes' := by
      intro hcon
      rw [hcon] at hj
      simp at hj
    have hne2 : (⟨j.val, by omega⟩ : Fin (tapes' + 2)) ≠ hostIdx tapes' side := by
      intro hcon
      have := congrArg Fin.val hcon
      cases side <;> simp [hostIdx] at this <;> omega
    rw [Function.update_of_ne hne, Function.update_of_ne hne2]
    exact h.ident j hj
  have hpark : ∀ (bl : List Block) (Gx : List TapeSymbol),
      (Function.update phys (Fin.last tapes') (ParkedTape bl Gx))
        (Fin.last tapes') = ParkedTape bl Gx := by
    intro bl Gx; simp
  cases mv with
  | stay =>
      obtain ⟨cost, hbound, hrun⟩ := updateTrack_stay_bounded side
        (Fin.last tapes') s pre cur post hsplit.preClear hsplit.curSet
      obtain ⟨G', hG', hhalt, htape⟩ := hrun G phys h.ghost h.parked
      refine ⟨cost, pre ++ setSymFlag side s true cur :: post, G', hbound,
        hhalt, htape, ?_, hpark _ _, hG', ?_⟩
      · exact hident _ _
      · have := h.hosts.update_stay side hsplit s
        simp only [virtTape_update_apply]
        exact this
  | right =>
      cases post with
      | cons nxt post' =>
          obtain ⟨cost, hbound, hrun⟩ := updateTrack_right_cons_bounded side
            (Fin.last tapes') s pre cur nxt post' hsplit.preClear hsplit.curSet
          obtain ⟨G', hG', hhalt, htape⟩ := hrun G phys h.ghost h.parked
          refine ⟨cost, pre ++ setSymFlag side s false cur ::
            setFlag side true nxt :: post', G', hbound, hhalt, htape,
            ?_, hpark _ _, hG', ?_⟩
          · exact hident _ _
          · have := h.hosts.update_right_mid side hsplit s
            simp only [virtTape_update_apply]
            exact this
      | nil =>
          obtain ⟨cost, hbound, hrun⟩ := updateTrack_right_nil_bounded side
            (Fin.last tapes') s pre cur hsplit.preClear hsplit.curSet
          obtain ⟨G', hG', hhalt, htape⟩ := hrun G phys h.ghost h.parked
          refine ⟨cost, pre ++ [setSymFlag side s false cur,
            freshFlagged side], G', hbound, hhalt, htape,
            ?_, hpark _ _, hG', ?_⟩
          · exact hident _ _
          · have := h.hosts.update_right_edge side hsplit s
            simp only [virtTape_update_apply]
            exact this
  | left =>
      rcases List.eq_nil_or_concat pre with rfl | ⟨pre', prv, rfl⟩
      · obtain ⟨cost, hbound, hrun⟩ := updateTrack_left_nil_bounded side
          (Fin.last tapes') s cur post hsplit.curSet
        obtain ⟨G', hG', hhalt, htape⟩ := hrun G phys h.ghost
          (by simpa using h.parked)
        refine ⟨cost, freshFlagged side :: setSymFlag side s false cur :: post,
          G', hbound, ?_, ?_, ?_, hpark _ _, hG', ?_⟩
        · simpa using hhalt
        · simpa using htape
        · exact hident _ _
        · have := h.hosts.update_left_edge side (by simpa using hsplit) s
          simp only [virtTape_update_apply]
          exact this
      · simp only [List.concat_eq_append] at *
        obtain ⟨cost, hbound, hrun⟩ := updateTrack_left_concat_bounded side
          (Fin.last tapes') s pre' prv cur post hsplit.preClear hsplit.curSet
        obtain ⟨G', hG', hhalt, htape⟩ := hrun G phys h.ghost h.parked
        refine ⟨cost, pre' ++ setFlag side true prv ::
          setSymFlag side s false cur :: post, G', hbound, hhalt, htape,
          ?_, hpark _ _, hG', ?_⟩
        · exact hident _ _
        · have := h.hosts.update_left_mid side hsplit s
          simp only [virtTape_update_apply]
          exact this

end SipserGacsLautemann
Source
Components of the per-step simulation theorem for two-track hosting; builds on Def_sgl_bounded_specs.

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