The per-step theorem
Definitionsgl_step_specThe 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 , 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 — 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.
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