The simulation loop
Definitionsgl_merge_loopThe 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 first halts after steps with answer , the loop halts with in at most 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.
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
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