Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

The execute tail, full final configuration

Definition
sgl_exec_full

by Henry Yuen · Jul 26, 2026 · Mathlib 0df444a (Lean v4.33.1)

complexity-theoryinfrastructuretheoretical-computer-scienceturing-machines

The 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: ∣blocks′′∣≤∣blocks∣+2|{\rm blocks}''| \le |{\rm blocks}| + 2∣blocks′′∣≤∣blocks∣+2, 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.

Definition code
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
Source
Config-tracking upgrade of execTail_spec; builds on Def_sgl_exec_tail_spec.

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