Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

The simulation trajectory

Definition
sgl_merge_round

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

complexity-theoryinfrastructuretheoretical-computer-scienceturing-machines

The simulation trajectory: the per-step theorem packaged as a round-indexed family.

MergeRound bundles everything one round needs and everything it returns — the simulated configuration, the identity class of physical tapes, the hosted region with its ghost, and the two invariant components (identity-mapping and HostsPair). Splitting the invariant this way matters: the parked component depends on the ghost while the other two do not, so a record yields the invariant at every ghost, which is the form the per-step theorem consumes.

round_exists repackages stepProgram_spec as a single existential over such records. That is what makes the trajectory one application of choice per round instead of a nest of them: rstep chooses a successor record and that round's cost together, traj iterates it, and rounds after the simulated machine halts stand still.

Two consequences are then immediate by induction: the simulated configuration after nnn rounds is M.step[n]M.\mathrm{step}^{[n]}M.step[n] of the initial one (while the machine stays live), and the hosted region grows by at most two blocks per round, so ∣blocksn∣≤∣blocks0∣+2n|{\rm blocks}_n| \le |{\rm blocks}_0| + 2n∣blocksn​∣≤∣blocks0​∣+2n and the per-round cost is bounded by 500(∣blocks0∣+2n)+1500500(|{\rm blocks}_0| + 2n) + 1500500(∣blocks0​∣+2n)+1500 — linear in the round index, which is what makes the whole simulation quadratic.

Definition code
import Definitions.Def_sgl_step_spec

/-!
# The simulation trajectory

Module F1 of DESIGN_step_spec_endgame, first part.

`MergeRound` bundles everything the per-step theorem needs and everything it
returns: the simulated configuration, the identity class of physical tapes, the
hosted region and its ghost, and the two invariant components.  `round_exists`
is `stepProgram_spec` repackaged as a single existential over such records, so
the trajectory is one application of choice per round rather than a nest of
them.

`traj` is then the round-indexed family, and `roundCost` its per-round cost.
-/

namespace SipserGacsLautemann

variable {states : Nat}

/-- The state of the simulation between rounds. -/
structure MergeRound (tapes' : Nat) (M : Machine (tapes' + 2) states) where
  virt : Configuration (tapes' + 2) states
  base : Fin (tapes' + 1) → Tape
  blocks : List Block
  ghost : List TapeSymbol
  hg : AllBlank ghost
  hident : IdentPart tapes' virt base
  hosts : HostsPair blocks (fun sd => virt.tape (hostIdx tapes' sd))

namespace MergeRound

variable {tapes' : Nat} {M : Machine (tapes' + 2) states}

/-- The physical tape configuration this round starts from. -/
def park (R : MergeRound tapes' M) : Fin (tapes' + 1) → Tape :=
  Function.update R.base (Fin.last tapes') (ParkedTape R.blocks R.ghost)

/-- The invariant, at every ghost — the form `stepProgram_spec` consumes. -/
theorem mergeInv (R : MergeRound tapes' M) (G : List TapeSymbol)
    (hG : AllBlank G) :
    MergeInv tapes' R.virt
      (Function.update R.base (Fin.last tapes') (ParkedTape R.blocks G))
      R.blocks G := by
  refine ⟨?_, by simp, hG, R.hosts⟩
  intro j hj
  have hne : j ≠ Fin.last tapes' := by
    intro hcon; rw [hcon] at hj; simp at hj
  rw [Function.update_of_ne hne]
  exact R.hident j hj

end MergeRound

/-- Seven `andThen` layers over a continuation state — the shape of one read
phase's terminal control state. -/
abbrev Layer7 (A₁ A₂ A₃ A₄ A₅ A₆ A₇ X : Type) : Type :=
  A₁ ⊕ Bool × (A₂ ⊕ Bool × (A₃ ⊕ Bool × (A₄ ⊕ Bool ×
    (A₅ ⊕ Bool × (A₆ ⊕ Bool × (A₇ ⊕ Bool × X))))))

/-- The execute tail's terminal control state: a state-dispatch layer over two
`andThen` layers over the parked next state. -/
abbrev TailState (U V W : Type) (states : Nat) : Type :=
  U ⊕ U × (V ⊕ Bool × (W ⊕ Bool × Option (Fin states)))

/-- The next simulated state, read off a terminal control state of
`stepProgram` by peeling its composition layers. -/
def nextState {A₁ A₂ A₃ A₄ A₅ A₆ A₇ B₁ B₂ B₃ B₄ B₅ B₆ B₇ U V W : Type}
    (b : Layer7 A₁ A₂ A₃ A₄ A₅ A₆ A₇
      (Layer7 B₁ B₂ B₃ B₄ B₅ B₆ B₇ (TailState U V W states))) :
    Option (Fin states) :=
  (((((peel7 b).bind peel7).bind peelS).bind peelB).bind peelB).bind id

/-- **One round, as a single existential.** -/
theorem round_exists {tapes' : Nat} {M : Machine (tapes' + 2) states}
    (R : MergeRound tapes' M) (hlive : M.result R.virt.state = none) :
    ∃ (R' : MergeRound tapes' M) (cost : Nat),
      cost ≤ 500 * R.blocks.length + 1500 ∧
      R'.blocks.length ≤ R.blocks.length + 2 ∧
      R'.virt = M.step R.virt ∧
      HaltsExactly (stepProgram tapes' M R.virt.state)
        ((stepProgram tapes' M R.virt.state).startCfg R.park) cost false ∧
      (((stepProgram tapes' M R.virt.state).step^[cost])
        ((stepProgram tapes' M R.virt.state).startCfg R.park)).tape =
        R'.park ∧
      nextState (states := states)
        ((((stepProgram tapes' M R.virt.state).step^[cost])
          ((stepProgram tapes' M R.virt.state).startCfg R.park)).state) =
        some ((M.step R.virt).state) := by
  classical
  obtain ⟨preA, curA, postA, hA, -⟩ := R.hosts TrackSide.A
  obtain ⟨preB, curB, postB, hB, -⟩ := R.hosts TrackSide.B
  obtain ⟨cost, blocks'', hcost, hlen, hrun⟩ :=
    stepProgram_spec M R.virt.state R.virt R.base R.blocks rfl hlive hA hB
      R.mergeInv
  obtain ⟨hhalt, G'', hG'', htape, hstate, hinv⟩ := hrun R.ghost R.hg
  refine ⟨⟨M.step R.virt,
    execBase tapes' M R.virt.state (TrackSide.A.pick curA)
      (TrackSide.B.pick curB) R.base R.blocks,
    blocks'', G'', hG'', ?_, hinv.hosts⟩, cost, hcost, hlen, rfl, ?_, ?_, ?_⟩
  · intro j hj
    have hne : j ≠ Fin.last tapes' := by
      intro hcon; rw [hcon] at hj; simp at hj
    have := hinv.ident j hj
    rwa [Function.update_of_ne hne] at this
  · exact hhalt
  · exact htape
  · exact hstate

variable {tapes' : Nat} {M : Machine (tapes' + 2) states}

/-- One round of the trajectory: the successor record and that round's cost.
Rounds after the simulated machine halts stand still. -/
noncomputable def rstep (R : MergeRound tapes' M) : MergeRound tapes' M × Nat :=
  if h : M.result R.virt.state = none then
    ⟨(round_exists R h).choose, (round_exists R h).choose_spec.choose⟩
  else ⟨R, 0⟩

/-- The trajectory. -/
noncomputable def traj (R₀ : MergeRound tapes' M) : Nat → MergeRound tapes' M
  | 0 => R₀
  | n + 1 => (rstep (traj R₀ n)).1

/-- The cost of the round leaving `traj R₀ n`. -/
noncomputable def roundCost (R₀ : MergeRound tapes' M) (n : Nat) : Nat :=
  (rstep (traj R₀ n)).2

@[simp] theorem traj_zero (R₀ : MergeRound tapes' M) : traj R₀ 0 = R₀ := rfl

@[simp] theorem traj_succ (R₀ : MergeRound tapes' M) (n : Nat) :
    traj R₀ (n + 1) = (rstep (traj R₀ n)).1 := rfl

/-- While the simulated machine is live, the trajectory does what
`round_exists` promises. -/
theorem rstep_spec (R : MergeRound tapes' M)
    (h : M.result R.virt.state = none) :
    (rstep R).2 ≤ 500 * R.blocks.length + 1500 ∧
    (rstep R).1.blocks.length ≤ R.blocks.length + 2 ∧
    (rstep R).1.virt = M.step R.virt ∧
    HaltsExactly (stepProgram tapes' M R.virt.state)
      ((stepProgram tapes' M R.virt.state).startCfg R.park) (rstep R).2 false ∧
    (((stepProgram tapes' M R.virt.state).step^[(rstep R).2])
      ((stepProgram tapes' M R.virt.state).startCfg R.park)).tape =
      (rstep R).1.park ∧
    nextState (states := states)
      ((((stepProgram tapes' M R.virt.state).step^[(rstep R).2])
        ((stepProgram tapes' M R.virt.state).startCfg R.park)).state) =
      some ((M.step R.virt).state) := by
  have hs := (round_exists R h).choose_spec.choose_spec
  rw [rstep, dif_pos h]
  exact hs

/-- The simulated configuration after `n` rounds is `M.step^[n]` of the
initial one, as long as the machine stays live. -/
theorem traj_virt (R₀ : MergeRound tapes' M) (n : Nat)
    (hlive : ∀ i, i < n → M.result (traj R₀ i).virt.state = none) :
    (traj R₀ n).virt = (M.step^[n]) R₀.virt := by
  induction n with
  | zero => rfl
  | succ n ih =>
      have hn := ih (fun i hi => hlive i (Nat.lt_succ_of_lt hi))
      rw [traj_succ, (rstep_spec (traj R₀ n) (hlive n (Nat.lt_succ_self n))).2.2.1,
        hn, Function.iterate_succ_apply']

/-- The region grows by at most two blocks per round. -/
theorem traj_blocks_length (R₀ : MergeRound tapes' M) (n : Nat) :
    (traj R₀ n).blocks.length ≤ R₀.blocks.length + 2 * n := by
  induction n with
  | zero => simp
  | succ n ih =>
      by_cases h : M.result (traj R₀ n).virt.state = none
      · have := (rstep_spec (traj R₀ n) h).2.1
        rw [traj_succ]
        omega
      · rw [traj_succ, rstep, dif_neg h]
        simp only []
        omega

/-- …hence the per-round cost is bounded uniformly over the first `N` rounds. -/
theorem roundCost_le (R₀ : MergeRound tapes' M) (n : Nat) :
    roundCost R₀ n ≤ 500 * (R₀.blocks.length + 2 * n) + 1500 := by
  by_cases h : M.result (traj R₀ n).virt.state = none
  · have h1 := (rstep_spec (traj R₀ n) h).1
    have h2 := traj_blocks_length R₀ n
    rw [roundCost]
    omega
  · rw [roundCost, rstep, dif_neg h]
    simp only []
    omega

end SipserGacsLautemann
Source
Round-indexed trajectory for the two-track simulation; builds on Def_sgl_step_spec.

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