Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

The execute tail, fully specified

Definition
sgl_exec_tail_spec

by Henry Yuen · Jul 26, 2026 · Mathlib c5ea003 (Lean v4.30.0)

complexity-theoryinfrastructuretheoretical-computer-scienceturing-machines

The execute tail, fully specified: one simulated step of the hosted machine, from parked region to parked region.

execTail_spec is the per-step correctness of the simulation's suffix. From a region satisfying the merge invariant it halts within 300∣blocks∣+900300|{\rm blocks}| + 900300∣blocks∣+900 steps and re-establishes the invariant for the simulated successor M.step virtM.\mathrm{step}\ \mathrm{virt}M.step virt — stated ghost-uniformly, with the cost and output region fixed before the ghost, because the read phase that wraps it supplies an arbitrary one.

The intermediate configuration. The successor has all its tapes advanced, hosted ones included; but when the track updates run, the region still carries the old hosted tapes, since the execute stage touches only the identity-mapped ones. execMid names that mixture, and execMid_final proves the two updates carry it exactly to the successor. Naming the successor as the first update's target instead would make the invariant false at that point.

The alignment, avoided rather than fought. The tail's update parameters mention hostSyms\mathrm{hostSyms}hostSyms at the symbol view bound by the execute junction, while the update facts are stated at the virtual view; rewriting between them inside a machine term does not go through. The resolution is that the physical head view equals a ghost-free expression (exec_heads_indep). Feeding that to the junction as its exit state makes every downstream term match syntactically, and the identification with the virtual view is then needed exactly once, at the end, inside a Configuration. Choosing the canonical form of a quantity before building terms from it, rather than rewriting afterwards, is what lets the composition close.

Also here: execBase and exec_apply_eq, presenting the tapes the execute stage leaves with the ghost factored out; exec_ident, the execute stage's correctness on the identity-mapped tapes; and execBase_ident, carrying it into the mixture.

Definition code
import Definitions.Def_sgl_update_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


/-! ## Ghost-independence of the execute stage

The updates run on the tapes the execute stage leaves, so those must be
presented as `Function.update ⟨something ghost-free⟩ (last) (ParkedTape … G)`.
They are: the parked head is blank whatever the ghost, so the symbol view — and
hence the whole action — does not see the ghost at all. -/

@[simp] theorem parkedTape_head_blank (blocks : List Block)
    (G : List TapeSymbol) : (ParkedTape blocks G).head = TapeSymbol.blank := rfl

theorem exec_heads_indep (tapes' : Nat) (base : Fin (tapes' + 1) → Tape)
    (blocks : List Block) (G : List TapeSymbol) :
    (fun l => ((Function.update base (Fin.last tapes')
        (ParkedTape blocks G)) l).head) =
      Function.update (fun l => (base l).head) (Fin.last tapes')
        TapeSymbol.blank := by
  funext l
  by_cases hl : l = Fin.last tapes'
  · subst hl; simp
  · simp [hl]

/-- The tapes the execute stage leaves, with the ghost factored out. -/
def execBase (tapes' : Nat) (M : Machine (tapes' + 2) states) (q : Fin states)
    (sA sB : TapeSymbol) (base : Fin (tapes' + 1) → Tape)
    (blocks : List Block) : Fin (tapes' + 1) → Tape :=
  applyAction
    (Function.update base (Fin.last tapes') (ParkedTape blocks []))
    (execAction tapes' M q sA sB)

theorem exec_apply_eq (tapes' : Nat) (M : Machine (tapes' + 2) states)
    (q : Fin states) (sA sB : TapeSymbol) (base : Fin (tapes' + 1) → Tape)
    (blocks : List Block) (G : List TapeSymbol) :
    applyAction
        (Function.update base (Fin.last tapes') (ParkedTape blocks G))
        (execAction tapes' M q sA sB) =
      Function.update (execBase tapes' M q sA sB base blocks)
        (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, Function.update_self]
  · rw [Function.update_of_ne hj, execBase]
    simp only [applyAction]
    rw [exec_heads_indep, exec_heads_indep, Function.update_of_ne hj,
      Function.update_of_ne hj]

theorem execBase_ident {tapes' : Nat} {virt : Configuration (tapes' + 2) states}
    {base : Fin (tapes' + 1) → Tape} {blocks : List Block}
    {G : List TapeSymbol}
    (h : MergeInv tapes' virt
      (Function.update base (Fin.last tapes') (ParkedTape blocks G))
      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' (execMid tapes' M virt)
      (execBase tapes' M q (TrackSide.A.pick curA) (TrackSide.B.pick curB)
        base blocks) := by
  intro j hj
  have he := exec_ident h M q hlive hq hA hB
  have hj' := he j hj
  rw [exec_apply_eq] at hj'
  rw [Function.update_of_ne (by
    intro hcon; rw [hcon] at hj; simp at hj)] at hj'
  rw [hj', execMid_ident tapes' M virt _ hj]

/-! ## The tail, specified

The alignment problem — `execTail`'s update parameters mention `hostSyms` at
the *bound* symbol view, the update facts at the virtual one — is avoided
rather than rewritten.  `exec_heads_indep` says the physical head view equals a
ghost-free expression; feeding **that** to `chainStepS` as the junction's exit
state makes every downstream term match syntactically, and `hostSyms_eq` is
needed only at the end, in a `Configuration`. -/

set_option maxHeartbeats 4000000 in
theorem execTail_spec {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 ∧
      ∀ (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'' ∧
          MergeInv tapes' (M.step virt)
            ((((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)))).tape) 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
  -- the ghost-free view is the virtual view
  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
  -- the two updates carry the mixture to the successor
  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
  refine ⟨1 + 1 + (cA + 1 + (cB + 1 + 1)), blocksB, by omega, ?_⟩
  intro G hG
  set phys := Function.update base (Fin.last tapes') (ParkedTape blocks G)
    with hphys
  -- the junction's exit state, in ghost-free form
  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''))
  have hcarrytp : (((carryQ
      (M.transition q (hostSyms tapes' physHeads sA sB)).1).step^[1])
      ((carryQ (M.transition q (hostSyms tapes' physHeads sA sB)).1).startCfg
        (Function.update EB (Fin.last tapes') (ParkedTape blocksB G'')))).tape =
      Function.update EB (Fin.last tapes') (ParkedTape blocksB G'') := by
    rw [carryQ_run]
  have hchB := chainStep hhB htpB hcarry hcarrytp
  have hchA := chainStep hhA htpA hchB.1 hchB.2
  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
  refine ⟨hmain.1, G'', hG'', ?_⟩
  rw [hmidB] at hinvB
  have hfin := hmain.2
  have hgoal : (((execTail tapes' M q sA sB).step^[
      1 + 1 + (cA + 1 + (cB + 1 + 1))])
      ((execTail tapes' M q sA sB).startCfg phys)).tape =
      Function.update EB (Fin.last tapes') (ParkedTape blocksB G'') := by
    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]
    exact hchA.2
  rw [hgoal]
  exact hinvB

/-! ## Status

The remaining obligation of this module is `execTail_spec`.  Everything it
consumes is proved above, and the assembly has been worked out:

* the two updates run on `execBase`, not on the original base — the identity
  tapes must already be stepped, and `exec_apply_eq` presents that with the
  ghost factored out;
* track B's `HostsPair` after track A's update comes free from the *first*
  update's own `MergeInv` conclusion, extracted at any single ghost (the
  statement is ghost-independent);
* the successor is reached by `execMid_final`, with the two hosted writes
  identified via `Machine.step_of_result_none`;
* the cost is `1 + 1 + (cA + 1 + (cB + 1 + 1))`, polynomial because
  `updateTrack_step_u` now bounds its output region by `blocks.length + 1`.

**The one obstacle that remains**, and its fix.  `execTail`'s update parameters
mention `hostSyms tapes' syms sA sB` with `syms` bound by the `readAct`
junction; the update facts are stated with the *virtual* symbol view.  Aligning
them by rewriting `hostSyms_eq` inside the machine term is the difficulty the
plan flagged.

The way through is to avoid the rewrite entirely: by `exec_heads_indep`, the
physical head view `fun l => (phys l).head` equals a **ghost-free** expression,
`Function.update (fun l => (base l).head) (Fin.last tapes') TapeSymbol.blank`.
Defining the update parameters from *that* makes the chain's terms match
syntactically, and `hostSyms_eq` is then needed only once, at the very end,
to identify the result with `M.step virt` — where it is an ordinary rewrite in
a `Configuration`, not inside a machine.
-/

end SipserGacsLautemann
Source
Per-step correctness of the execute suffix in the two-track simulation; builds on Def_sgl_update_uniform.

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me