The block codec: blocks as physical cells
Definitionsgl_block_codecThe block codec: the physical layer beneath the two-track representation.
sgl_two_track supplied the logical layer — a list of blocks, each carrying one cell of two virtual tracks together with their head flags, projecting onto two virtual tapes. This module supplies the physical one: how a block is written as TapeSymbol cells, and how walking the physical tape corresponds to walking the block list.
A symbol occupies two cells, and every encoded cell is written. The symbol blank is encoded as rather than as a physical blank, so a physical blank retains its meaning of "outside the region" and the existing scan guards continue to work unchanged; encodeBlocks_ne_blank records this. The code is unused and held in reserve for markers. A block is therefore six cells: two per track symbol, one per track flag.
The load-bearing result is atBlockStart_advance: six steps to the right carry the head from one block boundary to the next. This is what allows a sweep over the region to be analysed one block at a time rather than one cell at a time, and it is the interface every phase of the simulation will use.
parkedTape is the form the simulation invariant takes between simulated steps — the head resting on the blank immediately left of the region — chosen so that the invariant mentions a flat list of blocks and no zipper at all. parkedTape_enter steps from there to the first block boundary.
Formalization notes. encodeBlocks is defined by explicit recursion rather than List.flatMap, which keeps its rewriting elementary. atBlockStart carries an explicit left-context parameter for whatever lies beyond the region: entering the region from the parked position leaves the parking blank behind on the left, and a representation without room for it does not survive parkedTape_enter.
import Definitions.Def_sgl_loop_state
/-!
# The block codec
Module C of the merge_empty plan (`DESIGN_merge_empty_v2.md`).
`sgl_two_track` gave the *logical* layer: a list of blocks, each holding one
cell of two virtual tracks plus their head flags, projecting onto two virtual
tapes. This module gives the *physical* layer: how a block is written as
`TapeSymbol` cells, and how walking the physical tape corresponds to walking the
block list.
Two decisions, both taken to keep the proofs small:
* **A symbol is encoded in two cells, and every encoded cell is written.**
`blank` becomes `(0,0)` rather than a physical blank, so a physical blank
still means "outside the region" and the existing scan guards keep working.
The pair `(1,1)` is unused and held in reserve for markers.
* **`encodeBlocks` is defined by explicit recursion, not `List.flatMap`.**
The plan's kill-switch for this module was the risk of drowning in flatMap
rewriting; declining to use flatMap in the first place is the cheap way to
avoid it.
The load-bearing result is `atBlockStart_advance`: six physical steps to the
right move the head from one block boundary to the next, which is what lets a
sweep be analysed one block at a time.
-/
namespace SipserGacsLautemann
/-! ## Symbols in two cells -/
/-- A tape symbol as two written cells. Never blank, so physical blank keeps
its meaning as "unwritten". -/
def cellsOfSymbol : TapeSymbol → TapeSymbol × TapeSymbol
| TapeSymbol.blank => (TapeSymbol.bit false, TapeSymbol.bit false)
| TapeSymbol.bit false => (TapeSymbol.bit false, TapeSymbol.bit true)
| TapeSymbol.bit true => (TapeSymbol.bit true, TapeSymbol.bit false)
/-- The inverse; the unused code `(1,1)` is mapped to `blank` so the function is
total. -/
def symbolOfCells : TapeSymbol → TapeSymbol → TapeSymbol
| TapeSymbol.bit false, TapeSymbol.bit false => TapeSymbol.blank
| TapeSymbol.bit false, TapeSymbol.bit true => TapeSymbol.bit false
| TapeSymbol.bit true, TapeSymbol.bit false => TapeSymbol.bit true
| _, _ => TapeSymbol.blank
@[simp] theorem symbolOfCells_cellsOfSymbol (s : TapeSymbol) :
symbolOfCells (cellsOfSymbol s).1 (cellsOfSymbol s).2 = s := by
cases s with
| blank => rfl
| bit b => cases b <;> rfl
theorem cellsOfSymbol_fst_ne_blank (s : TapeSymbol) :
(cellsOfSymbol s).1 ≠ TapeSymbol.blank := by
cases s with
| blank => simp [cellsOfSymbol]
| bit b => cases b <;> simp [cellsOfSymbol]
theorem cellsOfSymbol_snd_ne_blank (s : TapeSymbol) :
(cellsOfSymbol s).2 ≠ TapeSymbol.blank := by
cases s with
| blank => simp [cellsOfSymbol]
| bit b => cases b <;> simp [cellsOfSymbol]
/-! ## Blocks in six cells -/
/-- A block as six physical cells: two for each track's symbol, one for each
track's head flag. -/
def Block.toCells (b : Block) : List TapeSymbol :=
[(cellsOfSymbol b.symA).1, (cellsOfSymbol b.symA).2, TapeSymbol.bit b.flagA,
(cellsOfSymbol b.symB).1, (cellsOfSymbol b.symB).2, TapeSymbol.bit b.flagB]
@[simp] theorem Block.toCells_length (b : Block) : b.toCells.length = 6 := rfl
theorem Block.toCells_ne_blank (b : Block) :
∀ c ∈ b.toCells, c ≠ TapeSymbol.blank := by
intro c hc
simp only [Block.toCells, List.mem_cons, List.not_mem_nil, or_false] at hc
rcases hc with rfl | rfl | rfl | rfl | rfl | rfl
· exact cellsOfSymbol_fst_ne_blank _
· exact cellsOfSymbol_snd_ne_blank _
· simp
· exact cellsOfSymbol_fst_ne_blank _
· exact cellsOfSymbol_snd_ne_blank _
· simp
/-- A region of blocks, in reading order. Explicit recursion, not `flatMap`. -/
def encodeBlocks : List Block → List TapeSymbol
| [] => []
| b :: bs => b.toCells ++ encodeBlocks bs
/-- The same region in `Tape.left`'s nearest-first order. -/
def encodeBlocksRev : List Block → List TapeSymbol
| [] => []
| b :: bs => b.toCells.reverse ++ encodeBlocksRev bs
@[simp] theorem encodeBlocks_nil : encodeBlocks [] = [] := rfl
@[simp] theorem encodeBlocks_cons (b : Block) (bs : List Block) :
encodeBlocks (b :: bs) = b.toCells ++ encodeBlocks bs := rfl
@[simp] theorem encodeBlocksRev_cons (b : Block) (bs : List Block) :
encodeBlocksRev (b :: bs) = b.toCells.reverse ++ encodeBlocksRev bs := rfl
theorem encodeBlocks_length (bs : List Block) :
(encodeBlocks bs).length = 6 * bs.length := by
induction bs with
| nil => rfl
| cons b bs ih => simp [encodeBlocks, ih]; omega
/-- Every cell of an encoded region is written: physical blank still marks the
region's end. -/
theorem encodeBlocks_ne_blank (bs : List Block) :
∀ c ∈ encodeBlocks bs, c ≠ TapeSymbol.blank := by
induction bs with
| nil => intro c hc; simp at hc
| cons b bs ih =>
intro c hc
rw [encodeBlocks_cons, List.mem_append] at hc
rcases hc with h | h
· exact Block.toCells_ne_blank b c h
· exact ih c h
/-! ## Standing at a block boundary -/
/-- The physical tape with the head on the first cell of block `b`, the blocks
of `before` behind it (nearest-first) and `after` ahead.
`tail` is whatever lies beyond the region on the left — in the simulation, the
blank the head was parked on. It is a parameter rather than `[]` because
entering the region from the parked position leaves that blank behind, and a
representation with no room for it does not survive `parkedTape_enter`. -/
def atBlockStart (tail : List TapeSymbol) (before : List Block) (b : Block)
(after : List Block) : Tape :=
⟨encodeBlocksRev before ++ tail,
(cellsOfSymbol b.symA).1,
[(cellsOfSymbol b.symA).2, TapeSymbol.bit b.flagA,
(cellsOfSymbol b.symB).1, (cellsOfSymbol b.symB).2,
TapeSymbol.bit b.flagB] ++ encodeBlocks after⟩
/-- **The load-bearing lemma.** Six steps right move the head from one block
boundary to the next, so a sweep can be analysed one block at a time. -/
theorem atBlockStart_advance (tail : List TapeSymbol) (before : List Block)
(b nxt : Block) (after : List Block) :
(moveDir HeadMove.right)^[6] (atBlockStart tail before b (nxt :: after)) =
atBlockStart tail (b :: before) nxt after := by
simp only [atBlockStart, encodeBlocksRev_cons, encodeBlocks_cons,
Block.toCells, List.reverse_cons, List.append_assoc, List.cons_append,
List.nil_append, List.reverse_nil]
rfl
/-- Parked: the head sits on the blank immediately left of the region. This is
the form the simulation invariant uses between simulated steps, so that no block
zipper appears in the invariant at all. -/
def parkedTape (blocks : List Block) : Tape :=
⟨[], TapeSymbol.blank, encodeBlocks blocks⟩
/-- One step right from the parked position stands at the first block. -/
theorem parkedTape_enter (b : Block) (after : List Block) :
moveDir HeadMove.right (parkedTape (b :: after)) =
atBlockStart [TapeSymbol.blank] [] b after := by
simp only [parkedTape, atBlockStart, encodeBlocks_cons, Block.toCells,
encodeBlocksRev, List.cons_append, List.nil_append]
rfl
/-- The parked head reads blank, so a scan guard fires immediately there. -/
@[simp] theorem parkedTape_head (blocks : List Block) :
(parkedTape blocks).head = TapeSymbol.blank := rfl
/-- At a block boundary the head reads a written cell, so a scan guard does not
fire inside the region. -/
theorem atBlockStart_head_ne_blank (tail : List TapeSymbol)
(before : List Block) (b : Block) (after : List Block) :
(atBlockStart tail before b after).head ≠ TapeSymbol.blank :=
cellsOfSymbol_fst_ne_blank _
/-! ## Reading a block back
The projections a sweep needs when standing at a boundary: the two symbols and
the two flags, recovered from the cells under and just ahead of the head. -/
theorem atBlockStart_symA (tail : List TapeSymbol) (before : List Block)
(b : Block) (after : List Block) :
symbolOfCells (atBlockStart tail before b after).head
((atBlockStart tail before b after).right.headD TapeSymbol.blank) =
b.symA := by
simp only [atBlockStart, List.headD, List.head?]
exact symbolOfCells_cellsOfSymbol b.symA
theorem atBlockStart_flagA (tail : List TapeSymbol) (before : List Block)
(b : Block) (after : List Block) :
((moveDir HeadMove.right)^[2]
(atBlockStart tail before b after)).head = TapeSymbol.bit b.flagA := by
simp only [atBlockStart, Block.toCells]
rfl
theorem atBlockStart_flagB (tail : List TapeSymbol) (before : List Block)
(b : Block) (after : List Block) :
((moveDir HeadMove.right)^[5]
(atBlockStart tail before b after)).head = TapeSymbol.bit b.flagB := by
simp only [atBlockStart, Block.toCells]
rfl
end SipserGacsLautemann