Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

The step program, with its read phases proven

Definition
sgl_step_program

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

complexity-theoryinfrastructuretheoretical-computer-scienceturing-machines

The step program: one simulated step of the (n+2)(n+2)(n+2)-tape machine on n+1n+1n+1 physical tapes — defined in full, with its read phases proven.

The shape, the simulated state qqq a construction parameter supplied by the outer loop's carry:

readPhaseA(sA↦readPhaseB(sB↦exec q sA sB⊳updateA⊳updateB⊳carry q′))\mathrm{readPhase}_A\big(s_A \mapsto \mathrm{readPhase}_B\big(s_B \mapsto \mathrm{exec}\ q\ s_A\ s_B \rhd \mathrm{update}_A \rhd \mathrm{update}_B \rhd \mathrm{carry}\ q'\big)\big)readPhaseA​(sA​↦readPhaseB​(sB​↦exec q sA​ sB​⊳updateA​⊳updateB​⊳carry q′))

hostSyms assembles the simulated machine's full symbol view — physical heads for the identity-mapped tapes, the two learned symbols for the hosted ones — and execAction applies the machine's writes and moves to the identity-mapped tapes in a single step, the host tape waiting for the update phases. The whole program elaborates with data-only dependence on runtime values, the dividend of the fixed-state-type discipline maintained since the counter machines.

readPhase_spec, proven here, is the module's substance. From the parked region, a read phase halts with its continuation's verdict; its terminal configuration is an explicit seven-layer tower ending in the continuation's own run; the continuation receives exactly the track's virtual head symbol (the two probe verdicts decode to it); and the region survives untouched up to ghost growth. The proof chains seven junctions with full configurations — the two probe junctions identify their verdicts by reading the flagged block at the split, and the parking scan reassembles the identical region.

What remains for the per-step theorem is assembly: instantiate the read phases twice, compose the execute readAct and the two proven track updates through the configuration-tracking chain, and case on the simulated machine's head-moves to select the matching update specifications and invariant preservations.

Definition code
import Definitions.Def_sgl_step_chain

/-!
# The step program

Module E of the merge_empty plan, fourth part: one simulated step of the
`(tapes' + 2)`-tape machine, as a program on `tapes' + 1` physical tapes.

The shape, with the simulated state `q` a construction parameter supplied by
the outer loop's carry:

```
readPhase A (fun sA =>           -- learn virtual tape A's head symbol
  readPhase B (fun sB =>         -- learn virtual tape B's head symbol
    exec q sA sB ⟶               -- read heads 0..tapes'-1, apply M's action
      updateTrack A ⟶            -- write + flag-move for track A
        updateTrack B ⟶          -- write + flag-move for track B
          carryQ q'))            -- park the next state for the loop
```

Each `readPhase` learns its symbol through two Boolean block-reads piped
through `andThen`'s continuations (`sgl_read_bits`), so no state extraction
occurs anywhere inside the chain; the single extraction — the loop's `next`
reading `q'` — peels the fixed nesting to the `carryQ` payload at the end.
-/

namespace SipserGacsLautemann

variable {tapes : Nat}

/-! ## The read phase -/

/-- Learn a hosted track's head symbol and hand it to the continuation:
enter, walk to the flag, step back, probe bit one, step back, probe bit two,
park, continue.  Content-preserving; the symbol travels through the two
`Bool`-indexed continuations. -/
def readPhase (side : TrackSide) (i : Fin tapes) {S : Type}
    (cont : TapeSymbol → TypedMachine tapes S) :=
  (moveUpTo i 1 HeadMove.right).andThen fun _ =>
    (walkToFlag side i).andThen fun _ =>
      (moveUpTo i 6 HeadMove.left).andThen fun _ =>
        (blockRead i (sideBit1 side)).andThen fun b₁ =>
          (moveUpTo i 6 HeadMove.left).andThen fun _ =>
            (blockRead i (sideBit2 side)).andThen fun b₂ =>
              (scanToBlank i HeadMove.left).andThen fun _ =>
                cont (symbolOfBits b₁ b₂)

/-! ## The execute phase -/

/-- Assemble the simulated machine's full symbol view: physical heads for the
identity-mapped tapes, the two learned symbols for the hosted ones. -/
def hostSyms (tapes' : Nat) (syms : Fin (tapes' + 1) → TapeSymbol)
    (sA sB : TapeSymbol) : Fin (tapes' + 2) → TapeSymbol :=
  fun k =>
    if h : k.val < tapes' then syms ⟨k.val, by omega⟩
    else if k.val = tapes' then sA else sB

/-- Apply the simulated machine's writes and moves to the identity-mapped
tapes; the host tape waits for the update phases. -/
def execAction {states : Nat} (tapes' : Nat)
    (M : Machine (tapes' + 2) states) (q : Fin states) (sA sB : TapeSymbol) :
    (Fin (tapes' + 1) → TapeSymbol) →
      (Fin (tapes' + 1) → TapeSymbol × HeadMove) :=
  fun syms j =>
    if h : j.val < tapes' then
      (M.transition q (hostSyms tapes' syms sA sB)).2 ⟨j.val, by omega⟩
    else (syms j, HeadMove.stay)

/-- The virtual index of a hosted track. -/
def hostIdx (tapes' : Nat) : TrackSide → Fin (tapes' + 2)
  | .A => ⟨tapes', by omega⟩
  | .B => ⟨tapes' + 1, by omega⟩

/-! ## The step program -/

/-- One simulated step, from parked to parked, ending with the next simulated
state parked in a `carryQ` for the loop's `next` to read. -/
def stepProgram {states : Nat} (tapes' : Nat)
    (M : Machine (tapes' + 2) states) (q : Fin states) :=
  readPhase TrackSide.A (Fin.last tapes') fun sA =>
    readPhase TrackSide.B (Fin.last tapes') fun sB =>
      (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

/-! ## Peeling the next state out -/

/-- Seven `andThen` layers of one read phase. -/
def peel7 {S₁ S₂ S₃ S₄ S₅ S₆ S₇ S : Type}
    (st : S₁ ⊕ Bool × (S₂ ⊕ Bool × (S₃ ⊕ Bool × (S₄ ⊕ Bool ×
      (S₅ ⊕ Bool × (S₆ ⊕ Bool × (S₇ ⊕ Bool × S))))))) : Option S :=
  (peelB st).bind fun st => (peelB st).bind fun st => (peelB st).bind fun st =>
    (peelB st).bind fun st => (peelB st).bind fun st =>
      (peelB st).bind fun st => peelB st

/-- The full extraction: through both read phases, the execute dispatch, the
two updates, into the `carryQ` payload; `q` if anything is off-shape (it never
is on the terminal term the specification pins). -/
def stepPeel {states : Nat} (tapes' : Nat) {ST₁ ST₂ SX SU₁ SU₂ : Type}
    (q : Fin states)
    (st : ST₁ ⊕ Bool × (ST₂ ⊕ Bool × (SX ⊕ SX ×
      (SU₁ ⊕ Bool × (SU₂ ⊕ Bool × Option (Fin states)))))) : Fin states :=
  (((peelB st).bind fun st => (peelB st).bind fun st =>
    (peelS st).bind fun st => (peelB st).bind fun st =>
      (peelB st).bind fun st => st).getD q)


/-! ## The read phase, specified -/

set_option maxHeartbeats 4000000 in
/-- **The read phase implements its contract**: from the parked region it
halts with the continuation's verdict, its terminal configuration is the
seven-layer tower ending in the continuation's run, the continuation receives
exactly the track's virtual head symbol, and the region survives untouched up
to ghost growth. -/
theorem readPhase_spec (side : TrackSide) (i : Fin tapes) {S : Type}
    (cont : TapeSymbol → TypedMachine tapes S)
    (tape : Fin tapes → Tape) (mid : List Block) (cur : Block)
    (post : List Block) (G : List TapeSymbol) (hG : AllBlank G)
    (hmid : ∀ b ∈ mid, side.getFlag b = false)
    (hcur : side.getFlag cur = true)
    (hi : tape i = ParkedTape (mid ++ cur :: post) G)
    {k : Nat} {v : Bool}
    (hcont : ∀ (G' : List TapeSymbol), AllBlank G' →
      HaltsExactly (cont (side.pick cur))
        ((cont (side.pick cur)).startCfg
          (Function.update tape i (ParkedTape (mid ++ cur :: post) G'))) k v) :
    ∃ (cost : Nat) (G' : List TapeSymbol), AllBlank G' ∧
      HaltsExactly (readPhase side i cont)
        ((readPhase side i cont).startCfg tape) cost v ∧
      ((readPhase side i cont).step^[cost])
        ((readPhase side i cont).startCfg tape) =
        TypedConfiguration.inRight true (TypedConfiguration.inRight false
          (TypedConfiguration.inRight true (TypedConfiguration.inRight
            (sideBit1 side cur) (TypedConfiguration.inRight true
              (TypedConfiguration.inRight (sideBit2 side cur)
                (TypedConfiguration.inRight false
                  (((cont (side.pick cur)).step^[k])
                    ((cont (side.pick cur)).startCfg
                      (Function.update tape i
                        (ParkedTape (mid ++ cur :: post) G')))))))))) := by
  classical
  have hCl : (Block.toCells cur).length = 6 := Block.toCells_length cur
  -- ===== junction 1: enter =====
  set T1 : Fin tapes → Tape := Function.update tape i
    (cellsTape [TapeSymbol.blank]
      (encodeBlocks (mid ++ cur :: post) ++ G)) with hT1
  have htp1 : (((moveUpTo i 1 HeadMove.right).step^[1])
      ((moveUpTo i 1 HeadMove.right).startCfg tape)).tape = T1 := by
    rw [moveUpTo_tape i 1 HeadMove.right (by omega) tape, hT1]
    congr 1
    rw [Function.iterate_one, hi, ParkedTape]
    exact cellsTape_moveRight _ _ _
  have hT1i : T1 i = cellsTape [TapeSymbol.blank]
      (encodeBlocks (mid ++ cur :: post) ++ G) := by
    rw [hT1]; simp
  -- ===== junction 2: walk =====
  obtain ⟨hw, -, hwt⟩ := walkToFlag_spec side i T1 [TapeSymbol.blank] G
    mid cur post hmid hcur hT1i
  set W1 := loopCost (fun _ => blockReadSteps) mid.length + blockReadSteps
    with hW1
  set T2 := scanTapesDir T1 i HeadMove.right (6 * (mid.length + 1)) with hT2
  have hsplit : encodeBlocks (mid ++ cur :: post) =
      encodeBlocks (mid ++ [cur]) ++ encodeBlocks post := by
    rw [← encodeBlocks_append]
    congr 1
    simp
  have hT2i : T2 i =
      cellsTape ((encodeBlocks (mid ++ [cur])).reverse ++ [TapeSymbol.blank])
        (encodeBlocks post ++ G) := by
    rw [hT2, scanTapesDir_self, hT1i, hsplit, List.append_assoc,
      show 6 * (mid.length + 1) = (encodeBlocks (mid ++ [cur])).length by
        rw [encodeBlocks_length]; simp,
      cellsTape_advance]
  -- ===== junction 3: back to the flagged block =====
  obtain ⟨G₃, hG₃, hret3⟩ := retreat_block (Block.toCells cur).reverse
    ((encodeBlocks mid).reverse ++ [TapeSymbol.blank]) post G hG
  set T3 := Function.update T2 i
    (cellsTape ((encodeBlocks mid).reverse ++ [TapeSymbol.blank])
      (Block.toCells cur ++ (encodeBlocks post ++ G₃))) with hT3
  have htp3 : (((moveUpTo i 6 HeadMove.left).step^[6])
      ((moveUpTo i 6 HeadMove.left).startCfg T2)).tape = T3 := by
    rw [moveUpTo_tape i 6 HeadMove.left (by omega) T2, hT3]
    congr 1
    rw [hT2i,
      show (encodeBlocks (mid ++ [cur])).reverse ++ [TapeSymbol.blank] =
          (Block.toCells cur).reverse ++
            ((encodeBlocks mid).reverse ++ [TapeSymbol.blank]) by
        rw [encodeBlocks_append]
        simp [List.reverse_append, encodeBlocks_cons],
      show (6 : Nat) = ((Block.toCells cur).reverse).length by simp [hCl]]
    rw [hret3, List.reverse_reverse]
  have hT3i : T3 i = cellsTape
      ((encodeBlocks mid).reverse ++ [TapeSymbol.blank])
      (Block.toCells cur ++ (encodeBlocks post ++ G₃)) := by
    rw [hT3]; simp
  -- ===== junction 4: first probe =====
  have hread1 : HaltsExactly (blockRead i (sideBit1 side))
      ((blockRead i (sideBit1 side)).startCfg T3) blockReadSteps
      (sideBit1 side cur) := by
    have h := blockRead_spec i (sideBit1 side) T3
    rwa [blockOfCells_cellsTape i T3 _ _ cur hT3i] at h
  set T4 := Function.update T3 i
    (cellsTape ((Block.toCells cur).reverse ++
        ((encodeBlocks mid).reverse ++ [TapeSymbol.blank]))
      (encodeBlocks post ++ G₃)) with hT4
  have htp4 : (((blockRead i (sideBit1 side)).step^[blockReadSteps])
      ((blockRead i (sideBit1 side)).startCfg T3)).tape = T4 := by
    have h := blockRead_tape i (sideBit1 side) T3
    rw [show (blockRead i (sideBit1 side)).startCfg T3 =
        TypedConfiguration.inLeftState
          ((readCellRight i).startCfg T3) from rfl] at *
    rw [h, hT4]
    funext j
    by_cases hj : j = i
    · subst hj
      rw [scanTapesDir_self, hT3i,
        show (6 : Nat) = (Block.toCells cur).length from hCl.symm,
        cellsTape_advance]
      simp
    · simp [scanTapesDir, hj]
  have hT4i : T4 i = cellsTape
      ((Block.toCells cur).reverse ++
        ((encodeBlocks mid).reverse ++ [TapeSymbol.blank]))
      (encodeBlocks post ++ G₃) := by
    rw [hT4]; simp
  -- ===== junction 5: back again =====
  obtain ⟨G₅, hG₅, hret5⟩ := retreat_block (Block.toCells cur).reverse
    ((encodeBlocks mid).reverse ++ [TapeSymbol.blank]) post G₃ hG₃
  set T5 := Function.update T4 i
    (cellsTape ((encodeBlocks mid).reverse ++ [TapeSymbol.blank])
      (Block.toCells cur ++ (encodeBlocks post ++ G₅))) with hT5
  have htp5 : (((moveUpTo i 6 HeadMove.left).step^[6])
      ((moveUpTo i 6 HeadMove.left).startCfg T4)).tape = T5 := by
    rw [moveUpTo_tape i 6 HeadMove.left (by omega) T4, hT5]
    congr 1
    rw [hT4i,
      show (6 : Nat) = ((Block.toCells cur).reverse).length by simp [hCl]]
    rw [hret5, List.reverse_reverse]
  have hT5i : T5 i = cellsTape
      ((encodeBlocks mid).reverse ++ [TapeSymbol.blank])
      (Block.toCells cur ++ (encodeBlocks post ++ G₅)) := by
    rw [hT5]; simp
  -- ===== junction 6: second probe =====
  have hread2 : HaltsExactly (blockRead i (sideBit2 side))
      ((blockRead i (sideBit2 side)).startCfg T5) blockReadSteps
      (sideBit2 side cur) := by
    have h := blockRead_spec i (sideBit2 side) T5
    rwa [blockOfCells_cellsTape i T5 _ _ cur hT5i] at h
  set T6 := Function.update T5 i
    (cellsTape ((Block.toCells cur).reverse ++
        ((encodeBlocks mid).reverse ++ [TapeSymbol.blank]))
      (encodeBlocks post ++ G₅)) with hT6
  have htp6 : (((blockRead i (sideBit2 side)).step^[blockReadSteps])
      ((blockRead i (sideBit2 side)).startCfg T5)).tape = T6 := by
    have h := blockRead_tape i (sideBit2 side) T5
    rw [show (blockRead i (sideBit2 side)).startCfg T5 =
        TypedConfiguration.inLeftState
          ((readCellRight i).startCfg T5) from rfl] at *
    rw [h, hT6]
    funext j
    by_cases hj : j = i
    · subst hj
      rw [scanTapesDir_self, hT5i,
        show (6 : Nat) = (Block.toCells cur).length from hCl.symm,
        cellsTape_advance]
      simp
    · simp [scanTapesDir, hj]
  have hT6i : T6 i = cellsTape
      ((Block.toCells cur).reverse ++
        ((encodeBlocks mid).reverse ++ [TapeSymbol.blank]))
      (encodeBlocks post ++ G₅) := by
    rw [hT6]; simp
  -- ===== junction 7: park =====
  set Wp := (Block.toCells cur).reverse ++ (encodeBlocks mid).reverse
    with hWp
  have hassoc : (Block.toCells cur).reverse ++
      ((encodeBlocks mid).reverse ++ [TapeSymbol.blank]) =
      Wp ++ [TapeSymbol.blank] := by
    rw [hWp, List.append_assoc]
  have hWp_nb : ∀ c ∈ Wp, c ≠ TapeSymbol.blank := by
    intro c hc
    rw [hWp] at hc
    rcases List.mem_append.mp hc with h | h
    · exact Block.toCells_ne_blank _ c (List.mem_reverse.mp h)
    · exact encodeBlocks_ne_blank _ c (List.mem_reverse.mp h)
  obtain ⟨hlt', heq'⟩ := blank_scan_left_spec (Wp ++ [TapeSymbol.blank])
    ((encodeBlocks post ++ G₅).headD TapeSymbol.blank)
    ((encodeBlocks post ++ G₅).tail)
  rw [blankIndex_written Wp [] hWp_nb] at hlt' heq'
  have hlt : ∀ j, j < Wp.length →
      ((moveDir HeadMove.left)^[j + 1] (T6 i)).head ≠ TapeSymbol.blank := by
    intro j hj
    rw [hT6i, hassoc]
    exact hlt' j hj
  have heq : ((moveDir HeadMove.left)^[Wp.length + 1] (T6 i)).head =
      TapeSymbol.blank := by
    rw [hT6i, hassoc]
    exact heq'
  obtain ⟨G₇, hG₇, hret7⟩ := retreat_block Wp [TapeSymbol.blank] post G₅ hG₅
  have hWrev : Wp.reverse = encodeBlocks mid ++ Block.toCells cur := by
    rw [hWp, List.reverse_append, List.reverse_reverse, List.reverse_reverse]
  have hX7 : (moveDir HeadMove.left)^[Wp.length + 1] (T6 i) =
      ParkedTape (mid ++ cur :: post) G₇ := by
    rw [Function.iterate_succ_apply', hT6i, hassoc, hret7]
    obtain ⟨r, R', hcons⟩ : ∃ r R',
        Wp.reverse ++ (encodeBlocks post ++ G₇) = r :: R' := by
      rw [hWrev]
      cases hx : encodeBlocks mid ++ Block.toCells cur ++
          (encodeBlocks post ++ G₇) with
      | nil =>
          exfalso
          have := congrArg List.length hx
          simp [Block.toCells] at this
      | cons a as => exact ⟨a, as, rfl⟩
    rw [hcons,
      show ([TapeSymbol.blank] : List TapeSymbol) =
        TapeSymbol.blank :: [] from rfl,
      cellsTape_moveLeft, ← hcons, hWrev, ParkedTape]
    have henc : encodeBlocks (mid ++ cur :: post) =
        encodeBlocks mid ++ (Block.toCells cur ++ encodeBlocks post) := by
      rw [encodeBlocks_append, encodeBlocks_cons]
    rw [henc]
    simp [List.append_assoc]
  set T7 := Function.update T6 i (ParkedTape (mid ++ cur :: post) G₇)
    with hT7
  have htp7 : (((scanToBlank i HeadMove.left).step^[Wp.length * 4 + 3])
      ((scanToBlank i HeadMove.left).startCfg T6)).tape = T7 := by
    rw [scanToBlank_tape_of i HeadMove.left T6 Wp.length hlt heq, hT7]
    show Function.update T6 i
      ((moveDir HeadMove.left)^[Wp.length + 1] (T6 i)) = _
    rw [hX7]
  have hP7 : HaltsExactly (scanToBlank i HeadMove.left)
      ((scanToBlank i HeadMove.left).startCfg T6) (Wp.length * 4 + 3)
      false := scanToBlank_spec_of i HeadMove.left T6 Wp.length hlt heq
  -- ===== the continuation's start =====
  have hT7flat : T7 = Function.update tape i
      (ParkedTape (mid ++ cur :: post) G₇) := by
    rw [hT7, hT6, hT5, hT4, hT3, hT2, hT1]
    simp only [scanTapesDir, Function.update_idem]
  have hK := hcont G₇ hG₇
  rw [← hT7flat] at hK
  -- ===== assemble, inside out =====
  have hsym : symbolOfBits (sideBit1 side cur) (sideBit2 side cur) =
      side.pick cur := symbolOfBits_decode side cur
  have hC7 := chainStepD
    (M₂ := fun _ => cont (symbolOfBits (sideBit1 side cur)
      (sideBit2 side cur)))
    hP7 htp7 (by rw [hsym]; exact hK)
  have hC6 := chainStepD
    (M₂ := fun b₂ => (scanToBlank i HeadMove.left).andThen fun _ =>
      cont (symbolOfBits (sideBit1 side cur) b₂))
    hread2 htp6 hC7.1
  have hC5 := chainStepC (moveUpTo_spec i 6 HeadMove.left (by omega) T4)
    htp5 hC6.1
  have hC4 := chainStepD
    (M₂ := fun b₁ => (moveUpTo i 6 HeadMove.left).andThen fun _ =>
      (blockRead i (sideBit2 side)).andThen fun b₂ =>
        (scanToBlank i HeadMove.left).andThen fun _ =>
          cont (symbolOfBits b₁ b₂))
    hread1 htp4 hC5.1
  have hC3 := chainStepC (moveUpTo_spec i 6 HeadMove.left (by omega) T2)
    htp3 hC4.1
  have hC2 := chainStepC hw hwt hC3.1
  have hC1 := chainStepC (moveUpTo_spec i 1 HeadMove.right (by omega) tape)
    htp1 hC2.1
  rw [show cont (side.pick cur) = cont (symbolOfBits (sideBit1 side cur)
    (sideBit2 side cur)) by rw [hsym]]
  refine ⟨_, G₇, hG₇, hC1.1, ?_⟩
  have hfin := hC1.2
  rw [hC2.2] at hfin
  rw [hC3.2] at hfin
  rw [hC4.2] at hfin
  rw [hC5.2] at hfin
  rw [hC6.2] at hfin
  rw [hC7.2] at hfin
  rw [hT7flat] at hfin
  exact hfin

end SipserGacsLautemann
Source
The per-step simulation program for two-track hosting, specialized to the model of Def_sipser_gacs_lautemann; builds on Def_sgl_step_chain.

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