Advancing past a delegated run's garbage
Definitionsgl_skip_aheadAdvancing past a delegated run's garbage — instead of erasing it.
After a delegated run the working tapes hold garbage of unknown extent. The obvious remedy is a clock-guided erase, but that costs six clock passes per tape and writes to every cell.
There is a cheaper move, and it comes from what a Turing machine cannot do: tell where on its tape it is. A round therefore does not need clean tapes, only fresh ones. Advance each working tape past everything the previous round could have written, and the region ahead is untouched by construction. Two clock passes per tape, no writing at all, and the correctness argument is the same geometry as the erase — a run of steps moves a head at most cells from its origin, so to the right of where it stopped is beyond every cell it wrote.
A formalisation note that shaped the statement. The worker's position after advances is given as applied to its tape, not as list surgery on a cellsTape — because moving right off the end of the written region materialises blanks, so the list form is simply false when the context runs out. That case is exactly the one this machine spends its whole time in.
import Definitions.Def_sgl_mark_back
/-!
# Advancing past a delegated run's garbage
After a delegated run the working tapes hold garbage of unknown extent. The
obvious remedy is to erase it, guided by the clock — but erasing costs six
clock passes per tape and writes to every cell.
There is a cheaper move. A machine cannot tell where on its tape it is, so a
round does not need *clean* tapes, only *fresh* ones: advance each working
tape past everything the previous round could have written, and the region
ahead is untouched by construction. Two clock passes per tape, no writing at
all, and the correctness argument is the same geometry — a run of `T` steps
moves a head at most `T` cells from its origin, so `2T` to the right of where
it stopped is beyond every cell it wrote.
`skipAhead` is that move: two guided passes with the clock rewound between,
leaving the clock as it found it.
-/
namespace SipserGacsLautemann
variable {tapes : Nat}
/-- Advance the worker by twice the clock's length, restoring the clock. -/
def skipAhead (clk w : Fin tapes) :=
(guidedWalk clk w HeadMove.right none).andThen fun _ =>
(rewindRun clk).andThen fun _ =>
(guidedWalk clk w HeadMove.right none).andThen fun _ =>
rewindRun clk
/-- One advancing round, in `cellsTape` form. -/
theorem guidedStep_skip (g w : Fin tapes) (hgw : g ≠ w)
(T : Fin tapes → Tape) (a : TapeSymbol) (Lg Rg : List TapeSymbol)
(hg : T g = cellsTape Lg (a :: Rg)) :
(guidedStep g w HeadMove.right none T) g = cellsTape (a :: Lg) Rg ∧
(guidedStep g w HeadMove.right none T) w =
moveDir HeadMove.right (T w) := 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 (T w) else _) = _
rw [if_neg (fun h => hgw h.symm), if_pos rfl]
theorem guidedStep_skip_iterate (g w : Fin tapes) (hgw : g ≠ w) :
∀ (marks : List TapeSymbol) (T : Fin tapes → Tape)
(Lg Rg : List TapeSymbol),
T g = cellsTape Lg (marks ++ Rg) →
(((guidedStep g w HeadMove.right none)^[marks.length]) T) g =
cellsTape (marks.reverse ++ Lg) Rg ∧
(((guidedStep g w HeadMove.right none)^[marks.length]) T) w =
((moveDir HeadMove.right)^[marks.length]) (T w) := by
intro marks
induction marks with
| nil => intro T Lg Rg hg; simpa using hg
| cons a marks ih =>
intro T Lg Rg hg
rw [List.length_cons, Function.iterate_succ_apply]
obtain ⟨hg', hw'⟩ := guidedStep_skip g w hgw T a Lg (marks ++ Rg)
(by rw [hg]; rfl)
obtain ⟨ha, hb⟩ := ih _ (a :: Lg) Rg hg'
refine ⟨by rw [ha]; congr 1; simp, ?_⟩
rw [hb, hw', Function.iterate_succ_apply]
theorem guidedStep_skip_marks (g w : Fin tapes) (hgw : g ≠ w) :
∀ (marks : List TapeSymbol) (T : Fin tapes → Tape)
(Lg Rg : List TapeSymbol),
(∀ c ∈ marks, c ≠ TapeSymbol.blank) →
T g = cellsTape Lg (marks ++ Rg) →
∀ r, r < marks.length →
(((((guidedStep g w HeadMove.right none)^[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 hnb hg 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', -⟩ := guidedStep_skip g w hgw T a Lg (marks ++ Rg)
(by rw [hg]; rfl)
exact ih _ (a :: Lg) Rg (fun x hx => hnb x (by simp [hx])) hg' r'
(by simp at hr; omega)
end SipserGacsLautemann