Copying one tape onto another
Definitionsgl_copy_runCopying one tape onto another. copyRun s t walks the source rightwards over a run of non-blank cells, writing each onto the target and advancing both heads: a run of cells copied in steps.
It is the guided walk once more, with the written symbol read from the guide rather than fixed — the last shape the round pattern needs. Three machines now share this body structure (guided walk, erase, copy), which is the point of having settled it: each new one is the action plus its two caller-facing lemmas.
copyStep_iterate states the outcome in the form a caller wants — source and target both advanced past the run, the run's cells now on the target, everything else untouched — and copyStep_marks discharges the termination hypothesis from the run being non-blank. With this the round of a scheduler loop is fully equipped: erase the working tapes guided by the spent clock, copy the inputs onto them, delegate, harvest the verdict.
import Definitions.Def_sgl_erase_run
/-!
# Copying one tape onto another
`copyRun s t` walks the source tape `s` rightwards over a run of non-blank
cells, writing each onto the target tape `t` and advancing both. It is the
guided walk again, with the *written symbol read from the guide* rather than
fixed — the last shape the round pattern needs.
With this, a round of a scheduler loop is: erase the working tapes (guided by
the spent clock), copy the inputs onto them, delegate, harvest the verdict.
-/
namespace SipserGacsLautemann
variable {tapes : Nat}
/-- Copy the source's symbol onto the target; advance both. -/
def copyAction (s t : Fin tapes) :
(Fin tapes → TapeSymbol) → (Fin tapes → TapeSymbol × HeadMove) :=
fun symbols i =>
if i = s then (symbols s, HeadMove.right)
else if i = t then (symbols s, HeadMove.right)
else (symbols i, HeadMove.stay)
/-- One round: test the source, then copy-and-advance or stop. -/
def copyBody (s t : Fin tapes) :=
(TypedMachine.test (notBlankAt s)).andThen fun b =>
if b then
(TypedMachine.act (copyAction s t)).andThen fun _ =>
TypedMachine.halt (tapes := tapes) true
else
(TypedMachine.act (fun symbols j => (symbols j, HeadMove.stay))).andThen
fun _ => TypedMachine.halt (tapes := tapes) false
/-- Copy a run. -/
def copyRun (s t : Fin tapes) := (copyBody s t).repeatUntilFalse
/-- The tapes after one copying round. -/
def copyStep (s t : Fin tapes) (T : Fin tapes → Tape) : Fin tapes → Tape :=
fun i =>
if i = s then moveDir HeadMove.right (T s)
else if i = t then
moveDir HeadMove.right (Tape.write (T t) (T s).head)
else T i
theorem copyStep_eq (s t : Fin tapes) (hst : s ≠ t) (T : Fin tapes → Tape) :
applyAction T (copyAction s t) = copyStep s t T := by
funext i
show applyAction T (copyAction s t) i =
(if i = s then moveDir HeadMove.right (T s)
else if i = t then
moveDir HeadMove.right (Tape.write (T t) (T s).head)
else T i)
by_cases hi : i = s
· subst hi
simp [applyAction, copyAction, Tape.write_head_self, moveDir]
· rw [if_neg hi]
by_cases hi2 : i = t
· subst hi2
simp [applyAction, copyAction, hi, moveDir]
· simp [applyAction, copyAction, hi, hi2, Tape.write_head_self, Tape.move]
/-! ## Rounds -/
set_option maxHeartbeats 1000000 in
theorem copyBody_mark (s t : Fin tapes) (hst : s ≠ t) (T : Fin tapes → Tape)
(hmark : (T s).head ≠ TapeSymbol.blank) :
HaltsExactly (copyBody s t) ((copyBody s t).startCfg T)
(1 + 1 + (1 + 1 + 0)) true ∧
(((copyBody s t).step^[1 + 1 + (1 + 1 + 0)])
((copyBody s t).startCfg T)).tape = copyStep s t T := by
have htest := TypedMachine.test_spec (notBlankAt s) T
rw [notBlankAt_true s T hmark] at htest
have htestt : (((TypedMachine.test (notBlankAt s)).step^[1])
((TypedMachine.test (notBlankAt s)).startCfg T)).tape = T := by
rw [Function.iterate_one]
funext j
simp [TypedMachine.step, TypedMachine.test, TypedMachine.startCfg,
Tape.write_head_self, Tape.move]
have hact := TypedMachine.act_spec (copyAction s t) T
have hactt : (((TypedMachine.act (copyAction s t)).step^[1])
((TypedMachine.act (copyAction s t)).startCfg T)).tape = copyStep s t T := by
rw [Function.iterate_one, ← copyStep_eq s t hst]
funext j
simp [TypedMachine.step, TypedMachine.act, TypedMachine.startCfg,
applyAction]
have hhalt := TypedMachine.halt_spec (tapes := tapes) true
((TypedMachine.halt (tapes := tapes) true).startCfg (copyStep s t T))
have hinner := chainStepC hact hactt hhalt
have hmain := chainStepD
(M₂ := fun b =>
if b then
(TypedMachine.act (copyAction s t)).andThen fun _ =>
TypedMachine.halt (tapes := tapes) true
else
(TypedMachine.act (fun symbols j => (symbols j, HeadMove.stay))).andThen
fun _ => TypedMachine.halt (tapes := tapes) false)
htest htestt (by simpa using hinner.1)
refine ⟨hmain.1, ?_⟩
have hfin := hmain.2
have hfin' : ((copyBody s t).step^[1 + 1 + (1 + 1 + 0)])
((copyBody s t).startCfg T) = _ := hfin
rw [hfin']
simp only [if_true]
rw [hinner.2]
rfl
set_option maxHeartbeats 1000000 in
theorem copyBody_blank (s t : Fin tapes) (hst : s ≠ t) (T : Fin tapes → Tape)
(hblank : (T s).head = TapeSymbol.blank) :
HaltsExactly (copyBody s t) ((copyBody s t).startCfg T)
(1 + 1 + (1 + 1 + 0)) false ∧
(((copyBody s t).step^[1 + 1 + (1 + 1 + 0)])
((copyBody s t).startCfg T)).tape = T := by
have htest := TypedMachine.test_spec (notBlankAt s) T
rw [notBlankAt_false s T hblank] at htest
have htestt : (((TypedMachine.test (notBlankAt s)).step^[1])
((TypedMachine.test (notBlankAt s)).startCfg T)).tape = T := by
rw [Function.iterate_one]
funext j
simp [TypedMachine.step, TypedMachine.test, TypedMachine.startCfg,
Tape.write_head_self, Tape.move]
have hact := TypedMachine.act_spec
(fun symbols : Fin tapes → TapeSymbol => fun j =>
(symbols j, HeadMove.stay)) T
have hactt : (((TypedMachine.act
(fun symbols : Fin tapes → TapeSymbol => fun j =>
(symbols j, HeadMove.stay))).step^[1])
((TypedMachine.act
(fun symbols : Fin tapes → TapeSymbol => fun j =>
(symbols j, HeadMove.stay))).startCfg T)).tape = T := by
rw [Function.iterate_one]
funext j
simp [TypedMachine.step, TypedMachine.act, TypedMachine.startCfg,
applyAction, Tape.write_head_self, Tape.move]
have hhalt := TypedMachine.halt_spec (tapes := tapes) false
((TypedMachine.halt (tapes := tapes) false).startCfg T)
have hinner := chainStepC hact hactt hhalt
have hmain := chainStepD
(M₂ := fun b =>
if b then
(TypedMachine.act (copyAction s t)).andThen fun _ =>
TypedMachine.halt (tapes := tapes) true
else
(TypedMachine.act (fun symbols j => (symbols j, HeadMove.stay))).andThen
fun _ => TypedMachine.halt (tapes := tapes) false)
htest htestt (by simpa using hinner.1)
refine ⟨hmain.1, ?_⟩
have hfin := hmain.2
have hfin' : ((copyBody s t).step^[1 + 1 + (1 + 1 + 0)])
((copyBody s t).startCfg T) = _ := hfin
rw [hfin']
simp only [Bool.false_eq_true, if_false]
rw [hinner.2]
rfl
set_option maxHeartbeats 1000000 in
/-- **Erasing a run.** A run of `m` marks is blanked in `5m + 4` steps, the
head left on the blank past it. -/
theorem copyRun_spec (s t : Fin tapes) (hst : s ≠ t) (m : Nat) (T : Fin tapes → Tape)
(hmarks : ∀ r, r < m → ((((copyStep s t)^[r]) T) s).head ≠ TapeSymbol.blank)
(hexit : ((((copyStep s t)^[m]) T) s).head = TapeSymbol.blank) :
HaltsExactly (copyRun s t) ((copyRun s t).startCfg T) (m * 5 + 4) false ∧
(((copyRun s t).step^[m * 5 + 4]) ((copyRun s t).startCfg T)).tape =
((copyStep s t)^[m]) T := by
classical
set body := copyBody s t with hbody
set cfg : Nat → TypedConfiguration tapes _ :=
fun r => body.startCfg (((copyStep s t)^[r]) T) with hcfg
have hround : ∀ r, r < m →
HaltsExactly body (cfg r) 4 true ∧
cfg (r + 1) = ⟨body.start, ((body.step^[4]) (cfg r)).tape⟩ := by
intro r hr
obtain ⟨hh, ht⟩ := copyBody_mark s t hst (((copyStep s t)^[r]) T) (hmarks r hr)
have hh4 : HaltsExactly body (cfg r) 4 true := by
rw [hcfg, hbody]; simpa using hh
have ht4 : ((body.step^[4]) (cfg r)).tape = ((copyStep s t)^[r + 1]) T := by
rw [hcfg, hbody]
rw [show (4 : Nat) = 1 + 1 + (1 + 1 + 0) from rfl]
rw [ht, Function.iterate_succ_apply']
refine ⟨hh4, ?_⟩
show body.startCfg (((copyStep s t)^[r + 1]) T) = _
rw [← ht4]
rfl
have hexitr : HaltsExactly body (cfg m) 4 false := by
have := (copyBody_blank s t hst (((copyStep s t)^[m]) T) hexit).1
rw [hcfg, hbody]; simpa using this
have hspec := TypedMachine.repeatUntilFalse_spec body cfg (fun _ => 4) m 4
hround hexitr
rw [loopCost_const] at hspec
have hrun := TypedMachine.repeatUntilFalse_rounds body cfg (fun _ => 4) m
hround
rw [loopCost_const] at hrun
have hstart : (copyRun s t).startCfg T = cfg 0 := by rw [hcfg]; rfl
refine ⟨by rw [hstart, show (copyRun s t) = body.repeatUntilFalse from rfl]; exact hspec, ?_⟩
rw [hstart, show m * 5 + 4 = 4 + m * (4 + 1) by omega,
Function.iterate_add_apply]
show ((copyRun s t).step^[4]
(((copyRun s t).step^[m * (4 + 1)]) (cfg 0))).tape = _
rw [show (copyRun s t) = body.repeatUntilFalse from rfl, hrun]
have htp : ((body.repeatUntilFalse.step^[4]) (cfg m)).tape =
((body.step^[4]) (cfg m)).tape := by
rw [body.repeatUntilFalse_iterate_fresh (cfg m) 4 hexitr.fresh]
rw [htp, hcfg, hbody]
exact (copyBody_blank s t hst (((copyStep s t)^[m]) T) hexit).2
/-! ## Applying it to a concrete run -/
theorem copyStep_tapes (s t : Fin tapes) (hst : s ≠ t) (T : Fin tapes → Tape)
(c : TapeSymbol) (L R L' R' : List TapeSymbol)
(hs : T s = cellsTape L (c :: R)) (ht : T t = cellsTape L' R') :
(copyStep s t T) s = cellsTape (c :: L) R ∧
(copyStep s t T) t = cellsTape (c :: L') R'.tail := by
constructor
· show (if s = s then moveDir HeadMove.right (T s) else _) = _
rw [if_pos rfl, hs, cellsTape_moveRight]
· show (if t = s then _ else if t = t then
moveDir HeadMove.right (Tape.write (T t) (T s).head) else _) = _
rw [if_neg (fun h => hst h.symm), if_pos rfl, ht, hs]
show moveDir HeadMove.right (Tape.write (cellsTape L' R')
(cellsTape L (c :: R)).head) = _
rw [show (cellsTape L (c :: R)).head = c from rfl, write_cellsTape,
cellsTape_moveRight]
/-- **The copy.** A run `cs` on the source is written onto the target, both
heads advancing past it. -/
theorem copyStep_iterate (s t : Fin tapes) (hst : s ≠ t) :
∀ (cs : List TapeSymbol) (T : Fin tapes → Tape)
(L R L' R' : List TapeSymbol),
T s = cellsTape L (cs ++ R) → T t = cellsTape L' R' →
(((copyStep s t)^[cs.length]) T) s = cellsTape (cs.reverse ++ L) R ∧
(((copyStep s t)^[cs.length]) T) t =
cellsTape (cs.reverse ++ L') (R'.drop cs.length) := by
intro cs
induction cs with
| nil => intro T L R L' R' hs ht; simpa using ⟨hs, ht⟩
| cons c cs ih =>
intro T L R L' R' hs ht
rw [List.length_cons, Function.iterate_succ_apply]
obtain ⟨hs', ht'⟩ := copyStep_tapes s t hst T c L (cs ++ R) L' R'
(by rw [hs]; rfl) ht
obtain ⟨ha, hb⟩ := ih (copyStep s t T) (c :: L) R (c :: L') R'.tail
hs' ht'
refine ⟨?_, ?_⟩
· rw [ha]; congr 1; simp
· rw [hb]
congr 1
· simp
· rw [List.drop_tail]
/-- Every cell of the run is seen before the source's blank. -/
theorem copyStep_marks (s t : Fin tapes) (hst : s ≠ t) :
∀ (cs : List TapeSymbol) (T : Fin tapes → Tape)
(L R L' R' : List TapeSymbol),
(∀ c ∈ cs, c ≠ TapeSymbol.blank) →
T s = cellsTape L (cs ++ R) → T t = cellsTape L' R' →
∀ r, r < cs.length →
((((copyStep s t)^[r]) T) s).head ≠ TapeSymbol.blank := by
intro cs
induction cs with
| nil => intro _ _ _ _ _ _ _ _ r hr; simp at hr
| cons c cs ih =>
intro T L R L' R' hnb hs ht r hr
cases r with
| zero =>
simp only [Function.iterate_zero, id_eq]
rw [hs]
show (cellsTape L (c :: (cs ++ R))).head ≠ _
exact hnb c (by simp)
| succ r' =>
rw [Function.iterate_succ_apply]
obtain ⟨hs', ht'⟩ := copyStep_tapes s t hst T c L (cs ++ R) L' R'
(by rw [hs]; rfl) ht
exact ih (copyStep s t T) (c :: L) R (c :: L') R'.tail
(fun x hx => hnb x (by simp [hx])) hs' ht' r'
(by simp at hr; omega)
end SipserGacsLautemann