Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

The initial region

Definition
sgl_merge_init

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

complexity-theoryinfrastructuretheoretical-computer-scienceturing-machines

The initial region: one block, written and parked.

The two tapes being merged are empty — that is precisely the hypothesis of merge_empty_scratch_tapes, and it is what makes this half of the scratch-tape elimination tractable. So the initial region is a single block, flagged on both tracks and blank on both. Each track's projection is then the one-cell blank tape, which is the empty tape, so PadEq holds by reflexivity and HostsPair is immediate. No copying, no alignment: the whole initial invariant is one block and two reflexivities.

initRegion writes that block and parks the head, in fourteen steps. Starting from an empty tape it writes six cells rightwards, then steps left seven times: six to retrace the block, and one more that steps off the end of the zipper and materialises a blank. That last step is what leaves the head on the parking blank with the block laid out to its right — and it is why the resulting ghost is [blank][{\rm blank}][blank] rather than empty. The ghost machinery, introduced to track exactly these materialised blanks, absorbs it without comment.

initRound packages the result as the trajectory's starting record.

Definition code
import Definitions.Def_sgl_merge_loop

/-!
# The initial region

Module F2 of DESIGN_step_spec_endgame.

The two tapes being merged are **empty** — that is exactly the hypothesis of
`merge_empty_scratch_tapes`, and it is what makes this half of the elimination
tractable.  So the initial region is a single block, flagged on both tracks and
blank on both: each track's projection is then the one-cell blank tape, which
is the empty tape, and `PadEq` holds by reflexivity.

`initRegion` writes that block and parks the head.  Starting from an empty
tape it writes six cells rightwards and then steps left seven times: six to
retrace the block and one more, which — a leftward step off the end of the
zipper materialising a blank — lands the head on the parking blank with the
block laid out to its right.  That seventh step is why the resulting ghost is
`[blank]` rather than `[]`.
-/

namespace SipserGacsLautemann

variable {tapes : Nat}

/-- The initial block: flagged on both tracks, blank on both. -/
def initBlock : Block :=
  ⟨TapeSymbol.blank, true, TapeSymbol.blank, true⟩

@[simp] theorem initBlock_flagA : TrackSide.A.getFlag initBlock = true := rfl
@[simp] theorem initBlock_flagB : TrackSide.B.getFlag initBlock = true := rfl
@[simp] theorem initBlock_pickA :
    TrackSide.A.pick initBlock = TapeSymbol.blank := rfl
@[simp] theorem initBlock_pickB :
    TrackSide.B.pick initBlock = TapeSymbol.blank := rfl

/-- Write the initial block and park the head. -/
def initRegion (i : Fin tapes) :=
  (writeRun i (Block.toCells initBlock)).andThen fun _ =>
    moveUpTo i 7 HeadMove.left

/-- Seven leftward steps from the just-written run land on the parking blank. -/
theorem initRegion_park :
    ((moveDir HeadMove.left)^[7])
        ⟨(Block.toCells initBlock).reverse, TapeSymbol.blank, []⟩ =
      ParkedTape [initBlock] [TapeSymbol.blank] := rfl

set_option maxHeartbeats 1000000 in
/-- **The initial region is established in fourteen steps.** -/
theorem initRegion_spec (i : Fin tapes) (tape : Fin tapes → Tape)
    (hi : tape i = ⟨[], TapeSymbol.blank, []⟩) :
    HaltsExactly (initRegion i) ((initRegion i).startCfg tape) 14 true ∧
    (((initRegion i).step^[14]) ((initRegion i).startCfg tape)).tape =
      Function.update tape i (ParkedTape [initBlock] [TapeSymbol.blank]) := by
  have hcells : tape i = cellsTape [] [] := by rw [hi]; rfl
  have hlen : (Block.toCells initBlock).length = 6 := Block.toCells_length _
  have hw : HaltsExactly (writeRun i (Block.toCells initBlock))
      ((writeRun i (Block.toCells initBlock)).startCfg tape) 6 true :=
    writeRun_spec i (Block.toCells initBlock) tape [] [] hcells
  have hwt : (((writeRun i (Block.toCells initBlock)).step^[6])
      ((writeRun i (Block.toCells initBlock)).startCfg tape)).tape =
      Function.update tape i
        (cellsTape (Block.toCells initBlock).reverse []) := by
    have h := writeRun_tape i (Block.toCells initBlock) tape [] [] hcells
    simpa using h
  set T1 := Function.update tape i
    (cellsTape (Block.toCells initBlock).reverse []) with hT1
  have hT1i : T1 i = ⟨(Block.toCells initBlock).reverse, TapeSymbol.blank, []⟩ := by
    rw [hT1]; simp [cellsTape]
  have hm := moveUpTo_spec i 7 HeadMove.left (by omega) T1
  have hmt := moveUpTo_tape i 7 HeadMove.left (by omega) T1
  rw [hT1i, initRegion_park] at hmt
  have hchain := chainStepC hw hwt hm
  refine ⟨hchain.1, ?_⟩
  have hfin := congrArg TypedConfiguration.tape hchain.2
  show _ = _
  rw [show (TypedConfiguration.inRight true
      (((moveUpTo i 7 HeadMove.left).step^[7])
        ((moveUpTo i 7 HeadMove.left).startCfg T1))).tape =
      (((moveUpTo i 7 HeadMove.left).step^[7])
        ((moveUpTo i 7 HeadMove.left).startCfg T1)).tape from rfl] at hfin
  rw [hmt] at hfin
  rw [hT1, Function.update_idem] at hfin
  exact hfin

/-! ## The initial round -/

variable {states : Nat} {tapes' : Nat} {M : Machine (tapes' + 2) states}

/-- Both hosted tapes empty is hosted by the single initial block. -/
theorem hostsPair_initBlock (t : TrackSide → Tape)
    (ht : ∀ sd, t sd = ⟨[], TapeSymbol.blank, []⟩) :
    HostsPair [initBlock] t := by
  intro side
  refine ⟨[], initBlock, [], ⟨rfl, ?_, ?_, ?_⟩, ?_⟩
  · intro b hb; simp at hb
  · cases side <;> rfl
  · intro b hb; simp at hb
  · rw [ht side]
    cases side <;> exact ⟨[], [], AllBlank.nil, AllBlank.nil, rfl⟩

/-- **The initial round.**  With the two hosted virtual tapes empty and the
host physical tape empty, the region written by `initRegion` satisfies the
merge invariant. -/
noncomputable def initRound (M : Machine (tapes' + 2) states)
    (virt : Configuration (tapes' + 2) states)
    (base : Fin (tapes' + 1) → Tape)
    (hident : IdentPart tapes' virt base)
    (hhost : ∀ sd, virt.tape (hostIdx tapes' sd) = ⟨[], TapeSymbol.blank, []⟩) :
    MergeRound tapes' M :=
  { virt := virt
    base := base
    blocks := [initBlock]
    ghost := [TapeSymbol.blank]
    hg := AllBlank.single
    hident := hident
    hosts := hostsPair_initBlock _ hhost }

@[simp] theorem initRound_virt (M : Machine (tapes' + 2) states)
    (virt : Configuration (tapes' + 2) states)
    (base : Fin (tapes' + 1) → Tape) (hident) (hhost) :
    (initRound M virt base hident hhost).virt = virt := rfl

@[simp] theorem initRound_blocks (M : Machine (tapes' + 2) states)
    (virt : Configuration (tapes' + 2) states)
    (base : Fin (tapes' + 1) → Tape) (hident) (hhost) :
    (initRound M virt base hident hhost).blocks = [initBlock] := rfl

@[simp] theorem initRound_park (M : Machine (tapes' + 2) states)
    (virt : Configuration (tapes' + 2) states)
    (base : Fin (tapes' + 1) → Tape) (hident) (hhost) :
    (initRound M virt base hident hhost).park =
      Function.update base (Fin.last tapes')
        (ParkedTape [initBlock] [TapeSymbol.blank]) := rfl

end SipserGacsLautemann
Source
Initial region for the two-track simulation; builds on Def_sgl_merge_loop.

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