Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

The segment shifter

Definition
sgl_shift_seg

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

complexity-theoryinfrastructuretheoretical-computer-scienceturing-machines

The segment shifter: the primitive for in-place input dilation under a three-symbol alphabet.

shiftSeg5 i expects the head on the rightmost cell of a non-blank segment. Each eleven-step cycle picks the cell up (erasing it), carries it five cells right, drops it, and retreats to the cell left of the vacated one; a pickup that reads blank halts the machine. Right-to-left order is what makes the target always blank — cells to the right have already moved. shiftSeg5_spec runs it over a whole segment: cost 11(∣seg∣)+111(|{\rm seg}|)+111(∣seg∣)+1, every cell translated five right, head parked on the boundary blank, with the vacated cells left explicitly blank.

The probe. The zipper representation records only cells actually visited, so a segment's right context may be a materialised-blank history of any length — the visited-blank problem, again. moveDir_probe5 resolves it without touching the shift machine: walking five right and five back changes no content but forces at least five cells beyond the head to exist explicitly, after which every cycle can use the explicit six-cell window form. One lemma, pure tape algebra, no machine case analysis.

A design simplification found while building this. The dilation needs no separate shift-by-one pre-pass: running this same shifter once over the whole input creates a five-blank separator region, and the block-writing loop maintains five-blank separators invariantly — each iteration's six-cell block overwrites the five separators plus the harvested cell, and the shift vacates the next five. One primitive machine serves the entire dilation.

Definition code
import Definitions.Def_sgl_merge_solution

/-!
# Shifting a segment right by five

Module G1 of DESIGN_finish_mission: the primitive for in-place input dilation.

`shiftSeg5 i` expects the head on the rightmost cell of a non-blank segment
whose right context is blank far enough out.  Each eleven-step cycle picks the
cell up (erasing it), carries it five cells right, drops it, and returns to
the cell to the left of the vacated one; when the pickup reads blank the
machine halts.  Right-to-left order is what makes the target cell always
blank: cells to the right have already moved.
-/

namespace SipserGacsLautemann

variable {tapes : Nat}

/-- Carry one cell five to the right, repeatedly, right to left. -/
def shiftSeg5 (i : Fin tapes) : TypedMachine tapes (Fin 12 × TapeSymbol) where
  start := (⟨0, by omega⟩, TapeSymbol.blank)
  transition := fun s symbols =>
    if _h0 : s.1.val = 0 then
      if symbols i = TapeSymbol.blank then
        ((⟨11, by omega⟩, TapeSymbol.blank),
          fun j => (symbols j, HeadMove.stay))
      else
        ((⟨1, by omega⟩, symbols i),
          fun j =>
            (if j = i then TapeSymbol.blank else symbols j,
              if j = i then HeadMove.right else HeadMove.stay))
    else if _h4 : s.1.val ≤ 4 then
      ((⟨s.1.val + 1, by omega⟩, s.2),
        fun j => (symbols j, if j = i then HeadMove.right else HeadMove.stay))
    else if _h5 : s.1.val = 5 then
      ((⟨6, by omega⟩, TapeSymbol.blank),
        fun j =>
          (if j = i then s.2 else symbols j,
            if j = i then HeadMove.left else HeadMove.stay))
    else if _h9 : s.1.val ≤ 9 then
      ((⟨s.1.val + 1, by omega⟩, TapeSymbol.blank),
        fun j => (symbols j, if j = i then HeadMove.left else HeadMove.stay))
    else if _h10 : s.1.val = 10 then
      ((⟨0, by omega⟩, TapeSymbol.blank),
        fun j => (symbols j, if j = i then HeadMove.left else HeadMove.stay))
    else (s, fun j => (symbols j, HeadMove.stay))
  result := fun s => if s.1.val = 11 then some false else none

/-! ## Step equations -/

theorem shiftSeg5_step_halt (i : Fin tapes) (t : Fin tapes → Tape)
    (hb : (t i).head = TapeSymbol.blank) :
    (shiftSeg5 i).step ⟨(⟨0, by omega⟩, TapeSymbol.blank), t⟩ =
      ⟨(⟨11, by omega⟩, TapeSymbol.blank), t⟩ := by
  have hres : (shiftSeg5 i).result (⟨0, by omega⟩, TapeSymbol.blank) = none := by
    simp [shiftSeg5]
  simp only [TypedMachine.step, hres]
  simp only [shiftSeg5, hb]
  norm_num
  funext j
  simp [Tape.write_head_self, Tape.move]

theorem shiftSeg5_step_pick (i : Fin tapes) (t : Fin tapes → Tape)
    (hb : (t i).head ≠ TapeSymbol.blank) :
    (shiftSeg5 i).step ⟨(⟨0, by omega⟩, TapeSymbol.blank), t⟩ =
      ⟨(⟨1, by omega⟩, (t i).head),
        Function.update t i
          (moveDir HeadMove.right (Tape.write (t i) TapeSymbol.blank))⟩ := by
  have hres : (shiftSeg5 i).result (⟨0, by omega⟩, TapeSymbol.blank) = none := by
    simp [shiftSeg5]
  simp only [TypedMachine.step, hres]
  simp only [shiftSeg5]
  norm_num [hb]
  funext j
  by_cases hj : j = i
  · subst hj
    simp [moveDir]
  · simp [hj, Function.update_of_ne hj, Tape.write_head_self, Tape.move]

theorem shiftSeg5_step_right (i : Fin tapes) (t : Fin tapes → Tape)
    (k : Nat) (hk1 : 1 ≤ k) (hk4 : k ≤ 4) (x : TapeSymbol) :
    (shiftSeg5 i).step ⟨(⟨k, by omega⟩, x), t⟩ =
      ⟨(⟨k + 1, by omega⟩, x),
        Function.update t i (moveDir HeadMove.right (t i))⟩ := by
  have hres : (shiftSeg5 i).result (⟨k, by omega⟩, x) = none := by
    simp only [shiftSeg5]
    exact if_neg (by omega)
  simp only [TypedMachine.step, hres]
  simp only [shiftSeg5]
  rw [dif_neg (show ¬ (k = 0) by omega)]
  rw [dif_pos (show k ≤ 4 from hk4)]
  congr 1
  funext j
  by_cases hj : j = i
  · subst hj
    simp [moveDir, Tape.write_head_self]
  · simp [hj, Function.update_of_ne hj, Tape.write_head_self, Tape.move]

theorem shiftSeg5_step_drop (i : Fin tapes) (t : Fin tapes → Tape)
    (x : TapeSymbol) :
    (shiftSeg5 i).step ⟨(⟨5, by omega⟩, x), t⟩ =
      ⟨(⟨6, by omega⟩, TapeSymbol.blank),
        Function.update t i (moveDir HeadMove.left (Tape.write (t i) x))⟩ := by
  have hres : (shiftSeg5 i).result (⟨5, by omega⟩, x) = none := by
    simp [shiftSeg5]
  simp only [TypedMachine.step, hres]
  simp only [shiftSeg5]
  norm_num
  funext j
  by_cases hj : j = i
  · subst hj
    simp [moveDir]
  · simp [hj, Function.update_of_ne hj, Tape.write_head_self, Tape.move]

theorem shiftSeg5_step_left (i : Fin tapes) (t : Fin tapes → Tape)
    (k : Nat) (hk6 : 6 ≤ k) (hk9 : k ≤ 9) (x : TapeSymbol) :
    (shiftSeg5 i).step ⟨(⟨k, by omega⟩, x), t⟩ =
      ⟨(⟨k + 1, by omega⟩, TapeSymbol.blank),
        Function.update t i (moveDir HeadMove.left (t i))⟩ := by
  have hres : (shiftSeg5 i).result (⟨k, by omega⟩, x) = none := by
    simp only [shiftSeg5]
    exact if_neg (by omega)
  simp only [TypedMachine.step, hres]
  simp only [shiftSeg5]
  rw [dif_neg (show ¬ (k = 0) by omega), dif_neg (show ¬ (k ≤ 4) by omega),
    dif_neg (show ¬ (k = 5) by omega), dif_pos (show k ≤ 9 from hk9)]
  congr 1
  funext j
  by_cases hj : j = i
  · subst hj
    simp [moveDir, Tape.write_head_self]
  · simp [hj, Function.update_of_ne hj, Tape.write_head_self, Tape.move]

theorem shiftSeg5_step_home (i : Fin tapes) (t : Fin tapes → Tape)
    (x : TapeSymbol) :
    (shiftSeg5 i).step ⟨(⟨10, by omega⟩, x), t⟩ =
      ⟨(⟨0, by omega⟩, TapeSymbol.blank),
        Function.update t i (moveDir HeadMove.left (t i))⟩ := by
  have hres : (shiftSeg5 i).result (⟨10, by omega⟩, x) = none := by
    simp [shiftSeg5]
  simp only [TypedMachine.step, hres]
  simp only [shiftSeg5]
  norm_num
  funext j
  by_cases hj : j = i
  · subst hj
    simp [moveDir, Tape.write_head_self]
  · simp [hj, Function.update_of_ne hj, Tape.write_head_self, Tape.move]


/-! ## Blank-context move helpers -/

theorem moveDir_right_blank (L R : List TapeSymbol) (hR : AllBlank R) :
    moveDir HeadMove.right (cellsTape L R) =
      cellsTape (TapeSymbol.blank :: L) R.tail := by
  cases R with
  | nil => exact cellsTape_moveRight_nil L
  | cons r R' =>
      have hr : r = TapeSymbol.blank := hR r (by simp)
      rw [show cellsTape L (r :: R') = cellsTape L (TapeSymbol.blank :: R') by
        rw [hr]]
      exact cellsTape_moveRight L TapeSymbol.blank R'

theorem write_cellsTape (L R : List TapeSymbol) (y : TapeSymbol) :
    Tape.write (cellsTape L R) y = cellsTape L (y :: R.tail) := by
  cases R <;> rfl

/-! ## One eleven-step cycle, explicit-cons right context -/

set_option maxHeartbeats 1000000 in
/-- One cycle over a six-cell window: the head cell moves five right, the
window's other five cells are preserved, the head retreats one left of the
vacated cell. -/
theorem shiftSeg5_cycle (i : Fin tapes) (T : Fin tapes → Tape)
    (c y r₁ r₂ r₃ r₄ r₅ : TapeSymbol) (L Q : List TapeSymbol)
    (hy : y ≠ TapeSymbol.blank)
    (hTi : T i = cellsTape (c :: L) (y :: r₁ :: r₂ :: r₃ :: r₄ :: r₅ :: Q)) :
    (((shiftSeg5 i).step^[11]) ⟨(⟨0, by omega⟩, TapeSymbol.blank), T⟩ :
        TypedConfiguration tapes (Fin 12 × TapeSymbol)) =
      ⟨(⟨0, by omega⟩, TapeSymbol.blank),
        Function.update T i
          (cellsTape L (c :: TapeSymbol.blank :: r₁ :: r₂ :: r₃ :: r₄ ::
            y :: Q))⟩ ∧
    ∀ j, j < 11 →
      ((((shiftSeg5 i).step^[j]) ⟨(⟨0, by omega⟩, TapeSymbol.blank), T⟩ :
        TypedConfiguration tapes (Fin 12 × TapeSymbol))).state.1.val ≠ 11 := by
  have hy' : (T i).head = y := by rw [hTi]; rfl
  have e0 := shiftSeg5_step_pick i T (by rw [hy']; exact hy)
  rw [hy'] at e0
  set T1 := Function.update T i
    (cellsTape (TapeSymbol.blank :: c :: L)
      (r₁ :: r₂ :: r₃ :: r₄ :: r₅ :: Q)) with hT1
  have e0' : (shiftSeg5 i).step ⟨(⟨0, by omega⟩, TapeSymbol.blank), T⟩ =
      ⟨(⟨1, by omega⟩, y), T1⟩ := by
    rw [e0, hT1, hTi, write_cellsTape]
    rw [show (y :: r₁ :: r₂ :: r₃ :: r₄ :: r₅ :: Q).tail =
      r₁ :: r₂ :: r₃ :: r₄ :: r₅ :: Q from rfl]
    rw [cellsTape_moveRight]
  have hT1i : T1 i = cellsTape (TapeSymbol.blank :: c :: L)
      (r₁ :: r₂ :: r₃ :: r₄ :: r₅ :: Q) := by rw [hT1]; simp
  -- four carries right
  have e1 := shiftSeg5_step_right i T1 1 (by omega) (by omega) y
  set T2 := Function.update T1 i
    (cellsTape (r₁ :: TapeSymbol.blank :: c :: L) (r₂ :: r₃ :: r₄ :: r₅ :: Q))
    with hT2
  have e1' : (shiftSeg5 i).step ⟨(⟨1, by omega⟩, y), T1⟩ =
      ⟨(⟨2, by omega⟩, y), T2⟩ := by
    rw [e1, hT2, hT1i, cellsTape_moveRight]
  have hT2i : T2 i = cellsTape (r₁ :: TapeSymbol.blank :: c :: L)
      (r₂ :: r₃ :: r₄ :: r₅ :: Q) := by rw [hT2]; simp
  have e2 := shiftSeg5_step_right i T2 2 (by omega) (by omega) y
  set T3 := Function.update T2 i
    (cellsTape (r₂ :: r₁ :: TapeSymbol.blank :: c :: L) (r₃ :: r₄ :: r₅ :: Q))
    with hT3
  have e2' : (shiftSeg5 i).step ⟨(⟨2, by omega⟩, y), T2⟩ =
      ⟨(⟨3, by omega⟩, y), T3⟩ := by
    rw [e2, hT3, hT2i, cellsTape_moveRight]
  have hT3i : T3 i = cellsTape (r₂ :: r₁ :: TapeSymbol.blank :: c :: L)
      (r₃ :: r₄ :: r₅ :: Q) := by rw [hT3]; simp
  have e3 := shiftSeg5_step_right i T3 3 (by omega) (by omega) y
  set T4 := Function.update T3 i
    (cellsTape (r₃ :: r₂ :: r₁ :: TapeSymbol.blank :: c :: L)
      (r₄ :: r₅ :: Q)) with hT4
  have e3' : (shiftSeg5 i).step ⟨(⟨3, by omega⟩, y), T3⟩ =
      ⟨(⟨4, by omega⟩, y), T4⟩ := by
    rw [e3, hT4, hT3i, cellsTape_moveRight]
  have hT4i : T4 i = cellsTape (r₃ :: r₂ :: r₁ :: TapeSymbol.blank :: c :: L)
      (r₄ :: r₅ :: Q) := by rw [hT4]; simp
  have e4 := shiftSeg5_step_right i T4 4 (by omega) (by omega) y
  set T5 := Function.update T4 i
    (cellsTape (r₄ :: r₃ :: r₂ :: r₁ :: TapeSymbol.blank :: c :: L)
      (r₅ :: Q)) with hT5
  have e4' : (shiftSeg5 i).step ⟨(⟨4, by omega⟩, y), T4⟩ =
      ⟨(⟨5, by omega⟩, y), T5⟩ := by
    rw [e4, hT5, hT4i, cellsTape_moveRight]
  have hT5i : T5 i = cellsTape
      (r₄ :: r₃ :: r₂ :: r₁ :: TapeSymbol.blank :: c :: L) (r₅ :: Q) := by
    rw [hT5]; simp
  -- drop
  have e5 := shiftSeg5_step_drop i T5 y
  set T6 := Function.update T5 i
    (cellsTape (r₃ :: r₂ :: r₁ :: TapeSymbol.blank :: c :: L)
      (r₄ :: y :: Q)) with hT6
  have e5' : (shiftSeg5 i).step ⟨(⟨5, by omega⟩, y), T5⟩ =
      ⟨(⟨6, by omega⟩, TapeSymbol.blank), T6⟩ := by
    rw [e5, hT6, hT5i, write_cellsTape]
    rw [show (r₅ :: Q).tail = Q from rfl]
    rw [cellsTape_moveLeft]
  have hT6i : T6 i = cellsTape (r₃ :: r₂ :: r₁ :: TapeSymbol.blank :: c :: L)
      (r₄ :: y :: Q) := by rw [hT6]; simp
  -- five retreats
  have e6 := shiftSeg5_step_left i T6 6 (by omega) (by omega) TapeSymbol.blank
  set T7 := Function.update T6 i
    (cellsTape (r₂ :: r₁ :: TapeSymbol.blank :: c :: L)
      (r₃ :: r₄ :: y :: Q)) with hT7
  have e6' : (shiftSeg5 i).step ⟨(⟨6, by omega⟩, TapeSymbol.blank), T6⟩ =
      ⟨(⟨7, by omega⟩, TapeSymbol.blank), T7⟩ := by
    rw [e6, hT7, hT6i, cellsTape_moveLeft]
  have hT7i : T7 i = cellsTape (r₂ :: r₁ :: TapeSymbol.blank :: c :: L)
      (r₃ :: r₄ :: y :: Q) := by rw [hT7]; simp
  have e7 := shiftSeg5_step_left i T7 7 (by omega) (by omega) TapeSymbol.blank
  set T8 := Function.update T7 i
    (cellsTape (r₁ :: TapeSymbol.blank :: c :: L)
      (r₂ :: r₃ :: r₄ :: y :: Q)) with hT8
  have e7' : (shiftSeg5 i).step ⟨(⟨7, by omega⟩, TapeSymbol.blank), T7⟩ =
      ⟨(⟨8, by omega⟩, TapeSymbol.blank), T8⟩ := by
    rw [e7, hT8, hT7i, cellsTape_moveLeft]
  have hT8i : T8 i = cellsTape (r₁ :: TapeSymbol.blank :: c :: L)
      (r₂ :: r₃ :: r₄ :: y :: Q) := by rw [hT8]; simp
  have e8 := shiftSeg5_step_left i T8 8 (by omega) (by omega) TapeSymbol.blank
  set T9 := Function.update T8 i
    (cellsTape (TapeSymbol.blank :: c :: L)
      (r₁ :: r₂ :: r₃ :: r₄ :: y :: Q)) with hT9
  have e8' : (shiftSeg5 i).step ⟨(⟨8, by omega⟩, TapeSymbol.blank), T8⟩ =
      ⟨(⟨9, by omega⟩, TapeSymbol.blank), T9⟩ := by
    rw [e8, hT9, hT8i, cellsTape_moveLeft]
  have hT9i : T9 i = cellsTape (TapeSymbol.blank :: c :: L)
      (r₁ :: r₂ :: r₃ :: r₄ :: y :: Q) := by rw [hT9]; simp
  have e9 := shiftSeg5_step_left i T9 9 (by omega) (by omega) TapeSymbol.blank
  set T10 := Function.update T9 i
    (cellsTape (c :: L)
      (TapeSymbol.blank :: r₁ :: r₂ :: r₃ :: r₄ :: y :: Q)) with hT10
  have e9' : (shiftSeg5 i).step ⟨(⟨9, by omega⟩, TapeSymbol.blank), T9⟩ =
      ⟨(⟨10, by omega⟩, TapeSymbol.blank), T10⟩ := by
    rw [e9, hT10, hT9i, cellsTape_moveLeft]
  have hT10i : T10 i = cellsTape (c :: L)
      (TapeSymbol.blank :: r₁ :: r₂ :: r₃ :: r₄ :: y :: Q) := by
    rw [hT10]; simp
  have e10 := shiftSeg5_step_home i T10 TapeSymbol.blank
  set T11 := Function.update T10 i
    (cellsTape L
      (c :: TapeSymbol.blank :: r₁ :: r₂ :: r₃ :: r₄ :: y :: Q)) with hT11
  have e10' : (shiftSeg5 i).step ⟨(⟨10, by omega⟩, TapeSymbol.blank), T10⟩ =
      ⟨(⟨0, by omega⟩, TapeSymbol.blank), T11⟩ := by
    rw [e10, hT11, hT10i, cellsTape_moveLeft]
  -- assemble
  have hflat : T11 = Function.update T i
      (cellsTape L (c :: TapeSymbol.blank :: r₁ :: r₂ :: r₃ :: r₄ ::
        y :: Q)) := by
    rw [hT11, hT10, hT9, hT8, hT7, hT6, hT5, hT4, hT3, hT2, hT1]
    simp only [Function.update_idem]
  set M := shiftSeg5 i
  set c₀ : TypedConfiguration tapes (Fin 12 × TapeSymbol) :=
    ⟨(⟨0, by omega⟩, TapeSymbol.blank), T⟩ with hc₀
  have p1 : (M.step^[1]) c₀ = ⟨(⟨1, by omega⟩, y), T1⟩ := by
    rw [Function.iterate_one, hc₀, e0']
  have p2 : (M.step^[2]) c₀ = ⟨(⟨2, by omega⟩, y), T2⟩ := by
    show (M.step^[1+1]) c₀ = _
    rw [Function.iterate_add_apply, p1, Function.iterate_one, e1']
  have p3 : (M.step^[3]) c₀ = ⟨(⟨3, by omega⟩, y), T3⟩ := by
    show (M.step^[1+2]) c₀ = _
    rw [Function.iterate_add_apply, p2, Function.iterate_one, e2']
  have p4 : (M.step^[4]) c₀ = ⟨(⟨4, by omega⟩, y), T4⟩ := by
    show (M.step^[1+3]) c₀ = _
    rw [Function.iterate_add_apply, p3, Function.iterate_one, e3']
  have p5 : (M.step^[5]) c₀ = ⟨(⟨5, by omega⟩, y), T5⟩ := by
    show (M.step^[1+4]) c₀ = _
    rw [Function.iterate_add_apply, p4, Function.iterate_one, e4']
  have p6 : (M.step^[6]) c₀ = ⟨(⟨6, by omega⟩, TapeSymbol.blank), T6⟩ := by
    show (M.step^[1+5]) c₀ = _
    rw [Function.iterate_add_apply, p5, Function.iterate_one, e5']
  have p7 : (M.step^[7]) c₀ = ⟨(⟨7, by omega⟩, TapeSymbol.blank), T7⟩ := by
    show (M.step^[1+6]) c₀ = _
    rw [Function.iterate_add_apply, p6, Function.iterate_one, e6']
  have p8 : (M.step^[8]) c₀ = ⟨(⟨8, by omega⟩, TapeSymbol.blank), T8⟩ := by
    show (M.step^[1+7]) c₀ = _
    rw [Function.iterate_add_apply, p7, Function.iterate_one, e7']
  have p9 : (M.step^[9]) c₀ = ⟨(⟨9, by omega⟩, TapeSymbol.blank), T9⟩ := by
    show (M.step^[1+8]) c₀ = _
    rw [Function.iterate_add_apply, p8, Function.iterate_one, e8']
  have p10 : (M.step^[10]) c₀ = ⟨(⟨10, by omega⟩, TapeSymbol.blank), T10⟩ := by
    show (M.step^[1+9]) c₀ = _
    rw [Function.iterate_add_apply, p9, Function.iterate_one, e9']
  have p11 : (M.step^[11]) c₀ = ⟨(⟨0, by omega⟩, TapeSymbol.blank), T11⟩ := by
    show (M.step^[1+10]) c₀ = _
    rw [Function.iterate_add_apply, p10, Function.iterate_one, e10']
  refine ⟨by rw [p11, hflat], ?_⟩
  intro j hj
  interval_cases j
  · simp [hc₀]
  · rw [p1]; simp
  · rw [p2]; simp
  · rw [p3]; simp
  · rw [p4]; simp
  · rw [p5]; simp
  · rw [p6]; simp
  · rw [p7]; simp
  · rw [p8]; simp
  · rw [p9]; simp
  · rw [p10]; simp


/-! ## The probe: normalising the right context

Walking five right and five back leaves the tape's *content* untouched but
forces at least five cells beyond the head to exist explicitly in the zipper —
materialised blanks become real.  This is what lets every shift cycle use the
explicit-cons form regardless of excursion history. -/

theorem allBlank_eq_replicate {G : List TapeSymbol} (hG : AllBlank G) :
    G = List.replicate G.length TapeSymbol.blank := by
  induction G with
  | nil => rfl
  | cons c G' ih =>
      have hc : c = TapeSymbol.blank := hG c (by simp)
      have hG' : AllBlank G' := fun x hx => hG x (by simp [hx])
      rw [List.length_cons, List.replicate_succ, hc]
      exact congrArg _ (by conv_lhs => rw [ih hG'])

set_option maxHeartbeats 1000000 in
theorem moveDir_probe5 (c y : TapeSymbol) (L G : List TapeSymbol)
    (hG : AllBlank G) :
    ((moveDir HeadMove.left)^[5]) (((moveDir HeadMove.right)^[5])
        (cellsTape (c :: L) (y :: G))) =
      cellsTape (c :: L)
        (y :: List.replicate 5 TapeSymbol.blank ++ G.drop 5) := by
  rw [allBlank_eq_replicate hG]
  rcases Nat.lt_or_ge G.length 5 with h5 | h5
  · interval_cases h : G.length <;>
      simp [List.replicate, cellsTape, moveDir, Tape.move,
        Function.iterate_succ_apply, Function.iterate_zero]
  · obtain ⟨d, hd⟩ := Nat.exists_eq_add_of_le h5
    rw [hd]
    rw [show List.replicate (5 + d) TapeSymbol.blank =
      List.replicate 5 TapeSymbol.blank ++ List.replicate d TapeSymbol.blank
      from (List.replicate_add 5 d _).symm ▸ rfl]
    rw [show (List.replicate 5 TapeSymbol.blank ++
        List.replicate d TapeSymbol.blank).drop 5 =
      List.replicate d TapeSymbol.blank by
        rw [List.drop_append_of_le_length (by simp)]
        simp]
    -- five explicit cells: round trip is the identity
    simp only [List.replicate, List.cons_append, List.nil_append]
    simp [Function.iterate_succ_apply, cellsTape_moveRight,
      cellsTape_moveLeft, moveDir, Tape.move, cellsTape]


/-! ## The whole segment -/

theorem shiftSeg5_run (i : Fin tapes) :
    ∀ (ls : List TapeSymbol) (h : TapeSymbol) (B Q : List TapeSymbol)
      (T : Fin tapes → Tape),
      h ≠ TapeSymbol.blank → (∀ c ∈ ls, c ≠ TapeSymbol.blank) →
      T i = cellsTape (ls ++ TapeSymbol.blank :: B)
        (h :: List.replicate 5 TapeSymbol.blank ++ Q) →
      (((shiftSeg5 i).step^[11 * (ls.length + 1)])
          ⟨(⟨0, by omega⟩, TapeSymbol.blank), T⟩ :
        TypedConfiguration tapes (Fin 12 × TapeSymbol)) =
        ⟨(⟨0, by omega⟩, TapeSymbol.blank),
          Function.update T i
            (cellsTape B (TapeSymbol.blank ::
              List.replicate 5 TapeSymbol.blank ++ (ls.reverse ++ h :: Q)))⟩ ∧
      ∀ j, j < 11 * (ls.length + 1) →
        ((((shiftSeg5 i).step^[j])
            ⟨(⟨0, by omega⟩, TapeSymbol.blank), T⟩ :
          TypedConfiguration tapes (Fin 12 × TapeSymbol))).state.1.val ≠ 11 := by
  intro ls
  induction ls with
  | nil =>
      intro h B Q T hh _ hTi
      have hshape : T i = cellsTape (TapeSymbol.blank :: B)
          (h :: TapeSymbol.blank :: TapeSymbol.blank :: TapeSymbol.blank ::
            TapeSymbol.blank :: TapeSymbol.blank :: Q) := by
        rw [hTi]; rfl
      obtain ⟨hrun, hfresh⟩ := shiftSeg5_cycle i T TapeSymbol.blank h
        TapeSymbol.blank TapeSymbol.blank TapeSymbol.blank TapeSymbol.blank
        TapeSymbol.blank B Q hh hshape
      constructor
      · rw [show 11 * (([] : List TapeSymbol).length + 1) = 11 by simp, hrun]
        rfl
      · intro j hj
        exact hfresh j (by simpa using hj)
  | cons l ls' ih =>
      intro h B Q T hh hls hTi
      have hl : l ≠ TapeSymbol.blank := hls l (by simp)
      have hls' : ∀ c ∈ ls', c ≠ TapeSymbol.blank :=
        fun c hc => hls c (by simp [hc])
      have hshape : T i = cellsTape (l :: (ls' ++ TapeSymbol.blank :: B))
          (h :: TapeSymbol.blank :: TapeSymbol.blank :: TapeSymbol.blank ::
            TapeSymbol.blank :: TapeSymbol.blank :: Q) := by
        rw [hTi]; rfl
      obtain ⟨hcyc, hcfresh⟩ := shiftSeg5_cycle i T l h
        TapeSymbol.blank TapeSymbol.blank TapeSymbol.blank TapeSymbol.blank
        TapeSymbol.blank (ls' ++ TapeSymbol.blank :: B) Q hh hshape
      set T' := Function.update T i
        (cellsTape (ls' ++ TapeSymbol.blank :: B)
          (l :: TapeSymbol.blank :: TapeSymbol.blank :: TapeSymbol.blank ::
            TapeSymbol.blank :: TapeSymbol.blank :: h :: Q)) with hT'
      have hT'i : T' i = cellsTape (ls' ++ TapeSymbol.blank :: B)
          (l :: List.replicate 5 TapeSymbol.blank ++ (h :: Q)) := by
        rw [hT']; simp
      obtain ⟨hrun', hfresh'⟩ := ih l B (h :: Q) T' hl hls' hT'i
      have hsplit : 11 * ((l :: ls').length + 1) =
          11 * (ls'.length + 1) + 11 := by simp [List.length_cons]; ring
      constructor
      · rw [hsplit, Function.iterate_add_apply, hcyc, hrun', hT']
        simp only [Function.update_idem]
        rw [show ls'.reverse ++ l :: (h :: Q) =
          (l :: ls').reverse ++ h :: Q by simp]
      · intro j hj
        rcases Nat.lt_or_ge j 11 with hj11 | hj11
        · exact hcfresh j hj11
        · obtain ⟨j', rfl⟩ := Nat.exists_eq_add_of_le hj11
          rw [Nat.add_comm, Function.iterate_add_apply, hcyc]
          exact hfresh' j' (by rw [hsplit] at hj; omega)

/-- **The segment shifter, as a subroutine.**  `ls` is the segment's cells
left of the head cell `h`, nearest first; everything moves five right, the
head retreats to the boundary blank. -/
theorem shiftSeg5_spec (i : Fin tapes) (ls : List TapeSymbol)
    (h : TapeSymbol) (B Q : List TapeSymbol) (T : Fin tapes → Tape)
    (hh : h ≠ TapeSymbol.blank) (hls : ∀ c ∈ ls, c ≠ TapeSymbol.blank)
    (hTi : T i = cellsTape (ls ++ TapeSymbol.blank :: B)
      (h :: List.replicate 5 TapeSymbol.blank ++ Q)) :
    HaltsExactly (shiftSeg5 i) ((shiftSeg5 i).startCfg T)
      (11 * (ls.length + 1) + 1) false ∧
    (((shiftSeg5 i).step^[11 * (ls.length + 1) + 1])
        ((shiftSeg5 i).startCfg T)).tape =
      Function.update T i
        (cellsTape B (TapeSymbol.blank ::
          List.replicate 5 TapeSymbol.blank ++ (ls.reverse ++ h :: Q))) := by
  obtain ⟨hrun, hfresh⟩ := shiftSeg5_run i ls h B Q T hh hls hTi
  have hstart : (shiftSeg5 i).startCfg T =
      (⟨(⟨0, by omega⟩, TapeSymbol.blank), T⟩ :
        TypedConfiguration tapes (Fin 12 × TapeSymbol)) := rfl
  set Tf := Function.update T i
    (cellsTape B (TapeSymbol.blank ::
      List.replicate 5 TapeSymbol.blank ++ (ls.reverse ++ h :: Q))) with hTf
  have hTfi : (Tf i).head = TapeSymbol.blank := by
    rw [hTf]; simp; rfl
  have hlast : (((shiftSeg5 i).step^[11 * (ls.length + 1) + 1])
      ((shiftSeg5 i).startCfg T) :
      TypedConfiguration tapes (Fin 12 × TapeSymbol)) =
      ⟨(⟨11, by omega⟩, TapeSymbol.blank), Tf⟩ := by
    rw [Function.iterate_succ_apply', hstart, hrun, shiftSeg5_step_halt i Tf hTfi]
  refine ⟨⟨?_, ?_⟩, ?_⟩
  · rw [hlast]
    rfl
  · intro j hj
    rcases Nat.lt_or_ge j (11 * (ls.length + 1)) with hlt | hge
    · have hne := hfresh j hlt
      rw [hstart]
      exact if_neg hne
    · have hj' : j = 11 * (ls.length + 1) := by omega
      subst hj'
      rw [hstart, hrun]
      rfl
  · rw [hlast]

end SipserGacsLautemann
Source
In-place dilation primitive for eliminate_last_scratch_tape; builds on Def_sgl_merge_solution.

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