The simulation invariant and the packaged track update
Definitionsgl_step_piecesPieces of the per-step theorem: the simulation invariant, the symbol-view identification, and the packaged track update.
MergeInv is the full simulation invariant. The physical tapes below the host index are the corresponding virtual tapes (identity-mapped, so the simulated machine's writes and moves apply to them directly); the host tape carries the remaining two virtual tapes as a parked two-track region with an all-blank ghost; and the two tracks satisfy HostsPair.
hostSyms_eq is the identification that makes the execute phase correct: the symbol view the step program assembles equals the simulated machine's true view . Below the host index the physical head is the virtual head by identity-mapping; at the two hosted indices, the symbols the read phases learned are the virtual heads by HostsPair.head_eq. So the transition the program applies is the transition the simulated machine would take.
updateTrack_step packages all of module D's and the invariant layer's case analysis into one uniform fact. Given the invariant and a write-and-move for one track, the update halts within steps, leaves the host tape parked on a new region, and re-establishes MergeInv with that track's virtual tape written and moved and the other untouched. Internally it selects among the five bounded specifications and pairs each with its matching HostsPair preservation — three head-moves, two of which split at the region's edges. The per-step theorem therefore sees a single fact per track rather than a five-way case analysis, and the nine-case product across two tracks never arises.
Formalization note. virtTape_update_apply transports an update at a hosted virtual index through the two-track view; stated pointwise rather than as a function equality, it rewrites under binders and keeps the preservation proofs to two lines each.
import Definitions.Def_sgl_bounded_specs
/-!
# Pieces of the per-step theorem
Module E3b of the merge_empty plan, first part: the small facts the per-step
theorem needs, isolated and proved before the large composition depends on
them.
The two with real content:
* `hostSyms_eq` — the symbol view the step program assembles equals the
simulated machine's *true* view. The identity-mapped tapes contribute
their physical heads (they are literally the virtual tapes), and the two
hosted tracks contribute the symbols the read phases learned, which
`HostsPair.head_eq` identifies with the virtual heads.
* `MergeInv` — the full simulation invariant, and its head-symbol corollary.
-/
namespace SipserGacsLautemann
/-! ## Track sides as virtual indices -/
@[simp] theorem hostIdx_A_val (tapes' : Nat) :
(hostIdx tapes' TrackSide.A).val = tapes' := rfl
@[simp] theorem hostIdx_B_val (tapes' : Nat) :
(hostIdx tapes' TrackSide.B).val = tapes' + 1 := rfl
/-! ## The full invariant -/
/-- The simulation invariant: the identity-mapped physical tapes *are* the
corresponding virtual tapes, the host tape carries the other two as a parked
two-track region, and the control carries the simulated state. -/
structure MergeInv {states : Nat} (tapes' : Nat)
(virt : Configuration (tapes' + 2) states)
(phys : Fin (tapes' + 1) → Tape) (blocks : List Block)
(G : List TapeSymbol) : Prop where
ident : ∀ j : Fin (tapes' + 1), j.val < tapes' →
phys j = virt.tape ⟨j.val, by omega⟩
parked : phys (Fin.last tapes') = ParkedTape blocks G
ghost : AllBlank G
hosts : HostsPair blocks
(fun side => virt.tape (hostIdx tapes' side))
/-- The symbol view the step program assembles is the simulated machine's true
view. Below `tapes'` the physical head *is* the virtual head; at the two
hosted indices the learned symbols are the virtual heads by `HostsPair`. -/
theorem hostSyms_eq {states : Nat} {tapes' : Nat}
{virt : Configuration (tapes' + 2) states}
{phys : Fin (tapes' + 1) → Tape} {blocks : List Block}
{G : List TapeSymbol} (h : MergeInv tapes' virt phys blocks G)
{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) :
hostSyms tapes' (fun j => (phys j).head)
(TrackSide.A.pick curA) (TrackSide.B.pick curB) =
fun k => (virt.tape k).head := by
funext k
rw [hostSyms]
by_cases hk : k.val < tapes'
· rw [dif_pos hk, h.ident ⟨k.val, by omega⟩ hk]
· rw [dif_neg hk]
by_cases hk2 : k.val = tapes'
· rw [if_pos hk2, h.hosts.head_eq TrackSide.A hA]
exact congrArg (fun t : Tape => t.head)
(congrArg virt.tape (Fin.ext (by simp [hostIdx, hk2])))
· rw [if_neg hk2, h.hosts.head_eq TrackSide.B hB]
have hval : k.val = tapes' + 1 := by omega
exact congrArg (fun t : Tape => t.head)
(congrArg virt.tape (Fin.ext (by simp [hostIdx, hval])))
/-! ## The execute step's tape effect -/
/-- The execute action leaves the host tape alone. -/
theorem execAction_host {states : Nat} (tapes' : Nat)
(M : Machine (tapes' + 2) states) (q : Fin states) (sA sB : TapeSymbol)
(syms : Fin (tapes' + 1) → TapeSymbol) :
execAction tapes' M q sA sB syms (Fin.last tapes') =
(syms (Fin.last tapes'), HeadMove.stay) := by
rw [execAction, dif_neg (by simp)]
/-- …so applying it preserves the host tape exactly. -/
theorem applyAction_execAction_host {states : Nat} (tapes' : Nat)
(M : Machine (tapes' + 2) states) (q : Fin states) (sA sB : TapeSymbol)
(tape : Fin (tapes' + 1) → Tape) :
applyAction tape (execAction tapes' M q sA sB) (Fin.last tapes') =
tape (Fin.last tapes') := by
rw [applyAction, execAction_host]
simp [Tape.write_head_self, Tape.move]
/-- On an identity-mapped tape the execute action applies the simulated
machine's own action. -/
theorem applyAction_execAction_ident {states : Nat} (tapes' : Nat)
(M : Machine (tapes' + 2) states) (q : Fin states) (sA sB : TapeSymbol)
(tape : Fin (tapes' + 1) → Tape) (j : Fin (tapes' + 1))
(hj : j.val < tapes') :
applyAction tape (execAction tapes' M q sA sB) j =
Tape.move
(Tape.write (tape j)
((M.transition q (hostSyms tapes' (fun l => (tape l).head) sA sB)).2
⟨j.val, by omega⟩).1)
((M.transition q (hostSyms tapes' (fun l => (tape l).head) sA sB)).2
⟨j.val, by omega⟩).2 := by
rw [applyAction, execAction, dif_pos hj]
/-! ## The simulated step, unfolded -/
/-- While the simulated machine is live, its step applies its transition. -/
theorem Machine.step_of_result_none {n states : Nat}
(M : Machine n states) (c : Configuration n states)
(h : M.result c.state = none) :
M.step c =
{ state := (M.transition c.state (fun i => (c.tape i).head)).1
tape := fun i =>
Tape.move
(Tape.write (c.tape i)
((M.transition c.state (fun i => (c.tape i).head)).2 i).1)
((M.transition c.state (fun i => (c.tape i).head)).2 i).2 } := by
unfold Machine.step
rw [h]
theorem hostIdx_ne {tapes' : Nat} {side side' : TrackSide} (h : side' ≠ side) :
hostIdx tapes' side' ≠ hostIdx tapes' side := by
cases side <;> cases side' <;>
first
| exact absurd rfl h
| (intro hcon; have := congrArg Fin.val hcon; simp [hostIdx] at this)
/-- Updating a virtual tape at a hosted index, viewed through the two tracks. -/
@[simp] theorem virtTape_update_apply (tapes' : Nat)
(vt : Fin (tapes' + 2) → Tape) (side side' : TrackSide) (X : Tape) :
Function.update vt (hostIdx tapes' side) X (hostIdx tapes' side') =
Function.update (fun s' => vt (hostIdx tapes' s')) side X side' := by
by_cases hss : side' = side
· subst hss; simp
· rw [Function.update_of_ne hss, Function.update_of_ne (hostIdx_ne hss)]
/-! ## The single-track update, packaged
One theorem covering all three head-moves and both edges: given the invariant
and a write-and-move for one track, the update halts within an affine bound and
re-establishes the invariant with that track's virtual tape written and moved,
the other untouched. The five bounded specifications and the five `HostsPair`
preservations are matched up here, once, so the per-step theorem sees a single
uniform fact. -/
theorem updateTrack_step {states : Nat} {tapes' : Nat}
{virt : Configuration (tapes' + 2) states}
{phys : Fin (tapes' + 1) → Tape} {blocks : List Block}
{G : List TapeSymbol} (h : MergeInv tapes' virt phys blocks G)
(side : TrackSide) (s : TapeSymbol) (mv : HeadMove) :
∃ (cost : Nat) (blocks' : List Block) (G' : List TapeSymbol),
cost ≤ 100 * blocks.length + 300 ∧
HaltsExactly (updateTrack side (Fin.last tapes') s mv)
((updateTrack side (Fin.last tapes') s mv).startCfg phys) cost false ∧
(((updateTrack side (Fin.last tapes') s mv).step^[cost])
((updateTrack side (Fin.last tapes') s mv).startCfg phys)).tape =
Function.update phys (Fin.last tapes') (ParkedTape blocks' G') ∧
MergeInv tapes'
{ state := virt.state
tape := Function.update virt.tape (hostIdx tapes' side)
(Tape.move (Tape.write (virt.tape (hostIdx tapes' side)) s) mv) }
(Function.update phys (Fin.last tapes') (ParkedTape blocks' G'))
blocks' G' := by
classical
obtain ⟨pre, cur, post, hsplit, -⟩ := h.hosts side
have hblocks := hsplit.eq
subst hblocks
-- the invariant's non-host components are untouched by every variant
have hident : ∀ (bl : List Block) (Gx : List TapeSymbol),
∀ j : Fin (tapes' + 1), j.val < tapes' →
(Function.update phys (Fin.last tapes') (ParkedTape bl Gx)) j =
(Function.update virt.tape (hostIdx tapes' side)
(Tape.move (Tape.write (virt.tape (hostIdx tapes' side)) s) mv))
⟨j.val, by omega⟩ := by
intro bl Gx j hj
have hne : j ≠ Fin.last tapes' := by
intro hcon
rw [hcon] at hj
simp at hj
have hne2 : (⟨j.val, by omega⟩ : Fin (tapes' + 2)) ≠ hostIdx tapes' side := by
intro hcon
have := congrArg Fin.val hcon
cases side <;> simp [hostIdx] at this <;> omega
rw [Function.update_of_ne hne, Function.update_of_ne hne2]
exact h.ident j hj
have hpark : ∀ (bl : List Block) (Gx : List TapeSymbol),
(Function.update phys (Fin.last tapes') (ParkedTape bl Gx))
(Fin.last tapes') = ParkedTape bl Gx := by
intro bl Gx; simp
cases mv with
| stay =>
obtain ⟨cost, hbound, hrun⟩ := updateTrack_stay_bounded side
(Fin.last tapes') s pre cur post hsplit.preClear hsplit.curSet
obtain ⟨G', hG', hhalt, htape⟩ := hrun G phys h.ghost h.parked
refine ⟨cost, pre ++ setSymFlag side s true cur :: post, G', hbound,
hhalt, htape, ?_, hpark _ _, hG', ?_⟩
· exact hident _ _
· have := h.hosts.update_stay side hsplit s
simp only [virtTape_update_apply]
exact this
| right =>
cases post with
| cons nxt post' =>
obtain ⟨cost, hbound, hrun⟩ := updateTrack_right_cons_bounded side
(Fin.last tapes') s pre cur nxt post' hsplit.preClear hsplit.curSet
obtain ⟨G', hG', hhalt, htape⟩ := hrun G phys h.ghost h.parked
refine ⟨cost, pre ++ setSymFlag side s false cur ::
setFlag side true nxt :: post', G', hbound, hhalt, htape,
?_, hpark _ _, hG', ?_⟩
· exact hident _ _
· have := h.hosts.update_right_mid side hsplit s
simp only [virtTape_update_apply]
exact this
| nil =>
obtain ⟨cost, hbound, hrun⟩ := updateTrack_right_nil_bounded side
(Fin.last tapes') s pre cur hsplit.preClear hsplit.curSet
obtain ⟨G', hG', hhalt, htape⟩ := hrun G phys h.ghost h.parked
refine ⟨cost, pre ++ [setSymFlag side s false cur,
freshFlagged side], G', hbound, hhalt, htape,
?_, hpark _ _, hG', ?_⟩
· exact hident _ _
· have := h.hosts.update_right_edge side hsplit s
simp only [virtTape_update_apply]
exact this
| left =>
rcases List.eq_nil_or_concat pre with rfl | ⟨pre', prv, rfl⟩
· obtain ⟨cost, hbound, hrun⟩ := updateTrack_left_nil_bounded side
(Fin.last tapes') s cur post hsplit.curSet
obtain ⟨G', hG', hhalt, htape⟩ := hrun G phys h.ghost
(by simpa using h.parked)
refine ⟨cost, freshFlagged side :: setSymFlag side s false cur :: post,
G', hbound, ?_, ?_, ?_, hpark _ _, hG', ?_⟩
· simpa using hhalt
· simpa using htape
· exact hident _ _
· have := h.hosts.update_left_edge side (by simpa using hsplit) s
simp only [virtTape_update_apply]
exact this
· simp only [List.concat_eq_append] at *
obtain ⟨cost, hbound, hrun⟩ := updateTrack_left_concat_bounded side
(Fin.last tapes') s pre' prv cur post hsplit.preClear hsplit.curSet
obtain ⟨G', hG', hhalt, htape⟩ := hrun G phys h.ghost h.parked
refine ⟨cost, pre' ++ setFlag side true prv ::
setSymFlag side s false cur :: post, G', hbound, hhalt, htape,
?_, hpark _ _, hG', ?_⟩
· exact hident _ _
· have := h.hosts.update_left_mid side hsplit s
simp only [virtTape_update_apply]
exact this
end SipserGacsLautemann