Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

The block codec: blocks as physical cells

Definition
sgl_block_codec

by Henry Yuen · Jul 25, 2026 · Mathlib 0df444a (Lean v4.33.1)

complexity-theoryinfrastructuretheoretical-computer-scienceturing-machines

The 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 (0,0)(0,0)(0,0) 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 (1,1)(1,1)(1,1) 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.

Definition code
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
Source
Standard track/block encoding for multitape Turing-machine simulation, specialized to the model of Def_sipser_gacs_lautemann; physical layer for Def_sgl_two_track.

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