Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

The merge invariant: PadEq and the five preservations

Definition
sgl_merge_invariant

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

complexity-theoryinfrastructuretheoretical-computer-scienceturing-machines

The merge invariant: what a hosted region means, and why the updates preserve it.

Padding, not equality. The obvious invariant — each track's projection equals its virtual tape — is false, and the counterexample is region growth: when one track's flag walks off the edge, the fresh block's other-track symbol is a written blank, a cell the other virtual tape never asked for. The correct relation is PadEq: agreement up to all-blank padding at the two far ends. It agrees on the head, so reads are faithful; and PadEq.move — the load-bearing lemma — shows it stable under head movement: when the true tape steps into fresh blanks, the padded one steps into its padding, and reads blank there too.

The five bridges. Each update variant's block-level result projects, on its own track, to exactly Tape.write or Tape.move ∘ Tape.write of the old projection — with no padding on the own side: the fresh blocks the edges materialise carry precisely the blank the virtual zipper grows by. All five proofs are one simp over the map-form of the projection.

Cross-side survival. An update must not disturb the other track. For the equal-length variants the result is pointwise other-side-equal, and SplitAtFlag.transfer carries the other split across positionally with its projection intact; the edge variants append or prepend one fresh block, which the other side absorbs as end-padding via snoc/cons split extensions and PadEq.pad_right/pad_left.

The theorems. HostsPair blocks t says the region carries a virtual tape per track, each up to padding; HostsPair.head_eq says reading the flagged block reads the virtual head; and the five preservation theorems — update_stay, update_right_mid, update_right_edge, update_left_mid, update_left_edge — say every track update re-establishes the pair with the updated side's tape written-and-moved and the other side untouched. Together with the updateTrack specifications of the previous module, a physical update now is a virtual Tape.write-and-move, semantically and operationally at once. Split uniqueness (SplitAtFlag.unique) glues any two accounts of the same region together.

Definition code
import Definitions.Def_sgl_track_update
import Definitions.Def_sgl_two_track

/-!
# The merge invariant

Module E of the merge_empty plan, first part: the relation between a hosted
region and the two virtual tapes it carries, and the bridge lemmas showing the
track updates implement virtual `Tape.write` and `Tape.move`.

## Padding, not equality

The obvious invariant — each track's projection *equals* its virtual tape —
is false, and the counterexample is region growth.  When track A's flag walks
off the edge, a fresh block materialises whose B-symbol is a written blank: the
B-projection gains a cell its virtual tape never asked for.  The correct
relation is `PadEq`: equal up to all-blank padding at the two far ends.  It
agrees on the head (so reads are faithful), and it is stable under `Tape.write`
and `Tape.move` (so steps preserve it) — the padding is exactly the visited
region's ghost, now on the virtual side.
-/

namespace SipserGacsLautemann

/-! ## Track sides, completed -/

def TrackSide.pick : TrackSide → Block → TapeSymbol
  | .A => Block.symA
  | .B => Block.symB

def TrackSide.other : TrackSide → TrackSide
  | .A => .B
  | .B => .A

@[simp] theorem pick_setSymFlag_self (side : TrackSide) (s : TapeSymbol)
    (f : Bool) (b : Block) :
    side.pick (setSymFlag side s f b) = s := by
  cases side <;> rfl

@[simp] theorem getFlag_setSymFlag_self (side : TrackSide) (s : TapeSymbol)
    (f : Bool) (b : Block) :
    side.getFlag (setSymFlag side s f b) = f := by
  cases side <;> rfl

@[simp] theorem pick_setSymFlag_other (side : TrackSide) (s : TapeSymbol)
    (f : Bool) (b : Block) :
    side.other.pick (setSymFlag side s f b) = side.other.pick b := by
  cases side <;> rfl

@[simp] theorem getFlag_setSymFlag_other (side : TrackSide) (s : TapeSymbol)
    (f : Bool) (b : Block) :
    side.other.getFlag (setSymFlag side s f b) = side.other.getFlag b := by
  cases side <;> rfl

@[simp] theorem pick_setFlag (side side' : TrackSide) (f : Bool)
    (b : Block) : side'.pick (setFlag side f b) = side'.pick b := by
  cases side <;> cases side' <;> rfl

@[simp] theorem getFlag_setFlag_self (side : TrackSide) (f : Bool)
    (b : Block) : side.getFlag (setFlag side f b) = f := by
  cases side <;> rfl

@[simp] theorem getFlag_setFlag_other (side : TrackSide) (f : Bool)
    (b : Block) :
    side.other.getFlag (setFlag side f b) = side.other.getFlag b := by
  cases side <;> rfl

@[simp] theorem pick_freshFlagged_other (side : TrackSide) :
    side.other.pick (freshFlagged side) = TapeSymbol.blank := by
  cases side <;> rfl

@[simp] theorem getFlag_freshFlagged_other (side : TrackSide) :
    side.other.getFlag (freshFlagged side) = false := by
  cases side <;> rfl

@[simp] theorem pick_freshFlagged_self (side : TrackSide) :
    side.pick (freshFlagged side) = TapeSymbol.blank := by
  cases side <;> rfl

@[simp] theorem getFlag_freshFlagged_self (side : TrackSide) :
    side.getFlag (freshFlagged side) = true := by
  cases side <;> rfl

/-! ## The split and the projection -/

/-- `blocks` splits at `side`'s unique flag: clear before, set at `cur`, clear
after. -/
structure SplitAtFlag (side : TrackSide) (blocks : List Block)
    (pre : List Block) (cur : Block) (post : List Block) : Prop where
  eq : blocks = pre ++ cur :: post
  preClear : ∀ b ∈ pre, side.getFlag b = false
  curSet : side.getFlag cur = true
  postClear : ∀ b ∈ post, side.getFlag b = false

/-- The virtual tape a track carries, from a flat split (reading order). -/
def trackOfSplit (pick : Block → TapeSymbol) (pre : List Block) (cur : Block)
    (post : List Block) : Tape :=
  trackTape pick pre.reverse cur post

/-! ## Equality up to end-padding -/

/-- Two tapes agreeing everywhere the first one reaches, the second possibly
carrying all-blank padding at its two far ends. -/
def PadEq (t tp : Tape) : Prop :=
  ∃ lp rp, AllBlank lp ∧ AllBlank rp ∧
    tp = ⟨t.left ++ lp, t.head, t.right ++ rp⟩

theorem PadEq.refl (t : Tape) : PadEq t t :=
  ⟨[], [], AllBlank.nil, AllBlank.nil, by simp⟩

theorem PadEq.head_eq {t tp : Tape} (h : PadEq t tp) : tp.head = t.head := by
  obtain ⟨lp, rp, -, -, heq⟩ := h
  rw [heq]

theorem PadEq.write {t tp : Tape} (h : PadEq t tp) (c : TapeSymbol) :
    PadEq (Tape.write t c) (Tape.write tp c) := by
  obtain ⟨lp, rp, hlp, hrp, heq⟩ := h
  exact ⟨lp, rp, hlp, hrp, by rw [heq]; rfl⟩

theorem AllBlank.head_eq {c : TapeSymbol} {rest : List TapeSymbol}
    (h : AllBlank (c :: rest)) : c = TapeSymbol.blank :=
  h c List.mem_cons_self

theorem AllBlank.tail_of {c : TapeSymbol} {rest : List TapeSymbol}
    (h : AllBlank (c :: rest)) : AllBlank rest :=
  fun x hx => h x (List.mem_cons_of_mem _ hx)

/-- The load-bearing stability: a head move on the padded tape is the padded
head move.  When the true tape steps into fresh blanks, the padded one steps
into its padding — and reads blank there too, because the padding is
all-blank. -/
theorem PadEq.move {t tp : Tape} (h : PadEq t tp) (d : HeadMove) :
    PadEq (Tape.move t d) (Tape.move tp d) := by
  obtain ⟨lp, rp, hlp, hrp, heq⟩ := h
  subst heq
  cases t with
  | mk l hd r =>
      cases d with
      | stay => exact ⟨lp, rp, hlp, hrp, rfl⟩
      | right =>
          cases r with
          | cons r₀ rs =>
              exact ⟨lp, rp, hlp, hrp, rfl⟩
          | nil =>
              cases hrpc : rp with
              | nil => exact ⟨lp, [], hlp, AllBlank.nil, rfl⟩
              | cons p₀ rp' =>
                  subst hrpc
                  refine ⟨lp, rp', hlp, hrp.tail_of, ?_⟩
                  show (⟨hd :: (l ++ lp), p₀, rp'⟩ : Tape) = _
                  rw [hrp.head_eq]
                  rfl
      | left =>
          cases l with
          | cons x l' =>
              exact ⟨lp, rp, hlp, hrp, rfl⟩
          | nil =>
              cases hlpc : lp with
              | nil => exact ⟨[], rp, AllBlank.nil, hrp, rfl⟩
              | cons p₀ lp' =>
                  subst hlpc
                  refine ⟨lp', rp, hlp.tail_of, hrp, ?_⟩
                  show (⟨lp', p₀, hd :: (r ++ rp)⟩ : Tape) = _
                  rw [hlp.head_eq]
                  rfl


/-! ## The projection, computed -/

theorem trackOfSplit_eq (pick : Block → TapeSymbol) (pre : List Block)
    (cur : Block) (post : List Block) :
    trackOfSplit pick pre cur post =
      ⟨(pre.map pick).reverse, pick cur, post.map pick⟩ := by
  simp [trackOfSplit, trackTape, trackSyms, List.map_reverse]

/-- Reading at the split *is* reading the virtual head. -/
theorem trackOfSplit_head (pick : Block → TapeSymbol) (pre : List Block)
    (cur : Block) (post : List Block) :
    (trackOfSplit pick pre cur post).head = pick cur := rfl

/-! ## Own-side bridges: the five update results are write and move

Each update variant's block-level result projects, on its own track, to
exactly `Tape.write` — or `Tape.move ∘ Tape.write` — of the old projection.
No padding appears on the own side; the fresh blocks the edges materialise
carry precisely the blank the virtual zipper grows by. -/

theorem bridge_stay (side : TrackSide) (pre : List Block) (cur : Block)
    (post : List Block) (s : TapeSymbol) :
    trackOfSplit side.pick pre (setSymFlag side s true cur) post =
      Tape.write (trackOfSplit side.pick pre cur post) s := by
  simp [trackOfSplit_eq, Tape.write]

theorem bridge_right_mid (side : TrackSide) (pre : List Block) (cur : Block)
    (nxt : Block) (post : List Block) (s : TapeSymbol) :
    trackOfSplit side.pick (pre ++ [setSymFlag side s false cur])
        (setFlag side true nxt) post =
      Tape.move
        (Tape.write (trackOfSplit side.pick pre cur (nxt :: post)) s)
        HeadMove.right := by
  simp [trackOfSplit_eq, Tape.write, Tape.move]

theorem bridge_right_edge (side : TrackSide) (pre : List Block) (cur : Block)
    (s : TapeSymbol) :
    trackOfSplit side.pick (pre ++ [setSymFlag side s false cur])
        (freshFlagged side) [] =
      Tape.move
        (Tape.write (trackOfSplit side.pick pre cur []) s)
        HeadMove.right := by
  simp [trackOfSplit_eq, Tape.write, Tape.move]

theorem bridge_left_mid (side : TrackSide) (pre : List Block) (prv : Block)
    (cur : Block) (post : List Block) (s : TapeSymbol) :
    trackOfSplit side.pick pre (setFlag side true prv)
        (setSymFlag side s false cur :: post) =
      Tape.move
        (Tape.write (trackOfSplit side.pick (pre ++ [prv]) cur post) s)
        HeadMove.left := by
  simp [trackOfSplit_eq, Tape.write, Tape.move]

theorem bridge_left_edge (side : TrackSide) (cur : Block)
    (post : List Block) (s : TapeSymbol) :
    trackOfSplit side.pick [] (freshFlagged side)
        (setSymFlag side s false cur :: post) =
      Tape.move
        (Tape.write (trackOfSplit side.pick [] cur post) s)
        HeadMove.left := by
  simp [trackOfSplit_eq, Tape.write, Tape.move]

/-! ## Own-side splits survive -/

theorem splitAtFlag_stay (side : TrackSide) {blocks pre cur post}
    (h : SplitAtFlag side blocks pre cur post) (s : TapeSymbol) :
    SplitAtFlag side (pre ++ setSymFlag side s true cur :: post)
      pre (setSymFlag side s true cur) post :=
  ⟨rfl, h.preClear, by simp, h.postClear⟩

theorem splitAtFlag_right_mid (side : TrackSide) {blocks pre cur nxt post}
    (h : SplitAtFlag side blocks pre cur (nxt :: post)) (s : TapeSymbol) :
    SplitAtFlag side
      (pre ++ setSymFlag side s false cur :: setFlag side true nxt :: post)
      (pre ++ [setSymFlag side s false cur]) (setFlag side true nxt) post := by
  refine ⟨by simp, ?_, by simp, ?_⟩
  · intro b hb
    rcases List.mem_append.mp hb with hb | hb
    · exact h.preClear b hb
    · rcases List.mem_singleton.mp hb with rfl
      simp
  · intro b hb
    exact h.postClear b (List.mem_cons_of_mem _ hb)

theorem splitAtFlag_right_edge (side : TrackSide) {blocks pre cur}
    (h : SplitAtFlag side blocks pre cur []) (s : TapeSymbol) :
    SplitAtFlag side
      (pre ++ [setSymFlag side s false cur, freshFlagged side])
      (pre ++ [setSymFlag side s false cur]) (freshFlagged side) [] := by
  refine ⟨by simp, ?_, by simp, ?_⟩
  · intro b hb
    rcases List.mem_append.mp hb with hb | hb
    · exact h.preClear b hb
    · rcases List.mem_singleton.mp hb with rfl
      simp
  · intro b hb
    simp at hb

theorem splitAtFlag_left_mid (side : TrackSide) {blocks pre prv cur post}
    (h : SplitAtFlag side blocks (pre ++ [prv]) cur post) (s : TapeSymbol) :
    SplitAtFlag side
      (pre ++ setFlag side true prv :: setSymFlag side s false cur :: post)
      pre (setFlag side true prv) (setSymFlag side s false cur :: post) := by
  refine ⟨by simp, ?_, by simp, ?_⟩
  · intro b hb
    exact h.preClear b (List.mem_append.mpr (Or.inl hb))
  · intro b hb
    rcases List.mem_cons.mp hb with rfl | hb
    · simp
    · exact h.postClear b hb

theorem splitAtFlag_left_edge (side : TrackSide) {blocks cur post}
    (h : SplitAtFlag side blocks [] cur post) (s : TapeSymbol) :
    SplitAtFlag side
      (freshFlagged side :: setSymFlag side s false cur :: post)
      [] (freshFlagged side) (setSymFlag side s false cur :: post) := by
  refine ⟨rfl, ?_, by simp, ?_⟩
  · intro b hb
    simp at hb
  · intro b hb
    rcases List.mem_cons.mp hb with rfl | hb
    · simp
    · exact h.postClear b hb


/-! ## Cross-side transfer

An update on one track must not disturb the other.  For the equal-length
variants the result is pointwise other-side-equal, so the other split
transfers positionally; the edge variants append or prepend one fresh block,
which the other side absorbs as end-padding.  `trackRel` is the pointwise
relation; `Forall₂` carries it through the list structure. -/

def trackRel (side : TrackSide) (b b' : Block) : Prop :=
  side.pick b' = side.pick b ∧ side.getFlag b' = side.getFlag b

theorem trackRel_refl (side : TrackSide) (b : Block) : trackRel side b b :=
  ⟨rfl, rfl⟩

theorem forall₂_trackRel_refl (side : TrackSide) (l : List Block) :
    List.Forall₂ (trackRel side) l l :=
  List.forall₂_same.mpr (fun b _ => trackRel_refl side b)

theorem forall₂_map_eq {side : TrackSide} :
    ∀ {l l' : List Block}, List.Forall₂ (trackRel side) l l' →
      l'.map side.pick = l.map side.pick := by
  intro l l' h
  induction h with
  | nil => rfl
  | cons hr _ ih => simp [ih, hr.1]

theorem forall₂_flagClear {side : TrackSide} :
    ∀ {l l' : List Block}, List.Forall₂ (trackRel side) l l' →
      (∀ b ∈ l, side.getFlag b = false) →
      ∀ b' ∈ l', side.getFlag b' = false := by
  intro l l' h
  induction h with
  | nil => intro _ b' hb'; simp at hb'
  | @cons a a' as as' hr _ ih =>
      intro hclear b' hb'
      rcases List.mem_cons.mp hb' with rfl | hb'
      · rw [hr.2]
        exact hclear a List.mem_cons_self
      · exact ih (fun b hb => hclear b (List.mem_cons_of_mem _ hb)) b' hb'

theorem forall₂_append_left {α β : Type} {R : α → β → Prop} :
    ∀ {l₁ l₂ : List α} {u : List β}, List.Forall₂ R (l₁ ++ l₂) u →
      ∃ u₁ u₂, u = u₁ ++ u₂ ∧ List.Forall₂ R l₁ u₁ ∧ List.Forall₂ R l₂ u₂ := by
  intro l₁
  induction l₁ with
  | nil =>
      intro l₂ u h
      exact ⟨[], u, rfl, List.Forall₂.nil, h⟩
  | cons a as ih =>
      intro l₂ u h
      rw [List.cons_append] at h
      obtain ⟨b, u', hab, h', rfl⟩ := List.forall₂_cons_left_iff.mp h
      obtain ⟨u₁, u₂, rfl, h₁, h₂⟩ := ih h'
      exact ⟨b :: u₁, u₂, rfl, List.Forall₂.cons hab h₁, h₂⟩

/-- A split transfers along a pointwise-related list, projection intact. -/
theorem SplitAtFlag.transfer {side : TrackSide} {blocks blocks' : List Block}
    {pre post : List Block} {cur : Block}
    (h : SplitAtFlag side blocks pre cur post)
    (hf : List.Forall₂ (trackRel side) blocks blocks') :
    ∃ pre' cur' post', SplitAtFlag side blocks' pre' cur' post' ∧
      trackOfSplit side.pick pre' cur' post' =
        trackOfSplit side.pick pre cur post := by
  rw [h.eq] at hf
  obtain ⟨pre', rest, hb', hfpre, hfrest⟩ := forall₂_append_left hf
  obtain ⟨cur', post', hrcur, hfpost, hrest⟩ :=
    List.forall₂_cons_left_iff.mp hfrest
  refine ⟨pre', cur', post', ⟨by rw [hb', hrest], ?_, ?_, ?_⟩, ?_⟩
  · exact forall₂_flagClear hfpre h.preClear
  · rw [hrcur.2, h.curSet]
  · exact forall₂_flagClear hfpost h.postClear
  · rw [trackOfSplit_eq, trackOfSplit_eq, forall₂_map_eq hfpre,
      forall₂_map_eq hfpost, hrcur.1]

/-! ## End-extension of a split -/

theorem SplitAtFlag.snoc {side : TrackSide} {blocks pre cur post}
    (h : SplitAtFlag side blocks pre cur post) {b₀ : Block}
    (hflag : side.getFlag b₀ = false) :
    SplitAtFlag side (blocks ++ [b₀]) pre cur (post ++ [b₀]) := by
  refine ⟨by rw [h.eq]; simp, h.preClear, h.curSet, ?_⟩
  intro b hb
  rcases List.mem_append.mp hb with hb | hb
  · exact h.postClear b hb
  · rcases List.mem_singleton.mp hb with rfl
    exact hflag

theorem SplitAtFlag.cons {side : TrackSide} {blocks pre cur post}
    (h : SplitAtFlag side blocks pre cur post) {b₀ : Block}
    (hflag : side.getFlag b₀ = false) :
    SplitAtFlag side (b₀ :: blocks) (b₀ :: pre) cur post := by
  refine ⟨by rw [h.eq]; rfl, ?_, h.curSet, h.postClear⟩
  intro b hb
  rcases List.mem_cons.mp hb with rfl | hb
  · exact hflag
  · exact h.preClear b hb

theorem trackOfSplit_snoc (pick : Block → TapeSymbol) (pre : List Block)
    (cur : Block) (post : List Block) (b₀ : Block) :
    trackOfSplit pick pre cur (post ++ [b₀]) =
      ⟨(trackOfSplit pick pre cur post).left,
        (trackOfSplit pick pre cur post).head,
        (trackOfSplit pick pre cur post).right ++ [pick b₀]⟩ := by
  simp [trackOfSplit_eq]

theorem trackOfSplit_cons (pick : Block → TapeSymbol) (pre : List Block)
    (cur : Block) (post : List Block) (b₀ : Block) :
    trackOfSplit pick (b₀ :: pre) cur post =
      ⟨(trackOfSplit pick pre cur post).left ++ [pick b₀],
        (trackOfSplit pick pre cur post).head,
        (trackOfSplit pick pre cur post).right⟩ := by
  simp [trackOfSplit_eq]

/-! ## Padding composes -/

theorem PadEq.pad_right {t tp : Tape} (h : PadEq t tp) {c : TapeSymbol}
    (hc : c = TapeSymbol.blank) :
    PadEq t ⟨tp.left, tp.head, tp.right ++ [c]⟩ := by
  obtain ⟨lp, rp, hlp, hrp, heq⟩ := h
  refine ⟨lp, rp ++ [c], hlp, ?_, ?_⟩
  · intro x hx
    rcases List.mem_append.mp hx with hx | hx
    · exact hrp x hx
    · rcases List.mem_singleton.mp hx with rfl
      exact hc
  · rw [heq]
    simp

theorem PadEq.pad_left {t tp : Tape} (h : PadEq t tp) {c : TapeSymbol}
    (hc : c = TapeSymbol.blank) :
    PadEq t ⟨tp.left ++ [c], tp.head, tp.right⟩ := by
  obtain ⟨lp, rp, hlp, hrp, heq⟩ := h
  refine ⟨lp ++ [c], rp, ?_, hrp, ?_⟩
  · intro x hx
    rcases List.mem_append.mp hx with hx | hx
    · exact hlp x hx
    · rcases List.mem_singleton.mp hx with rfl
      exact hc
  · rw [heq]
    simp

/-! ## The pair invariant -/

instance : DecidableEq TrackSide := fun a b => by
  cases a <;> cases b <;> first
    | exact isTrue rfl
    | exact isFalse (by intro h; cases h)

/-- Two splits at the same side's unique flag coincide. -/
theorem split_flag_unique {side : TrackSide} :
    ∀ (pre₁ : List Block) {cur₁ : Block} {post₁ : List Block}
      (pre₂ : List Block) {cur₂ : Block} {post₂ : List Block},
      pre₁ ++ cur₁ :: post₁ = pre₂ ++ cur₂ :: post₂ →
      (∀ b ∈ pre₁, side.getFlag b = false) → side.getFlag cur₁ = true →
      (∀ b ∈ pre₂, side.getFlag b = false) → side.getFlag cur₂ = true →
      pre₁ = pre₂ ∧ cur₁ = cur₂ ∧ post₁ = post₂ := by
  intro pre₁
  induction pre₁ with
  | nil =>
      intro cur₁ post₁ pre₂ cur₂ post₂ he h1p h1c h2p h2c
      cases pre₂ with
      | nil =>
          rw [List.nil_append, List.nil_append] at he
          injection he with h₁ h₂
          exact ⟨rfl, h₁, h₂⟩
      | cons x xs =>
          rw [List.nil_append, List.cons_append] at he
          injection he with h₁ h₂
          exfalso
          have hx : side.getFlag x = false := h2p x List.mem_cons_self
          rw [← h₁, h1c] at hx
          exact Bool.noConfusion hx
  | cons y ys ih =>
      intro cur₁ post₁ pre₂ cur₂ post₂ he h1p h1c h2p h2c
      cases pre₂ with
      | nil =>
          rw [List.cons_append, List.nil_append] at he
          injection he with h₁ h₂
          exfalso
          have hy : side.getFlag y = false := h1p y List.mem_cons_self
          rw [h₁, h2c] at hy
          exact Bool.noConfusion hy
      | cons x xs =>
          rw [List.cons_append, List.cons_append] at he
          injection he with h₁ h₂
          obtain ⟨hp, hc, hpo⟩ := ih xs h₂
            (fun b hb => h1p b (List.mem_cons_of_mem _ hb)) h1c
            (fun b hb => h2p b (List.mem_cons_of_mem _ hb)) h2c
          exact ⟨by rw [h₁, hp], hc, hpo⟩

theorem SplitAtFlag.unique {side : TrackSide} {blocks : List Block}
    {pre₁ pre₂ : List Block} {cur₁ cur₂ : Block} {post₁ post₂ : List Block}
    (h₁ : SplitAtFlag side blocks pre₁ cur₁ post₁)
    (h₂ : SplitAtFlag side blocks pre₂ cur₂ post₂) :
    pre₁ = pre₂ ∧ cur₁ = cur₂ ∧ post₁ = post₂ :=
  split_flag_unique pre₁ pre₂ (by rw [← h₁.eq, ← h₂.eq])
    h₁.preClear h₁.curSet h₂.preClear h₂.curSet

/-- The hosted region carries a virtual tape per track, each up to
end-padding. -/
def HostsPair (blocks : List Block) (t : TrackSide → Tape) : Prop :=
  ∀ side, ∃ pre cur post, SplitAtFlag side blocks pre cur post ∧
    PadEq (t side) (trackOfSplit side.pick pre cur post)

/-- Reading the flagged block reads the virtual head, on either track. -/
theorem HostsPair.head_eq {blocks t} (h : HostsPair blocks t)
    (side : TrackSide) {pre cur post}
    (hsplit : SplitAtFlag side blocks pre cur post) :
    side.pick cur = (t side).head := by
  obtain ⟨pre', cur', post', hsplit', hpad⟩ := h side
  obtain ⟨hpre, hcur, hpost⟩ := hsplit.unique hsplit'
  subst hcur
  have := hpad.head_eq
  rw [trackOfSplit_head] at this
  exact this


theorem TrackSide.eq_other_of_ne {side side' : TrackSide} (h : side' ≠ side) :
    side' = side.other := by
  cases side <;> cases side' <;> first | rfl | exact absurd rfl h

/-- Cross-side survival along any pointwise-related result. -/
theorem HostsPair.cross {blocks blocks' : List Block} {t : TrackSide → Tape}
    (h : HostsPair blocks t) (side' : TrackSide)
    (hforall : List.Forall₂ (trackRel side') blocks blocks') :
    ∃ pre' cur' post', SplitAtFlag side' blocks' pre' cur' post' ∧
      PadEq (t side') (trackOfSplit side'.pick pre' cur' post') := by
  obtain ⟨pre₀, cur₀, post₀, hsp₀, hpad₀⟩ := h side'
  obtain ⟨pre', cur', post', hsp', hproj⟩ := hsp₀.transfer hforall
  exact ⟨pre', cur', post', hsp', hproj ▸ hpad₀⟩

/-! ## The five preservation theorems -/

theorem HostsPair.update_stay {blocks : List Block} {t : TrackSide → Tape}
    (h : HostsPair blocks t) (side : TrackSide)
    {pre : List Block} {cur : Block} {post : List Block}
    (hsplit : SplitAtFlag side blocks pre cur post) (s : TapeSymbol) :
    HostsPair (pre ++ setSymFlag side s true cur :: post)
      (Function.update t side (Tape.write (t side) s)) := by
  intro side'
  by_cases hss : side' = side
  · subst hss
    refine ⟨pre, setSymFlag side' s true cur, post,
      splitAtFlag_stay side' hsplit s, ?_⟩
    rw [Function.update_self, bridge_stay]
    obtain ⟨pre₀, cur₀, post₀, hsp₀, hpad₀⟩ := h side'
    obtain ⟨rfl, rfl, rfl⟩ := hsplit.unique hsp₀
    exact hpad₀.write s
  · have hother := TrackSide.eq_other_of_ne hss
    have hforall : List.Forall₂ (trackRel side') blocks
        (pre ++ setSymFlag side s true cur :: post) := by
      rw [hsplit.eq]
      refine List.rel_append (forall₂_trackRel_refl side' pre)
        (List.Forall₂.cons ?_ (forall₂_trackRel_refl side' post))
      subst hother
      exact ⟨pick_setSymFlag_other side s true cur,
        getFlag_setSymFlag_other side s true cur⟩
    obtain ⟨pre', cur', post', hsp', hpad'⟩ := h.cross side' hforall
    rw [Function.update_of_ne hss]
    exact ⟨pre', cur', post', hsp', hpad'⟩

theorem HostsPair.update_right_mid {blocks : List Block} {t : TrackSide → Tape}
    (h : HostsPair blocks t) (side : TrackSide)
    {pre : List Block} {cur nxt : Block} {post : List Block}
    (hsplit : SplitAtFlag side blocks pre cur (nxt :: post)) (s : TapeSymbol) :
    HostsPair
      (pre ++ setSymFlag side s false cur :: setFlag side true nxt :: post)
      (Function.update t side
        (Tape.move (Tape.write (t side) s) HeadMove.right)) := by
  intro side'
  by_cases hss : side' = side
  · subst hss
    refine ⟨pre ++ [setSymFlag side' s false cur], setFlag side' true nxt,
      post, splitAtFlag_right_mid side' hsplit s, ?_⟩
    rw [Function.update_self, bridge_right_mid]
    obtain ⟨pre₀, cur₀, post₀, hsp₀, hpad₀⟩ := h side'
    obtain ⟨rfl, rfl, rfl⟩ := hsplit.unique hsp₀
    exact (hpad₀.write s).move HeadMove.right
  · have hother := TrackSide.eq_other_of_ne hss
    have hforall : List.Forall₂ (trackRel side') blocks
        (pre ++ setSymFlag side s false cur ::
          setFlag side true nxt :: post) := by
      rw [hsplit.eq]
      refine List.rel_append (forall₂_trackRel_refl side' pre)
        (List.Forall₂.cons ?_ (List.Forall₂.cons ?_
          (forall₂_trackRel_refl side' post)))
      · subst hother
        exact ⟨pick_setSymFlag_other side s false cur,
          getFlag_setSymFlag_other side s false cur⟩
      · exact ⟨pick_setFlag side side' true nxt, by
          subst hother
          exact getFlag_setFlag_other side true nxt⟩
    obtain ⟨pre', cur', post', hsp', hpad'⟩ := h.cross side' hforall
    rw [Function.update_of_ne hss]
    exact ⟨pre', cur', post', hsp', hpad'⟩

theorem HostsPair.update_right_edge {blocks : List Block}
    {t : TrackSide → Tape} (h : HostsPair blocks t) (side : TrackSide)
    {pre : List Block} {cur : Block}
    (hsplit : SplitAtFlag side blocks pre cur []) (s : TapeSymbol) :
    HostsPair (pre ++ [setSymFlag side s false cur, freshFlagged side])
      (Function.update t side
        (Tape.move (Tape.write (t side) s) HeadMove.right)) := by
  intro side'
  by_cases hss : side' = side
  · subst hss
    refine ⟨pre ++ [setSymFlag side' s false cur], freshFlagged side', [],
      splitAtFlag_right_edge side' hsplit s, ?_⟩
    rw [Function.update_self, bridge_right_edge]
    obtain ⟨pre₀, cur₀, post₀, hsp₀, hpad₀⟩ := h side'
    obtain ⟨rfl, rfl, rfl⟩ := hsplit.unique hsp₀
    exact (hpad₀.write s).move HeadMove.right
  · have hother := TrackSide.eq_other_of_ne hss
    have hforall : List.Forall₂ (trackRel side') blocks
        (pre ++ [setSymFlag side s false cur]) := by
      rw [hsplit.eq]
      refine List.rel_append (forall₂_trackRel_refl side' pre)
        (List.Forall₂.cons ?_ List.Forall₂.nil)
      subst hother
      exact ⟨pick_setSymFlag_other side s false cur,
        getFlag_setSymFlag_other side s false cur⟩
    obtain ⟨pre', cur', post', hsp', hpad'⟩ := h.cross side' hforall
    rw [Function.update_of_ne hss]
    have hsnoc := hsp'.snoc (b₀ := freshFlagged side) (by
      subst hother
      exact getFlag_freshFlagged_other side)
    have hblocks : pre ++ [setSymFlag side s false cur, freshFlagged side] =
        (pre ++ [setSymFlag side s false cur]) ++ [freshFlagged side] := by
      simp
    rw [hblocks]
    refine ⟨pre', cur', post' ++ [freshFlagged side], hsnoc, ?_⟩
    rw [trackOfSplit_snoc]
    exact hpad'.pad_right (by
      subst hother
      exact pick_freshFlagged_other side)

theorem HostsPair.update_left_mid {blocks : List Block} {t : TrackSide → Tape}
    (h : HostsPair blocks t) (side : TrackSide)
    {pre : List Block} {prv cur : Block} {post : List Block}
    (hsplit : SplitAtFlag side blocks (pre ++ [prv]) cur post)
    (s : TapeSymbol) :
    HostsPair
      (pre ++ setFlag side true prv :: setSymFlag side s false cur :: post)
      (Function.update t side
        (Tape.move (Tape.write (t side) s) HeadMove.left)) := by
  intro side'
  by_cases hss : side' = side
  · subst hss
    refine ⟨pre, setFlag side' true prv,
      setSymFlag side' s false cur :: post,
      splitAtFlag_left_mid side' hsplit s, ?_⟩
    rw [Function.update_self, bridge_left_mid]
    obtain ⟨pre₀, cur₀, post₀, hsp₀, hpad₀⟩ := h side'
    obtain ⟨rfl, rfl, rfl⟩ := hsplit.unique hsp₀
    exact (hpad₀.write s).move HeadMove.left
  · have hother := TrackSide.eq_other_of_ne hss
    have hforall : List.Forall₂ (trackRel side') blocks
        (pre ++ setFlag side true prv ::
          setSymFlag side s false cur :: post) := by
      have heq : blocks = pre ++ prv :: cur :: post := by
        rw [hsplit.eq]
        simp
      rw [heq]
      refine List.rel_append (forall₂_trackRel_refl side' pre)
        (List.Forall₂.cons ?_ (List.Forall₂.cons ?_
          (forall₂_trackRel_refl side' post)))
      · exact ⟨pick_setFlag side side' true prv, by
          subst hother
          exact getFlag_setFlag_other side true prv⟩
      · subst hother
        exact ⟨pick_setSymFlag_other side s false cur,
          getFlag_setSymFlag_other side s false cur⟩
    obtain ⟨pre', cur', post', hsp', hpad'⟩ := h.cross side' hforall
    rw [Function.update_of_ne hss]
    exact ⟨pre', cur', post', hsp', hpad'⟩

theorem HostsPair.update_left_edge {blocks : List Block}
    {t : TrackSide → Tape} (h : HostsPair blocks t) (side : TrackSide)
    {cur : Block} {post : List Block}
    (hsplit : SplitAtFlag side blocks [] cur post) (s : TapeSymbol) :
    HostsPair (freshFlagged side :: setSymFlag side s false cur :: post)
      (Function.update t side
        (Tape.move (Tape.write (t side) s) HeadMove.left)) := by
  intro side'
  by_cases hss : side' = side
  · subst hss
    refine ⟨[], freshFlagged side', setSymFlag side' s false cur :: post,
      splitAtFlag_left_edge side' hsplit s, ?_⟩
    rw [Function.update_self, bridge_left_edge]
    obtain ⟨pre₀, cur₀, post₀, hsp₀, hpad₀⟩ := h side'
    obtain ⟨rfl, rfl, rfl⟩ := hsplit.unique hsp₀
    exact (hpad₀.write s).move HeadMove.left
  · have hother := TrackSide.eq_other_of_ne hss
    have hforall : List.Forall₂ (trackRel side') blocks
        (setSymFlag side s false cur :: post) := by
      have heq : blocks = cur :: post := by
        rw [hsplit.eq]
        rfl
      rw [heq]
      refine List.Forall₂.cons ?_ (forall₂_trackRel_refl side' post)
      subst hother
      exact ⟨pick_setSymFlag_other side s false cur,
        getFlag_setSymFlag_other side s false cur⟩
    obtain ⟨pre', cur', post', hsp', hpad'⟩ := h.cross side' hforall
    rw [Function.update_of_ne hss]
    have hcons := hsp'.cons (b₀ := freshFlagged side) (by
      subst hother
      exact getFlag_freshFlagged_other side)
    refine ⟨freshFlagged side :: pre', cur', post', hcons, ?_⟩
    rw [trackOfSplit_cons]
    exact hpad'.pad_left (by
      subst hother
      exact pick_freshFlagged_other side)

end SipserGacsLautemann
Source
Simulation invariant for two-track hosting of multitape Turing-machine tapes, specialized to the model of Def_sipser_gacs_lautemann; builds on Def_sgl_track_update and 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