The execute tail, full final configuration
Definitionsgl_exec_fullThe execute tail with its full final configuration: one simulated step, and the terminal term made explicit.
Same chain as execTail_spec, with the two upgrades the step-program assembly needs. The junctions use the configuration-tracking chain (chainStepC) rather than the tape-only one, so the conclusion carries the explicit terminal term — inRightState (some physHeads) (inRight false (inRight false ⟨some (M.step virt).state, tape⟩)) — in particular the next simulated state, parked by carryQ, exactly where the outer loop's next function reads it by peeling. And the output region's growth is stated: , one block per track at most, which is what keeps the region linear in the round number and the total simulation cost quadratic.
The conclusion is in the canonical phase shape — cost and output region fixed after the identity class and before the ghost — so it is verbatim the continuation hypothesis a read phase consumes.
import Definitions.Def_sgl_exec_tail_spec
/-!
# The execute tail, full final configuration
Module E5a of DESIGN_step_spec_endgame. Same chain as `execTail_spec`, with
two upgrades the step-program assembly needs:
* the junctions use `chainStepC` (full configurations) instead of the
tape-only chain, so the conclusion carries the **explicit terminal term** —
in particular the next simulated state, parked by `carryQ`, which the loop's
`next` reads;
* the output region's growth is stated: `blocks''.length ≤ blocks.length + 2`.
The conclusion is in the canonical phase shape: cost and output region fixed
after the identity class, before the ghost.
-/
namespace SipserGacsLautemann
variable {states : Nat}
set_option maxHeartbeats 4000000 in
/-- **One simulated step, full final configuration.** -/
theorem execTail_full {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 ≤ 300 * blocks.length + 900 ∧
blocks''.length ≤ blocks.length + 2 ∧
∀ (G : List TapeSymbol), AllBlank G →
HaltsExactly
(execTail tapes' M q (TrackSide.A.pick curA)
(TrackSide.B.pick curB))
((execTail tapes' M q (TrackSide.A.pick curA)
(TrackSide.B.pick curB)).startCfg
(Function.update base (Fin.last tapes')
(ParkedTape blocks G))) cost false ∧
∃ G'' : List TapeSymbol, AllBlank G'' ∧
((execTail tapes' M q (TrackSide.A.pick curA)
(TrackSide.B.pick curB)).step^[cost])
((execTail tapes' M q (TrackSide.A.pick curA)
(TrackSide.B.pick curB)).startCfg
(Function.update base (Fin.last tapes')
(ParkedTape blocks G))) =
TypedConfiguration.inRightState
(some (Function.update (fun l => (base l).head)
(Fin.last tapes') TapeSymbol.blank))
(TypedConfiguration.inRight false
(TypedConfiguration.inRight false
(⟨some ((M.step virt).state),
Function.update
(execBase tapes' M q (TrackSide.A.pick curA)
(TrackSide.B.pick curB) base blocks)
(Fin.last tapes')
(ParkedTape blocks'' G'')⟩))) ∧
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
set sA := TrackSide.A.pick curA with hsA
set sB := TrackSide.B.pick curB with hsB
set physHeads := Function.update (fun l => (base l).head)
(Fin.last tapes') TapeSymbol.blank with hph
set mid := execMid tapes' M virt with hmid
set EB := execBase tapes' M q sA sB base blocks with hEB
have hview : hostSyms tapes' physHeads sA sB =
fun k => (virt.tape k).head := by
have h0 := hostSyms_eq (hinv [] AllBlank.nil) hA hB
rwa [exec_heads_indep tapes' base blocks []] at h0
set actA := (M.transition q (hostSyms tapes' physHeads sA sB)).2
(hostIdx tapes' TrackSide.A) with hactA
set actB := (M.transition q (hostSyms tapes' physHeads sA sB)).2
(hostIdx tapes' TrackSide.B) with hactB
have hEBident : IdentPart tapes' mid EB :=
execBase_ident (hinv [] AllBlank.nil) M q hlive hq hA hB
have hmidhosts : HostsPair blocks
(fun sd => mid.tape (hostIdx tapes' sd)) := by
have := (hinv [] AllBlank.nil).hosts
simpa [hmid] using this
obtain ⟨cA, blocksA, hcA, hlenA, hrunA⟩ := updateTrack_step_u
(virt := mid) (base := EB) (blocks := blocks)
(side := TrackSide.A) (s := actA.1) (mv := actA.2) hEBident hmidhosts
set midA : Configuration (tapes' + 2) states :=
⟨mid.state, Function.update mid.tape (hostIdx tapes' TrackSide.A)
(Tape.move (Tape.write (mid.tape (hostIdx tapes' TrackSide.A))
actA.1) actA.2)⟩ with hmidA
have hmidAident : IdentPart tapes' midA EB := by
intro j hj
have hne : (⟨j.val, by omega⟩ : Fin (tapes' + 2)) ≠
hostIdx tapes' TrackSide.A := by
intro hcon
have := congrArg Fin.val hcon
simp [hostIdx] at this
omega
rw [hmidA]
show EB j = Function.update mid.tape _ _ _
rw [Function.update_of_ne hne]
exact hEBident j hj
have hmidAhosts : HostsPair blocksA
(fun sd => midA.tape (hostIdx tapes' sd)) := by
obtain ⟨-, G'₀, -, -, hinvA₀⟩ := hrunA [] AllBlank.nil
exact hinvA₀.hosts
obtain ⟨cB, blocksB, hcB, hlenB, hrunB⟩ := updateTrack_step_u
(virt := midA) (base := EB) (blocks := blocksA)
(side := TrackSide.B) (s := actB.1) (mv := actB.2) hmidAident hmidAhosts
have hstep := Machine.step_of_result_none M virt hlive
have hmidB : (⟨midA.state, Function.update midA.tape
(hostIdx tapes' TrackSide.B)
(Tape.move (Tape.write (midA.tape (hostIdx tapes' TrackSide.B))
actB.1) actB.2)⟩ : Configuration (tapes' + 2) states) =
M.step virt := by
have hA' : mid.tape (hostIdx tapes' TrackSide.A) =
virt.tape (hostIdx tapes' TrackSide.A) := execMid_host _ _ _ _
have hB' : midA.tape (hostIdx tapes' TrackSide.B) =
virt.tape (hostIdx tapes' TrackSide.B) := by
rw [hmidA]
show Function.update mid.tape _ _ _ = _
rw [Function.update_of_ne (hostIdx_ne (by intro hc; cases hc))]
exact execMid_host _ _ _ _
have hXA : Tape.move (Tape.write (virt.tape (hostIdx tapes' TrackSide.A))
actA.1) actA.2 =
(M.step virt).tape (hostIdx tapes' TrackSide.A) := by
rw [hstep, hactA, hview, hq]
have hXB : Tape.move (Tape.write (virt.tape (hostIdx tapes' TrackSide.B))
actB.1) actB.2 =
(M.step virt).tape (hostIdx tapes' TrackSide.B) := by
rw [hstep, hactB, hview, hq]
have htapes : Function.update midA.tape (hostIdx tapes' TrackSide.B)
(Tape.move (Tape.write (midA.tape (hostIdx tapes' TrackSide.B))
actB.1) actB.2) = (M.step virt).tape := by
rw [hB', hXB, hmidA]
show Function.update (Function.update mid.tape
(hostIdx tapes' TrackSide.A) _) _ _ = _
rw [hA', hXA]
exact execMid_final M virt hlive
have hstates : midA.state = (M.step virt).state := rfl
calc (⟨midA.state, Function.update midA.tape (hostIdx tapes' TrackSide.B)
(Tape.move (Tape.write (midA.tape (hostIdx tapes' TrackSide.B))
actB.1) actB.2)⟩ : Configuration (tapes' + 2) states)
= ⟨(M.step virt).state, (M.step virt).tape⟩ := by
rw [hstates, htapes]
_ = M.step virt := rfl
-- the parked next state equals the simulated successor's state
have hqstate : (M.transition q (hostSyms tapes' physHeads sA sB)).1 =
(M.step virt).state := by
rw [hview, hstep, hq]
refine ⟨1 + 1 + (cA + 1 + (cB + 1 + 1)), blocksB, by omega, by omega, ?_⟩
intro G hG
set phys := Function.update base (Fin.last tapes') (ParkedTape blocks G)
with hphys
have hst : (((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
phys)).state = some physHeads := by
rw [readAct_exec_state, hphys, exec_heads_indep]
have htp : (((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
phys)).tape =
Function.update EB (Fin.last tapes') (ParkedTape blocks G) := by
rw [readAct_exec_tape, hphys, exec_apply_eq]
obtain ⟨hhA, G', hG', htpA, hinvA⟩ := hrunA G hG
obtain ⟨hhB, G'', hG'', htpB, hinvB⟩ := hrunB G' hG'
have hcarry := carryQ_spec
(M.transition q (hostSyms tapes' physHeads sA sB)).1
(Function.update EB (Fin.last tapes') (ParkedTape blocksB G''))
-- inner chain: update B, then carry — full configuration
have hchB := chainStepC hhB htpB hcarry
-- outer chain: update A, then the B-chain — full configuration
have hchA := chainStepC hhA htpA hchB.1
have hfires := readAct_exec_fires tapes' M q sA sB phys
have hmain := chainStepS
(M₂ := 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)
hfires.fires hfires.fresh hst htp hchA.1
rw [hmidB] at hinvB
refine ⟨hmain.1, G'', hG'', ?_, hinvB⟩
-- assemble the explicit terminal term, inside out
have hinner := hchB.2
rw [carryQ_run] at hinner
have houter := hchA.2
rw [hinner] at houter
have hfin := hmain.2
rw [houter] at hfin
rw [show (((execTail tapes' M q sA sB).step^[
1 + 1 + (cA + 1 + (cB + 1 + 1))])
((execTail tapes' M q sA sB).startCfg phys)) = _ from hfin]
rw [hqstate]
end SipserGacsLautemann