Erasing a contiguous run
Definitionsgl_erase_runErasing a contiguous run. eraseRun i walks tape i rightwards over a run of non-blank cells, blanking each: marks in steps, head left on the blank past the run. It is the guided walk with one tape playing both roles, and it is what retires a clock once its marks have been spent.
With guidedWalk this completes the erase toolkit. A clock of marks drives the worker's head right and then left writing blanks — covering every cell a -step run could have written, since each head moves at most one cell per step — after which this machine erases the clock, leaving both tapes blank for the next round.
The last three lemmas are what make it usable: for a tape presented as cellsTape L (marks ++ blank :: R) with marks non-blank, eraseRun_spec's hypotheses are read straight off the list, and the result is the marks replaced by blanks in the left context. A caller never reasons about the iteration.
import Definitions.Def_sgl_guided_walk
/-!
# Erasing a contiguous run
`eraseRun i` walks tape `i` rightwards over a run of non-blank cells, blanking
each. It is the guided walk with one tape playing both roles, and it is what
retires a clock once its marks have been spent.
Together with `guidedWalk` this completes the erase toolkit: a clock of `T`
marks drives the worker's head `2T` right and then `4T` left writing blanks —
covering every cell a `T`-step run could have written — after which the clock
itself is erased by this machine, leaving both tapes blank for the next round.
-/
namespace SipserGacsLautemann
variable {tapes : Nat}
/-- Blank the current cell and step right. -/
def eraseAction (i : Fin tapes) :
(Fin tapes → TapeSymbol) → (Fin tapes → TapeSymbol × HeadMove) :=
fun symbols j =>
if j = i then (TapeSymbol.blank, HeadMove.right)
else (symbols j, HeadMove.stay)
/-- One round: test, then blank-and-advance or stop. -/
def eraseBody (i : Fin tapes) :=
(TypedMachine.test (notBlankAt i)).andThen fun b =>
if b then
(TypedMachine.act (eraseAction i)).andThen fun _ =>
TypedMachine.halt (tapes := tapes) true
else
(TypedMachine.act (fun symbols j => (symbols j, HeadMove.stay))).andThen
fun _ => TypedMachine.halt (tapes := tapes) false
/-- Erase a run of marks. -/
def eraseRun (i : Fin tapes) := (eraseBody i).repeatUntilFalse
/-- The tapes after one erasing round. -/
def eraseStep (i : Fin tapes) (T : Fin tapes → Tape) : Fin tapes → Tape :=
fun j =>
if j = i then moveDir HeadMove.right (Tape.write (T i) TapeSymbol.blank)
else T j
theorem eraseStep_eq (i : Fin tapes) (T : Fin tapes → Tape) :
applyAction T (eraseAction i) = eraseStep i T := by
funext j
show applyAction T (eraseAction i) j =
(if j = i then moveDir HeadMove.right (Tape.write (T i) TapeSymbol.blank)
else T j)
by_cases hj : j = i
· subst hj
simp [applyAction, eraseAction, moveDir]
· simp [applyAction, eraseAction, hj, Tape.write_head_self, Tape.move]
/-! ## Rounds -/
set_option maxHeartbeats 1000000 in
theorem eraseBody_mark (i : Fin tapes) (T : Fin tapes → Tape)
(hmark : (T i).head ≠ TapeSymbol.blank) :
HaltsExactly (eraseBody i) ((eraseBody i).startCfg T)
(1 + 1 + (1 + 1 + 0)) true ∧
(((eraseBody i).step^[1 + 1 + (1 + 1 + 0)])
((eraseBody i).startCfg T)).tape = eraseStep i T := by
have htest := TypedMachine.test_spec (notBlankAt i) T
rw [notBlankAt_true i T hmark] at htest
have htestt : (((TypedMachine.test (notBlankAt i)).step^[1])
((TypedMachine.test (notBlankAt i)).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 (eraseAction i) T
have hactt : (((TypedMachine.act (eraseAction i)).step^[1])
((TypedMachine.act (eraseAction i)).startCfg T)).tape = eraseStep i T := by
rw [Function.iterate_one, ← eraseStep_eq i]
funext j
simp [TypedMachine.step, TypedMachine.act, TypedMachine.startCfg,
applyAction]
have hhalt := TypedMachine.halt_spec (tapes := tapes) true
((TypedMachine.halt (tapes := tapes) true).startCfg (eraseStep i T))
have hinner := chainStepC hact hactt hhalt
have hmain := chainStepD
(M₂ := fun b =>
if b then
(TypedMachine.act (eraseAction i)).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' : ((eraseBody i).step^[1 + 1 + (1 + 1 + 0)])
((eraseBody i).startCfg T) = _ := hfin
rw [hfin']
simp only [if_true]
rw [hinner.2]
rfl
set_option maxHeartbeats 1000000 in
theorem eraseBody_blank (i : Fin tapes) (T : Fin tapes → Tape)
(hblank : (T i).head = TapeSymbol.blank) :
HaltsExactly (eraseBody i) ((eraseBody i).startCfg T)
(1 + 1 + (1 + 1 + 0)) false ∧
(((eraseBody i).step^[1 + 1 + (1 + 1 + 0)])
((eraseBody i).startCfg T)).tape = T := by
have htest := TypedMachine.test_spec (notBlankAt i) T
rw [notBlankAt_false i T hblank] at htest
have htestt : (((TypedMachine.test (notBlankAt i)).step^[1])
((TypedMachine.test (notBlankAt i)).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 (eraseAction i)).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' : ((eraseBody i).step^[1 + 1 + (1 + 1 + 0)])
((eraseBody i).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 eraseRun_spec (i : Fin tapes) (m : Nat) (T : Fin tapes → Tape)
(hmarks : ∀ r, r < m → ((((eraseStep i)^[r]) T) i).head ≠ TapeSymbol.blank)
(hexit : ((((eraseStep i)^[m]) T) i).head = TapeSymbol.blank) :
HaltsExactly (eraseRun i) ((eraseRun i).startCfg T) (m * 5 + 4) false ∧
(((eraseRun i).step^[m * 5 + 4]) ((eraseRun i).startCfg T)).tape =
((eraseStep i)^[m]) T := by
classical
set body := eraseBody i with hbody
set cfg : Nat → TypedConfiguration tapes _ :=
fun r => body.startCfg (((eraseStep i)^[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⟩ := eraseBody_mark i (((eraseStep i)^[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 = ((eraseStep i)^[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 (((eraseStep i)^[r + 1]) T) = _
rw [← ht4]
rfl
have hexitr : HaltsExactly body (cfg m) 4 false := by
have := (eraseBody_blank i (((eraseStep i)^[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 : (eraseRun i).startCfg T = cfg 0 := by rw [hcfg]; rfl
refine ⟨by rw [hstart]; simpa using hspec, ?_⟩
rw [hstart, show m * 5 + 4 = 4 + m * (4 + 1) by omega,
Function.iterate_add_apply]
show ((eraseRun i).step^[4]
(((eraseRun i).step^[m * (4 + 1)]) (cfg 0))).tape = _
rw [show (eraseRun i) = 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 (eraseBody_blank i (((eraseStep i)^[m]) T) hexit).2
/-! ## Applying it to a concrete run
For a tape presented as `cellsTape L (marks ++ blank :: R)` with `marks`
non-blank, the hypotheses of `eraseRun_spec` are read off the list.
-/
theorem eraseStep_cellsTape (i : Fin tapes) (T : Fin tapes → Tape)
(L R : List TapeSymbol) (c : TapeSymbol)
(hT : T i = cellsTape L (c :: R)) :
(eraseStep i T) i = cellsTape (TapeSymbol.blank :: L) R := by
show (if i = i then moveDir HeadMove.right
(Tape.write (T i) TapeSymbol.blank) else T i) = _
rw [if_pos rfl, hT, write_cellsTape]
show moveDir HeadMove.right (cellsTape L (TapeSymbol.blank :: R)) = _
rw [cellsTape_moveRight]
theorem replicate_cons_comm (n : Nat) (b : TapeSymbol) (L : List TapeSymbol) :
List.replicate n b ++ (b :: L) = b :: (List.replicate n b ++ L) := by
induction n with
| zero => rfl
| succ n ih => rw [List.replicate_succ, List.cons_append, ih]; rfl
/-- Iterating the erase over a run of marks. -/
theorem eraseStep_iterate (i : Fin tapes) :
∀ (marks : List TapeSymbol) (T : Fin tapes → Tape) (L R : List TapeSymbol),
T i = cellsTape L (marks ++ R) →
((((eraseStep i)^[marks.length]) T) i) =
cellsTape (List.replicate marks.length TapeSymbol.blank ++ L) R := by
intro marks
induction marks with
| nil => intro T L R hT; simpa using hT
| cons c marks ih =>
intro T L R hT
rw [List.length_cons, Function.iterate_succ_apply]
have hstep : (eraseStep i T) i =
cellsTape (TapeSymbol.blank :: L) (marks ++ R) := by
exact eraseStep_cellsTape i T L (marks ++ R) c (by rw [hT]; rfl)
rw [ih (eraseStep i T) (TapeSymbol.blank :: L) R hstep]
congr 1
exact replicate_cons_comm marks.length TapeSymbol.blank L
/-- Every cell of the run is seen before the blank. -/
theorem eraseStep_marks (i : Fin tapes) :
∀ (marks : List TapeSymbol) (T : Fin tapes → Tape) (L R : List TapeSymbol),
(∀ c ∈ marks, c ≠ TapeSymbol.blank) →
T i = cellsTape L (marks ++ R) →
∀ r, r < marks.length →
((((eraseStep i)^[r]) T) i).head ≠ TapeSymbol.blank := by
intro marks
induction marks with
| nil => intro _ _ _ _ _ r hr; simp at hr
| cons c marks ih =>
intro T L R hnb hT r hr
cases r with
| zero =>
simp only [Function.iterate_zero, id_eq]
rw [hT]
show (cellsTape L (c :: (marks ++ R))).head ≠ _
exact hnb c (by simp)
| succ r' =>
rw [Function.iterate_succ_apply]
have hstep : (eraseStep i T) i =
cellsTape (TapeSymbol.blank :: L) (marks ++ R) :=
eraseStep_cellsTape i T L (marks ++ R) c (by rw [hT]; rfl)
exact ih (eraseStep i T) (TapeSymbol.blank :: L) R
(fun x hx => hnb x (by simp [hx])) hstep r'
(by simp at hr; omega)
end SipserGacsLautemann