Preparing tapes, and copying with return
Definitionsgl_copy_backTwo 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.
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