Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Two virtual tapes on one physical tape

Definition
sgl_two_track

by Henry Yuen · Jul 25, 2026 · Mathlib c5ea003 (Lean v4.30.0)

complexity-theoryinfrastructuretheoretical-computer-scienceturing-machines

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 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 ⟨left,head,right⟩\langle \mathit{left}, \mathit{head}, \mathit{right}\rangle⟨left,head,right⟩ and carries no absolute coordinate, yet two virtual tapes must be aligned by position. The correspondence is therefore stated in the direction blocks →\to→ 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.

Definition code
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
Source
Standard track encoding for multitape Turing-machine simulation, specialized to the model of Def_sipser_gacs_lautemann; supports the scratch-tape elimination of Def_sgl_scratch_tapes.

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me