Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

The read phase, canonical shape

Definition
sgl_read_phase_ex

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

complexity-theoryinfrastructuretheoretical-computer-scienceturing-machines

The read phase in the canonical, self-composing shape.

The earlier readPhase_bounded demands its continuation halt at one fixed time for every tape whose host is the parked region — which a continuation whose runtime depends on the identity tapes cannot supply; that mismatch is what blocked the per-step composition. Here the statement is per identity class: inputs are update base i (Parked blocks G)\mathrm{update}\ base\ i\ (\mathrm{Parked}\ blocks\ G)update base i (Parked blocks G) for fixed base and varying ghost; the continuation's time kkk is an explicit argument, uniform over the ghost (legitimate, because at a fixed identity class the machine's actions are determined and the ghost is never read); and the conclusion is the same shape one level up, with a cost bounded by 100∣blocks∣+300+k100|{\rm blocks}| + 300 + k100∣blocks∣+300+k and the terminal configuration exposed as the seven-layer tower whose exponent is that same kkk — so a consumer rewrites the continuation's own configuration equation under the tower, and read phases nest with the execute tail's specification fitting verbatim.

The junction body is readPhase_bounded's; only the quantifier prefix moved. The general principle, learned the hard way across four failed interfaces: every quantity in a phase specification must be fixed exactly after the data it depends on and before the data it doesn't.

Definition code
import Definitions.Def_sgl_exec_full

/-!
# The read phase, canonical shape

Module E5b of DESIGN_step_spec_endgame.

`readPhase_bounded` demands its continuation halt at one fixed time for
*every* tape whose host is the parked region — which a continuation whose
runtime depends on the identity tapes cannot supply.  Here the statement is
per **identity class**: the input tapes are `Function.update base i (ParkedTape
blocks G)` for a fixed `base` and varying ghost, the continuation's time `k`
is an explicit argument uniform over the ghost, and the conclusion is the same
shape one level up with the tower's exponent being that same `k` — so a
consumer can rewrite the continuation's own configuration equation under the
tower, and read phases nest.  The execute tail's specification is verbatim the
hypothesis.

The junction body is the one from `readPhase_bounded`; only the quantifier
prefix moved.
-/

namespace SipserGacsLautemann

variable {tapes : Nat}

set_option maxHeartbeats 4000000 in
/-- **The read phase over an identity class.** -/
theorem readPhase_ex (side : TrackSide) (i : Fin tapes) {S : Type}
    (cont : TapeSymbol → TypedMachine tapes S)
    (mid : List Block) (cur : Block) (post : List Block)
    (hmid : ∀ b ∈ mid, side.getFlag b = false)
    (hcur : side.getFlag cur = true)
    (k : Nat) (v : Bool) (base : Fin tapes → Tape)
    (hcont : ∀ (G' : List TapeSymbol), AllBlank G' →
      HaltsExactly (cont (side.pick cur))
        ((cont (side.pick cur)).startCfg
          (Function.update base i (ParkedTape (mid ++ cur :: post) G'))) k v) :
    ∃ (cost : Nat),
      cost ≤ 100 * (mid ++ cur :: post).length + 300 + k ∧
      ∀ (G : List TapeSymbol), AllBlank G →
        ∃ G', AllBlank G' ∧
          HaltsExactly (readPhase side i cont)
            ((readPhase side i cont).startCfg
              (Function.update base i (ParkedTape (mid ++ cur :: post) G)))
            cost v ∧
          ((readPhase side i cont).step^[cost])
            ((readPhase side i cont).startCfg
              (Function.update base i (ParkedTape (mid ++ cur :: post) G))) =
            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 base i
                            (ParkedTape (mid ++ cur :: post) G')))))))))) := by
  have hcontB := hcont
  refine ⟨1 + 1 + ((loopCost (fun _ => blockReadSteps) mid.length +
      blockReadSteps) + 1 + (6 + 1 + (blockReadSteps + 1 + (6 + 1 +
      (blockReadSteps + 1 +
      ((((Block.toCells cur).reverse ++
        (encodeBlocks mid).reverse).length) * 4 + 3 + 1 + k)))))),
      ?_, ?_⟩
  · rw [loopCost_const, blockReadSteps_eq]
    simp only [List.length_append, List.length_reverse,
      Block.toCells_length, encodeBlocks_length, List.length_cons]
    omega
  intro G hG
  set tape := Function.update base i (ParkedTape (mid ++ cur :: post) G)
    with htape
  have hi : tape i = ParkedTape (mid ++ cur :: post) G := by
    rw [htape]; simp
  have hcollapse : ∀ Gx, Function.update base i
      (ParkedTape (mid ++ cur :: post) Gx) =
      Function.update tape i (ParkedTape (mid ++ cur :: post) Gx) := by
    intro Gx
    rw [htape, Function.update_idem]
  simp only [hcollapse]
  have 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 := by
    intro G' hG'
    rw [← hcollapse G']
    exact hcontB G' hG'
  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
Quantifier-reordered read phase specification; builds on Def_sgl_exec_full.

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