Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Preparing tapes, and copying with return

Definition
sgl_copy_back

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

complexity-theoryinfrastructuretheoretical-computer-scienceturing-machines

Two compositions the scheduler round repeats.

prepTape i steps left then right, materialising a blank to the left of the head. Every later shape in a round assumes that blank — it is the origin marker a rewind scans back to, and a tape presented as cellsTape [] R has none. Scratch and input tapes alike are prepared once at setup.

copyBack s t copies a run from source to target and returns both heads to its start: the operation a round performs three times, restoring the delegate's input tapes from the originals without disturbing either. The source is left exactly as it was.

Two facts the composition forced into the open. First, copyRun halts when the source blanks, so a copied run must be followed by a blank — the specification now says so, rather than leaving a caller to discover it. Second, a rewind whose right context is empty materialises a blank, so the target's conclusion keeps the normalised headD :: tail form instead of collapsing it: writing the collapsed form would be false exactly when the scratch region is exhausted. Both are the kind of edge that only appears when primitives are composed, which is why the round's atomic operations are being specified before the round itself.

Definition code
import Definitions.Def_sgl_rewind

/-!
# Preparing tapes, and copying with return

Two compositions the scheduler round repeats.

`prepTape i` steps left then right, which materialises a blank to the left of
the head.  Every later shape in the round assumes that blank: it is the origin
marker a rewind scans back to, and a tape presented as `cellsTape [] R` has
none.  Scratch tapes and input tapes alike are prepared once at setup.

`copyBack s t` copies a run from `s` to `t` and returns *both* heads to the
run's start.  That is the operation a round performs three times, restoring the
delegate's input tapes from the originals without disturbing either.
-/

namespace SipserGacsLautemann

variable {tapes : Nat}

/-- Materialise the origin blank. -/
def prepTape (i : Fin tapes) :=
  (moveUpTo i 1 HeadMove.left).andThen fun _ =>
    moveUpTo i 1 HeadMove.right

set_option maxHeartbeats 1000000 in
theorem prepTape_spec (i : Fin tapes) (T : Fin tapes → Tape)
    (R : List TapeSymbol) (hT : T i = cellsTape [] R) :
    HaltsExactly (prepTape i) ((prepTape i).startCfg T) (1 + 1 + 1) true ∧
    (((prepTape i).step^[1 + 1 + 1]) ((prepTape i).startCfg T)).tape =
      Function.update T i (cellsTape [TapeSymbol.blank] R) := by
  have hA := moveUpTo_spec i 1 HeadMove.left (by omega) T
  set T1 := Function.update T i ((moveDir HeadMove.left) (T i)) with hT1
  have hAt : (((moveUpTo i 1 HeadMove.left).step^[1])
      ((moveUpTo i 1 HeadMove.left).startCfg T)).tape = T1 := by
    rw [moveUpTo_tape i 1 HeadMove.left (by omega) T, hT1]
    rfl
  have hB := moveUpTo_spec i 1 HeadMove.right (by omega) T1
  have hBt : (((moveUpTo i 1 HeadMove.right).step^[1])
      ((moveUpTo i 1 HeadMove.right).startCfg T1)).tape =
      Function.update T i (cellsTape [TapeSymbol.blank] R) := by
    rw [moveUpTo_tape i 1 HeadMove.right (by omega) T1, hT1]
    simp only [Function.update_idem, Function.update_self]
    congr 1
    rw [Function.iterate_one]
    exact prePass_enter i [] R T (by rw [hT]; simp)
  have hchain := chainStepC hA hAt hB
  refine ⟨hchain.1, ?_⟩
  have hfin := hchain.2
  have hfin' : ((prepTape i).step^[1 + 1 + 1])
      ((prepTape i).startCfg T) = _ := hfin
  rw [hfin']
  show (((moveUpTo i 1 HeadMove.right).step^[1])
    ((moveUpTo i 1 HeadMove.right).startCfg T1)).tape = _
  rw [hBt]


/-! ## Copy, then return both heads -/

/-- Tapes other than the source and target are untouched by a copy. -/
theorem copyStep_other (s t : Fin tapes) (hst : s ≠ t) :
    ∀ (m : Nat) (T : Fin tapes → Tape) (j : Fin tapes), j ≠ s → j ≠ t →
      (((copyStep s t)^[m]) T) j = T j := by
  intro m
  induction m with
  | zero => intro T j _ _; rfl
  | succ m ih =>
      intro T j hjs hjt
      rw [Function.iterate_succ_apply]
      rw [ih (copyStep s t T) j hjs hjt]
      show (if j = s then _ else if j = t then _ else T j) = _
      rw [if_neg hjs, if_neg hjt]


/-- Copy a run and rewind both tapes to its start. -/
def copyBack (s t : Fin tapes) :=
  (copyRun s t).andThen fun _ =>
    (rewindRun s).andThen fun _ => rewindRun t

set_option maxHeartbeats 4000000 in
/-- **Restore a tape from another.**  The source is left exactly as it was;
the target now carries the same run, both heads on its first cell. -/
theorem copyBack_spec (s t : Fin tapes) (hst : s ≠ t)
    (cs : List TapeSymbol) (Ls Lt Rs Rt : List TapeSymbol)
    (T : Fin tapes → Tape)
    (hnb : ∀ c ∈ cs, c ≠ TapeSymbol.blank)
    (hs : T s = cellsTape (TapeSymbol.blank :: Ls) (cs ++ TapeSymbol.blank :: Rs))
    (ht : T t = cellsTape (TapeSymbol.blank :: Lt) Rt)
    (hlen : cs.length ≤ Rt.length) :
    ∃ cost : Nat,
      HaltsExactly (copyBack s t) ((copyBack s t).startCfg T) cost true ∧
      (((copyBack s t).step^[cost]) ((copyBack s t).startCfg T)).tape =
        Function.update (Function.update T s
          (cellsTape (TapeSymbol.blank :: Ls) (cs ++ TapeSymbol.blank :: Rs))) t
          (cellsTape (TapeSymbol.blank :: Lt)
            (cs ++ (Rt.drop cs.length).headD TapeSymbol.blank ::
              (Rt.drop cs.length).tail)) := by
  classical
  -- the copy
  obtain ⟨hC, hCt⟩ := copyRun_spec s t hst cs.length T
    (copyStep_marks s t hst cs T (TapeSymbol.blank :: Ls) (TapeSymbol.blank :: Rs)
      (TapeSymbol.blank :: Lt) Rt hnb (by rw [hs]) (by rw [ht]))
    (by
      obtain ⟨ha, -⟩ := copyStep_iterate s t hst cs T
        (TapeSymbol.blank :: Ls) (TapeSymbol.blank :: Rs) (TapeSymbol.blank :: Lt) Rt
        (by rw [hs]) (by rw [ht])
      rw [ha]
      rfl)
  obtain ⟨hia, hib⟩ := copyStep_iterate s t hst cs T
    (TapeSymbol.blank :: Ls) (TapeSymbol.blank :: Rs) (TapeSymbol.blank :: Lt) Rt
    (by rw [hs]) (by rw [ht])
  set T1 := ((copyStep s t)^[cs.length]) T with hT1
  have hT1s : T1 s = cellsTape (cs.reverse ++ TapeSymbol.blank :: Ls)
      (TapeSymbol.blank :: Rs) := hia
  have hT1t : T1 t = cellsTape (cs.reverse ++ TapeSymbol.blank :: Lt)
      (Rt.drop cs.length) := hib
  -- rewind the source
  obtain ⟨hRs, hRst⟩ := rewindRun_spec s cs Ls Rs TapeSymbol.blank T1
    hnb (by rw [hT1s])
  set T2 := Function.update T1 s
    (cellsTape (TapeSymbol.blank :: Ls) (cs ++ TapeSymbol.blank :: Rs))
    with hT2
  have hT2t : T2 t = cellsTape (cs.reverse ++ TapeSymbol.blank :: Lt)
      (Rt.drop cs.length) := by
    rw [hT2, Function.update_of_ne (fun h => hst h.symm)]
    exact hT1t
  -- rewind the target
  obtain ⟨hRt, hRtt⟩ := rewindRun_spec t cs Lt ((Rt.drop cs.length).tail)
    ((Rt.drop cs.length).headD TapeSymbol.blank) T2 hnb
    (by rw [hT2t]; exact cellsTape_norm _ _)
  refine ⟨(cs.length * 5 + 4) + 1 +
    ((cs.length * 4 + 3 + 1 + 1) + 1 + (cs.length * 4 + 3 + 1 + 1)), ?_, ?_⟩
  · exact (chainStepC hC hCt (chainStepC hRs hRst hRt).1).1
  · have hch := chainStepC hC hCt (chainStepC hRs hRst hRt).1
    have hin := chainStepC hRs hRst hRt
    have hfin := hch.2
    rw [hin.2] at hfin
    have hfin' : ((copyBack s t).step^[(cs.length * 5 + 4) + 1 +
        ((cs.length * 4 + 3 + 1 + 1) + 1 + (cs.length * 4 + 3 + 1 + 1))])
        ((copyBack s t).startCfg T) = _ := hfin
    rw [hfin']
    show (((rewindRun t).step^[cs.length * 4 + 3 + 1 + 1])
      ((rewindRun t).startCfg T2)).tape = _
    rw [hRtt, hT2]
    funext j
    by_cases hj : j = t
    · subst hj
      simp only [Function.update_self]

    · rw [Function.update_of_ne hj, Function.update_of_ne hj]
      by_cases hj2 : j = s
      · subst hj2
        simp only [Function.update_self]
      · rw [Function.update_of_ne hj2, Function.update_of_ne hj2, hT1]
        exact copyStep_other s t hst cs.length T j hj2 hj

end SipserGacsLautemann
Source
Round primitives for the bounded-exists scheduler; builds on Def_sgl_rewind.

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