Movement and write runs for the update sweep
Definitionsgl_region_updateMovement and write runs: the counter machines of the update sweep.
An update to the hosted region is: enter, walk to the flag, reposition, overwrite a few cells, park. The repositioning and overwriting are straight-line runs of known length — head moves, or a fixed list of cells written left to right. Building such runs from the binary combinators would nest the state type once per step; instead each is one counter machine over : the counter is the program counter, the run lemma is a single induction, and the cost is exactly .
moveRun i k dir moves head exactly cells; its run lemma gives the configuration after any prefix of the run, so both the halting spec and the final tapes are projections. writeRun i cs writes the cells of cs under head ; after the run the region reads cs.reverse ++ L on the left with R.drop |cs| remaining ahead.
The uniformity that retires the edge case. Writing then moving right consumes one cell of R if there is one and materialises nothing otherwise — in both cases the result is cellsTape (c :: L) R.tail. So the write lemmas need no case split at the region's right edge, which is precisely where the visited-blank problem of the zipper representation would otherwise return: appending a fresh block writes over materialised blanks with the same lemma that overwrites existing cells.
Together with walkToFlag and the parking scan, these are all the moving parts of the update variants: each variant (write-in-place, flag left, flag right, with growth at either edge) is now an andThen chain of proven pieces plus list algebra.
import Definitions.Def_sgl_region_walk
/-!
# Updating the region: movement and write runs
Module D of the merge_empty plan, third part: the primitives from which every
update variant is assembled.
An update is: enter, walk to the flag, reposition, overwrite a few cells, and
park. The repositioning and overwriting are *straight-line runs of a known
length* — `k` head moves, or a fixed list of cells written left-to-right — so
rather than build them from the binary combinators (whose nested state types
grow with the length), each is one **counter machine** over `Fin (k+1)`: the
counter is the program counter, the run lemma is a single induction, and the
cost is exactly `k`.
`writeRun`'s tape effect is uniform in what lies ahead: writing then moving
right consumes one cell of `R` if there is one and materialises nothing
otherwise, which is `cellsTape (c :: L) R.tail` in both cases. So the write
lemmas need no case split at the region's right edge — the place where the
visited-blank problem would otherwise return.
-/
namespace SipserGacsLautemann
variable {tapes : Nat}
/-! ## Tape effect of a write-and-move -/
theorem cellsTape_writeMove (L R : List TapeSymbol) (c : TapeSymbol) :
Tape.move (Tape.write (cellsTape L R) c) HeadMove.right =
cellsTape (c :: L) R.tail := by
cases R with
| nil => rfl
| cons r rs => cases rs <;> rfl
/-! ## The counter machines -/
/-- Move head `i` exactly `k` cells in direction `dir`. -/
def moveRun (i : Fin tapes) (k : Nat) (dir : HeadMove) :
TypedMachine tapes (Fin (k + 1)) where
start := ⟨0, Nat.succ_pos k⟩
transition := fun s symbols =>
if h : s.val < k then
(⟨s.val + 1, Nat.succ_lt_succ h⟩,
fun j => (symbols j, if j = i then dir else HeadMove.stay))
else (s, fun j => (symbols j, HeadMove.stay))
result := fun s => if s.val = k then some true else none
/-- Write the cells of `cs` under head `i`, left to right. -/
def writeRun (i : Fin tapes) (cs : List TapeSymbol) :
TypedMachine tapes (Fin (cs.length + 1)) where
start := ⟨0, Nat.succ_pos _⟩
transition := fun s symbols =>
if h : s.val < cs.length then
(⟨s.val + 1, Nat.succ_lt_succ h⟩,
fun j =>
(if j = i then cs.getD s.val TapeSymbol.blank else symbols j,
if j = i then HeadMove.right else HeadMove.stay))
else (s, fun j => (symbols j, HeadMove.stay))
result := fun s => if s.val = cs.length then some true else none
/-! ## Run lemmas -/
theorem moveRun_step (i : Fin tapes) (k : Nat) (dir : HeadMove)
(m : Nat) (hm : m < k) (t : Fin tapes → Tape) :
(moveRun i k dir).step ⟨⟨m, by omega⟩, t⟩ =
⟨⟨m + 1, by omega⟩, Function.update t i (moveDir dir (t i))⟩ := by
have hres : (moveRun i k dir).result ⟨m, by omega⟩ = none := by
simp [moveRun]
omega
simp only [TypedMachine.step, hres]
simp only [moveRun, dif_pos hm]
congr 1
funext j
by_cases hj : j = i
· subst hj
simp [moveDir, Tape.write_head_self]
· simp [hj, Tape.write_head_self, Tape.move]
theorem moveRun_run (i : Fin tapes) (k : Nat) (dir : HeadMove) (m : Nat)
(hm : m ≤ k) (tape : Fin tapes → Tape) :
((moveRun i k dir).step^[m]) ((moveRun i k dir).startCfg tape) =
⟨⟨m, by omega⟩, Function.update tape i ((moveDir dir)^[m] (tape i))⟩ := by
induction m with
| zero =>
simp only [Function.iterate_zero_apply, Function.iterate_zero, id_eq,
Function.update_eq_self]
rfl
| succ m ih =>
rw [Function.iterate_succ_apply', ih (by omega),
moveRun_step i k dir m (by omega)]
congr 1
· funext j
by_cases hj : j = i
· subst hj
simp [Function.iterate_succ_apply']
· simp [hj]
theorem moveRun_spec (i : Fin tapes) (k : Nat) (dir : HeadMove)
(tape : Fin tapes → Tape) :
HaltsExactly (moveRun i k dir) ((moveRun i k dir).startCfg tape) k true := by
constructor
· rw [moveRun_run i k dir k (le_refl k) tape]
simp [moveRun]
· intro j hj
rw [moveRun_run i k dir j (by omega) tape]
simp [moveRun]
omega
theorem moveRun_tape (i : Fin tapes) (k : Nat) (dir : HeadMove)
(tape : Fin tapes → Tape) :
(((moveRun i k dir).step^[k]) ((moveRun i k dir).startCfg tape)).tape =
Function.update tape i ((moveDir dir)^[k] (tape i)) := by
rw [moveRun_run i k dir k (le_refl k) tape]
theorem writeRun_step (i : Fin tapes) (cs : List TapeSymbol)
(m : Nat) (hm : m < cs.length) (t : Fin tapes → Tape) :
(writeRun i cs).step ⟨⟨m, by omega⟩, t⟩ =
⟨⟨m + 1, by omega⟩,
Function.update t i
(Tape.move (Tape.write (t i) (cs.getD m TapeSymbol.blank))
HeadMove.right)⟩ := by
have hres : (writeRun i cs).result ⟨m, by omega⟩ = none := by
simp [writeRun]
omega
simp only [TypedMachine.step, hres]
simp only [writeRun, dif_pos hm]
congr 1
funext j
by_cases hj : j = i
· subst hj
simp
· simp [hj, Tape.write_head_self, Tape.move]
theorem writeRun_run (i : Fin tapes) (cs : List TapeSymbol) (m : Nat)
(hm : m ≤ cs.length) (tape : Fin tapes → Tape) (L R : List TapeSymbol)
(hi : tape i = cellsTape L R) :
((writeRun i cs).step^[m]) ((writeRun i cs).startCfg tape) =
⟨⟨m, by omega⟩,
Function.update tape i
(cellsTape ((cs.take m).reverse ++ L) (R.drop m))⟩ := by
induction m with
| zero =>
simp only [Function.iterate_zero_apply, List.take_zero, List.drop_zero,
List.reverse_nil, List.nil_append, ← hi, Function.update_eq_self]
rfl
| succ m ih =>
rw [Function.iterate_succ_apply', ih (by omega),
writeRun_step i cs m (by omega)]
congr 1
funext j
by_cases hj : j = i
· subst hj
simp only [Function.update_self]
rw [cellsTape_writeMove]
have htake : (cs.take (m + 1)).reverse =
cs.getD m TapeSymbol.blank :: (cs.take m).reverse := by
rw [List.getD_eq_getElem cs TapeSymbol.blank (by omega), List.take_succ,
List.getElem?_eq_getElem (by omega)]
simp
rw [htake, List.tail_drop]
simp
· simp [hj]
theorem writeRun_spec (i : Fin tapes) (cs : List TapeSymbol)
(tape : Fin tapes → Tape) (L R : List TapeSymbol)
(hi : tape i = cellsTape L R) :
HaltsExactly (writeRun i cs) ((writeRun i cs).startCfg tape)
cs.length true := by
constructor
· rw [writeRun_run i cs cs.length (le_refl _) tape L R hi]
simp [writeRun]
· intro j hj
rw [writeRun_run i cs j (by omega) tape L R hi]
simp [writeRun]
omega
theorem writeRun_tape (i : Fin tapes) (cs : List TapeSymbol)
(tape : Fin tapes → Tape) (L R : List TapeSymbol)
(hi : tape i = cellsTape L R) :
(((writeRun i cs).step^[cs.length]) ((writeRun i cs).startCfg tape)).tape =
Function.update tape i
(cellsTape (cs.reverse ++ L) (R.drop cs.length)) := by
rw [writeRun_run i cs cs.length (le_refl _) tape L R hi]
simp
end SipserGacsLautemann