The merge invariant: PadEq and the five preservations
Definitionsgl_merge_invariantThe 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.
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