Walking the region to a flag
Definitionsgl_region_walkWalking the region to a flag: the sweep loop, fully specified.
walkToFlag repeats blockRead until the block whose track-flag is set has been consumed. Its specification is exact on all three axes: the machine halts false at precisely steps (where mid is the unflagged prefix), the final configuration equals the last body run's — so the exit state carries the flagged block's cells, which the read phases of the simulation will extract — and the tapes are unchanged except tape , whose head stands just past the flagged block.
The cellsTape view. Tape is a zipper, and a zipper remembers where the head has been: moving onto the blank beyond the region and back leaves a visited blank in the lists, so the tape is no longer structurally equal to its clean description. This bites exactly when the flagged block is last, and it would otherwise have surfaced as an unprovable goal deep inside the update sweep. cellsTape L R — head reading the first cell of R, blank if R is empty — makes the bookkeeping uniform: every head move is a list shuffle provable by rfl after a case split, and a visited blank is a [blank] suffix carried in R. The identity cellsTape L [] = cellsTape L [\mathrm{blank}] holds definitionally, so the first excursion beyond the region costs nothing.
Structure of the proof. The walk is repeatUntilFalse over blockRead; each round's verdict comes from blockOfCells_cellsTape (the block standing at boundary is mid[m], whose flag is down), each round's tape effect from blockRead_tape (six cells of advance, nothing else touched), and the boundary bookkeeping from one rewrite chain over take/drop splits — no bespoke induction. Also here: repeatUntilFalse_config, the full-configuration form of the loop run lemmas, which downstream phases need because a loop's exit state carries the data its last body run collected.
import Definitions.Def_sgl_block_read
/-!
# Walking the region to a flag
Module D of the merge_empty plan, second part: the sweep loop. `walkToFlag`
repeats `blockRead` until it stands past the block whose track-flag is set, and
its specification locates the halt exactly and gives the final tapes.
## The `cellsTape` view
`Tape` is a zipper, and a zipper remembers where the head has been: moving onto
the blank beyond the region and back leaves a *visited* blank in the lists,
so the tape is no longer structurally equal to its clean description. This
bites precisely when the flagged block is last, and it would have surfaced as
an unprovable goal deep inside the update sweep.
`cellsTape L R` — head reading the first cell of `R`, blank if `R` is empty —
makes the bookkeeping uniform: every head move is a list shuffle, provable by
`rfl` after a case split, and a trailing visited blank is just a `[blank]`
suffix carried in `R`. Usefully, `cellsTape L [] = cellsTape L [blank]` holds
*definitionally*, so the first excursion beyond the region costs nothing at
all.
-/
namespace SipserGacsLautemann
variable {tapes : Nat}
/-! ## Track sides -/
/-- Which of the two hosted virtual tapes an operation concerns. -/
inductive TrackSide where
| A
| B
def TrackSide.getFlag : TrackSide → Block → Bool
| .A => Block.flagA
| .B => Block.flagB
/-! ## The `cellsTape` view of a physical tape -/
/-- A tape as: cells left of the head (nearest-first), and cells at and right
of the head. The head reads the first right-cell, blank if there is none —
the zipper's implicit blank-extension made explicit. -/
def cellsTape (L R : List TapeSymbol) : Tape :=
⟨L, R.headD TapeSymbol.blank, R.tail⟩
theorem cellsTape_moveRight (L : List TapeSymbol) (c : TapeSymbol)
(R : List TapeSymbol) :
moveDir HeadMove.right (cellsTape L (c :: R)) = cellsTape (c :: L) R := by
cases R <;> rfl
theorem cellsTape_moveRight_nil (L : List TapeSymbol) :
moveDir HeadMove.right (cellsTape L []) =
cellsTape (TapeSymbol.blank :: L) [] := rfl
theorem cellsTape_moveLeft (L : List TapeSymbol) (c r : TapeSymbol)
(R : List TapeSymbol) :
moveDir HeadMove.left (cellsTape (c :: L) (r :: R)) =
cellsTape L (c :: r :: R) := rfl
theorem cellsTape_moveLeft_nil (L : List TapeSymbol) (c : TapeSymbol) :
moveDir HeadMove.left (cellsTape (c :: L) []) =
cellsTape L (c :: [TapeSymbol.blank]) := rfl
/-- Consuming a run of cells rightward. -/
theorem cellsTape_advance (cs : List TapeSymbol) :
∀ (L R : List TapeSymbol),
(moveDir HeadMove.right)^[cs.length] (cellsTape L (cs ++ R)) =
cellsTape (cs.reverse ++ L) R := by
induction cs with
| nil => intro L R; simp
| cons c cs ih =>
intro L R
rw [List.length_cons, Function.iterate_succ_apply, List.cons_append,
cellsTape_moveRight, ih]
simp [List.append_assoc]
/-- Retreating over a run of cells leftward, with something ahead. -/
theorem cellsTape_retreat (cs : List TapeSymbol) :
∀ (L R : List TapeSymbol) (r : TapeSymbol),
(moveDir HeadMove.left)^[cs.length] (cellsTape (cs ++ L) (r :: R)) =
cellsTape L (cs.reverse ++ r :: R) := by
induction cs with
| nil => intro L R r; simp
| cons c cs ih =>
intro L R r
rw [List.length_cons, Function.iterate_succ_apply, List.cons_append,
cellsTape_moveLeft, ih]
simp [List.append_assoc]
/-- Retreating from the position just past the region: the first step
materialises the visited blank, and it lands at the run's start with that
blank recorded ahead. -/
theorem cellsTape_retreat_end (cs : List TapeSymbol) (L : List TapeSymbol) :
(moveDir HeadMove.left)^[cs.length] (cellsTape (cs ++ L) []) =
cellsTape L (cs.reverse ++ [TapeSymbol.blank]) := by
cases cs with
| nil => rfl
| cons c cs =>
rw [List.length_cons, Function.iterate_succ_apply, List.cons_append,
cellsTape_moveLeft_nil, cellsTape_retreat]
simp
/-! ## Splitting an encoded region -/
theorem encodeBlocks_append (xs ys : List Block) :
encodeBlocks (xs ++ ys) = encodeBlocks xs ++ encodeBlocks ys := by
induction xs with
| nil => rfl
| cons b bs ih => simp [encodeBlocks_cons, ih]
/-- The block a head standing at a boundary is looking at, recovered from the
cells: the `cellsTape` version of the codec/reader join. -/
theorem blockOfCells_cellsTape (i : Fin tapes) (tape : Fin tapes → Tape)
(L R : List TapeSymbol) (b : Block)
(hi : tape i = cellsTape L (Block.toCells b ++ R)) :
blockOfCells (cellAt i tape 0) (cellAt i tape 1) (cellAt i tape 2)
(cellAt i tape 3) (cellAt i tape 4) (cellAt i tape 5) = b := by
have e0 : cellAt i tape 0 = (cellsOfSymbol b.symA).1 := by
rw [cellAt, hi]; rfl
have e1 : cellAt i tape 1 = (cellsOfSymbol b.symA).2 := by
rw [cellAt, hi]; rfl
have e2 : cellAt i tape 2 = TapeSymbol.bit b.flagA := by
rw [cellAt, hi]; rfl
have e3 : cellAt i tape 3 = (cellsOfSymbol b.symB).1 := by
rw [cellAt, hi]; rfl
have e4 : cellAt i tape 4 = (cellsOfSymbol b.symB).2 := by
rw [cellAt, hi]; rfl
have e5 : cellAt i tape 5 = TapeSymbol.bit b.flagB := by
rw [cellAt, hi]; rfl
rw [e0, e1, e2, e3, e4, e5]
exact blockOfCells_toCells b
/-! ## The tape-effect of a block read -/
/-- `scanTapesDir` at the updated index. -/
theorem scanTapesDir_self (tape : Fin tapes → Tape) (i : Fin tapes)
(dir : HeadMove) (n : Nat) :
(scanTapesDir tape i dir n) i = (moveDir dir)^[n] (tape i) := by
simp [scanTapesDir]
/-- Composing two head-advances of the same tape. -/
theorem scanTapesDir_compose (tape : Fin tapes → Tape) (i : Fin tapes)
(dir : HeadMove) (n m : Nat) :
scanTapesDir (scanTapesDir tape i dir n) i dir m =
scanTapesDir tape i dir (m + n) := by
funext j
by_cases hj : j = i
· subst hj
simp [scanTapesDir, Function.iterate_add_apply]
· simp [scanTapesDir, hj]
/-- The tape version of `readCellRight_chain`: one link of the chain, tracking
tapes instead of the verdict. -/
theorem readCellRight_chain_tape {S : Type} (i : Fin tapes)
(tape : Fin tapes → Tape) (n : Nat)
(M₂ : Option TapeSymbol → TypedMachine tapes S) (k : Nat)
(T : Fin tapes → Tape)
(h : (((M₂ (some (cellAt i tape n))).step^[k])
((M₂ (some (cellAt i tape n))).startCfg
(scanTapesDir tape i HeadMove.right (n + 1)))).tape = T) :
((((readCellRight i).andThenState (fun s => s.isSome) M₂).step^[1 + 1 + k])
(TypedConfiguration.inLeftState
((readCellRight i).startCfg
(scanTapesDir tape i HeadMove.right n)))).tape = T := by
have hexit : (fun s : Option TapeSymbol => s.isSome)
(((readCellRight i).step^[1])
((readCellRight i).startCfg
(scanTapesDir tape i HeadMove.right n))).state = true := by
rw [readCellRight_state]; rfl
have hfresh : ∀ j, j < 1 →
(fun s : Option TapeSymbol => s.isSome)
(((readCellRight i).step^[j])
((readCellRight i).startCfg
(scanTapesDir tape i HeadMove.right n))).state = false := by
intro j hj
have : j = 0 := by omega
subst this; rfl
rw [TypedMachine.andThenState_iterate _ _ _ _ 1 hexit hfresh k]
simp only [TypedConfiguration.inRightState]
rw [readCellRight_state, readCellRight_tape, advance_succ, advance_head] at *
exact h
/-- The first link, on the original tapes. -/
theorem readCellRight_chain_tape_zero {S : Type} (i : Fin tapes)
(tape : Fin tapes → Tape)
(M₂ : Option TapeSymbol → TypedMachine tapes S) (k : Nat)
(T : Fin tapes → Tape)
(h : (((M₂ (some (cellAt i tape 0))).step^[k])
((M₂ (some (cellAt i tape 0))).startCfg
(scanTapesDir tape i HeadMove.right 1))).tape = T) :
((((readCellRight i).andThenState (fun s => s.isSome) M₂).step^[1 + 1 + k])
(TypedConfiguration.inLeftState ((readCellRight i).startCfg tape))).tape
= T := by
have hc := readCellRight_chain_tape i tape 0 M₂ k T h
rwa [scanTapesDir_zero] at hc
/-- The number of steps of one `blockRead`. -/
def blockReadSteps : Nat :=
1 + 1 + (1 + 1 + (1 + 1 + (1 + 1 + (1 + 1 + (1 + 1 + 0)))))
/-- A block read advances tape `i` by exactly six cells and touches nothing
else. -/
theorem blockRead_tape (i : Fin tapes) (test : Block → Bool)
(tape : Fin tapes → Tape) :
(((blockRead i test).step^[blockReadSteps])
(TypedConfiguration.inLeftState
((readCellRight i).startCfg tape))).tape =
scanTapesDir tape i HeadMove.right 6 := by
refine readCellRight_chain_tape_zero i tape _ _ _ ?_
refine readCellRight_chain_tape i tape 1 _ _ _ ?_
refine readCellRight_chain_tape i tape 2 _ _ _ ?_
refine readCellRight_chain_tape i tape 3 _ _ _ ?_
refine readCellRight_chain_tape i tape 4 _ _ _ ?_
refine readCellRight_chain_tape i tape 5 _ _ _ ?_
rfl
/-- The full final configuration of a `repeatUntilFalse` run — state and tapes
together. `repeatUntilFalse_spec` gives the verdict and `repeatUntilFalse_tape`
the tapes; downstream phases also need the *state*, because a loop's exit state
carries the data its last body run collected. -/
theorem TypedMachine.repeatUntilFalse_config {S : Type}
(body : TypedMachine tapes S)
(config : Nat → TypedConfiguration tapes S) (cost : Nat → Nat)
(rounds a : Nat)
(hround : ∀ i, i < rounds →
HaltsExactly body (config i) (cost i) true ∧
config (i + 1) = ⟨body.start, ((body.step^[cost i]) (config i)).tape⟩)
(hexit : HaltsExactly body (config rounds) a false) :
((body.repeatUntilFalse.step^[loopCost cost rounds + a]) (config 0)) =
(body.step^[a]) (config rounds) := by
rw [Nat.add_comm, Function.iterate_add_apply,
body.repeatUntilFalse_rounds config cost rounds hround,
body.repeatUntilFalse_iterate_fresh (config rounds) a hexit.fresh]
/-! ## The walk -/
/-- Continue while the current block's `side` flag is down. -/
def walkTest (side : TrackSide) : Block → Bool :=
fun b => !side.getFlag b
def walkBody (side : TrackSide) (i : Fin tapes) :=
blockRead i (walkTest side)
/-- Repeat block reads until the flagged block has been consumed. -/
def walkToFlag (side : TrackSide) (i : Fin tapes) :=
(walkBody side i).repeatUntilFalse
/-- The tape at boundary `m` of the walk, in region terms. -/
theorem walk_boundary (L R : List TapeSymbol) (mid : List Block) (cur : Block)
(post : List Block) (m : Nat) (hm : m < mid.length) :
(moveDir HeadMove.right)^[6 * m]
(cellsTape L (encodeBlocks (mid ++ cur :: post) ++ R)) =
cellsTape ((encodeBlocks (mid.take m)).reverse ++ L)
(Block.toCells (mid.getD m Block.blank) ++
(encodeBlocks (mid.drop (m + 1) ++ cur :: post) ++ R)) := by
conv_lhs =>
rw [show mid ++ cur :: post = mid.take m ++ (mid.drop m ++ cur :: post) by
rw [← List.append_assoc, List.take_append_drop]]
rw [show mid.drop m = mid.getD m Block.blank :: mid.drop (m + 1) by
rw [List.getD_eq_getElem mid Block.blank hm]
exact List.drop_eq_getElem_cons hm]
rw [encodeBlocks_append, List.cons_append, encodeBlocks_cons]
simp only [List.append_assoc]
rw [show (6 : Nat) * m = (encodeBlocks (mid.take m)).length by
rw [encodeBlocks_length, List.length_take]; omega,
cellsTape_advance]
/-- The tape at the flagged block's boundary. -/
theorem walk_boundary_cur (L R : List TapeSymbol) (mid : List Block)
(cur : Block) (post : List Block) :
(moveDir HeadMove.right)^[6 * mid.length]
(cellsTape L (encodeBlocks (mid ++ cur :: post) ++ R)) =
cellsTape ((encodeBlocks mid).reverse ++ L)
(Block.toCells cur ++ (encodeBlocks post ++ R)) := by
rw [encodeBlocks_append, encodeBlocks_cons, List.append_assoc,
List.append_assoc,
show (6 : Nat) * mid.length = (encodeBlocks mid).length by
rw [encodeBlocks_length],
cellsTape_advance]
/-- **The walk, specified.** From a region `mid ++ cur :: post` whose `side`
flag is down throughout `mid` and up at `cur`, the walk halts `false` after
`|mid|` full rounds plus the read of `cur`, leaving every tape unchanged except
tape `i`, whose head has advanced past `cur`. -/
theorem walkToFlag_spec (side : TrackSide) (i : Fin tapes)
(tape : Fin tapes → Tape) (L R : List TapeSymbol)
(mid : List Block) (cur : Block) (post : List Block)
(hmid : ∀ b ∈ mid, side.getFlag b = false)
(hcur : side.getFlag cur = true)
(hi : tape i = cellsTape L (encodeBlocks (mid ++ cur :: post) ++ R)) :
HaltsExactly (walkToFlag side i) ((walkToFlag side i).startCfg tape)
(loopCost (fun _ => blockReadSteps) mid.length + blockReadSteps) false ∧
((walkToFlag side i).step^[
loopCost (fun _ => blockReadSteps) mid.length + blockReadSteps])
((walkToFlag side i).startCfg tape) =
(walkBody side i).step^[blockReadSteps]
⟨(walkBody side i).start,
scanTapesDir tape i HeadMove.right (6 * mid.length)⟩ ∧
(((walkToFlag side i).step^[
loopCost (fun _ => blockReadSteps) mid.length + blockReadSteps])
((walkToFlag side i).startCfg tape)).tape =
scanTapesDir tape i HeadMove.right (6 * (mid.length + 1)) := by
set body := walkBody side i with hbody
-- the round plan: tapes advanced by 6m cells
set T : Nat → (Fin tapes → Tape) :=
fun m => scanTapesDir tape i HeadMove.right (6 * m) with hT
set config : Nat → TypedConfiguration tapes _ :=
fun m => ⟨body.start, T m⟩ with hconfig
-- each round's tape effect
have htapeStep : ∀ m : Nat,
((body.step^[blockReadSteps]) (config m)).tape = T (m + 1) := by
intro m
have hc : config m =
TypedConfiguration.inLeftState ((readCellRight i).startCfg (T m)) := rfl
rw [hc, hbody]
show (((blockRead i (walkTest side)).step^[blockReadSteps])
(TypedConfiguration.inLeftState
((readCellRight i).startCfg (T m)))).tape = T (m + 1)
rw [blockRead_tape]
simp only [hT]
rw [scanTapesDir_compose, show 6 + 6 * m = 6 * (m + 1) by omega]
-- each round's verdict, from whatever block stands at the boundary
have hverdict : ∀ (m : Nat) (b : Block) (L' R' : List TapeSymbol),
T m i = cellsTape L' (Block.toCells b ++ R') →
HaltsExactly body (config m) blockReadSteps (walkTest side b) := by
intro m b L' R' hTi
have hb := blockOfCells_cellsTape i (T m) L' R' b hTi
have hs := blockRead_spec i (walkTest side) (T m)
rw [hb] at hs
exact hs
have hround : ∀ m, m < mid.length →
HaltsExactly body (config m) blockReadSteps true ∧
config (m + 1) =
⟨body.start, ((body.step^[blockReadSteps]) (config m)).tape⟩ := by
intro m hm
have hTi : T m i = cellsTape ((encodeBlocks (mid.take m)).reverse ++ L)
(Block.toCells (mid.getD m Block.blank) ++
(encodeBlocks (mid.drop (m + 1) ++ cur :: post) ++ R)) := by
rw [hT]
simp only [scanTapesDir_self]
rw [hi]
exact walk_boundary L R mid cur post m hm
have h := hverdict m (mid.getD m Block.blank) _ _ hTi
have hflag : walkTest side (mid.getD m Block.blank) = true := by
have hmem : mid.getD m Block.blank ∈ mid := by
rw [List.getD_eq_getElem mid Block.blank hm]
exact List.getElem_mem hm
rw [walkTest, hmid _ hmem]
rfl
rw [hflag] at h
refine ⟨h, ?_⟩
rw [htapeStep m]
have hexit : HaltsExactly body (config mid.length) blockReadSteps false := by
have hTi : T mid.length i =
cellsTape ((encodeBlocks mid).reverse ++ L)
(Block.toCells cur ++ (encodeBlocks post ++ R)) := by
rw [hT]
simp only [scanTapesDir_self]
rw [hi]
exact walk_boundary_cur L R mid cur post
have h := hverdict mid.length cur _ _ hTi
have hflag : walkTest side cur = false := by
rw [walkTest, hcur]
rfl
rwa [hflag] at h
-- assemble
have hmain := TypedMachine.repeatUntilFalse_spec body config
(fun _ => blockReadSteps) mid.length blockReadSteps hround hexit
have hcfgF := TypedMachine.repeatUntilFalse_config body config
(fun _ => blockReadSteps) mid.length blockReadSteps hround hexit
have htape := TypedMachine.repeatUntilFalse_tape body config
(fun _ => blockReadSteps) mid.length blockReadSteps hround hexit
have hcfg0 : config 0 = (walkToFlag side i).startCfg tape := by
rw [hconfig]
show (⟨body.start, T 0⟩ : TypedConfiguration tapes _) = _
rw [hT]
show (⟨body.start, scanTapesDir tape i HeadMove.right (6 * 0)⟩ :
TypedConfiguration tapes _) = _
rw [Nat.mul_zero, scanTapesDir_zero]
rfl
rw [hcfg0] at hmain hcfgF htape
refine ⟨hmain, ?_, ?_⟩
· show (body.repeatUntilFalse.step^[
loopCost (fun _ => blockReadSteps) mid.length + blockReadSteps])
((walkToFlag side i).startCfg tape) = _
exact hcfgF
· show ((body.repeatUntilFalse.step^[
loopCost (fun _ => blockReadSteps) mid.length + blockReadSteps])
((walkToFlag side i).startCfg tape)).tape = _
rw [htape, htapeStep mid.length]
end SipserGacsLautemann