Writing a counter's worth of marks
Definitionsgl_mark_backWriting a counter's worth of marks. The scheduler round builds the delegate's fourth tape — the unary replicate offset true — by walking the persistent offset counter and writing one mark per counter mark. markBack c w does that and returns both heads, exactly as copyBack does for a copy: the counter is restored untouched, the worker gains a run as long as the counter's, both heads on its first cell.
This is the third composition built to the same recipe (copy-and-return, mark-and-return), and it compiled on the first attempt — the walk's iteration lemmas, the rewind, and the untouched-tapes fact all slotted together without adjustment. The shape being reused is: iterate the step over an explicit cell list, prove the marks hypothesis from the run being non-blank, chain walk-then-rewind-then-rewind, and finish with a funext case split over the three classes of tape (guide, worker, everything else).
With this, every stage of a round has its specification: erase, restore the inputs, build the offset tape, delegate, dispatch.
import Definitions.Def_sgl_copy_back
/-!
# Writing a counter's worth of marks
The round builds the delegate's fourth tape — `replicate offset true` — by
walking the persistent offset counter and writing one mark per counter mark.
`markBack c w` does that and returns both heads, exactly as `copyBack` does
for a copy. The counter is untouched; the worker gains a run of marks as long
as the counter's.
-/
namespace SipserGacsLautemann
variable {tapes : Nat}
/-- Write one mark per counter mark, then return both heads. -/
def markBack (c w : Fin tapes) :=
(guidedWalk c w HeadMove.right (some (TapeSymbol.bit true))).andThen fun _ =>
(rewindRun c).andThen fun _ => rewindRun w
/-- Tapes other than the guide and worker are untouched. -/
theorem guidedStep_other (g w : Fin tapes) (dir : HeadMove)
(wr : Option TapeSymbol) :
∀ (m : Nat) (T : Fin tapes → Tape) (j : Fin tapes), j ≠ g → j ≠ w →
(((guidedStep g w dir wr)^[m]) T) j = T j := by
intro m
induction m with
| zero => intro T j _ _; rfl
| succ m ih =>
intro T j hjg hjw
rw [Function.iterate_succ_apply, ih (guidedStep g w dir wr T) j hjg hjw]
show (if j = g then _ else if j = w then _ else T j) = _
rw [if_neg hjg, if_neg hjw]
/-- One writing round, in `cellsTape` form. -/
theorem guidedStep_write (g w : Fin tapes) (hgw : g ≠ w)
(T : Fin tapes → Tape) (a : TapeSymbol) (Lg Rg Lw Rw : List TapeSymbol)
(hg : T g = cellsTape Lg (a :: Rg)) (hw : T w = cellsTape Lw Rw) :
(guidedStep g w HeadMove.right (some (TapeSymbol.bit true)) T) g =
cellsTape (a :: Lg) Rg ∧
(guidedStep g w HeadMove.right (some (TapeSymbol.bit true)) T) w =
cellsTape (TapeSymbol.bit true :: Lw) Rw.tail := by
constructor
· show (if g = g then moveDir HeadMove.right (T g) else _) = _
rw [if_pos rfl, hg, cellsTape_moveRight]
· show (if w = g then _ else if w = w then
moveDir HeadMove.right (Tape.write (T w) (TapeSymbol.bit true))
else _) = _
rw [if_neg (fun h => hgw h.symm), if_pos rfl, hw, write_cellsTape,
cellsTape_moveRight]
/-! ## Iterating the write -/
theorem guidedStep_write_iterate (g w : Fin tapes) (hgw : g ≠ w) :
∀ (marks : List TapeSymbol) (T : Fin tapes → Tape)
(Lg Rg Lw Rw : List TapeSymbol),
T g = cellsTape Lg (marks ++ Rg) → T w = cellsTape Lw Rw →
(((guidedStep g w HeadMove.right (some (TapeSymbol.bit true)))^[
marks.length]) T) g = cellsTape (marks.reverse ++ Lg) Rg ∧
(((guidedStep g w HeadMove.right (some (TapeSymbol.bit true)))^[
marks.length]) T) w =
cellsTape (List.replicate marks.length (TapeSymbol.bit true) ++ Lw)
(Rw.drop marks.length) := by
intro marks
induction marks with
| nil => intro T Lg Rg Lw Rw hg hw; simpa using ⟨hg, hw⟩
| cons a marks ih =>
intro T Lg Rg Lw Rw hg hw
rw [List.length_cons, Function.iterate_succ_apply]
obtain ⟨hg', hw'⟩ := guidedStep_write g w hgw T a Lg (marks ++ Rg) Lw Rw
(by rw [hg]; rfl) hw
obtain ⟨ha, hb⟩ := ih _ (a :: Lg) Rg (TapeSymbol.bit true :: Lw) Rw.tail
hg' hw'
refine ⟨?_, ?_⟩
· rw [ha]; congr 1; simp
· rw [hb]
congr 1
· rw [List.replicate_succ]
exact (replicate_cons_comm marks.length (TapeSymbol.bit true) Lw).symm
▸ rfl
· rw [List.drop_tail]
theorem guidedStep_write_marks (g w : Fin tapes) (hgw : g ≠ w) :
∀ (marks : List TapeSymbol) (T : Fin tapes → Tape)
(Lg Rg Lw Rw : List TapeSymbol),
(∀ c ∈ marks, c ≠ TapeSymbol.blank) →
T g = cellsTape Lg (marks ++ Rg) → T w = cellsTape Lw Rw →
∀ r, r < marks.length →
(((((guidedStep g w HeadMove.right
(some (TapeSymbol.bit true)))^[r]) T) g).head ≠ TapeSymbol.blank) := by
intro marks
induction marks with
| nil => intro _ _ _ _ _ _ _ _ r hr; simp at hr
| cons a marks ih =>
intro T Lg Rg Lw Rw hnb hg hw r hr
cases r with
| zero =>
simp only [Function.iterate_zero, id_eq]
rw [hg]
show (cellsTape Lg (a :: (marks ++ Rg))).head ≠ _
exact hnb a (by simp)
| succ r' =>
rw [Function.iterate_succ_apply]
obtain ⟨hg', hw'⟩ := guidedStep_write g w hgw T a Lg (marks ++ Rg)
Lw Rw (by rw [hg]; rfl) hw
exact ih _ (a :: Lg) Rg (TapeSymbol.bit true :: Lw) Rw.tail
(fun x hx => hnb x (by simp [hx])) hg' hw' r'
(by simp at hr; omega)
/-! ## The composition -/
set_option maxHeartbeats 4000000 in
/-- **Build the offset tape.** The counter is restored exactly; the worker
gains a run of marks as long as the counter's, both heads on its first cell. -/
theorem markBack_spec (c w : Fin tapes) (hcw : c ≠ w)
(marks : List TapeSymbol) (Lc Lw Rc Rw : List TapeSymbol)
(T : Fin tapes → Tape)
(hnb : ∀ x ∈ marks, x ≠ TapeSymbol.blank)
(hc : T c = cellsTape (TapeSymbol.blank :: Lc)
(marks ++ TapeSymbol.blank :: Rc))
(hw : T w = cellsTape (TapeSymbol.blank :: Lw) Rw) :
∃ cost : Nat,
HaltsExactly (markBack c w) ((markBack c w).startCfg T) cost true ∧
(((markBack c w).step^[cost]) ((markBack c w).startCfg T)).tape =
Function.update (Function.update T c
(cellsTape (TapeSymbol.blank :: Lc)
(marks ++ TapeSymbol.blank :: Rc))) w
(cellsTape (TapeSymbol.blank :: Lw)
(List.replicate marks.length (TapeSymbol.bit true) ++
(Rw.drop marks.length).headD TapeSymbol.blank ::
(Rw.drop marks.length).tail)) := by
classical
set G := guidedStep c w HeadMove.right (some (TapeSymbol.bit true)) with hG
obtain ⟨hia, hib⟩ := guidedStep_write_iterate c w hcw marks T
(TapeSymbol.blank :: Lc) (TapeSymbol.blank :: Rc)
(TapeSymbol.blank :: Lw) Rw (by rw [hc]) (by rw [hw])
-- the walk
obtain ⟨hW, hWt⟩ := guidedWalk_spec c w hcw HeadMove.right
(some (TapeSymbol.bit true)) marks.length T
(guidedStep_write_marks c w hcw marks T (TapeSymbol.blank :: Lc)
(TapeSymbol.blank :: Rc) (TapeSymbol.blank :: Lw) Rw hnb
(by rw [hc]) (by rw [hw]))
(by rw [hia]; rfl)
set T1 := ((G)^[marks.length]) T with hT1
have hT1c : T1 c = cellsTape (marks.reverse ++ TapeSymbol.blank :: Lc)
(TapeSymbol.blank :: Rc) := hia
have hT1w : T1 w =
cellsTape (List.replicate marks.length (TapeSymbol.bit true) ++
TapeSymbol.blank :: Lw) (Rw.drop marks.length) := hib
-- rewind the counter
obtain ⟨hRc, hRct⟩ := rewindRun_spec c marks Lc Rc TapeSymbol.blank T1
hnb (by rw [hT1c])
set T2 := Function.update T1 c
(cellsTape (TapeSymbol.blank :: Lc) (marks ++ TapeSymbol.blank :: Rc))
with hT2
have hT2w : T2 w =
cellsTape (List.replicate marks.length (TapeSymbol.bit true) ++
TapeSymbol.blank :: Lw) (Rw.drop marks.length) := by
rw [hT2, Function.update_of_ne (fun h => hcw h.symm)]
exact hT1w
-- rewind the worker
have hrep : ∀ x ∈ List.replicate marks.length (TapeSymbol.bit true),
x ≠ TapeSymbol.blank := by
intro x hx
rw [List.eq_of_mem_replicate hx]
simp
obtain ⟨hRw, hRwt⟩ := rewindRun_spec w
(List.replicate marks.length (TapeSymbol.bit true)) Lw
((Rw.drop marks.length).tail)
((Rw.drop marks.length).headD TapeSymbol.blank) T2 hrep
(by
rw [hT2w]
rw [show (List.replicate marks.length (TapeSymbol.bit true)).reverse =
List.replicate marks.length (TapeSymbol.bit true) by
simp [List.reverse_replicate]]
exact cellsTape_norm _ _)
refine ⟨_, (chainStepC hW hWt (chainStepC hRc hRct hRw).1).1, ?_⟩
have hch := chainStepC hW hWt (chainStepC hRc hRct hRw).1
have hin := chainStepC hRc hRct hRw
have hfin := hch.2
rw [hin.2] at hfin
have hfin' : ((markBack c w).step^[_])
((markBack c w).startCfg T) = _ := hfin
rw [hfin']
show (((rewindRun w).step^[_]) ((rewindRun w).startCfg T2)).tape = _
rw [hRwt, hT2]
funext j
by_cases hj : j = w
· subst hj; simp
· rw [Function.update_of_ne hj, Function.update_of_ne hj]
by_cases hj2 : j = c
· subst hj2; simp
· rw [Function.update_of_ne hj2, Function.update_of_ne hj2, hT1]
exact guidedStep_other c w HeadMove.right (some (TapeSymbol.bit true))
marks.length T j hj2 hj
end SipserGacsLautemann