The simulation trajectory
Definitionsgl_merge_roundThe 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 rounds is of the initial one (while the machine stays live), and the hosted region grows by at most two blocks per round, so and the per-round cost is bounded by — linear in the round index, which is what makes the whole simulation quadratic.
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