The execute tail and the intermediate configuration
Definitionsgl_exec_tailThe execute tail: the suffix of the step program that runs after both read phases, together with the intermediate configuration that makes its correctness statable.
The problem this module solves. The simulated successor has all its tapes advanced, hosted ones included. But at the moment the track updates run, the hosted region still carries the old virtual tapes — the execute stage deliberately touches only the identity-mapped ones, leaving the hosted writes and moves to the updates. So the successor cannot be named as the target of the first update; the invariant would be false there.
execMid names the intermediate state: identity-mapped tapes already stepped, hosted tapes not yet. The updates carry it the rest of the way, and execMid_final proves the destination is exactly — updating the two hosted indices to their successor values turns the mixture into the successor outright.
exec_ident is the correctness of the execute stage: after applying the machine's action to the identity-mapped tapes, those tapes still are the corresponding virtual tapes of the stepped configuration. It composes hostSyms_eq (the assembled symbol view is the true one) with the unfolded simulated step, so the physical write and move agree with the virtual ones index by index.
exec_host records the complementary fact: the execute stage leaves the host tape untouched, so the parked region survives into the update stage unchanged.
import Definitions.Def_sgl_step_uniform
/-!
# The execute tail
Module E3b, third part: the suffix of the step program that runs after both
read phases — apply the simulated machine's action to the identity-mapped
tapes, update both hosted tracks, and park the next state.
This is where the two `updateTrack_step_u` facts are consumed and where the
`MergeInv` for the successor configuration is assembled. Stated ghost-
uniformly, because the read phase that wraps it supplies an arbitrary ghost.
-/
namespace SipserGacsLautemann
variable {states : Nat}
/-- The tail of the step program: execute, update A, update B, carry. -/
def execTail (tapes' : Nat) (M : Machine (tapes' + 2) states)
(q : Fin states) (sA sB : TapeSymbol) :=
(TypedMachine.readAct
(fun syms => (syms, execAction tapes' M q sA sB syms))).andThenState
(fun s => s.isSome) fun rec =>
match rec with
| some syms =>
(updateTrack TrackSide.A (Fin.last tapes')
((M.transition q (hostSyms tapes' syms sA sB)).2
(hostIdx tapes' .A)).1
((M.transition q (hostSyms tapes' syms sA sB)).2
(hostIdx tapes' .A)).2).andThen fun _ =>
(updateTrack TrackSide.B (Fin.last tapes')
((M.transition q (hostSyms tapes' syms sA sB)).2
(hostIdx tapes' .B)).1
((M.transition q (hostSyms tapes' syms sA sB)).2
(hostIdx tapes' .B)).2).andThen fun _ =>
carryQ (M.transition q (hostSyms tapes' syms sA sB)).1
| none =>
(updateTrack TrackSide.A (Fin.last tapes') TapeSymbol.blank
HeadMove.stay).andThen fun _ =>
(updateTrack TrackSide.B (Fin.last tapes') TapeSymbol.blank
HeadMove.stay).andThen fun _ =>
carryQ q
/-! ## The readAct stage -/
theorem readAct_exec_fires (tapes' : Nat) (M : Machine (tapes' + 2) states)
(q : Fin states) (sA sB : TapeSymbol) (tape : Fin (tapes' + 1) → Tape) :
FiresExactly (fun c => c.state.isSome)
(TypedMachine.readAct
(fun syms => (syms, execAction tapes' M q sA sB syms))).step
((TypedMachine.readAct
(fun syms => (syms, execAction tapes' M q sA sB syms))).startCfg
tape) 1 :=
TypedMachine.readAct_fires _ tape
theorem readAct_exec_state (tapes' : Nat) (M : Machine (tapes' + 2) states)
(q : Fin states) (sA sB : TapeSymbol) (tape : Fin (tapes' + 1) → Tape) :
(((TypedMachine.readAct
(fun syms => (syms, execAction tapes' M q sA sB syms))).step^[1])
((TypedMachine.readAct
(fun syms => (syms, execAction tapes' M q sA sB syms))).startCfg
tape)).state = some (fun j => (tape j).head) := by
rw [TypedMachine.readAct_run_one]
theorem readAct_exec_tape (tapes' : Nat) (M : Machine (tapes' + 2) states)
(q : Fin states) (sA sB : TapeSymbol) (tape : Fin (tapes' + 1) → Tape) :
(((TypedMachine.readAct
(fun syms => (syms, execAction tapes' M q sA sB syms))).step^[1])
((TypedMachine.readAct
(fun syms => (syms, execAction tapes' M q sA sB syms))).startCfg
tape)).tape = applyAction tape (execAction tapes' M q sA sB) := by
rw [TypedMachine.readAct_run_one]
/-! ## The execute stage preserves the identity part and the host tape -/
theorem exec_ident {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)
(M : Machine (tapes' + 2) states) (q : Fin states)
(hlive : M.result virt.state = none) (hq : virt.state = q)
{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) :
IdentPart tapes' (M.step virt)
(applyAction phys
(execAction tapes' M q (TrackSide.A.pick curA)
(TrackSide.B.pick curB))) := by
intro j hj
have hsym := hostSyms_eq h hA hB
rw [applyAction_execAction_ident tapes' M q _ _ phys j hj]
have hheads : (fun l => (phys l).head) = fun l => (phys l).head := rfl
rw [Machine.step_of_result_none M virt hlive]
show Tape.move (Tape.write (phys j) _) _ = _
have hview : hostSyms tapes' (fun l => (phys l).head)
(TrackSide.A.pick curA) (TrackSide.B.pick curB) =
fun k => (virt.tape k).head := hsym
rw [hview, hq] at *
rw [h.ident j hj]
/-- The execute stage leaves the host tape untouched, so the region survives
into the update stage unchanged. -/
theorem exec_host {tapes' : Nat} (M : Machine (tapes' + 2) states)
(q : Fin states) (sA sB : TapeSymbol) (phys : Fin (tapes' + 1) → Tape)
(blocks : List Block) (G : List TapeSymbol)
(hpark : phys (Fin.last tapes') = ParkedTape blocks G) :
applyAction phys (execAction tapes' M q sA sB) =
Function.update
(applyAction phys (execAction tapes' M q sA sB))
(Fin.last tapes') (ParkedTape blocks G) := by
funext j
by_cases hj : j = Fin.last tapes'
· subst hj
rw [Function.update_self, applyAction_execAction_host, hpark]
· rw [Function.update_of_ne hj]
/-! ## The intermediate configuration
`M.step virt` has *all* its tapes advanced, hosted ones included — but at the
moment the updates run, the region still carries the old hosted tapes. The
mixture `execMid` names that intermediate state: identity-mapped tapes already
stepped, hosted tapes not yet. The two updates then carry it the rest of the
way, and `execMid_final` shows the result is exactly `M.step virt`. -/
/-- Identity tapes stepped, hosted tapes still old. -/
def execMid (tapes' : Nat) (M : Machine (tapes' + 2) states)
(virt : Configuration (tapes' + 2) states) :
Configuration (tapes' + 2) states where
state := (M.step virt).state
tape := fun k => if k.val < tapes' then (M.step virt).tape k else virt.tape k
@[simp] theorem execMid_host (tapes' : Nat) (M : Machine (tapes' + 2) states)
(virt : Configuration (tapes' + 2) states) (sd : TrackSide) :
(execMid tapes' M virt).tape (hostIdx tapes' sd) =
virt.tape (hostIdx tapes' sd) := by
cases sd <;> simp [execMid, hostIdx]
theorem execMid_ident (tapes' : Nat) (M : Machine (tapes' + 2) states)
(virt : Configuration (tapes' + 2) states) (k : Fin (tapes' + 2))
(hk : k.val < tapes') :
(execMid tapes' M virt).tape k = (M.step virt).tape k := by
simp [execMid, hk]
/-- After both hosted tracks are updated, the mixture *is* the simulated
successor. -/
theorem execMid_final {tapes' : Nat} (M : Machine (tapes' + 2) states)
(virt : Configuration (tapes' + 2) states)
(hlive : M.result virt.state = none) :
Function.update
(Function.update (execMid tapes' M virt).tape
(hostIdx tapes' TrackSide.A)
((M.step virt).tape (hostIdx tapes' TrackSide.A)))
(hostIdx tapes' TrackSide.B)
((M.step virt).tape (hostIdx tapes' TrackSide.B)) =
(M.step virt).tape := by
funext k
by_cases hkB : k = hostIdx tapes' TrackSide.B
· subst hkB; simp
· rw [Function.update_of_ne hkB]
by_cases hkA : k = hostIdx tapes' TrackSide.A
· subst hkA; simp
· rw [Function.update_of_ne hkA]
have hk : k.val < tapes' := by
rcases Nat.lt_or_ge k.val tapes' with h | h
· exact h
· exfalso
have hlt := k.isLt
have hcases : k.val = tapes' ∨ k.val = tapes' + 1 := by omega
rcases hcases with hv | hv
· exact hkA (Fin.ext (by simp [hostIdx, hv]))
· exact hkB (Fin.ext (by simp [hostIdx, hv]))
exact execMid_ident tapes' M virt k hk
end SipserGacsLautemann