Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

The track update: write and flag-move, fully specified

Definition
sgl_track_update

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

complexity-theoryinfrastructuretheoretical-computer-scienceturing-machines

The track update, complete: module D's summit.

updateTrack side i s mv performs one full surgical update on a hosted track: from the parked position, walk to the flagged block, write symbol sss there, move the track's head-flag per mvmvmv, and return to the parked position. Its three specifications — updateTrack_stay, updateTrack_right, updateTrack_left — each give an exact halting time and the exact final tapes:

tape′  =  update tape i (ParkedTape (newBlocks) G′),\mathrm{tape}' \;=\; \mathrm{update}\ \mathrm{tape}\ i\ \big(\mathrm{ParkedTape}\ (\mathit{newBlocks})\ G'\big),tape′=update tape i (ParkedTape (newBlocks) G′),

where newBlocks rewrites the flagged block and relocates the flag — onto the same block, the next (materialising a fresh block at the right edge), or the previous (materialising one before the region's start, which relocates the park itself). The ghost parameter GGG — all-blank residue beyond the region from earlier excursions — is carried through every specification, growing as the head explores.

One machine, all cases. The variants differ only in data — window contents and retreat distances — never in shape, so the state type is independent of side and mv and the simulation can dispatch on runtime data without type trouble. There is no runtime edge test anywhere: the normalising window materialises a fresh block by exactly the six operations that leave an existing one intact.

Proof structure. Each specification is a chain of seven junctions — enter, walk, retreat, symbol window, reposition, flag window, park — composed by chainStep, which propagates a piece's halt and final tapes through andThen in one application. The junction tapes are explicit cellsTape values; the only case analyses are the genuine ones (does a neighbouring block exist), handled as list-shape splits in the proof, never as tests in the machine.

With this module the low-level plumbing for merge_empty_scratch_tapes is complete: what remains is the simulation invariant and the per-step program (module E), which consume these specifications without touching step or run again.

Definition code
import Definitions.Def_sgl_patch_run

set_option maxHeartbeats 4000000

/-!
# The track update

Module D of the merge_empty plan, final part.  `updateTrack side i s mv` writes
symbol `s` at the flagged block of a track and moves the flag per `mv`, from
the parked position back to the parked position.

**One machine, all cases.**  The variants differ only in *data* — which cells
the two patch windows write and how far the head retreats between them — never
in shape, so the machine's state type is independent of `side` and `mv` and the
simulation can dispatch on runtime data without type trouble.  In particular
there is no runtime edge test anywhere: a normalising window materialises a
fresh block out of raw tape by exactly the same six operations that leave an
existing block intact.
-/

namespace SipserGacsLautemann

variable {tapes : Nat}

/-! ## Ghost blanks and the parked form -/

def AllBlank (G : List TapeSymbol) : Prop := ∀ c ∈ G, c = TapeSymbol.blank

theorem AllBlank.nil : AllBlank [] := by intro c hc; simp at hc

theorem AllBlank.single : AllBlank [TapeSymbol.blank] := by
  intro c hc; simpa using hc

/-- The region between simulated steps: head parked on the blank left of the
blocks, ghost blanks `G` beyond the region from earlier excursions. -/
def ParkedTape (blocks : List Block) (G : List TapeSymbol) : Tape :=
  cellsTape [] (TapeSymbol.blank :: (encodeBlocks blocks ++ G))

/-! ## Retreats with ghost accounting -/

theorem encodeBlocks_eq_nil {post : List Block}
    (h : encodeBlocks post = []) : post = [] := by
  cases post with
  | nil => rfl
  | cons b bs =>
      rw [encodeBlocks_cons] at h
      simp [Block.toCells] at h

/-- Retreating over `cs` when a block region and ghost lie ahead: the result is
the same shape with a possibly-grown ghost. -/
theorem retreat_block (cs L : List TapeSymbol) (post : List Block)
    (G : List TapeSymbol) (hG : AllBlank G) :
    ∃ G', AllBlank G' ∧
      (moveDir HeadMove.left)^[cs.length]
          (cellsTape (cs ++ L) (encodeBlocks post ++ G)) =
        cellsTape L (cs.reverse ++ (encodeBlocks post ++ G')) := by
  cases hR : encodeBlocks post ++ G with
  | nil =>
      have h2 := List.append_eq_nil_iff.mp hR
      have hpost : post = [] := encodeBlocks_eq_nil h2.1
      subst hpost
      refine ⟨[TapeSymbol.blank], AllBlank.single, ?_⟩
      simp only [encodeBlocks_nil, List.nil_append]
      exact cellsTape_retreat_end cs L
  | cons r rs =>
      refine ⟨G, hG, ?_⟩
      rw [hR, cellsTape_retreat]

/-- Retreating past the left end of the used tape materialises blanks. -/
theorem cellsTape_retreat_past (k : Nat) (r : TapeSymbol)
    (R : List TapeSymbol) :
    (moveDir HeadMove.left)^[k] (cellsTape [] (r :: R)) =
      cellsTape [] (List.replicate k TapeSymbol.blank ++ r :: R) := by
  induction k with
  | zero => simp
  | succ k ih =>
      rw [Function.iterate_succ_apply']
      rw [ih]
      cases k with
      | zero =>
          show moveDir HeadMove.left (cellsTape [] (r :: R)) = _
          rfl
      | succ k =>
          show moveDir HeadMove.left
            (cellsTape [] (TapeSymbol.blank :: _)) = _
          rfl

/-- Retreat with nothing beyond the run on the left. -/
theorem cellsTape_retreat_nilL (cs : List TapeSymbol) (r : TapeSymbol)
    (R : List TapeSymbol) :
    (moveDir HeadMove.left)^[cs.length] (cellsTape cs (r :: R)) =
      cellsTape [] (cs.reverse ++ r :: R) := by
  have h := cellsTape_retreat cs [] R r
  rwa [List.append_nil] at h

/-! ## Chaining -/

/-- One junction of an update chain: compose a piece's halt and tapes with the
rest's, producing the composite's. -/
theorem chainStep {S₁ S₂ : Type} {M₁ : TypedMachine tapes S₁}
    {M₂ : TypedMachine tapes S₂} {T T' Tfin : Fin tapes → Tape}
    {a : Nat} {b : Bool} {k : Nat} {v : Bool}
    (h₁ : HaltsExactly M₁ (M₁.startCfg T) a b)
    (htp : ((M₁.step^[a]) (M₁.startCfg T)).tape = T')
    (h₂ : HaltsExactly M₂ (M₂.startCfg T') k v)
    (h₂tp : ((M₂.step^[k]) (M₂.startCfg T')).tape = Tfin) :
    HaltsExactly (M₁.andThen fun _ => M₂)
        ((M₁.andThen fun _ => M₂).startCfg T) (a + 1 + k) v ∧
      (((M₁.andThen fun _ => M₂).step^[a + 1 + k])
        ((M₁.andThen fun _ => M₂).startCfg T)).tape = Tfin := by
  have h := HaltsExactly.andThen_full (M₂ := fun _ => M₂) h₁
    (by rw [htp]; exact h₂)
  have hcfg : (M₁.andThen fun _ => M₂).startCfg T =
      TypedConfiguration.inLeft (M₁.startCfg T) := rfl
  rw [hcfg]
  refine ⟨h.1, ?_⟩
  rw [h.2, htp, h₂tp]

/-! ## The windows -/

/-- Overwrite a track's symbol and flag; normalise (i.e. keep) the other
track's cells. -/
def symWindow (side : TrackSide) (s : TapeSymbol) (f : Bool) : List PatchOp :=
  match side with
  | .A => [.put (cellsOfSymbol s).1, .put (cellsOfSymbol s).2,
      .put (TapeSymbol.bit f), .norm, .norm, .norm]
  | .B => [.norm, .norm, .norm, .put (cellsOfSymbol s).1,
      .put (cellsOfSymbol s).2, .put (TapeSymbol.bit f)]

/-- Raise a track's flag; keep everything else.  Over raw tape this
materialises a fresh block whose symbols are written blanks. -/
def flagWindow (side : TrackSide) : List PatchOp :=
  match side with
  | .A => [.norm, .norm, .put (TapeSymbol.bit true), .norm, .norm, .norm]
  | .B => [.norm, .norm, .norm, .norm, .norm, .put (TapeSymbol.bit true)]

/-- Keep all six cells. -/
def allNormWindow : List PatchOp := [.norm, .norm, .norm, .norm, .norm, .norm]

/-- Set a track's symbol and flag in a block. -/
def setSymFlag (side : TrackSide) (s : TapeSymbol) (f : Bool) (b : Block) :
    Block :=
  match side with
  | .A => ⟨s, f, b.symB, b.flagB⟩
  | .B => ⟨b.symA, b.flagA, s, f⟩

/-- Set a track's flag in a block. -/
def setFlag (side : TrackSide) (f : Bool) (b : Block) : Block :=
  match side with
  | .A => { b with flagA := f }
  | .B => { b with flagB := f }

/-- The block a flag window materialises from raw tape. -/
def freshFlagged (side : TrackSide) : Block :=
  match side with
  | .A => ⟨TapeSymbol.blank, true, TapeSymbol.blank, false⟩
  | .B => ⟨TapeSymbol.blank, false, TapeSymbol.blank, true⟩

@[simp] theorem normalizeSym_cell_fst (x : TapeSymbol) :
    normalizeSym (cellsOfSymbol x).1 = (cellsOfSymbol x).1 := by
  cases x with
  | blank => rfl
  | bit b => cases b <;> rfl

@[simp] theorem normalizeSym_cell_snd (x : TapeSymbol) :
    normalizeSym (cellsOfSymbol x).2 = (cellsOfSymbol x).2 := by
  cases x with
  | blank => rfl
  | bit b => cases b <;> rfl

/-! ## Window content lemmas -/

theorem patchCellsN_symWindow (side : TrackSide) (s : TapeSymbol) (f : Bool)
    (b : Block) (R : List TapeSymbol) :
    patchCellsN 6 (symWindow side s f) (Block.toCells b ++ R) =
      Block.toCells (setSymFlag side s f b) := by
  cases side <;>
    simp [symWindow, Block.toCells, setSymFlag, patchCellsN, opValue]

theorem patchCellsN_flagWindow (side : TrackSide) (b : Block)
    (R : List TapeSymbol) :
    patchCellsN 6 (flagWindow side) (Block.toCells b ++ R) =
      Block.toCells (setFlag side true b) := by
  cases side <;>
    simp [flagWindow, Block.toCells, setFlag, patchCellsN, opValue]

theorem patchCellsN_allNorm (b : Block) (R : List TapeSymbol) :
    patchCellsN 6 allNormWindow (Block.toCells b ++ R) = Block.toCells b := by
  simp [allNormWindow, Block.toCells, patchCellsN, opValue]

/-- A patch pass reads only what its length covers. -/
theorem patchCellsN_congr_prefix (n : Nat) :
    ∀ (ops : List PatchOp) (R R' : List TapeSymbol),
      R.take n = R'.take n →
      patchCellsN n ops R = patchCellsN n ops R' := by
  induction n with
  | zero => intro ops R R' _; rfl
  | succ n ih =>
      intro ops R R' h
      cases R with
      | nil =>
          cases R' with
          | nil => rfl
          | cons r' rs' => simp at h
      | cons r rs =>
          cases R' with
          | nil => simp at h
          | cons r' rs' =>
              rw [List.take_succ_cons, List.take_succ_cons] at h
              injection h with hr ht
              rw [patchCellsN_succ, patchCellsN_succ]
              simp only [List.headD_cons, List.tail_cons]
              rw [hr, ih ops.tail rs rs' ht]

/-- Over all-blank tape a pass writes its ops' blank-values: the fresh-block
case of the flag window. -/
theorem patchCellsN_allBlank (n : Nat) :
    ∀ (ops : List PatchOp) (R : List TapeSymbol), AllBlank R →
      patchCellsN n ops R = patchCellsN n ops [] := by
  induction n with
  | zero => intro ops R _; rfl
  | succ n ih =>
      intro ops R hR
      rw [patchCellsN_succ, patchCellsN_succ]
      have hh : R.headD TapeSymbol.blank = TapeSymbol.blank := by
        cases R with
        | nil => rfl
        | cons r rs => exact hR r List.mem_cons_self
      have ht : AllBlank R.tail := by
        intro c hc
        cases R with
        | nil => simp at hc
        | cons r rs => exact hR c (List.mem_cons_of_mem _ hc)
      rw [hh, ih ops.tail R.tail ht]
      rfl

theorem patchCellsN_flagWindow_fresh (side : TrackSide)
    (R : List TapeSymbol) (hR : AllBlank R) :
    patchCellsN 6 (flagWindow side) R =
      Block.toCells (freshFlagged side) := by
  rw [patchCellsN_allBlank 6 (flagWindow side) R hR]
  cases side <;> rfl

/-! ## The machine -/

def flagOf : HeadMove → Bool
  | .stay => true
  | _ => false

def retreatOf : HeadMove → Nat
  | .stay => 6
  | .right => 0
  | .left => 12

def window2Of (side : TrackSide) : HeadMove → List PatchOp
  | .stay => allNormWindow
  | _ => flagWindow side

/-- The whole track update: enter, walk to the flag, retreat onto the flagged
block, rewrite it, reposition, patch the flag's destination, park.  Data-only
dependence on `side` and `mv`. -/
def updateTrack (side : TrackSide) (i : Fin tapes) (s : TapeSymbol)
    (mv : HeadMove) :=
  (moveUpTo i 1 HeadMove.right).andThen fun _ =>
    (walkToFlag side i).andThen fun _ =>
      (moveUpTo i 6 HeadMove.left).andThen fun _ =>
        (patchRun6 i (symWindow side s (flagOf mv))).andThen fun _ =>
          (moveUpTo i (retreatOf mv) HeadMove.left).andThen fun _ =>
            (patchRun6 i (window2Of side mv)).andThen fun _ =>
              scanToBlank i HeadMove.left


/-- Head-move past the left end of everything. -/
theorem cellsTape_moveLeft_nilL (r : TapeSymbol) (R : List TapeSymbol) :
    moveDir HeadMove.left (cellsTape [] (r :: R)) =
      cellsTape [] (TapeSymbol.blank :: r :: R) := rfl

/-- `blankIndex` of an unbroken written run. -/
theorem blankIndex_all (W : List TapeSymbol)
    (hW : ∀ c ∈ W, c ≠ TapeSymbol.blank) : blankIndex W = W.length := by
  induction W with
  | nil => rfl
  | cons c cs ih =>
      cases hc : c with
      | blank => exact absurd hc (hW c List.mem_cons_self)
      | bit b =>
          simp only [blankIndex, List.length_cons]
          rw [ih (fun x hx => hW x (List.mem_cons_of_mem _ hx))]

/-! ## The stay variant -/

theorem updateTrack_stay (side : TrackSide) (i : Fin tapes) (s : TapeSymbol)
    (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) :
    ∃ (cost : Nat) (G' : List TapeSymbol), AllBlank G' ∧
      HaltsExactly (updateTrack side i s HeadMove.stay)
        ((updateTrack side i s HeadMove.stay).startCfg tape) cost false ∧
      (((updateTrack side i s HeadMove.stay).step^[cost])
        ((updateTrack side i s HeadMove.stay).startCfg tape)).tape =
        Function.update tape i
          (ParkedTape (mid ++ setSymFlag side s true cur :: post) G') := by
  classical
  -- shorthands
  have hCl : (Block.toCells cur).length = 6 := Block.toCells_length cur
  set newCur := setSymFlag side s true cur with hnewCur
  -- ===== 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 onto 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: rewrite the flagged block =====
  set T4 := Function.update T3 i
    (cellsTape ((Block.toCells newCur).reverse ++
        ((encodeBlocks mid).reverse ++ [TapeSymbol.blank]))
      (encodeBlocks post ++ G₃)) with hT4
  have htp4 : (((patchRun6 i (symWindow side s true)).step^[6])
      ((patchRun6 i (symWindow side s true)).startCfg T3)).tape = T4 := by
    rw [patchRun6_tape i _ T3 _ _ hT3i, hT4]
    congr 1
    rw [patchCellsN_symWindow, ← hnewCur,
      show (6 : Nat) = (Block.toCells cur).length from hCl.symm,
      List.drop_left]
  have hT4i : T4 i = cellsTape
      ((Block.toCells newCur).reverse ++
        ((encodeBlocks mid).reverse ++ [TapeSymbol.blank]))
      (encodeBlocks post ++ G₃) := by
    rw [hT4]; simp
  -- ===== junction 5: retreat again (stay) =====
  obtain ⟨G₅, hG₅, hret5⟩ := retreat_block (Block.toCells newCur).reverse
    ((encodeBlocks mid).reverse ++ [TapeSymbol.blank]) post G₃ hG₃
  set T5 := Function.update T4 i
    (cellsTape ((encodeBlocks mid).reverse ++ [TapeSymbol.blank])
      (Block.toCells newCur ++ (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 newCur).reverse).length by
        simp [Block.toCells_length]]
    rw [hret5, List.reverse_reverse]
  have hT5i : T5 i = cellsTape
      ((encodeBlocks mid).reverse ++ [TapeSymbol.blank])
      (Block.toCells newCur ++ (encodeBlocks post ++ G₅)) := by
    rw [hT5]; simp
  -- ===== junction 6: identity window =====
  set T6 := Function.update T5 i
    (cellsTape ((Block.toCells newCur).reverse ++
        ((encodeBlocks mid).reverse ++ [TapeSymbol.blank]))
      (encodeBlocks post ++ G₅)) with hT6
  have htp6 : (((patchRun6 i allNormWindow).step^[6])
      ((patchRun6 i allNormWindow).startCfg T5)).tape = T6 := by
    rw [patchRun6_tape i _ T5 _ _ hT5i, hT6]
    congr 1
    rw [patchCellsN_allNorm,
      show (6 : Nat) = (Block.toCells newCur).length from
        (Block.toCells_length newCur).symm,
      List.drop_left]
  have hT6i : T6 i = cellsTape
      ((Block.toCells newCur).reverse ++
        ((encodeBlocks mid).reverse ++ [TapeSymbol.blank]))
      (encodeBlocks post ++ G₅) := by
    rw [hT6]; simp
  -- ===== junction 7: park =====
  set Wp := (Block.toCells newCur).reverse ++ (encodeBlocks mid).reverse
    with hWp
  have hassoc : (Block.toCells newCur).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 : ∀ k, k < Wp.length →
      ((moveDir HeadMove.left)^[k + 1] (T6 i)).head ≠ TapeSymbol.blank := by
    intro k hk
    rw [hT6i, hassoc]
    exact hlt' k hk
  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 newCur := by
    rw [hWp, List.reverse_append, List.reverse_reverse, List.reverse_reverse]
  have hX7 : (moveDir HeadMove.left)^[Wp.length + 1] (T6 i) =
      ParkedTape (mid ++ newCur :: 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 newCur ++
          (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 ++ newCur :: post) =
        encodeBlocks mid ++ (Block.toCells newCur ++ encodeBlocks post) := by
      rw [encodeBlocks_append, encodeBlocks_cons]
    rw [henc]
    simp [List.append_assoc]
  set T7 := Function.update T6 i (ParkedTape (mid ++ newCur :: 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
  -- ===== assemble =====
  have hC6 := chainStep (patchRun6_spec i allNormWindow T5 _ _ hT5i) htp6
    hP7 htp7
  have hC5 := chainStep (moveUpTo_spec i 6 HeadMove.left (by omega) T4) htp5
    hC6.1 hC6.2
  have hC4 := chainStep (patchRun6_spec i (symWindow side s true) T3 _ _ hT3i)
    htp4 hC5.1 hC5.2
  have hC3 := chainStep (moveUpTo_spec i 6 HeadMove.left (by omega) T2) htp3
    hC4.1 hC4.2
  have hC2 := chainStep hw hwt hC3.1 hC3.2
  have hC1 := chainStep (moveUpTo_spec i 1 HeadMove.right (by omega) tape)
    htp1 hC2.1 hC2.2
  refine ⟨_, G₇, hG₇, hC1.1, ?_⟩
  have hfin := hC1.2
  rw [hT7, hT6, hT5, hT4, hT3, hT2, hT1] at hfin
  simp only [scanTapesDir, Function.update_idem] at hfin
  exact hfin


theorem AllBlank.drop {G : List TapeSymbol} (hG : AllBlank G) (n : Nat) :
    AllBlank (G.drop n) :=
  fun c hc => hG c (List.mem_of_mem_drop hc)

/-- The region a rightward flag-move produces: the flag lands on the next
block, or on a materialised fresh one at the region's end. -/
def rightResult (side : TrackSide) (mid : List Block) (newCur : Block) :
    List Block → List Block
  | nxt :: post' => mid ++ newCur :: setFlag side true nxt :: post'
  | [] => mid ++ [newCur, freshFlagged side]

/-! ## The right variant -/

theorem updateTrack_right (side : TrackSide) (i : Fin tapes) (s : TapeSymbol)
    (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) :
    ∃ (cost : Nat) (G' : List TapeSymbol), AllBlank G' ∧
      HaltsExactly (updateTrack side i s HeadMove.right)
        ((updateTrack side i s HeadMove.right).startCfg tape) cost false ∧
      (((updateTrack side i s HeadMove.right).step^[cost])
        ((updateTrack side i s HeadMove.right).startCfg tape)).tape =
        Function.update tape i
          (ParkedTape
            (rightResult side mid (setSymFlag side s false cur) post) G') := by
  classical
  have hCl : (Block.toCells cur).length = 6 := Block.toCells_length cur
  set newCur := setSymFlag side s false cur with hnewCur
  -- ===== junctions 1-4: shared skeleton =====
  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
  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]
  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
  set T4 := Function.update T3 i
    (cellsTape ((Block.toCells newCur).reverse ++
        ((encodeBlocks mid).reverse ++ [TapeSymbol.blank]))
      (encodeBlocks post ++ G₃)) with hT4
  have htp4 : (((patchRun6 i (symWindow side s false)).step^[6])
      ((patchRun6 i (symWindow side s false)).startCfg T3)).tape = T4 := by
    rw [patchRun6_tape i _ T3 _ _ hT3i, hT4]
    congr 1
    rw [patchCellsN_symWindow, ← hnewCur,
      show (6 : Nat) = (Block.toCells cur).length from hCl.symm,
      List.drop_left]
  have hT4i : T4 i = cellsTape
      ((Block.toCells newCur).reverse ++
        ((encodeBlocks mid).reverse ++ [TapeSymbol.blank]))
      (encodeBlocks post ++ G₃) := by
    rw [hT4]; simp
  -- ===== junction 5: no movement =====
  have h5 : HaltsExactly (moveUpTo i 0 HeadMove.left)
      ((moveUpTo i 0 HeadMove.left).startCfg T4) 0 true :=
    moveUpTo_spec i 0 HeadMove.left (by omega) T4
  have htp5 : (((moveUpTo i 0 HeadMove.left).step^[0])
      ((moveUpTo i 0 HeadMove.left).startCfg T4)).tape = T4 := rfl
  -- ===== junctions 6-7: split on whether a next block exists =====
  cases post with
  | cons nxt post' =>
      set sNxt := setFlag side true nxt with hsNxt
      have hR4 : T4 i = cellsTape
          ((Block.toCells newCur).reverse ++
            ((encodeBlocks mid).reverse ++ [TapeSymbol.blank]))
          (Block.toCells nxt ++ (encodeBlocks post' ++ G₃)) := by
        rw [hT4i, encodeBlocks_cons, List.append_assoc]
      set T6 := Function.update T4 i
        (cellsTape ((Block.toCells sNxt).reverse ++
            ((Block.toCells newCur).reverse ++
              ((encodeBlocks mid).reverse ++ [TapeSymbol.blank])))
          (encodeBlocks post' ++ G₃)) with hT6
      have htp6 : (((patchRun6 i (flagWindow side)).step^[6])
          ((patchRun6 i (flagWindow side)).startCfg T4)).tape = T6 := by
        rw [patchRun6_tape i _ T4 _ _ hR4, hT6]
        congr 1
        rw [patchCellsN_flagWindow, ← hsNxt,
          show (6 : Nat) = (Block.toCells nxt).length from
            (Block.toCells_length nxt).symm,
          List.drop_left]
      have hT6i : T6 i = cellsTape
          ((Block.toCells sNxt).reverse ++
            ((Block.toCells newCur).reverse ++
              ((encodeBlocks mid).reverse ++ [TapeSymbol.blank])))
          (encodeBlocks post' ++ G₃) := by
        rw [hT6]; simp
      -- park
      set Wp := (Block.toCells sNxt).reverse ++
        ((Block.toCells newCur).reverse ++ (encodeBlocks mid).reverse)
        with hWp
      have hassoc : (Block.toCells sNxt).reverse ++
          ((Block.toCells newCur).reverse ++
            ((encodeBlocks mid).reverse ++ [TapeSymbol.blank])) =
          Wp ++ [TapeSymbol.blank] := by
        rw [hWp]
        simp [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)
        · rcases List.mem_append.mp h 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 : ∀ k, k < Wp.length →
          ((moveDir HeadMove.left)^[k + 1] (T6 i)).head ≠
            TapeSymbol.blank := by
        intro k hk
        rw [hT6i, hassoc]
        exact hlt' k hk
      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 newCur ++ Block.toCells sNxt) := by
        rw [hWp]
        simp [List.reverse_append]
      have hX7 : (moveDir HeadMove.left)^[Wp.length + 1] (T6 i) =
          ParkedTape (mid ++ newCur :: sNxt :: 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 newCur ++ Block.toCells sNxt) ++
              (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 ++ newCur :: sNxt :: post') =
            encodeBlocks mid ++ (Block.toCells newCur ++
              (Block.toCells sNxt ++ encodeBlocks post')) := by
          rw [encodeBlocks_append, encodeBlocks_cons, encodeBlocks_cons]
        rw [henc]
        simp [List.append_assoc]
      set T7 := Function.update T6 i
        (ParkedTape (mid ++ newCur :: sNxt :: 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
      have hC6 := chainStep (patchRun6_spec i (flagWindow side) T4 _ _ hR4)
        htp6 hP7 htp7
      have hC5 := chainStep h5 htp5 hC6.1 hC6.2
      have hC4 := chainStep
        (patchRun6_spec i (symWindow side s false) T3 _ _ hT3i) htp4
        hC5.1 hC5.2
      have hC3 := chainStep (moveUpTo_spec i 6 HeadMove.left (by omega) T2)
        htp3 hC4.1 hC4.2
      have hC2 := chainStep hw hwt hC3.1 hC3.2
      have hC1 := chainStep
        (moveUpTo_spec i 1 HeadMove.right (by omega) tape) htp1 hC2.1 hC2.2
      refine ⟨_, G₇, hG₇, hC1.1, ?_⟩
      have hfin := hC1.2
      rw [hT7, hT6, hT4, hT3, hT2, hT1] at hfin
      simp only [scanTapesDir, Function.update_idem] at hfin
      exact hfin
  | nil =>
      have hR4 : T4 i = cellsTape
          ((Block.toCells newCur).reverse ++
            ((encodeBlocks mid).reverse ++ [TapeSymbol.blank])) G₃ := by
        rw [hT4i]
        simp
      set T6 := Function.update T4 i
        (cellsTape ((Block.toCells (freshFlagged side)).reverse ++
            ((Block.toCells newCur).reverse ++
              ((encodeBlocks mid).reverse ++ [TapeSymbol.blank])))
          (G₃.drop 6)) with hT6
      have htp6 : (((patchRun6 i (flagWindow side)).step^[6])
          ((patchRun6 i (flagWindow side)).startCfg T4)).tape = T6 := by
        rw [patchRun6_tape i _ T4 _ _ hR4, hT6]
        congr 1
        rw [patchCellsN_flagWindow_fresh side G₃ hG₃]
      have hT6i : T6 i = cellsTape
          ((Block.toCells (freshFlagged side)).reverse ++
            ((Block.toCells newCur).reverse ++
              ((encodeBlocks mid).reverse ++ [TapeSymbol.blank])))
          (G₃.drop 6) := by
        rw [hT6]; simp
      have hG₆ : AllBlank (G₃.drop 6) := hG₃.drop 6
      set Wp := (Block.toCells (freshFlagged side)).reverse ++
        ((Block.toCells newCur).reverse ++ (encodeBlocks mid).reverse)
        with hWp
      have hassoc : (Block.toCells (freshFlagged side)).reverse ++
          ((Block.toCells newCur).reverse ++
            ((encodeBlocks mid).reverse ++ [TapeSymbol.blank])) =
          Wp ++ [TapeSymbol.blank] := by
        rw [hWp]
        simp [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)
        · rcases List.mem_append.mp h 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])
        ((G₃.drop 6).headD TapeSymbol.blank) ((G₃.drop 6).tail)
      rw [blankIndex_written Wp [] hWp_nb] at hlt' heq'
      have hlt : ∀ k, k < Wp.length →
          ((moveDir HeadMove.left)^[k + 1] (T6 i)).head ≠
            TapeSymbol.blank := by
        intro k hk
        rw [hT6i, hassoc]
        exact hlt' k hk
      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] []
        (G₃.drop 6) hG₆
      have hWrev : Wp.reverse = encodeBlocks mid ++
          (Block.toCells newCur ++ Block.toCells (freshFlagged side)) := by
        rw [hWp]
        simp [List.reverse_append]
      have hX7 : (moveDir HeadMove.left)^[Wp.length + 1] (T6 i) =
          ParkedTape (mid ++ [newCur, freshFlagged side]) G₇ := by
        rw [Function.iterate_succ_apply', hT6i, hassoc]
        have hret7' : (moveDir HeadMove.left)^[Wp.length]
            (cellsTape (Wp ++ [TapeSymbol.blank]) (G₃.drop 6)) =
            cellsTape [TapeSymbol.blank] (Wp.reverse ++ G₇) := by
          have h := hret7
          simpa using h
        rw [hret7']
        obtain ⟨r, R', hcons⟩ : ∃ r R', Wp.reverse ++ G₇ = r :: R' := by
          rw [hWrev]
          cases hx : encodeBlocks mid ++
              (Block.toCells newCur ++
                Block.toCells (freshFlagged side)) ++ 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 ++ [newCur, freshFlagged side]) =
            encodeBlocks mid ++ (Block.toCells newCur ++
              Block.toCells (freshFlagged side)) := by
          rw [encodeBlocks_append, encodeBlocks_cons, encodeBlocks_cons,
            encodeBlocks_nil, List.append_nil]
        rw [henc]
      set T7 := Function.update T6 i
        (ParkedTape (mid ++ [newCur, freshFlagged side]) 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
      have hC6 := chainStep (patchRun6_spec i (flagWindow side) T4 _ _ hR4)
        htp6 hP7 htp7
      have hC5 := chainStep h5 htp5 hC6.1 hC6.2
      have hC4 := chainStep
        (patchRun6_spec i (symWindow side s false) T3 _ _ hT3i) htp4
        hC5.1 hC5.2
      have hC3 := chainStep (moveUpTo_spec i 6 HeadMove.left (by omega) T2)
        htp3 hC4.1 hC4.2
      have hC2 := chainStep hw hwt hC3.1 hC3.2
      have hC1 := chainStep
        (moveUpTo_spec i 1 HeadMove.right (by omega) tape) htp1 hC2.1 hC2.2
      refine ⟨_, G₇, hG₇, hC1.1, ?_⟩
      have hfin := hC1.2
      rw [hT7, hT6, hT4, hT3, hT2, hT1] at hfin
      simp only [scanTapesDir, Function.update_idem] at hfin
      exact hfin


/-- The region a leftward flag-move produces: the flag lands on the previous
block, or on a materialised fresh one before the region's start. -/
def leftResult (side : TrackSide) (newCur : Block) (post : List Block)
    (mid : List Block) : List Block :=
  match mid.reverse with
  | [] => freshFlagged side :: newCur :: post
  | prv :: rmid' => rmid'.reverse ++ setFlag side true prv :: newCur :: post

theorem leftResult_nil (side : TrackSide) (newCur : Block)
    (post : List Block) :
    leftResult side newCur post [] =
      freshFlagged side :: newCur :: post := rfl

theorem leftResult_concat (side : TrackSide) (newCur : Block)
    (post : List Block) (mid' : List Block) (prv : Block) :
    leftResult side newCur post (mid' ++ [prv]) =
      mid' ++ setFlag side true prv :: newCur :: post := by
  simp [leftResult]

/-! ## The left variant -/

theorem updateTrack_left (side : TrackSide) (i : Fin tapes) (s : TapeSymbol)
    (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) :
    ∃ (cost : Nat) (G' : List TapeSymbol), AllBlank G' ∧
      HaltsExactly (updateTrack side i s HeadMove.left)
        ((updateTrack side i s HeadMove.left).startCfg tape) cost false ∧
      (((updateTrack side i s HeadMove.left).step^[cost])
        ((updateTrack side i s HeadMove.left).startCfg tape)).tape =
        Function.update tape i
          (ParkedTape
            (leftResult side (setSymFlag side s false cur) post mid) G') := by
  classical
  have hCl : (Block.toCells cur).length = 6 := Block.toCells_length cur
  set newCur := setSymFlag side s false cur with hnewCur
  -- ===== junctions 1-4: shared skeleton =====
  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
  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]
  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
  set T4 := Function.update T3 i
    (cellsTape ((Block.toCells newCur).reverse ++
        ((encodeBlocks mid).reverse ++ [TapeSymbol.blank]))
      (encodeBlocks post ++ G₃)) with hT4
  have htp4 : (((patchRun6 i (symWindow side s false)).step^[6])
      ((patchRun6 i (symWindow side s false)).startCfg T3)).tape = T4 := by
    rw [patchRun6_tape i _ T3 _ _ hT3i, hT4]
    congr 1
    rw [patchCellsN_symWindow, ← hnewCur,
      show (6 : Nat) = (Block.toCells cur).length from hCl.symm,
      List.drop_left]
  have hT4i : T4 i = cellsTape
      ((Block.toCells newCur).reverse ++
        ((encodeBlocks mid).reverse ++ [TapeSymbol.blank]))
      (encodeBlocks post ++ G₃) := by
    rw [hT4]; simp
  -- ===== junctions 5-7: split on whether a previous block exists =====
  rcases List.eq_nil_or_concat mid with rfl | ⟨mid', prv, rfl⟩
  · -- mid = []: the flag walks off the left end; the park relocates
    have hT4i' : T4 i = cellsTape
        ((Block.toCells newCur).reverse ++ [TapeSymbol.blank])
        (encodeBlocks post ++ G₃) := by
      rw [hT4i]
      simp
    obtain ⟨G₅, hG₅, hret5⟩ := retreat_block
      ((Block.toCells newCur).reverse ++ [TapeSymbol.blank]) [] post G₃ hG₃
    have hret5' : (moveDir HeadMove.left)^[7]
        (cellsTape ((Block.toCells newCur).reverse ++ [TapeSymbol.blank])
          (encodeBlocks post ++ G₃)) =
        cellsTape [] (TapeSymbol.blank :: Block.toCells newCur ++
          (encodeBlocks post ++ G₅)) := by
      have h7 : (7 : Nat) =
          ((Block.toCells newCur).reverse ++ [TapeSymbol.blank]).length := by
        simp [Block.toCells_length]
      rw [h7]
      have h := hret5
      rw [List.append_nil] at h
      rw [h]
      simp [List.reverse_append]
    have hX5 : (moveDir HeadMove.left)^[12] (T4 i) =
        cellsTape [] (List.replicate 5 TapeSymbol.blank ++
          TapeSymbol.blank :: Block.toCells newCur ++
            (encodeBlocks post ++ G₅)) := by
      rw [hT4i', show (12 : Nat) = 5 + 7 from rfl,
        Function.iterate_add_apply, hret5']
      exact cellsTape_retreat_past 5 TapeSymbol.blank
        (Block.toCells newCur ++ (encodeBlocks post ++ G₅))
    set T5 := Function.update T4 i
      (cellsTape [] (List.replicate 5 TapeSymbol.blank ++
        TapeSymbol.blank :: Block.toCells newCur ++
          (encodeBlocks post ++ G₅))) with hT5
    have htp5 : (((moveUpTo i 12 HeadMove.left).step^[12])
        ((moveUpTo i 12 HeadMove.left).startCfg T4)).tape = T5 := by
      rw [moveUpTo_tape i 12 HeadMove.left (by omega) T4, hT5]
      exact congrArg (Function.update T4 i) hX5
    have hT5i : T5 i = cellsTape []
        (List.replicate 5 TapeSymbol.blank ++
          TapeSymbol.blank :: Block.toCells newCur ++
            (encodeBlocks post ++ G₅)) := by
      rw [hT5]; simp
    -- the six cells ahead are all blank; the flag window materialises
    have hR5eq : List.replicate 5 TapeSymbol.blank ++
        TapeSymbol.blank :: Block.toCells newCur ++
          (encodeBlocks post ++ G₅) =
        List.replicate 6 TapeSymbol.blank ++
          (Block.toCells newCur ++ (encodeBlocks post ++ G₅)) := by
      rw [show List.replicate 6 TapeSymbol.blank =
          List.replicate 5 TapeSymbol.blank ++ [TapeSymbol.blank] from
          List.replicate_succ' .. ]
      simp [List.append_assoc]
    have hpatch : patchCellsN 6 (flagWindow side)
        (List.replicate 5 TapeSymbol.blank ++
          TapeSymbol.blank :: Block.toCells newCur ++
            (encodeBlocks post ++ G₅)) =
        Block.toCells (freshFlagged side) := by
      rw [hR5eq]
      rw [patchCellsN_congr_prefix 6 (flagWindow side) _
        (List.replicate 6 TapeSymbol.blank)
        (by rw [List.take_left' (by simp), List.take_of_length_le (by simp)])]
      exact patchCellsN_flagWindow_fresh side _
        (fun c hc => (List.eq_of_mem_replicate hc))
    have hdrop : (List.replicate 5 TapeSymbol.blank ++
        TapeSymbol.blank :: Block.toCells newCur ++
          (encodeBlocks post ++ G₅)).drop 6 =
        Block.toCells newCur ++ (encodeBlocks post ++ G₅) := by
      rw [hR5eq, List.drop_left' (by simp)]
    set T6 := Function.update T5 i
      (cellsTape ((Block.toCells (freshFlagged side)).reverse)
        (Block.toCells newCur ++ (encodeBlocks post ++ G₅))) with hT6
    have htp6 : (((patchRun6 i (flagWindow side)).step^[6])
        ((patchRun6 i (flagWindow side)).startCfg T5)).tape = T6 := by
      rw [patchRun6_tape i _ T5 _ _ hT5i, hT6]
      refine congrArg (Function.update T5 i) ?_
      rw [hpatch, hdrop]
      simp
    have hT6i : T6 i = cellsTape
        ((Block.toCells (freshFlagged side)).reverse)
        (Block.toCells newCur ++ (encodeBlocks post ++ G₅)) := by
      rw [hT6]; simp
    -- park: six written cells, no blank behind them
    have hW_nb : ∀ c ∈ (Block.toCells (freshFlagged side)).reverse,
        c ≠ TapeSymbol.blank := by
      intro c hc
      exact Block.toCells_ne_blank _ c (List.mem_reverse.mp hc)
    obtain ⟨hlt', heq'⟩ := blank_scan_left_spec
      ((Block.toCells (freshFlagged side)).reverse)
      ((Block.toCells newCur ++ (encodeBlocks post ++ G₅)).headD
        TapeSymbol.blank)
      ((Block.toCells newCur ++ (encodeBlocks post ++ G₅)).tail)
    rw [blankIndex_all _ hW_nb] at hlt' heq'
    have hWl : ((Block.toCells (freshFlagged side)).reverse).length = 6 := by
      simp [Block.toCells_length]
    have hlt : ∀ k, k < 6 →
        ((moveDir HeadMove.left)^[k + 1] (T6 i)).head ≠
          TapeSymbol.blank := by
      intro k hk
      rw [hT6i]
      exact hlt' k (by omega)
    have heq : ((moveDir HeadMove.left)^[6 + 1] (T6 i)).head =
        TapeSymbol.blank := by
      rw [hT6i]
      have h := heq'
      rw [hWl] at h
      exact h
    have hX7 : (moveDir HeadMove.left)^[6 + 1] (T6 i) =
        ParkedTape (freshFlagged side :: newCur :: post) G₅ := by
      rw [Function.iterate_succ_apply', hT6i]
      obtain ⟨r, R', hcons⟩ : ∃ r R',
          Block.toCells newCur ++ (encodeBlocks post ++ G₅) = r :: R' := by
        cases hx : Block.toCells newCur ++ (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 (6 : Nat) =
          ((Block.toCells (freshFlagged side)).reverse).length from hWl.symm]
      rw [cellsTape_retreat_nilL, List.reverse_reverse, ← hcons]
      obtain ⟨r₂, R₂, hcons₂⟩ : ∃ r₂ R₂,
          Block.toCells (freshFlagged side) ++
            (Block.toCells newCur ++ (encodeBlocks post ++ G₅)) =
            r₂ :: R₂ := by
        cases hx : Block.toCells (freshFlagged side) ++
            (Block.toCells newCur ++ (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₂, cellsTape_moveLeft_nilL, ← hcons₂, ParkedTape]
      simp [encodeBlocks_cons, List.append_assoc]
    set T7 := Function.update T6 i
      (ParkedTape (freshFlagged side :: newCur :: post) G₅) with hT7
    have htp7 : (((scanToBlank i HeadMove.left).step^[6 * 4 + 3])
        ((scanToBlank i HeadMove.left).startCfg T6)).tape = T7 := by
      rw [scanToBlank_tape_of i HeadMove.left T6 6 hlt heq, hT7]
      show Function.update T6 i
        ((moveDir HeadMove.left)^[6 + 1] (T6 i)) = _
      rw [hX7]
    have hP7 : HaltsExactly (scanToBlank i HeadMove.left)
        ((scanToBlank i HeadMove.left).startCfg T6) (6 * 4 + 3) false :=
      scanToBlank_spec_of i HeadMove.left T6 6 hlt heq
    have hC6 := chainStep (patchRun6_spec i (flagWindow side) T5 _ _ hT5i)
      htp6 hP7 htp7
    have hC5 := chainStep (moveUpTo_spec i 12 HeadMove.left (by omega) T4)
      htp5 hC6.1 hC6.2
    have hC4 := chainStep
      (patchRun6_spec i (symWindow side s false) T3 _ _ hT3i) htp4
      hC5.1 hC5.2
    have hC3 := chainStep (moveUpTo_spec i 6 HeadMove.left (by omega) T2)
      htp3 hC4.1 hC4.2
    have hC2 := chainStep hw hwt hC3.1 hC3.2
    have hC1 := chainStep
      (moveUpTo_spec i 1 HeadMove.right (by omega) tape) htp1 hC2.1 hC2.2
    have hT7flat : T7 = Function.update tape i
        (ParkedTape (freshFlagged side :: newCur :: post) G₅) := by
      rw [hT7, hT6, hT5, hT4, hT3, hT2, hT1]
      simp only [scanTapesDir, Function.update_idem]
    refine ⟨_, G₅, hG₅, hC1.1, ?_⟩
    rw [leftResult_nil]
    exact hC1.2.trans hT7flat
  · -- mid = mid' ++ [prv]: the flag lands on the previous block
    simp only [List.concat_eq_append] at *
    set sPrv := setFlag side true prv with hsPrv
    have hL4 : (Block.toCells newCur).reverse ++
        ((encodeBlocks (mid' ++ [prv])).reverse ++ [TapeSymbol.blank]) =
        ((Block.toCells newCur).reverse ++ (Block.toCells prv).reverse) ++
          ((encodeBlocks mid').reverse ++ [TapeSymbol.blank]) := by
      rw [encodeBlocks_append]
      simp [List.reverse_append, encodeBlocks_cons, List.append_assoc]
    obtain ⟨G₅, hG₅, hret5⟩ := retreat_block
      ((Block.toCells newCur).reverse ++ (Block.toCells prv).reverse)
      ((encodeBlocks mid').reverse ++ [TapeSymbol.blank]) post G₃ hG₃
    set T5 := Function.update T4 i
      (cellsTape ((encodeBlocks mid').reverse ++ [TapeSymbol.blank])
        (Block.toCells prv ++ (Block.toCells newCur ++
          (encodeBlocks post ++ G₅)))) with hT5
    have htp5 : (((moveUpTo i 12 HeadMove.left).step^[12])
        ((moveUpTo i 12 HeadMove.left).startCfg T4)).tape = T5 := by
      rw [moveUpTo_tape i 12 HeadMove.left (by omega) T4, hT5]
      refine congrArg (Function.update T4 i) ?_
      rw [hT4i, hL4,
        show (12 : Nat) = ((Block.toCells newCur).reverse ++
          (Block.toCells prv).reverse).length by
            simp [Block.toCells_length]]
      rw [hret5]
      simp [List.reverse_append, List.append_assoc]
    have hT5i : T5 i = cellsTape
        ((encodeBlocks mid').reverse ++ [TapeSymbol.blank])
        (Block.toCells prv ++ (Block.toCells newCur ++
          (encodeBlocks post ++ G₅))) := by
      rw [hT5]; simp
    set T6 := Function.update T5 i
      (cellsTape ((Block.toCells sPrv).reverse ++
          ((encodeBlocks mid').reverse ++ [TapeSymbol.blank]))
        (Block.toCells newCur ++ (encodeBlocks post ++ G₅))) with hT6
    have htp6 : (((patchRun6 i (flagWindow side)).step^[6])
        ((patchRun6 i (flagWindow side)).startCfg T5)).tape = T6 := by
      rw [patchRun6_tape i _ T5 _ _ hT5i, hT6]
      refine congrArg (Function.update T5 i) ?_
      rw [patchCellsN_flagWindow, ← hsPrv,
        show (6 : Nat) = (Block.toCells prv).length from
          (Block.toCells_length prv).symm,
        List.drop_left]
    have hT6i : T6 i = cellsTape
        ((Block.toCells sPrv).reverse ++
          ((encodeBlocks mid').reverse ++ [TapeSymbol.blank]))
        (Block.toCells newCur ++ (encodeBlocks post ++ G₅)) := by
      rw [hT6]; simp
    -- park
    set Wp := (Block.toCells sPrv).reverse ++ (encodeBlocks mid').reverse
      with hWp
    have hassoc : (Block.toCells sPrv).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])
      ((Block.toCells newCur ++ (encodeBlocks post ++ G₅)).headD
        TapeSymbol.blank)
      ((Block.toCells newCur ++ (encodeBlocks post ++ G₅)).tail)
    rw [blankIndex_written Wp [] hWp_nb] at hlt' heq'
    have hlt : ∀ k, k < Wp.length →
        ((moveDir HeadMove.left)^[k + 1] (T6 i)).head ≠
          TapeSymbol.blank := by
      intro k hk
      rw [hT6i, hassoc]
      exact hlt' k hk
    have heq : ((moveDir HeadMove.left)^[Wp.length + 1] (T6 i)).head =
        TapeSymbol.blank := by
      rw [hT6i, hassoc]
      exact heq'
    have hR6 : Block.toCells newCur ++ (encodeBlocks post ++ G₅) =
        encodeBlocks (newCur :: post) ++ G₅ := by
      rw [encodeBlocks_cons]
      simp [List.append_assoc]
    obtain ⟨G₇, hG₇, hret7⟩ := retreat_block Wp [TapeSymbol.blank]
      (newCur :: post) G₅ hG₅
    have hWrev : Wp.reverse = encodeBlocks mid' ++ Block.toCells sPrv := by
      rw [hWp, List.reverse_append, List.reverse_reverse,
        List.reverse_reverse]
    have hX7 : (moveDir HeadMove.left)^[Wp.length + 1] (T6 i) =
        ParkedTape (mid' ++ sPrv :: newCur :: post) G₇ := by
      rw [Function.iterate_succ_apply', hT6i, hassoc, hR6, hret7]
      obtain ⟨r, R', hcons⟩ : ∃ r R',
          Wp.reverse ++ (encodeBlocks (newCur :: post) ++ G₇) = r :: R' := by
        rw [hWrev]
        cases hx : encodeBlocks mid' ++ Block.toCells sPrv ++
            (encodeBlocks (newCur :: 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' ++ sPrv :: newCur :: post) =
          encodeBlocks mid' ++ (Block.toCells sPrv ++
            encodeBlocks (newCur :: post)) := by
        rw [encodeBlocks_append, encodeBlocks_cons]
      rw [henc]
      simp [List.append_assoc]
    set T7 := Function.update T6 i
      (ParkedTape (mid' ++ sPrv :: newCur :: 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
    have hC6 := chainStep (patchRun6_spec i (flagWindow side) T5 _ _ hT5i)
      htp6 hP7 htp7
    have hC5 := chainStep (moveUpTo_spec i 12 HeadMove.left (by omega) T4)
      htp5 hC6.1 hC6.2
    have hC4 := chainStep
      (patchRun6_spec i (symWindow side s false) T3 _ _ hT3i) htp4
      hC5.1 hC5.2
    have hC3 := chainStep (moveUpTo_spec i 6 HeadMove.left (by omega) T2)
      htp3 hC4.1 hC4.2
    have hC2 := chainStep hw hwt hC3.1 hC3.2
    have hC1 := chainStep
      (moveUpTo_spec i 1 HeadMove.right (by omega) tape) htp1 hC2.1 hC2.2
    have hT7flat : T7 = Function.update tape i
        (ParkedTape (mid' ++ sPrv :: newCur :: post) G₇) := by
      rw [hT7, hT6, hT5, hT4, hT3, hT2, hT1]
      simp only [scanTapesDir, Function.update_idem]
    refine ⟨_, G₇, hG₇, hC1.1, ?_⟩
    rw [leftResult_concat]
    exact hC1.2.trans hT7flat

end SipserGacsLautemann
Source
Standard track-surgery simulation for multitape Turing machines, specialized to the model of Def_sipser_gacs_lautemann; builds on Def_sgl_patch_run.

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