Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

The per-step theorem

Definition
sgl_step_spec

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

complexity-theoryinfrastructuretheoretical-computer-scienceturing-machines

The per-step theorem: stepProgram implements one step of the simulated machine. This completes module E of the merge_empty campaign.

For a live simulated state, over any identity class of physical tapes whose host carries the parked two-track region: the step program halts in a fixed cost at most 500∣blocks∣+1500500|{\rm blocks}| + 1500500∣blocks∣+1500, the final tape is re-parked on a region that grew by at most two blocks, the next simulated state is read off the final control state by peeling the composition layers (peel7 ∘ peel7 ∘ peelS ∘ peelB ∘ peelB, flattened), and the merge invariant is re-established for the simulated successor M.step virtM.\mathrm{step}\ \mathrm{virt}M.step virt — all ghost-uniformly.

The proof is three instantiations and two rewrites, as the interface design intended: execTail_full supplies the continuation time for the inner read phase; the inner phase's cost supplies it for the outer; stepProgram is definitionally the outer phase (a rfl bridge); and the two configuration equations thread the execute tail's explicit terminal term up through both seven-layer towers, where the tape and state conjuncts close by rfl — seventeen layers of structural projection, no tactic work.

Every quantity is fixed exactly after the data it depends on and before the data it doesn't: cost and output region after the identity class (the machine's actions depend on the identity heads), before the ghost (never read). That discipline, applied uniformly across execTail_full, readPhase_ex, and this statement, is what made the final composition a page instead of a campaign.

Definition code
import Definitions.Def_sgl_read_phase_ex

/-!
# The per-step theorem

Module E5c of DESIGN_step_spec_endgame — the end of module E.

`stepProgram` is definitionally `readPhase A` wrapping `readPhase B` wrapping
`execTail`, so its specification is three instantiations: `execTail_full`
supplies the continuation time for the inner `readPhase_ex`, whose cost
supplies it for the outer.  The conclusion exposes exactly what the loop
needs: halting at a fixed per-class cost, the final tape re-parked on a region
that grew by at most two blocks, the next simulated state readable off the
final state by peeling, and the merge invariant for the simulated successor.
-/

namespace SipserGacsLautemann

variable {states : Nat}

set_option maxHeartbeats 4000000 in
/-- **One round of the simulation: `stepProgram` implements `M.step`.** -/
theorem stepProgram_spec {tapes' : Nat} (M : Machine (tapes' + 2) states)
    (q : Fin states) (virt : Configuration (tapes' + 2) states)
    (base : Fin (tapes' + 1) → Tape) (blocks : List Block)
    (hq : virt.state = q) (hlive : M.result virt.state = none)
    {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)
    (hinv : ∀ G, AllBlank G → MergeInv tapes' virt
      (Function.update base (Fin.last tapes') (ParkedTape blocks G))
      blocks G) :
    ∃ (cost : Nat) (blocks'' : List Block),
      cost ≤ 500 * blocks.length + 1500 ∧
      blocks''.length ≤ blocks.length + 2 ∧
      ∀ (G : List TapeSymbol), AllBlank G →
        HaltsExactly (stepProgram tapes' M q)
          ((stepProgram tapes' M q).startCfg
            (Function.update base (Fin.last tapes')
              (ParkedTape blocks G))) cost false ∧
        ∃ G'' : List TapeSymbol, AllBlank G'' ∧
          (((stepProgram tapes' M q).step^[cost])
            ((stepProgram tapes' M q).startCfg
              (Function.update base (Fin.last tapes')
                (ParkedTape blocks G)))).tape =
            Function.update
              (execBase tapes' M q (TrackSide.A.pick curA)
                (TrackSide.B.pick curB) base blocks)
              (Fin.last tapes') (ParkedTape blocks'' G'') ∧
          (((((peel7 ((((stepProgram tapes' M q).step^[cost])
            ((stepProgram tapes' M q).startCfg
              (Function.update base (Fin.last tapes')
                (ParkedTape blocks G)))).state)).bind peel7).bind
            peelS).bind peelB).bind peelB).bind id =
            some ((M.step virt).state) ∧
          MergeInv tapes' (M.step virt)
            (Function.update
              (execBase tapes' M q (TrackSide.A.pick curA)
                (TrackSide.B.pick curB) base blocks)
              (Fin.last tapes') (ParkedTape blocks'' G''))
            blocks'' G'' := by
  classical
  -- the execute tail
  obtain ⟨cE, blocks'', hcE, hlen, hrunE⟩ :=
    execTail_full M q virt base blocks hq hlive hA hB hinv
  -- the inner read phase (track B), continuation time cE
  obtain ⟨costB, hcostB, hrunB⟩ := readPhase_ex TrackSide.B
    (Fin.last tapes')
    (fun sB => execTail tapes' M q (TrackSide.A.pick curA) sB)
    preB curB postB hB.preClear hB.curSet cE false base
    (by
      intro G' hG'
      rw [← hB.eq]
      exact (hrunE G' hG').1)
  -- the outer read phase (track A), continuation time costB
  obtain ⟨costA, hcostA, hrunA⟩ := readPhase_ex TrackSide.A
    (Fin.last tapes')
    (fun sA => readPhase TrackSide.B (Fin.last tapes')
      (fun sB => execTail tapes' M q sA sB))
    preA curA postA hA.preClear hA.curSet costB false base
    (by
      intro G' hG'
      rw [← hA.eq]
      obtain ⟨G₂, -, hH, -⟩ := hrunB G' hG'
      rw [← hB.eq] at hH
      exact hH)
  have hLA : (preA ++ curA :: postA).length = blocks.length := by
    rw [← hA.eq]
  have hLB : (preB ++ curB :: postB).length = blocks.length := by
    rw [← hB.eq]
  refine ⟨costA, blocks'', by omega, hlen, ?_⟩
  intro G hG
  obtain ⟨G₁, hG₁, hHaltA, hcfgA⟩ := hrunA G hG
  rw [← hA.eq] at hHaltA hcfgA
  have hHaltA' : HaltsExactly (stepProgram tapes' M q)
      ((stepProgram tapes' M q).startCfg
        (Function.update base (Fin.last tapes')
          (ParkedTape blocks G))) costA false := hHaltA
  obtain ⟨G₂, hG₂, hHaltB, hcfgB⟩ := hrunB G₁ hG₁
  rw [← hB.eq] at hcfgB
  obtain ⟨-, G₃, hG₃, hcfgE, hinvE⟩ := hrunE G₂ hG₂
  -- thread the inner configuration equations into the outer tower
  rw [hcfgB] at hcfgA
  rw [hcfgE] at hcfgA
  have hunfold : stepProgram tapes' M q =
      readPhase TrackSide.A (Fin.last tapes')
        (fun sA => readPhase TrackSide.B (Fin.last tapes')
          (fun sB => execTail tapes' M q sA sB)) := rfl
  refine ⟨hHaltA', G₃, hG₃, ?_, ?_, hinvE⟩
  · rw [hunfold, hcfgA]
    rfl
  · rw [hunfold, hcfgA]
    rfl

end SipserGacsLautemann
Source
Completion of module E: the per-step simulation theorem; builds on Def_sgl_read_phase_ex.

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