Two virtual tapes on one physical tape
Definitionsgl_two_trackTwo virtual tapes on one physical tape: the representation on which scratch-tape elimination rests.
A physical tape is read as a list of blocks, each holding one cell of each of two virtual tracks together with a flag marking whether that track's head sits there. Two heads cannot both be the physical head, so at least one position must be recorded on the tape; recording both makes the two tracks symmetric.
The design question this module settles. Tape is a zipper and carries no absolute coordinate, yet two virtual tapes must be aligned by position. The correspondence is therefore stated in the direction blocks tapes, with the flag supplying the missing coordinate: trackTape projects a block list onto one track and splits it at the flagged block.
The lemmas that matter. trackTape_write says writing at the flagged block implements Tape.write; trackTape_moveRight and trackTape_moveLeft say moving the flag one block implements Tape.move, with _pad variants extending the region by a blank block at either edge. Together they establish that block-level programs implement tape-level semantics, which is what a per-step simulation lemma needs as its target.
trackTape_setA_symB and its mirror record that the two virtual tapes are genuinely independent: writing on one track leaves the other's projection untouched, even though both are projections of the same block list.
Formalization note. before is stored nearest-block-first, matching Tape.left's own convention. Storing it in reading order and reversing is the more natural-looking choice and is wrong: Tape.move .right prepends the old head to left, so the two orders disagree the moment the head moves. Since both tracks are projections of one block list, differing only in which field is read, the two virtual tapes cost one set of lemmas rather than two.
import Definitions.Def_sgl_state_algebra
/-!
# Two virtual tapes on one physical tape
The representation on which scratch-tape elimination rests. A physical tape is
read as a list of **blocks**, each holding one cell of each of two virtual
tracks together with a flag marking whether that track's head is here.
The design question this module answers is whether the representation survives
contact with `Tape`, which is a zipper `⟨left, head, right⟩` with no absolute
coordinate. Two virtual tapes must be aligned *by position*, and a zipper does
not carry one — so the correspondence is stated in the direction
blocks → tapes, where the flag supplies the missing coordinate: the projected
tape is split at the flagged block.
`trackTape_write` and `trackTape_moveRight` are the two lemmas that matter.
They say that writing at the flagged block implements `Tape.write`, and moving
the flag one block right implements `Tape.move .right`, on the projected tape.
If these hold, block-level programs implement tape-level semantics and the
per-step simulation lemma has a target to aim at.
-/
namespace SipserGacsLautemann
/-- One position of the physical tape: a cell of each track, plus each track's
head flag. -/
structure Block where
symA : TapeSymbol
flagA : Bool
symB : TapeSymbol
flagB : Bool
/-- An untouched position. -/
def Block.blank : Block := ⟨TapeSymbol.blank, false, TapeSymbol.blank, false⟩
/-- Project a block list onto a track, as a plain symbol list. -/
def trackSyms (pick : Block → TapeSymbol) (blocks : List Block) :
List TapeSymbol :=
blocks.map pick
/-- The virtual tape carried by one track: the projected symbols, split at the
flagged block. The flag is what supplies the absolute coordinate that the
zipper representation lacks.
`before` is stored **nearest-block-first**, matching `Tape.left`'s own
convention. Storing it in reading order and reversing looks more natural and is
wrong: `Tape.move .right` prepends the old head to `left`, so the two orders
disagree the moment the head moves. -/
def trackTape (pick : Block → TapeSymbol) (before : List Block) (cur : Block)
(after : List Block) : Tape :=
⟨trackSyms pick before, pick cur, trackSyms pick after⟩
/-- Writing at the flagged block implements `Tape.write` on the projected
tape. -/
theorem trackTape_write (pick : Block → TapeSymbol) (set : TapeSymbol → Block → Block)
(hset : ∀ s b, pick (set s b) = s)
(before : List Block) (cur : Block) (after : List Block) (s : TapeSymbol) :
trackTape pick before (set s cur) after =
Tape.write (trackTape pick before cur after) s := by
simp [trackTape, Tape.write, hset]
/-- Moving the flag one block right implements `Tape.move .right`, when there is
a next block. -/
theorem trackTape_moveRight (pick : Block → TapeSymbol)
(before : List Block) (cur : Block) (nxt : Block) (after : List Block) :
trackTape pick (cur :: before) nxt after =
Tape.move (trackTape pick before cur (nxt :: after)) HeadMove.right := by
simp [trackTape, trackSyms, Tape.move]
/-- Moving the flag one block left implements `Tape.move .left`, when there is a
previous block. -/
theorem trackTape_moveLeft (pick : Block → TapeSymbol)
(before : List Block) (prv : Block) (cur : Block) (after : List Block) :
trackTape pick before prv (cur :: after) =
Tape.move (trackTape pick (prv :: before) cur after) HeadMove.left := by
simp [trackTape, trackSyms, Tape.move]
/-- At the right edge the region must be extended with a blank block; doing so
still implements `Tape.move .right`. -/
theorem trackTape_moveRight_pad (pick : Block → TapeSymbol)
(hblank : pick Block.blank = TapeSymbol.blank)
(before : List Block) (cur : Block) :
trackTape pick (cur :: before) Block.blank [] =
Tape.move (trackTape pick before cur []) HeadMove.right := by
simp [trackTape, trackSyms, Tape.move, hblank]
/-- And at the left edge. -/
theorem trackTape_moveLeft_pad (pick : Block → TapeSymbol)
(hblank : pick Block.blank = TapeSymbol.blank)
(cur : Block) (after : List Block) :
trackTape pick [] Block.blank (cur :: after) =
Tape.move (trackTape pick [] cur after) HeadMove.left := by
simp [trackTape, trackSyms, Tape.move, hblank]
/-! ## The two tracks
Both virtual tapes are projections of the *same* block list, differing only in
which field is read and which flag is followed. Everything above applies to
each track by instantiation, so the two tapes cost one set of lemmas rather
than two. -/
def Block.setA (s : TapeSymbol) (b : Block) : Block := { b with symA := s }
def Block.setB (s : TapeSymbol) (b : Block) : Block := { b with symB := s }
theorem Block.symA_setA (s : TapeSymbol) (b : Block) :
Block.symA (Block.setA s b) = s := rfl
theorem Block.symB_setB (s : TapeSymbol) (b : Block) :
Block.symB (Block.setB s b) = s := rfl
/-- Writing on track A leaves track B's projection untouched: the two virtual
tapes are independent even though they share a block list. -/
theorem trackTape_setA_symB (before : List Block) (cur : Block)
(after : List Block) (s : TapeSymbol) :
trackTape Block.symB before (Block.setA s cur) after =
trackTape Block.symB before cur after := by
simp [trackTape, Block.setA]
theorem trackTape_setB_symA (before : List Block) (cur : Block)
(after : List Block) (s : TapeSymbol) :
trackTape Block.symA before (Block.setB s cur) after =
trackTape Block.symA before cur after := by
simp [trackTape, Block.setB]
end SipserGacsLautemann