Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

The simulation loop

Definition
sgl_merge_loop

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

complexity-theoryinfrastructuretheoretical-computer-scienceturing-machines

The simulation loop: stepProgram iterated until the simulated machine halts, reporting its answer.

A correction to the loop algebra. loopState_spec ties the loop's verdict to the body's own exit code. But every round of a simulation is a subroutine that halts false — the answer is not in the body's exit code, it is in the terminal control state. So that form can only ever conclude false. loopState_spec_v drops the hypothesis tying the two and reports the computed verdict instead, which is sound because loopState's result field already is the verdict function applied to the terminal state. The freshness half of the proof is untouched; only the halting half changes, and it becomes shorter.

mergeRounds supplies the per-round records from the trajectory: each round runs one stepProgram, advances the carried state to the simulated successor (read by peeling the terminal tower), and hands on the tape it parked. The three non-trivial obligations line up exactly with the per-step theorem's three conclusions.

mergeMachine_spec is the whole simulation. If MMM first halts after rounds+1{\rm rounds}+1rounds+1 steps with answer ans{\rm ans}ans, the loop halts with ans{\rm ans}ans in at most (rounds+1) (500(∣blocks0∣+2 rounds)+1501)({\rm rounds}+1)\,(500(|{\rm blocks}_0| + 2\,{\rm rounds}) + 1501)(rounds+1)(500(∣blocks0​∣+2rounds)+1501) steps — quadratic in the simulated running time, because the hosted region grows by at most two blocks per round and each round's cost is linear in the region.

Definition code
import Definitions.Def_sgl_merge_round

/-!
# The simulation loop

Module F1, second part: `stepProgram` iterated until the simulated machine
halts.

Two things are needed beyond the published loop algebra.

`loopState_spec_v` is `loopState_spec` with the conclusion's verdict left as
the **computed** one rather than tied to the body's.  The published form
requires `verdict (carry rounds) … = v` where `v` is the body's own verdict —
but every round of this simulation is a subroutine that halts `false`, so that
form can only ever conclude `false`.  Since `loopState`'s `result` field
already *is* `verdict` applied to the terminal state, dropping the hypothesis
and reporting that value is both sound and what a simulation needs: the
answer lives in the terminal state, not in the body's exit code.

`mergeRounds` then supplies the per-round records from the trajectory.
-/

namespace SipserGacsLautemann

variable {tapes : Nat} {Carry B : Type}

section
variable (body : Carry → TypedMachine tapes B)
    (next : Carry → B → Carry) (stop : Carry → B → Bool)
    (verdict : Carry → B → Bool)

/-- **The loop, reporting its computed verdict.** -/
theorem TypedMachine.loopState_spec_v (s₀ : Carry)
    (carry : Nat → Carry) (config : Nat → TypedConfiguration tapes B)
    (cost : Nat → Nat) (rounds : Nat) (a : Nat) (v : Bool)
    (hround : ∀ i, i < rounds → LoopRound body next stop carry config cost i)
    (hexit : HaltsExactly (body (carry rounds)) (config rounds) a v)
    (hstop : stop (carry rounds)
      (((body (carry rounds)).step^[a]) (config rounds)).state = true) :
    HaltsExactly (TypedMachine.loopState body next stop verdict s₀)
      (TypedConfiguration.inLoop (carry 0) (config 0))
      (loopCost cost rounds + a)
      (verdict (carry rounds)
        (((body (carry rounds)).step^[a]) (config rounds)).state) := by
  have hrun :=
    TypedMachine.loopState_rounds body next stop verdict s₀ carry config cost
      rounds hround
  constructor
  · rw [Nat.add_comm, Function.iterate_add_apply, hrun,
      TypedMachine.loopState_iterate_body body next stop verdict s₀
        (carry rounds) (config rounds) a hexit.fresh,
      TypedMachine.loopState_result_stop body next stop verdict s₀
        (carry rounds) hexit.halts hstop]
  · intro j hj
    rcases Nat.lt_or_ge j (loopCost cost rounds) with hlt | hge
    · clear hrun hexit hstop hj
      induction rounds with
      | zero => simp [loopCost] at hlt
      | succ rounds ih =>
          rcases Nat.lt_or_ge j (loopCost cost rounds) with hlt' | hge'
          · exact ih (fun i hi => hround i (Nat.lt_succ_of_lt hi)) hlt'
          · obtain ⟨t, ht⟩ := Nat.exists_eq_add_of_le hge'
            have htlt : t < cost rounds + 1 := by
              rw [loopCost] at hlt; omega
            obtain ⟨v', hv'⟩ := (hround rounds (Nat.lt_succ_self rounds)).halts
            rw [ht, Nat.add_comm, Function.iterate_add_apply,
              TypedMachine.loopState_rounds body next stop verdict s₀ carry
                config cost rounds
                (fun i hi => hround i (Nat.lt_succ_of_lt hi))]
            exact TypedMachine.loopState_round_fresh body next stop verdict s₀
              (carry rounds) (config rounds) (cost rounds) v' hv'
              (hround rounds (Nat.lt_succ_self rounds)).keeps t htlt
    · obtain ⟨t, ht⟩ := Nat.exists_eq_add_of_le hge
      have htlt : t < a := by omega
      rw [ht, Nat.add_comm, Function.iterate_add_apply, hrun]
      exact TypedMachine.loopState_pre_fresh body next stop verdict s₀
        (carry rounds) (config rounds) a v hexit t htlt

end

/-! ## The simulation loop -/

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

/-- The loop's carried value: the simulated state. -/
noncomputable def mergeCarry (R₀ : MergeRound tapes' M) (n : Nat) : Fin states :=
  (traj R₀ n).virt.state

/-- The loop's per-round starting configuration. -/
noncomputable def mergeConfig (R₀ : MergeRound tapes' M) (n : Nat) :=
  (stepProgram tapes' M (mergeCarry R₀ n)).startCfg (traj R₀ n).park

/-- **The per-round records.**  Every round before the simulated machine halts
runs one `stepProgram`, advances the carried state to the simulated successor,
and hands on the tape it parked. -/
theorem mergeRounds (R₀ : MergeRound tapes' M) (rounds : Nat)
    (hlive : ∀ i, i ≤ rounds → M.result ((M.step^[i]) R₀.virt).state = none)
    (i : Nat) (hi : i < rounds) :
    LoopRound (fun q => stepProgram tapes' M q)
      (fun q b => (nextState b).getD q)
      (fun q b => (M.result ((nextState b).getD q)).isSome)
      (mergeCarry R₀) (mergeConfig R₀) (roundCost R₀) i := by
  have htv : ∀ j, j ≤ rounds → (traj R₀ j).virt = (M.step^[j]) R₀.virt := by
    intro j
    induction j with
    | zero => intro _; rfl
    | succ n ih =>
        intro hn
        have hn' := ih (by omega)
        have hlv : M.result (traj R₀ n).virt.state = none := by
          rw [hn']; exact hlive n (by omega)
        rw [traj_succ, (rstep_spec (traj R₀ n) hlv).2.2.1, hn',
          Function.iterate_succ_apply']
  have hlivetraj : ∀ j, j ≤ rounds → M.result (traj R₀ j).virt.state = none := by
    intro j hj
    rw [htv j hj]
    exact hlive j hj
  have hL := hlivetraj i (by omega)
  have hspec := rstep_spec (traj R₀ i) hL
  have hnext : (nextState
      ((((stepProgram tapes' M (mergeCarry R₀ i)).step^[roundCost R₀ i])
        (mergeConfig R₀ i)).state)).getD (mergeCarry R₀ i) =
      (M.step (traj R₀ i).virt).state := by
    rw [mergeConfig, mergeCarry, roundCost, hspec.2.2.2.2.2]
    rfl
  refine ⟨⟨false, ?_⟩, ?_, ?_, ?_⟩
  · rw [mergeConfig, mergeCarry, roundCost]
    exact hspec.2.2.2.1
  · rw [hnext]
    have : M.result (traj R₀ (i + 1)).virt.state = none :=
      hlivetraj (i + 1) (by omega)
    rw [traj_succ, hspec.2.2.1] at this
    rw [this]
    rfl
  · rw [hnext, mergeCarry, traj_succ, hspec.2.2.1]
  · rw [mergeConfig, mergeConfig, mergeCarry, traj_succ, roundCost]
    congr 1
    exact (hspec.2.2.2.2.1).symm


/-! ## The whole simulation -/

/-- Cost of a bounded number of rounds. -/
theorem loopCost_le_of {cost : Nat → Nat} {C n : Nat}
    (h : ∀ i, i < n → cost i ≤ C) : loopCost cost n ≤ n * (C + 1) := by
  induction n with
  | zero => simp [loopCost]
  | succ n ih =>
      have hn := ih (fun i hi => h i (Nat.lt_succ_of_lt hi))
      have := h n (Nat.lt_succ_self n)
      rw [loopCost]
      calc loopCost cost n + (cost n + 1)
          ≤ n * (C + 1) + (C + 1) := by omega
        _ = (n + 1) * (C + 1) := (Nat.succ_mul n (C + 1)).symm

/-- The machine that runs the simulation to completion and reports the
simulated machine's answer. -/
noncomputable def mergeMachine (tapes' : Nat) (M : Machine (tapes' + 2) states)
    (q₀ : Fin states) :=
  TypedMachine.loopState (fun q => stepProgram tapes' M q)
    (fun q b => (nextState b).getD q)
    (fun q b => (M.result ((nextState b).getD q)).isSome)
    (fun q b => ((M.result ((nextState b).getD q)).getD false))
    q₀

/-- **The simulation, run to the simulated machine's halting time.**  If `M`
first halts after `rounds + 1` steps with answer `ans`, the loop halts with
`ans`, in a number of steps that is quadratic in the number of rounds. -/
theorem mergeMachine_spec (R₀ : MergeRound tapes' M) (rounds : Nat)
    (ans : Bool)
    (hlive : ∀ i, i ≤ rounds → M.result ((M.step^[i]) R₀.virt).state = none)
    (hhalt : M.result ((M.step^[rounds + 1]) R₀.virt).state = some ans) :
    ∃ total : Nat,
      total ≤ (rounds + 1) *
        (500 * (R₀.blocks.length + 2 * rounds) + 1500 + 1) ∧
      HaltsExactly (mergeMachine tapes' M R₀.virt.state)
        (TypedConfiguration.inLoop R₀.virt.state
          ((stepProgram tapes' M R₀.virt.state).startCfg R₀.park))
        total ans := by
  classical
  have htv : ∀ j, j ≤ rounds → (traj R₀ j).virt = (M.step^[j]) R₀.virt := by
    intro j
    induction j with
    | zero => intro _; rfl
    | succ n ih =>
        intro hn
        have hn' := ih (by omega)
        have hlv : M.result (traj R₀ n).virt.state = none := by
          rw [hn']; exact hlive n (by omega)
        rw [traj_succ, (rstep_spec (traj R₀ n) hlv).2.2.1, hn',
          Function.iterate_succ_apply']
  have hLive : M.result (traj R₀ rounds).virt.state = none := by
    rw [htv rounds le_rfl]; exact hlive rounds le_rfl
  have hspec := rstep_spec (traj R₀ rounds) hLive
  -- the value the loop reads at the stopping round
  have hval : (nextState
      ((((stepProgram tapes' M (mergeCarry R₀ rounds)).step^[roundCost R₀ rounds])
        (mergeConfig R₀ rounds)).state)).getD (mergeCarry R₀ rounds) =
      ((M.step^[rounds + 1]) R₀.virt).state := by
    rw [mergeConfig, mergeCarry, roundCost, hspec.2.2.2.2.2]
    show (M.step (traj R₀ rounds).virt).state = _
    rw [htv rounds le_rfl, Function.iterate_succ_apply']
  have hexit : HaltsExactly
      ((fun q => stepProgram tapes' M q) (mergeCarry R₀ rounds))
      (mergeConfig R₀ rounds) (roundCost R₀ rounds) false := by
    rw [mergeConfig, mergeCarry, roundCost]
    exact hspec.2.2.2.1
  have hstop : (M.result ((nextState
      ((((stepProgram tapes' M (mergeCarry R₀ rounds)).step^[roundCost R₀ rounds])
        (mergeConfig R₀ rounds)).state)).getD
      (mergeCarry R₀ rounds))).isSome = true := by
    rw [hval, hhalt]; rfl
  have hmain := TypedMachine.loopState_spec_v
    (fun q => stepProgram tapes' M q)
    (fun q b => (nextState b).getD q)
    (fun q b => (M.result ((nextState b).getD q)).isSome)
    (fun q b => ((M.result ((nextState b).getD q)).getD false))
    R₀.virt.state (mergeCarry R₀) (mergeConfig R₀) (roundCost R₀)
    rounds (roundCost R₀ rounds) false
    (mergeRounds R₀ rounds hlive) hexit hstop
  simp only [] at hmain
  rw [hval, hhalt] at hmain
  refine ⟨loopCost (roundCost R₀) rounds + roundCost R₀ rounds, ?_, ?_⟩
  · set C := 500 * (R₀.blocks.length + 2 * rounds) + 1500 with hC
    have hb : ∀ i, i < rounds → roundCost R₀ i ≤ C := by
      intro i hi
      have hri := roundCost_le R₀ i
      have hmono : 500 * (R₀.blocks.length + 2 * i) + 1500 ≤ C := by
        rw [hC]; omega
      omega
    have h1 := loopCost_le_of hb
    have h2 : roundCost R₀ rounds ≤ C := by
      have := roundCost_le R₀ rounds
      rw [hC]; omega
    have hexp : (rounds + 1) * (C + 1) = rounds * (C + 1) + (C + 1) :=
      Nat.succ_mul _ _
    omega
  · exact hmain

end SipserGacsLautemann
Source
Loop instantiation for the two-track simulation; builds on Def_sgl_merge_round.

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