The track update: write and flag-move, fully specified
Definitionsgl_track_updateThe track update, complete: module D's summit.
updateTrack side i s mv performs one full surgical update on a hosted track: from the parked position, walk to the flagged block, write symbol there, move the track's head-flag per , and return to the parked position. Its three specifications — updateTrack_stay, updateTrack_right, updateTrack_left — each give an exact halting time and the exact final tapes:
where newBlocks rewrites the flagged block and relocates the flag — onto the same block, the next (materialising a fresh block at the right edge), or the previous (materialising one before the region's start, which relocates the park itself). The ghost parameter — all-blank residue beyond the region from earlier excursions — is carried through every specification, growing as the head explores.
One machine, all cases. The variants differ only in data — window contents and retreat distances — never in shape, so the state type is independent of side and mv and the simulation can dispatch on runtime data without type trouble. There is no runtime edge test anywhere: the normalising window materialises a fresh block by exactly the six operations that leave an existing one intact.
Proof structure. Each specification is a chain of seven junctions — enter, walk, retreat, symbol window, reposition, flag window, park — composed by chainStep, which propagates a piece's halt and final tapes through andThen in one application. The junction tapes are explicit cellsTape values; the only case analyses are the genuine ones (does a neighbouring block exist), handled as list-shape splits in the proof, never as tests in the machine.
With this module the low-level plumbing for merge_empty_scratch_tapes is complete: what remains is the simulation invariant and the per-step program (module E), which consume these specifications without touching step or run again.
import Definitions.Def_sgl_patch_run
set_option maxHeartbeats 4000000
/-!
# The track update
Module D of the merge_empty plan, final part. `updateTrack side i s mv` writes
symbol `s` at the flagged block of a track and moves the flag per `mv`, from
the parked position back to the parked position.
**One machine, all cases.** The variants differ only in *data* — which cells
the two patch windows write and how far the head retreats between them — never
in shape, so the machine's state type is independent of `side` and `mv` and the
simulation can dispatch on runtime data without type trouble. In particular
there is no runtime edge test anywhere: a normalising window materialises a
fresh block out of raw tape by exactly the same six operations that leave an
existing block intact.
-/
namespace SipserGacsLautemann
variable {tapes : Nat}
/-! ## Ghost blanks and the parked form -/
def AllBlank (G : List TapeSymbol) : Prop := ∀ c ∈ G, c = TapeSymbol.blank
theorem AllBlank.nil : AllBlank [] := by intro c hc; simp at hc
theorem AllBlank.single : AllBlank [TapeSymbol.blank] := by
intro c hc; simpa using hc
/-- The region between simulated steps: head parked on the blank left of the
blocks, ghost blanks `G` beyond the region from earlier excursions. -/
def ParkedTape (blocks : List Block) (G : List TapeSymbol) : Tape :=
cellsTape [] (TapeSymbol.blank :: (encodeBlocks blocks ++ G))
/-! ## Retreats with ghost accounting -/
theorem encodeBlocks_eq_nil {post : List Block}
(h : encodeBlocks post = []) : post = [] := by
cases post with
| nil => rfl
| cons b bs =>
rw [encodeBlocks_cons] at h
simp [Block.toCells] at h
/-- Retreating over `cs` when a block region and ghost lie ahead: the result is
the same shape with a possibly-grown ghost. -/
theorem retreat_block (cs L : List TapeSymbol) (post : List Block)
(G : List TapeSymbol) (hG : AllBlank G) :
∃ G', AllBlank G' ∧
(moveDir HeadMove.left)^[cs.length]
(cellsTape (cs ++ L) (encodeBlocks post ++ G)) =
cellsTape L (cs.reverse ++ (encodeBlocks post ++ G')) := by
cases hR : encodeBlocks post ++ G with
| nil =>
have h2 := List.append_eq_nil_iff.mp hR
have hpost : post = [] := encodeBlocks_eq_nil h2.1
subst hpost
refine ⟨[TapeSymbol.blank], AllBlank.single, ?_⟩
simp only [encodeBlocks_nil, List.nil_append]
exact cellsTape_retreat_end cs L
| cons r rs =>
refine ⟨G, hG, ?_⟩
rw [hR, cellsTape_retreat]
/-- Retreating past the left end of the used tape materialises blanks. -/
theorem cellsTape_retreat_past (k : Nat) (r : TapeSymbol)
(R : List TapeSymbol) :
(moveDir HeadMove.left)^[k] (cellsTape [] (r :: R)) =
cellsTape [] (List.replicate k TapeSymbol.blank ++ r :: R) := by
induction k with
| zero => simp
| succ k ih =>
rw [Function.iterate_succ_apply']
rw [ih]
cases k with
| zero =>
show moveDir HeadMove.left (cellsTape [] (r :: R)) = _
rfl
| succ k =>
show moveDir HeadMove.left
(cellsTape [] (TapeSymbol.blank :: _)) = _
rfl
/-- Retreat with nothing beyond the run on the left. -/
theorem cellsTape_retreat_nilL (cs : List TapeSymbol) (r : TapeSymbol)
(R : List TapeSymbol) :
(moveDir HeadMove.left)^[cs.length] (cellsTape cs (r :: R)) =
cellsTape [] (cs.reverse ++ r :: R) := by
have h := cellsTape_retreat cs [] R r
rwa [List.append_nil] at h
/-! ## Chaining -/
/-- One junction of an update chain: compose a piece's halt and tapes with the
rest's, producing the composite's. -/
theorem chainStep {S₁ S₂ : Type} {M₁ : TypedMachine tapes S₁}
{M₂ : TypedMachine tapes S₂} {T T' Tfin : Fin tapes → Tape}
{a : Nat} {b : Bool} {k : Nat} {v : Bool}
(h₁ : HaltsExactly M₁ (M₁.startCfg T) a b)
(htp : ((M₁.step^[a]) (M₁.startCfg T)).tape = T')
(h₂ : HaltsExactly M₂ (M₂.startCfg T') k v)
(h₂tp : ((M₂.step^[k]) (M₂.startCfg T')).tape = Tfin) :
HaltsExactly (M₁.andThen fun _ => M₂)
((M₁.andThen fun _ => M₂).startCfg T) (a + 1 + k) v ∧
(((M₁.andThen fun _ => M₂).step^[a + 1 + k])
((M₁.andThen fun _ => M₂).startCfg T)).tape = Tfin := by
have h := HaltsExactly.andThen_full (M₂ := fun _ => M₂) h₁
(by rw [htp]; exact h₂)
have hcfg : (M₁.andThen fun _ => M₂).startCfg T =
TypedConfiguration.inLeft (M₁.startCfg T) := rfl
rw [hcfg]
refine ⟨h.1, ?_⟩
rw [h.2, htp, h₂tp]
/-! ## The windows -/
/-- Overwrite a track's symbol and flag; normalise (i.e. keep) the other
track's cells. -/
def symWindow (side : TrackSide) (s : TapeSymbol) (f : Bool) : List PatchOp :=
match side with
| .A => [.put (cellsOfSymbol s).1, .put (cellsOfSymbol s).2,
.put (TapeSymbol.bit f), .norm, .norm, .norm]
| .B => [.norm, .norm, .norm, .put (cellsOfSymbol s).1,
.put (cellsOfSymbol s).2, .put (TapeSymbol.bit f)]
/-- Raise a track's flag; keep everything else. Over raw tape this
materialises a fresh block whose symbols are written blanks. -/
def flagWindow (side : TrackSide) : List PatchOp :=
match side with
| .A => [.norm, .norm, .put (TapeSymbol.bit true), .norm, .norm, .norm]
| .B => [.norm, .norm, .norm, .norm, .norm, .put (TapeSymbol.bit true)]
/-- Keep all six cells. -/
def allNormWindow : List PatchOp := [.norm, .norm, .norm, .norm, .norm, .norm]
/-- Set a track's symbol and flag in a block. -/
def setSymFlag (side : TrackSide) (s : TapeSymbol) (f : Bool) (b : Block) :
Block :=
match side with
| .A => ⟨s, f, b.symB, b.flagB⟩
| .B => ⟨b.symA, b.flagA, s, f⟩
/-- Set a track's flag in a block. -/
def setFlag (side : TrackSide) (f : Bool) (b : Block) : Block :=
match side with
| .A => { b with flagA := f }
| .B => { b with flagB := f }
/-- The block a flag window materialises from raw tape. -/
def freshFlagged (side : TrackSide) : Block :=
match side with
| .A => ⟨TapeSymbol.blank, true, TapeSymbol.blank, false⟩
| .B => ⟨TapeSymbol.blank, false, TapeSymbol.blank, true⟩
@[simp] theorem normalizeSym_cell_fst (x : TapeSymbol) :
normalizeSym (cellsOfSymbol x).1 = (cellsOfSymbol x).1 := by
cases x with
| blank => rfl
| bit b => cases b <;> rfl
@[simp] theorem normalizeSym_cell_snd (x : TapeSymbol) :
normalizeSym (cellsOfSymbol x).2 = (cellsOfSymbol x).2 := by
cases x with
| blank => rfl
| bit b => cases b <;> rfl
/-! ## Window content lemmas -/
theorem patchCellsN_symWindow (side : TrackSide) (s : TapeSymbol) (f : Bool)
(b : Block) (R : List TapeSymbol) :
patchCellsN 6 (symWindow side s f) (Block.toCells b ++ R) =
Block.toCells (setSymFlag side s f b) := by
cases side <;>
simp [symWindow, Block.toCells, setSymFlag, patchCellsN, opValue]
theorem patchCellsN_flagWindow (side : TrackSide) (b : Block)
(R : List TapeSymbol) :
patchCellsN 6 (flagWindow side) (Block.toCells b ++ R) =
Block.toCells (setFlag side true b) := by
cases side <;>
simp [flagWindow, Block.toCells, setFlag, patchCellsN, opValue]
theorem patchCellsN_allNorm (b : Block) (R : List TapeSymbol) :
patchCellsN 6 allNormWindow (Block.toCells b ++ R) = Block.toCells b := by
simp [allNormWindow, Block.toCells, patchCellsN, opValue]
/-- A patch pass reads only what its length covers. -/
theorem patchCellsN_congr_prefix (n : Nat) :
∀ (ops : List PatchOp) (R R' : List TapeSymbol),
R.take n = R'.take n →
patchCellsN n ops R = patchCellsN n ops R' := by
induction n with
| zero => intro ops R R' _; rfl
| succ n ih =>
intro ops R R' h
cases R with
| nil =>
cases R' with
| nil => rfl
| cons r' rs' => simp at h
| cons r rs =>
cases R' with
| nil => simp at h
| cons r' rs' =>
rw [List.take_succ_cons, List.take_succ_cons] at h
injection h with hr ht
rw [patchCellsN_succ, patchCellsN_succ]
simp only [List.headD_cons, List.tail_cons]
rw [hr, ih ops.tail rs rs' ht]
/-- Over all-blank tape a pass writes its ops' blank-values: the fresh-block
case of the flag window. -/
theorem patchCellsN_allBlank (n : Nat) :
∀ (ops : List PatchOp) (R : List TapeSymbol), AllBlank R →
patchCellsN n ops R = patchCellsN n ops [] := by
induction n with
| zero => intro ops R _; rfl
| succ n ih =>
intro ops R hR
rw [patchCellsN_succ, patchCellsN_succ]
have hh : R.headD TapeSymbol.blank = TapeSymbol.blank := by
cases R with
| nil => rfl
| cons r rs => exact hR r List.mem_cons_self
have ht : AllBlank R.tail := by
intro c hc
cases R with
| nil => simp at hc
| cons r rs => exact hR c (List.mem_cons_of_mem _ hc)
rw [hh, ih ops.tail R.tail ht]
rfl
theorem patchCellsN_flagWindow_fresh (side : TrackSide)
(R : List TapeSymbol) (hR : AllBlank R) :
patchCellsN 6 (flagWindow side) R =
Block.toCells (freshFlagged side) := by
rw [patchCellsN_allBlank 6 (flagWindow side) R hR]
cases side <;> rfl
/-! ## The machine -/
def flagOf : HeadMove → Bool
| .stay => true
| _ => false
def retreatOf : HeadMove → Nat
| .stay => 6
| .right => 0
| .left => 12
def window2Of (side : TrackSide) : HeadMove → List PatchOp
| .stay => allNormWindow
| _ => flagWindow side
/-- The whole track update: enter, walk to the flag, retreat onto the flagged
block, rewrite it, reposition, patch the flag's destination, park. Data-only
dependence on `side` and `mv`. -/
def updateTrack (side : TrackSide) (i : Fin tapes) (s : TapeSymbol)
(mv : HeadMove) :=
(moveUpTo i 1 HeadMove.right).andThen fun _ =>
(walkToFlag side i).andThen fun _ =>
(moveUpTo i 6 HeadMove.left).andThen fun _ =>
(patchRun6 i (symWindow side s (flagOf mv))).andThen fun _ =>
(moveUpTo i (retreatOf mv) HeadMove.left).andThen fun _ =>
(patchRun6 i (window2Of side mv)).andThen fun _ =>
scanToBlank i HeadMove.left
/-- Head-move past the left end of everything. -/
theorem cellsTape_moveLeft_nilL (r : TapeSymbol) (R : List TapeSymbol) :
moveDir HeadMove.left (cellsTape [] (r :: R)) =
cellsTape [] (TapeSymbol.blank :: r :: R) := rfl
/-- `blankIndex` of an unbroken written run. -/
theorem blankIndex_all (W : List TapeSymbol)
(hW : ∀ c ∈ W, c ≠ TapeSymbol.blank) : blankIndex W = W.length := by
induction W with
| nil => rfl
| cons c cs ih =>
cases hc : c with
| blank => exact absurd hc (hW c List.mem_cons_self)
| bit b =>
simp only [blankIndex, List.length_cons]
rw [ih (fun x hx => hW x (List.mem_cons_of_mem _ hx))]
/-! ## The stay variant -/
theorem updateTrack_stay (side : TrackSide) (i : Fin tapes) (s : TapeSymbol)
(tape : Fin tapes → Tape) (mid : List Block) (cur : Block)
(post : List Block) (G : List TapeSymbol) (hG : AllBlank G)
(hmid : ∀ b ∈ mid, side.getFlag b = false)
(hcur : side.getFlag cur = true)
(hi : tape i = ParkedTape (mid ++ cur :: post) G) :
∃ (cost : Nat) (G' : List TapeSymbol), AllBlank G' ∧
HaltsExactly (updateTrack side i s HeadMove.stay)
((updateTrack side i s HeadMove.stay).startCfg tape) cost false ∧
(((updateTrack side i s HeadMove.stay).step^[cost])
((updateTrack side i s HeadMove.stay).startCfg tape)).tape =
Function.update tape i
(ParkedTape (mid ++ setSymFlag side s true cur :: post) G') := by
classical
-- shorthands
have hCl : (Block.toCells cur).length = 6 := Block.toCells_length cur
set newCur := setSymFlag side s true cur with hnewCur
-- ===== junction 1: enter =====
set T1 : Fin tapes → Tape := Function.update tape i
(cellsTape [TapeSymbol.blank]
(encodeBlocks (mid ++ cur :: post) ++ G)) with hT1
have htp1 : (((moveUpTo i 1 HeadMove.right).step^[1])
((moveUpTo i 1 HeadMove.right).startCfg tape)).tape = T1 := by
rw [moveUpTo_tape i 1 HeadMove.right (by omega) tape, hT1]
congr 1
rw [Function.iterate_one, hi, ParkedTape]
exact cellsTape_moveRight _ _ _
have hT1i : T1 i = cellsTape [TapeSymbol.blank]
(encodeBlocks (mid ++ cur :: post) ++ G) := by
rw [hT1]; simp
-- ===== junction 2: walk =====
obtain ⟨hw, -, hwt⟩ := walkToFlag_spec side i T1 [TapeSymbol.blank] G
mid cur post hmid hcur hT1i
set W1 := loopCost (fun _ => blockReadSteps) mid.length + blockReadSteps
with hW1
set T2 := scanTapesDir T1 i HeadMove.right (6 * (mid.length + 1)) with hT2
have hsplit : encodeBlocks (mid ++ cur :: post) =
encodeBlocks (mid ++ [cur]) ++ encodeBlocks post := by
rw [← encodeBlocks_append]
congr 1
simp
have hT2i : T2 i =
cellsTape ((encodeBlocks (mid ++ [cur])).reverse ++ [TapeSymbol.blank])
(encodeBlocks post ++ G) := by
rw [hT2, scanTapesDir_self, hT1i, hsplit, List.append_assoc,
show 6 * (mid.length + 1) = (encodeBlocks (mid ++ [cur])).length by
rw [encodeBlocks_length]; simp,
cellsTape_advance]
-- ===== junction 3: back onto the flagged block =====
obtain ⟨G₃, hG₃, hret3⟩ := retreat_block (Block.toCells cur).reverse
((encodeBlocks mid).reverse ++ [TapeSymbol.blank]) post G hG
set T3 := Function.update T2 i
(cellsTape ((encodeBlocks mid).reverse ++ [TapeSymbol.blank])
(Block.toCells cur ++ (encodeBlocks post ++ G₃))) with hT3
have htp3 : (((moveUpTo i 6 HeadMove.left).step^[6])
((moveUpTo i 6 HeadMove.left).startCfg T2)).tape = T3 := by
rw [moveUpTo_tape i 6 HeadMove.left (by omega) T2, hT3]
congr 1
rw [hT2i,
show (encodeBlocks (mid ++ [cur])).reverse ++ [TapeSymbol.blank] =
(Block.toCells cur).reverse ++
((encodeBlocks mid).reverse ++ [TapeSymbol.blank]) by
rw [encodeBlocks_append]
simp [List.reverse_append, encodeBlocks_cons],
show (6 : Nat) = ((Block.toCells cur).reverse).length by simp [hCl]]
rw [hret3, List.reverse_reverse]
have hT3i : T3 i = cellsTape
((encodeBlocks mid).reverse ++ [TapeSymbol.blank])
(Block.toCells cur ++ (encodeBlocks post ++ G₃)) := by
rw [hT3]; simp
-- ===== junction 4: rewrite the flagged block =====
set T4 := Function.update T3 i
(cellsTape ((Block.toCells newCur).reverse ++
((encodeBlocks mid).reverse ++ [TapeSymbol.blank]))
(encodeBlocks post ++ G₃)) with hT4
have htp4 : (((patchRun6 i (symWindow side s true)).step^[6])
((patchRun6 i (symWindow side s true)).startCfg T3)).tape = T4 := by
rw [patchRun6_tape i _ T3 _ _ hT3i, hT4]
congr 1
rw [patchCellsN_symWindow, ← hnewCur,
show (6 : Nat) = (Block.toCells cur).length from hCl.symm,
List.drop_left]
have hT4i : T4 i = cellsTape
((Block.toCells newCur).reverse ++
((encodeBlocks mid).reverse ++ [TapeSymbol.blank]))
(encodeBlocks post ++ G₃) := by
rw [hT4]; simp
-- ===== junction 5: retreat again (stay) =====
obtain ⟨G₅, hG₅, hret5⟩ := retreat_block (Block.toCells newCur).reverse
((encodeBlocks mid).reverse ++ [TapeSymbol.blank]) post G₃ hG₃
set T5 := Function.update T4 i
(cellsTape ((encodeBlocks mid).reverse ++ [TapeSymbol.blank])
(Block.toCells newCur ++ (encodeBlocks post ++ G₅))) with hT5
have htp5 : (((moveUpTo i 6 HeadMove.left).step^[6])
((moveUpTo i 6 HeadMove.left).startCfg T4)).tape = T5 := by
rw [moveUpTo_tape i 6 HeadMove.left (by omega) T4, hT5]
congr 1
rw [hT4i,
show (6 : Nat) = ((Block.toCells newCur).reverse).length by
simp [Block.toCells_length]]
rw [hret5, List.reverse_reverse]
have hT5i : T5 i = cellsTape
((encodeBlocks mid).reverse ++ [TapeSymbol.blank])
(Block.toCells newCur ++ (encodeBlocks post ++ G₅)) := by
rw [hT5]; simp
-- ===== junction 6: identity window =====
set T6 := Function.update T5 i
(cellsTape ((Block.toCells newCur).reverse ++
((encodeBlocks mid).reverse ++ [TapeSymbol.blank]))
(encodeBlocks post ++ G₅)) with hT6
have htp6 : (((patchRun6 i allNormWindow).step^[6])
((patchRun6 i allNormWindow).startCfg T5)).tape = T6 := by
rw [patchRun6_tape i _ T5 _ _ hT5i, hT6]
congr 1
rw [patchCellsN_allNorm,
show (6 : Nat) = (Block.toCells newCur).length from
(Block.toCells_length newCur).symm,
List.drop_left]
have hT6i : T6 i = cellsTape
((Block.toCells newCur).reverse ++
((encodeBlocks mid).reverse ++ [TapeSymbol.blank]))
(encodeBlocks post ++ G₅) := by
rw [hT6]; simp
-- ===== junction 7: park =====
set Wp := (Block.toCells newCur).reverse ++ (encodeBlocks mid).reverse
with hWp
have hassoc : (Block.toCells newCur).reverse ++
((encodeBlocks mid).reverse ++ [TapeSymbol.blank]) =
Wp ++ [TapeSymbol.blank] := by
rw [hWp, List.append_assoc]
have hWp_nb : ∀ c ∈ Wp, c ≠ TapeSymbol.blank := by
intro c hc
rw [hWp] at hc
rcases List.mem_append.mp hc with h | h
· exact Block.toCells_ne_blank _ c (List.mem_reverse.mp h)
· exact encodeBlocks_ne_blank _ c (List.mem_reverse.mp h)
obtain ⟨hlt', heq'⟩ := blank_scan_left_spec (Wp ++ [TapeSymbol.blank])
((encodeBlocks post ++ G₅).headD TapeSymbol.blank)
((encodeBlocks post ++ G₅).tail)
rw [blankIndex_written Wp [] hWp_nb] at hlt' heq'
have hlt : ∀ k, k < Wp.length →
((moveDir HeadMove.left)^[k + 1] (T6 i)).head ≠ TapeSymbol.blank := by
intro k hk
rw [hT6i, hassoc]
exact hlt' k hk
have heq : ((moveDir HeadMove.left)^[Wp.length + 1] (T6 i)).head =
TapeSymbol.blank := by
rw [hT6i, hassoc]
exact heq'
obtain ⟨G₇, hG₇, hret7⟩ := retreat_block Wp [TapeSymbol.blank] post G₅ hG₅
have hWrev : Wp.reverse = encodeBlocks mid ++ Block.toCells newCur := by
rw [hWp, List.reverse_append, List.reverse_reverse, List.reverse_reverse]
have hX7 : (moveDir HeadMove.left)^[Wp.length + 1] (T6 i) =
ParkedTape (mid ++ newCur :: post) G₇ := by
rw [Function.iterate_succ_apply', hT6i, hassoc, hret7]
obtain ⟨r, R', hcons⟩ : ∃ r R',
Wp.reverse ++ (encodeBlocks post ++ G₇) = r :: R' := by
rw [hWrev]
cases hx : encodeBlocks mid ++ Block.toCells newCur ++
(encodeBlocks post ++ G₇) with
| nil =>
exfalso
have := congrArg List.length hx
simp [Block.toCells] at this
| cons a as => exact ⟨a, as, rfl⟩
rw [hcons,
show ([TapeSymbol.blank] : List TapeSymbol) =
TapeSymbol.blank :: [] from rfl,
cellsTape_moveLeft, ← hcons, hWrev, ParkedTape]
have henc : encodeBlocks (mid ++ newCur :: post) =
encodeBlocks mid ++ (Block.toCells newCur ++ encodeBlocks post) := by
rw [encodeBlocks_append, encodeBlocks_cons]
rw [henc]
simp [List.append_assoc]
set T7 := Function.update T6 i (ParkedTape (mid ++ newCur :: post) G₇)
with hT7
have htp7 : (((scanToBlank i HeadMove.left).step^[Wp.length * 4 + 3])
((scanToBlank i HeadMove.left).startCfg T6)).tape = T7 := by
rw [scanToBlank_tape_of i HeadMove.left T6 Wp.length hlt heq, hT7]
show Function.update T6 i
((moveDir HeadMove.left)^[Wp.length + 1] (T6 i)) = _
rw [hX7]
have hP7 : HaltsExactly (scanToBlank i HeadMove.left)
((scanToBlank i HeadMove.left).startCfg T6) (Wp.length * 4 + 3)
false := scanToBlank_spec_of i HeadMove.left T6 Wp.length hlt heq
-- ===== assemble =====
have hC6 := chainStep (patchRun6_spec i allNormWindow T5 _ _ hT5i) htp6
hP7 htp7
have hC5 := chainStep (moveUpTo_spec i 6 HeadMove.left (by omega) T4) htp5
hC6.1 hC6.2
have hC4 := chainStep (patchRun6_spec i (symWindow side s true) T3 _ _ hT3i)
htp4 hC5.1 hC5.2
have hC3 := chainStep (moveUpTo_spec i 6 HeadMove.left (by omega) T2) htp3
hC4.1 hC4.2
have hC2 := chainStep hw hwt hC3.1 hC3.2
have hC1 := chainStep (moveUpTo_spec i 1 HeadMove.right (by omega) tape)
htp1 hC2.1 hC2.2
refine ⟨_, G₇, hG₇, hC1.1, ?_⟩
have hfin := hC1.2
rw [hT7, hT6, hT5, hT4, hT3, hT2, hT1] at hfin
simp only [scanTapesDir, Function.update_idem] at hfin
exact hfin
theorem AllBlank.drop {G : List TapeSymbol} (hG : AllBlank G) (n : Nat) :
AllBlank (G.drop n) :=
fun c hc => hG c (List.mem_of_mem_drop hc)
/-- The region a rightward flag-move produces: the flag lands on the next
block, or on a materialised fresh one at the region's end. -/
def rightResult (side : TrackSide) (mid : List Block) (newCur : Block) :
List Block → List Block
| nxt :: post' => mid ++ newCur :: setFlag side true nxt :: post'
| [] => mid ++ [newCur, freshFlagged side]
/-! ## The right variant -/
theorem updateTrack_right (side : TrackSide) (i : Fin tapes) (s : TapeSymbol)
(tape : Fin tapes → Tape) (mid : List Block) (cur : Block)
(post : List Block) (G : List TapeSymbol) (hG : AllBlank G)
(hmid : ∀ b ∈ mid, side.getFlag b = false)
(hcur : side.getFlag cur = true)
(hi : tape i = ParkedTape (mid ++ cur :: post) G) :
∃ (cost : Nat) (G' : List TapeSymbol), AllBlank G' ∧
HaltsExactly (updateTrack side i s HeadMove.right)
((updateTrack side i s HeadMove.right).startCfg tape) cost false ∧
(((updateTrack side i s HeadMove.right).step^[cost])
((updateTrack side i s HeadMove.right).startCfg tape)).tape =
Function.update tape i
(ParkedTape
(rightResult side mid (setSymFlag side s false cur) post) G') := by
classical
have hCl : (Block.toCells cur).length = 6 := Block.toCells_length cur
set newCur := setSymFlag side s false cur with hnewCur
-- ===== junctions 1-4: shared skeleton =====
set T1 : Fin tapes → Tape := Function.update tape i
(cellsTape [TapeSymbol.blank]
(encodeBlocks (mid ++ cur :: post) ++ G)) with hT1
have htp1 : (((moveUpTo i 1 HeadMove.right).step^[1])
((moveUpTo i 1 HeadMove.right).startCfg tape)).tape = T1 := by
rw [moveUpTo_tape i 1 HeadMove.right (by omega) tape, hT1]
congr 1
rw [Function.iterate_one, hi, ParkedTape]
exact cellsTape_moveRight _ _ _
have hT1i : T1 i = cellsTape [TapeSymbol.blank]
(encodeBlocks (mid ++ cur :: post) ++ G) := by
rw [hT1]; simp
obtain ⟨hw, -, hwt⟩ := walkToFlag_spec side i T1 [TapeSymbol.blank] G
mid cur post hmid hcur hT1i
set W1 := loopCost (fun _ => blockReadSteps) mid.length + blockReadSteps
with hW1
set T2 := scanTapesDir T1 i HeadMove.right (6 * (mid.length + 1)) with hT2
have hsplit : encodeBlocks (mid ++ cur :: post) =
encodeBlocks (mid ++ [cur]) ++ encodeBlocks post := by
rw [← encodeBlocks_append]
congr 1
simp
have hT2i : T2 i =
cellsTape ((encodeBlocks (mid ++ [cur])).reverse ++ [TapeSymbol.blank])
(encodeBlocks post ++ G) := by
rw [hT2, scanTapesDir_self, hT1i, hsplit, List.append_assoc,
show 6 * (mid.length + 1) = (encodeBlocks (mid ++ [cur])).length by
rw [encodeBlocks_length]; simp,
cellsTape_advance]
obtain ⟨G₃, hG₃, hret3⟩ := retreat_block (Block.toCells cur).reverse
((encodeBlocks mid).reverse ++ [TapeSymbol.blank]) post G hG
set T3 := Function.update T2 i
(cellsTape ((encodeBlocks mid).reverse ++ [TapeSymbol.blank])
(Block.toCells cur ++ (encodeBlocks post ++ G₃))) with hT3
have htp3 : (((moveUpTo i 6 HeadMove.left).step^[6])
((moveUpTo i 6 HeadMove.left).startCfg T2)).tape = T3 := by
rw [moveUpTo_tape i 6 HeadMove.left (by omega) T2, hT3]
congr 1
rw [hT2i,
show (encodeBlocks (mid ++ [cur])).reverse ++ [TapeSymbol.blank] =
(Block.toCells cur).reverse ++
((encodeBlocks mid).reverse ++ [TapeSymbol.blank]) by
rw [encodeBlocks_append]
simp [List.reverse_append, encodeBlocks_cons],
show (6 : Nat) = ((Block.toCells cur).reverse).length by simp [hCl]]
rw [hret3, List.reverse_reverse]
have hT3i : T3 i = cellsTape
((encodeBlocks mid).reverse ++ [TapeSymbol.blank])
(Block.toCells cur ++ (encodeBlocks post ++ G₃)) := by
rw [hT3]; simp
set T4 := Function.update T3 i
(cellsTape ((Block.toCells newCur).reverse ++
((encodeBlocks mid).reverse ++ [TapeSymbol.blank]))
(encodeBlocks post ++ G₃)) with hT4
have htp4 : (((patchRun6 i (symWindow side s false)).step^[6])
((patchRun6 i (symWindow side s false)).startCfg T3)).tape = T4 := by
rw [patchRun6_tape i _ T3 _ _ hT3i, hT4]
congr 1
rw [patchCellsN_symWindow, ← hnewCur,
show (6 : Nat) = (Block.toCells cur).length from hCl.symm,
List.drop_left]
have hT4i : T4 i = cellsTape
((Block.toCells newCur).reverse ++
((encodeBlocks mid).reverse ++ [TapeSymbol.blank]))
(encodeBlocks post ++ G₃) := by
rw [hT4]; simp
-- ===== junction 5: no movement =====
have h5 : HaltsExactly (moveUpTo i 0 HeadMove.left)
((moveUpTo i 0 HeadMove.left).startCfg T4) 0 true :=
moveUpTo_spec i 0 HeadMove.left (by omega) T4
have htp5 : (((moveUpTo i 0 HeadMove.left).step^[0])
((moveUpTo i 0 HeadMove.left).startCfg T4)).tape = T4 := rfl
-- ===== junctions 6-7: split on whether a next block exists =====
cases post with
| cons nxt post' =>
set sNxt := setFlag side true nxt with hsNxt
have hR4 : T4 i = cellsTape
((Block.toCells newCur).reverse ++
((encodeBlocks mid).reverse ++ [TapeSymbol.blank]))
(Block.toCells nxt ++ (encodeBlocks post' ++ G₃)) := by
rw [hT4i, encodeBlocks_cons, List.append_assoc]
set T6 := Function.update T4 i
(cellsTape ((Block.toCells sNxt).reverse ++
((Block.toCells newCur).reverse ++
((encodeBlocks mid).reverse ++ [TapeSymbol.blank])))
(encodeBlocks post' ++ G₃)) with hT6
have htp6 : (((patchRun6 i (flagWindow side)).step^[6])
((patchRun6 i (flagWindow side)).startCfg T4)).tape = T6 := by
rw [patchRun6_tape i _ T4 _ _ hR4, hT6]
congr 1
rw [patchCellsN_flagWindow, ← hsNxt,
show (6 : Nat) = (Block.toCells nxt).length from
(Block.toCells_length nxt).symm,
List.drop_left]
have hT6i : T6 i = cellsTape
((Block.toCells sNxt).reverse ++
((Block.toCells newCur).reverse ++
((encodeBlocks mid).reverse ++ [TapeSymbol.blank])))
(encodeBlocks post' ++ G₃) := by
rw [hT6]; simp
-- park
set Wp := (Block.toCells sNxt).reverse ++
((Block.toCells newCur).reverse ++ (encodeBlocks mid).reverse)
with hWp
have hassoc : (Block.toCells sNxt).reverse ++
((Block.toCells newCur).reverse ++
((encodeBlocks mid).reverse ++ [TapeSymbol.blank])) =
Wp ++ [TapeSymbol.blank] := by
rw [hWp]
simp [List.append_assoc]
have hWp_nb : ∀ c ∈ Wp, c ≠ TapeSymbol.blank := by
intro c hc
rw [hWp] at hc
rcases List.mem_append.mp hc with h | h
· exact Block.toCells_ne_blank _ c (List.mem_reverse.mp h)
· rcases List.mem_append.mp h with h' | h'
· exact Block.toCells_ne_blank _ c (List.mem_reverse.mp h')
· exact encodeBlocks_ne_blank _ c (List.mem_reverse.mp h')
obtain ⟨hlt', heq'⟩ := blank_scan_left_spec (Wp ++ [TapeSymbol.blank])
((encodeBlocks post' ++ G₃).headD TapeSymbol.blank)
((encodeBlocks post' ++ G₃).tail)
rw [blankIndex_written Wp [] hWp_nb] at hlt' heq'
have hlt : ∀ k, k < Wp.length →
((moveDir HeadMove.left)^[k + 1] (T6 i)).head ≠
TapeSymbol.blank := by
intro k hk
rw [hT6i, hassoc]
exact hlt' k hk
have heq : ((moveDir HeadMove.left)^[Wp.length + 1] (T6 i)).head =
TapeSymbol.blank := by
rw [hT6i, hassoc]
exact heq'
obtain ⟨G₇, hG₇, hret7⟩ := retreat_block Wp [TapeSymbol.blank] post' G₃
hG₃
have hWrev : Wp.reverse = encodeBlocks mid ++
(Block.toCells newCur ++ Block.toCells sNxt) := by
rw [hWp]
simp [List.reverse_append]
have hX7 : (moveDir HeadMove.left)^[Wp.length + 1] (T6 i) =
ParkedTape (mid ++ newCur :: sNxt :: post') G₇ := by
rw [Function.iterate_succ_apply', hT6i, hassoc, hret7]
obtain ⟨r, R', hcons⟩ : ∃ r R',
Wp.reverse ++ (encodeBlocks post' ++ G₇) = r :: R' := by
rw [hWrev]
cases hx : encodeBlocks mid ++
(Block.toCells newCur ++ Block.toCells sNxt) ++
(encodeBlocks post' ++ G₇) with
| nil =>
exfalso
have := congrArg List.length hx
simp [Block.toCells] at this
| cons a as => exact ⟨a, as, rfl⟩
rw [hcons,
show ([TapeSymbol.blank] : List TapeSymbol) =
TapeSymbol.blank :: [] from rfl,
cellsTape_moveLeft, ← hcons, hWrev, ParkedTape]
have henc : encodeBlocks (mid ++ newCur :: sNxt :: post') =
encodeBlocks mid ++ (Block.toCells newCur ++
(Block.toCells sNxt ++ encodeBlocks post')) := by
rw [encodeBlocks_append, encodeBlocks_cons, encodeBlocks_cons]
rw [henc]
simp [List.append_assoc]
set T7 := Function.update T6 i
(ParkedTape (mid ++ newCur :: sNxt :: post') G₇) with hT7
have htp7 : (((scanToBlank i HeadMove.left).step^[Wp.length * 4 + 3])
((scanToBlank i HeadMove.left).startCfg T6)).tape = T7 := by
rw [scanToBlank_tape_of i HeadMove.left T6 Wp.length hlt heq, hT7]
show Function.update T6 i
((moveDir HeadMove.left)^[Wp.length + 1] (T6 i)) = _
rw [hX7]
have hP7 : HaltsExactly (scanToBlank i HeadMove.left)
((scanToBlank i HeadMove.left).startCfg T6) (Wp.length * 4 + 3)
false := scanToBlank_spec_of i HeadMove.left T6 Wp.length hlt heq
have hC6 := chainStep (patchRun6_spec i (flagWindow side) T4 _ _ hR4)
htp6 hP7 htp7
have hC5 := chainStep h5 htp5 hC6.1 hC6.2
have hC4 := chainStep
(patchRun6_spec i (symWindow side s false) T3 _ _ hT3i) htp4
hC5.1 hC5.2
have hC3 := chainStep (moveUpTo_spec i 6 HeadMove.left (by omega) T2)
htp3 hC4.1 hC4.2
have hC2 := chainStep hw hwt hC3.1 hC3.2
have hC1 := chainStep
(moveUpTo_spec i 1 HeadMove.right (by omega) tape) htp1 hC2.1 hC2.2
refine ⟨_, G₇, hG₇, hC1.1, ?_⟩
have hfin := hC1.2
rw [hT7, hT6, hT4, hT3, hT2, hT1] at hfin
simp only [scanTapesDir, Function.update_idem] at hfin
exact hfin
| nil =>
have hR4 : T4 i = cellsTape
((Block.toCells newCur).reverse ++
((encodeBlocks mid).reverse ++ [TapeSymbol.blank])) G₃ := by
rw [hT4i]
simp
set T6 := Function.update T4 i
(cellsTape ((Block.toCells (freshFlagged side)).reverse ++
((Block.toCells newCur).reverse ++
((encodeBlocks mid).reverse ++ [TapeSymbol.blank])))
(G₃.drop 6)) with hT6
have htp6 : (((patchRun6 i (flagWindow side)).step^[6])
((patchRun6 i (flagWindow side)).startCfg T4)).tape = T6 := by
rw [patchRun6_tape i _ T4 _ _ hR4, hT6]
congr 1
rw [patchCellsN_flagWindow_fresh side G₃ hG₃]
have hT6i : T6 i = cellsTape
((Block.toCells (freshFlagged side)).reverse ++
((Block.toCells newCur).reverse ++
((encodeBlocks mid).reverse ++ [TapeSymbol.blank])))
(G₃.drop 6) := by
rw [hT6]; simp
have hG₆ : AllBlank (G₃.drop 6) := hG₃.drop 6
set Wp := (Block.toCells (freshFlagged side)).reverse ++
((Block.toCells newCur).reverse ++ (encodeBlocks mid).reverse)
with hWp
have hassoc : (Block.toCells (freshFlagged side)).reverse ++
((Block.toCells newCur).reverse ++
((encodeBlocks mid).reverse ++ [TapeSymbol.blank])) =
Wp ++ [TapeSymbol.blank] := by
rw [hWp]
simp [List.append_assoc]
have hWp_nb : ∀ c ∈ Wp, c ≠ TapeSymbol.blank := by
intro c hc
rw [hWp] at hc
rcases List.mem_append.mp hc with h | h
· exact Block.toCells_ne_blank _ c (List.mem_reverse.mp h)
· rcases List.mem_append.mp h with h' | h'
· exact Block.toCells_ne_blank _ c (List.mem_reverse.mp h')
· exact encodeBlocks_ne_blank _ c (List.mem_reverse.mp h')
obtain ⟨hlt', heq'⟩ := blank_scan_left_spec (Wp ++ [TapeSymbol.blank])
((G₃.drop 6).headD TapeSymbol.blank) ((G₃.drop 6).tail)
rw [blankIndex_written Wp [] hWp_nb] at hlt' heq'
have hlt : ∀ k, k < Wp.length →
((moveDir HeadMove.left)^[k + 1] (T6 i)).head ≠
TapeSymbol.blank := by
intro k hk
rw [hT6i, hassoc]
exact hlt' k hk
have heq : ((moveDir HeadMove.left)^[Wp.length + 1] (T6 i)).head =
TapeSymbol.blank := by
rw [hT6i, hassoc]
exact heq'
obtain ⟨G₇, hG₇, hret7⟩ := retreat_block Wp [TapeSymbol.blank] []
(G₃.drop 6) hG₆
have hWrev : Wp.reverse = encodeBlocks mid ++
(Block.toCells newCur ++ Block.toCells (freshFlagged side)) := by
rw [hWp]
simp [List.reverse_append]
have hX7 : (moveDir HeadMove.left)^[Wp.length + 1] (T6 i) =
ParkedTape (mid ++ [newCur, freshFlagged side]) G₇ := by
rw [Function.iterate_succ_apply', hT6i, hassoc]
have hret7' : (moveDir HeadMove.left)^[Wp.length]
(cellsTape (Wp ++ [TapeSymbol.blank]) (G₃.drop 6)) =
cellsTape [TapeSymbol.blank] (Wp.reverse ++ G₇) := by
have h := hret7
simpa using h
rw [hret7']
obtain ⟨r, R', hcons⟩ : ∃ r R', Wp.reverse ++ G₇ = r :: R' := by
rw [hWrev]
cases hx : encodeBlocks mid ++
(Block.toCells newCur ++
Block.toCells (freshFlagged side)) ++ G₇ with
| nil =>
exfalso
have := congrArg List.length hx
simp [Block.toCells] at this
| cons a as => exact ⟨a, as, rfl⟩
rw [hcons,
show ([TapeSymbol.blank] : List TapeSymbol) =
TapeSymbol.blank :: [] from rfl,
cellsTape_moveLeft, ← hcons, hWrev, ParkedTape]
have henc : encodeBlocks (mid ++ [newCur, freshFlagged side]) =
encodeBlocks mid ++ (Block.toCells newCur ++
Block.toCells (freshFlagged side)) := by
rw [encodeBlocks_append, encodeBlocks_cons, encodeBlocks_cons,
encodeBlocks_nil, List.append_nil]
rw [henc]
set T7 := Function.update T6 i
(ParkedTape (mid ++ [newCur, freshFlagged side]) G₇) with hT7
have htp7 : (((scanToBlank i HeadMove.left).step^[Wp.length * 4 + 3])
((scanToBlank i HeadMove.left).startCfg T6)).tape = T7 := by
rw [scanToBlank_tape_of i HeadMove.left T6 Wp.length hlt heq, hT7]
show Function.update T6 i
((moveDir HeadMove.left)^[Wp.length + 1] (T6 i)) = _
rw [hX7]
have hP7 : HaltsExactly (scanToBlank i HeadMove.left)
((scanToBlank i HeadMove.left).startCfg T6) (Wp.length * 4 + 3)
false := scanToBlank_spec_of i HeadMove.left T6 Wp.length hlt heq
have hC6 := chainStep (patchRun6_spec i (flagWindow side) T4 _ _ hR4)
htp6 hP7 htp7
have hC5 := chainStep h5 htp5 hC6.1 hC6.2
have hC4 := chainStep
(patchRun6_spec i (symWindow side s false) T3 _ _ hT3i) htp4
hC5.1 hC5.2
have hC3 := chainStep (moveUpTo_spec i 6 HeadMove.left (by omega) T2)
htp3 hC4.1 hC4.2
have hC2 := chainStep hw hwt hC3.1 hC3.2
have hC1 := chainStep
(moveUpTo_spec i 1 HeadMove.right (by omega) tape) htp1 hC2.1 hC2.2
refine ⟨_, G₇, hG₇, hC1.1, ?_⟩
have hfin := hC1.2
rw [hT7, hT6, hT4, hT3, hT2, hT1] at hfin
simp only [scanTapesDir, Function.update_idem] at hfin
exact hfin
/-- The region a leftward flag-move produces: the flag lands on the previous
block, or on a materialised fresh one before the region's start. -/
def leftResult (side : TrackSide) (newCur : Block) (post : List Block)
(mid : List Block) : List Block :=
match mid.reverse with
| [] => freshFlagged side :: newCur :: post
| prv :: rmid' => rmid'.reverse ++ setFlag side true prv :: newCur :: post
theorem leftResult_nil (side : TrackSide) (newCur : Block)
(post : List Block) :
leftResult side newCur post [] =
freshFlagged side :: newCur :: post := rfl
theorem leftResult_concat (side : TrackSide) (newCur : Block)
(post : List Block) (mid' : List Block) (prv : Block) :
leftResult side newCur post (mid' ++ [prv]) =
mid' ++ setFlag side true prv :: newCur :: post := by
simp [leftResult]
/-! ## The left variant -/
theorem updateTrack_left (side : TrackSide) (i : Fin tapes) (s : TapeSymbol)
(tape : Fin tapes → Tape) (mid : List Block) (cur : Block)
(post : List Block) (G : List TapeSymbol) (hG : AllBlank G)
(hmid : ∀ b ∈ mid, side.getFlag b = false)
(hcur : side.getFlag cur = true)
(hi : tape i = ParkedTape (mid ++ cur :: post) G) :
∃ (cost : Nat) (G' : List TapeSymbol), AllBlank G' ∧
HaltsExactly (updateTrack side i s HeadMove.left)
((updateTrack side i s HeadMove.left).startCfg tape) cost false ∧
(((updateTrack side i s HeadMove.left).step^[cost])
((updateTrack side i s HeadMove.left).startCfg tape)).tape =
Function.update tape i
(ParkedTape
(leftResult side (setSymFlag side s false cur) post mid) G') := by
classical
have hCl : (Block.toCells cur).length = 6 := Block.toCells_length cur
set newCur := setSymFlag side s false cur with hnewCur
-- ===== junctions 1-4: shared skeleton =====
set T1 : Fin tapes → Tape := Function.update tape i
(cellsTape [TapeSymbol.blank]
(encodeBlocks (mid ++ cur :: post) ++ G)) with hT1
have htp1 : (((moveUpTo i 1 HeadMove.right).step^[1])
((moveUpTo i 1 HeadMove.right).startCfg tape)).tape = T1 := by
rw [moveUpTo_tape i 1 HeadMove.right (by omega) tape, hT1]
congr 1
rw [Function.iterate_one, hi, ParkedTape]
exact cellsTape_moveRight _ _ _
have hT1i : T1 i = cellsTape [TapeSymbol.blank]
(encodeBlocks (mid ++ cur :: post) ++ G) := by
rw [hT1]; simp
obtain ⟨hw, -, hwt⟩ := walkToFlag_spec side i T1 [TapeSymbol.blank] G
mid cur post hmid hcur hT1i
set W1 := loopCost (fun _ => blockReadSteps) mid.length + blockReadSteps
with hW1
set T2 := scanTapesDir T1 i HeadMove.right (6 * (mid.length + 1)) with hT2
have hsplit : encodeBlocks (mid ++ cur :: post) =
encodeBlocks (mid ++ [cur]) ++ encodeBlocks post := by
rw [← encodeBlocks_append]
congr 1
simp
have hT2i : T2 i =
cellsTape ((encodeBlocks (mid ++ [cur])).reverse ++ [TapeSymbol.blank])
(encodeBlocks post ++ G) := by
rw [hT2, scanTapesDir_self, hT1i, hsplit, List.append_assoc,
show 6 * (mid.length + 1) = (encodeBlocks (mid ++ [cur])).length by
rw [encodeBlocks_length]; simp,
cellsTape_advance]
obtain ⟨G₃, hG₃, hret3⟩ := retreat_block (Block.toCells cur).reverse
((encodeBlocks mid).reverse ++ [TapeSymbol.blank]) post G hG
set T3 := Function.update T2 i
(cellsTape ((encodeBlocks mid).reverse ++ [TapeSymbol.blank])
(Block.toCells cur ++ (encodeBlocks post ++ G₃))) with hT3
have htp3 : (((moveUpTo i 6 HeadMove.left).step^[6])
((moveUpTo i 6 HeadMove.left).startCfg T2)).tape = T3 := by
rw [moveUpTo_tape i 6 HeadMove.left (by omega) T2, hT3]
congr 1
rw [hT2i,
show (encodeBlocks (mid ++ [cur])).reverse ++ [TapeSymbol.blank] =
(Block.toCells cur).reverse ++
((encodeBlocks mid).reverse ++ [TapeSymbol.blank]) by
rw [encodeBlocks_append]
simp [List.reverse_append, encodeBlocks_cons],
show (6 : Nat) = ((Block.toCells cur).reverse).length by simp [hCl]]
rw [hret3, List.reverse_reverse]
have hT3i : T3 i = cellsTape
((encodeBlocks mid).reverse ++ [TapeSymbol.blank])
(Block.toCells cur ++ (encodeBlocks post ++ G₃)) := by
rw [hT3]; simp
set T4 := Function.update T3 i
(cellsTape ((Block.toCells newCur).reverse ++
((encodeBlocks mid).reverse ++ [TapeSymbol.blank]))
(encodeBlocks post ++ G₃)) with hT4
have htp4 : (((patchRun6 i (symWindow side s false)).step^[6])
((patchRun6 i (symWindow side s false)).startCfg T3)).tape = T4 := by
rw [patchRun6_tape i _ T3 _ _ hT3i, hT4]
congr 1
rw [patchCellsN_symWindow, ← hnewCur,
show (6 : Nat) = (Block.toCells cur).length from hCl.symm,
List.drop_left]
have hT4i : T4 i = cellsTape
((Block.toCells newCur).reverse ++
((encodeBlocks mid).reverse ++ [TapeSymbol.blank]))
(encodeBlocks post ++ G₃) := by
rw [hT4]; simp
-- ===== junctions 5-7: split on whether a previous block exists =====
rcases List.eq_nil_or_concat mid with rfl | ⟨mid', prv, rfl⟩
· -- mid = []: the flag walks off the left end; the park relocates
have hT4i' : T4 i = cellsTape
((Block.toCells newCur).reverse ++ [TapeSymbol.blank])
(encodeBlocks post ++ G₃) := by
rw [hT4i]
simp
obtain ⟨G₅, hG₅, hret5⟩ := retreat_block
((Block.toCells newCur).reverse ++ [TapeSymbol.blank]) [] post G₃ hG₃
have hret5' : (moveDir HeadMove.left)^[7]
(cellsTape ((Block.toCells newCur).reverse ++ [TapeSymbol.blank])
(encodeBlocks post ++ G₃)) =
cellsTape [] (TapeSymbol.blank :: Block.toCells newCur ++
(encodeBlocks post ++ G₅)) := by
have h7 : (7 : Nat) =
((Block.toCells newCur).reverse ++ [TapeSymbol.blank]).length := by
simp [Block.toCells_length]
rw [h7]
have h := hret5
rw [List.append_nil] at h
rw [h]
simp [List.reverse_append]
have hX5 : (moveDir HeadMove.left)^[12] (T4 i) =
cellsTape [] (List.replicate 5 TapeSymbol.blank ++
TapeSymbol.blank :: Block.toCells newCur ++
(encodeBlocks post ++ G₅)) := by
rw [hT4i', show (12 : Nat) = 5 + 7 from rfl,
Function.iterate_add_apply, hret5']
exact cellsTape_retreat_past 5 TapeSymbol.blank
(Block.toCells newCur ++ (encodeBlocks post ++ G₅))
set T5 := Function.update T4 i
(cellsTape [] (List.replicate 5 TapeSymbol.blank ++
TapeSymbol.blank :: Block.toCells newCur ++
(encodeBlocks post ++ G₅))) with hT5
have htp5 : (((moveUpTo i 12 HeadMove.left).step^[12])
((moveUpTo i 12 HeadMove.left).startCfg T4)).tape = T5 := by
rw [moveUpTo_tape i 12 HeadMove.left (by omega) T4, hT5]
exact congrArg (Function.update T4 i) hX5
have hT5i : T5 i = cellsTape []
(List.replicate 5 TapeSymbol.blank ++
TapeSymbol.blank :: Block.toCells newCur ++
(encodeBlocks post ++ G₅)) := by
rw [hT5]; simp
-- the six cells ahead are all blank; the flag window materialises
have hR5eq : List.replicate 5 TapeSymbol.blank ++
TapeSymbol.blank :: Block.toCells newCur ++
(encodeBlocks post ++ G₅) =
List.replicate 6 TapeSymbol.blank ++
(Block.toCells newCur ++ (encodeBlocks post ++ G₅)) := by
rw [show List.replicate 6 TapeSymbol.blank =
List.replicate 5 TapeSymbol.blank ++ [TapeSymbol.blank] from
List.replicate_succ' .. ]
simp [List.append_assoc]
have hpatch : patchCellsN 6 (flagWindow side)
(List.replicate 5 TapeSymbol.blank ++
TapeSymbol.blank :: Block.toCells newCur ++
(encodeBlocks post ++ G₅)) =
Block.toCells (freshFlagged side) := by
rw [hR5eq]
rw [patchCellsN_congr_prefix 6 (flagWindow side) _
(List.replicate 6 TapeSymbol.blank)
(by rw [List.take_left' (by simp), List.take_of_length_le (by simp)])]
exact patchCellsN_flagWindow_fresh side _
(fun c hc => (List.eq_of_mem_replicate hc))
have hdrop : (List.replicate 5 TapeSymbol.blank ++
TapeSymbol.blank :: Block.toCells newCur ++
(encodeBlocks post ++ G₅)).drop 6 =
Block.toCells newCur ++ (encodeBlocks post ++ G₅) := by
rw [hR5eq, List.drop_left' (by simp)]
set T6 := Function.update T5 i
(cellsTape ((Block.toCells (freshFlagged side)).reverse)
(Block.toCells newCur ++ (encodeBlocks post ++ G₅))) with hT6
have htp6 : (((patchRun6 i (flagWindow side)).step^[6])
((patchRun6 i (flagWindow side)).startCfg T5)).tape = T6 := by
rw [patchRun6_tape i _ T5 _ _ hT5i, hT6]
refine congrArg (Function.update T5 i) ?_
rw [hpatch, hdrop]
simp
have hT6i : T6 i = cellsTape
((Block.toCells (freshFlagged side)).reverse)
(Block.toCells newCur ++ (encodeBlocks post ++ G₅)) := by
rw [hT6]; simp
-- park: six written cells, no blank behind them
have hW_nb : ∀ c ∈ (Block.toCells (freshFlagged side)).reverse,
c ≠ TapeSymbol.blank := by
intro c hc
exact Block.toCells_ne_blank _ c (List.mem_reverse.mp hc)
obtain ⟨hlt', heq'⟩ := blank_scan_left_spec
((Block.toCells (freshFlagged side)).reverse)
((Block.toCells newCur ++ (encodeBlocks post ++ G₅)).headD
TapeSymbol.blank)
((Block.toCells newCur ++ (encodeBlocks post ++ G₅)).tail)
rw [blankIndex_all _ hW_nb] at hlt' heq'
have hWl : ((Block.toCells (freshFlagged side)).reverse).length = 6 := by
simp [Block.toCells_length]
have hlt : ∀ k, k < 6 →
((moveDir HeadMove.left)^[k + 1] (T6 i)).head ≠
TapeSymbol.blank := by
intro k hk
rw [hT6i]
exact hlt' k (by omega)
have heq : ((moveDir HeadMove.left)^[6 + 1] (T6 i)).head =
TapeSymbol.blank := by
rw [hT6i]
have h := heq'
rw [hWl] at h
exact h
have hX7 : (moveDir HeadMove.left)^[6 + 1] (T6 i) =
ParkedTape (freshFlagged side :: newCur :: post) G₅ := by
rw [Function.iterate_succ_apply', hT6i]
obtain ⟨r, R', hcons⟩ : ∃ r R',
Block.toCells newCur ++ (encodeBlocks post ++ G₅) = r :: R' := by
cases hx : Block.toCells newCur ++ (encodeBlocks post ++ G₅) with
| nil =>
exfalso
have := congrArg List.length hx
simp [Block.toCells] at this
| cons a as => exact ⟨a, as, rfl⟩
rw [hcons, show (6 : Nat) =
((Block.toCells (freshFlagged side)).reverse).length from hWl.symm]
rw [cellsTape_retreat_nilL, List.reverse_reverse, ← hcons]
obtain ⟨r₂, R₂, hcons₂⟩ : ∃ r₂ R₂,
Block.toCells (freshFlagged side) ++
(Block.toCells newCur ++ (encodeBlocks post ++ G₅)) =
r₂ :: R₂ := by
cases hx : Block.toCells (freshFlagged side) ++
(Block.toCells newCur ++ (encodeBlocks post ++ G₅)) with
| nil =>
exfalso
have := congrArg List.length hx
simp [Block.toCells] at this
| cons a as => exact ⟨a, as, rfl⟩
rw [hcons₂, cellsTape_moveLeft_nilL, ← hcons₂, ParkedTape]
simp [encodeBlocks_cons, List.append_assoc]
set T7 := Function.update T6 i
(ParkedTape (freshFlagged side :: newCur :: post) G₅) with hT7
have htp7 : (((scanToBlank i HeadMove.left).step^[6 * 4 + 3])
((scanToBlank i HeadMove.left).startCfg T6)).tape = T7 := by
rw [scanToBlank_tape_of i HeadMove.left T6 6 hlt heq, hT7]
show Function.update T6 i
((moveDir HeadMove.left)^[6 + 1] (T6 i)) = _
rw [hX7]
have hP7 : HaltsExactly (scanToBlank i HeadMove.left)
((scanToBlank i HeadMove.left).startCfg T6) (6 * 4 + 3) false :=
scanToBlank_spec_of i HeadMove.left T6 6 hlt heq
have hC6 := chainStep (patchRun6_spec i (flagWindow side) T5 _ _ hT5i)
htp6 hP7 htp7
have hC5 := chainStep (moveUpTo_spec i 12 HeadMove.left (by omega) T4)
htp5 hC6.1 hC6.2
have hC4 := chainStep
(patchRun6_spec i (symWindow side s false) T3 _ _ hT3i) htp4
hC5.1 hC5.2
have hC3 := chainStep (moveUpTo_spec i 6 HeadMove.left (by omega) T2)
htp3 hC4.1 hC4.2
have hC2 := chainStep hw hwt hC3.1 hC3.2
have hC1 := chainStep
(moveUpTo_spec i 1 HeadMove.right (by omega) tape) htp1 hC2.1 hC2.2
have hT7flat : T7 = Function.update tape i
(ParkedTape (freshFlagged side :: newCur :: post) G₅) := by
rw [hT7, hT6, hT5, hT4, hT3, hT2, hT1]
simp only [scanTapesDir, Function.update_idem]
refine ⟨_, G₅, hG₅, hC1.1, ?_⟩
rw [leftResult_nil]
exact hC1.2.trans hT7flat
· -- mid = mid' ++ [prv]: the flag lands on the previous block
simp only [List.concat_eq_append] at *
set sPrv := setFlag side true prv with hsPrv
have hL4 : (Block.toCells newCur).reverse ++
((encodeBlocks (mid' ++ [prv])).reverse ++ [TapeSymbol.blank]) =
((Block.toCells newCur).reverse ++ (Block.toCells prv).reverse) ++
((encodeBlocks mid').reverse ++ [TapeSymbol.blank]) := by
rw [encodeBlocks_append]
simp [List.reverse_append, encodeBlocks_cons, List.append_assoc]
obtain ⟨G₅, hG₅, hret5⟩ := retreat_block
((Block.toCells newCur).reverse ++ (Block.toCells prv).reverse)
((encodeBlocks mid').reverse ++ [TapeSymbol.blank]) post G₃ hG₃
set T5 := Function.update T4 i
(cellsTape ((encodeBlocks mid').reverse ++ [TapeSymbol.blank])
(Block.toCells prv ++ (Block.toCells newCur ++
(encodeBlocks post ++ G₅)))) with hT5
have htp5 : (((moveUpTo i 12 HeadMove.left).step^[12])
((moveUpTo i 12 HeadMove.left).startCfg T4)).tape = T5 := by
rw [moveUpTo_tape i 12 HeadMove.left (by omega) T4, hT5]
refine congrArg (Function.update T4 i) ?_
rw [hT4i, hL4,
show (12 : Nat) = ((Block.toCells newCur).reverse ++
(Block.toCells prv).reverse).length by
simp [Block.toCells_length]]
rw [hret5]
simp [List.reverse_append, List.append_assoc]
have hT5i : T5 i = cellsTape
((encodeBlocks mid').reverse ++ [TapeSymbol.blank])
(Block.toCells prv ++ (Block.toCells newCur ++
(encodeBlocks post ++ G₅))) := by
rw [hT5]; simp
set T6 := Function.update T5 i
(cellsTape ((Block.toCells sPrv).reverse ++
((encodeBlocks mid').reverse ++ [TapeSymbol.blank]))
(Block.toCells newCur ++ (encodeBlocks post ++ G₅))) with hT6
have htp6 : (((patchRun6 i (flagWindow side)).step^[6])
((patchRun6 i (flagWindow side)).startCfg T5)).tape = T6 := by
rw [patchRun6_tape i _ T5 _ _ hT5i, hT6]
refine congrArg (Function.update T5 i) ?_
rw [patchCellsN_flagWindow, ← hsPrv,
show (6 : Nat) = (Block.toCells prv).length from
(Block.toCells_length prv).symm,
List.drop_left]
have hT6i : T6 i = cellsTape
((Block.toCells sPrv).reverse ++
((encodeBlocks mid').reverse ++ [TapeSymbol.blank]))
(Block.toCells newCur ++ (encodeBlocks post ++ G₅)) := by
rw [hT6]; simp
-- park
set Wp := (Block.toCells sPrv).reverse ++ (encodeBlocks mid').reverse
with hWp
have hassoc : (Block.toCells sPrv).reverse ++
((encodeBlocks mid').reverse ++ [TapeSymbol.blank]) =
Wp ++ [TapeSymbol.blank] := by
rw [hWp, List.append_assoc]
have hWp_nb : ∀ c ∈ Wp, c ≠ TapeSymbol.blank := by
intro c hc
rw [hWp] at hc
rcases List.mem_append.mp hc with h | h
· exact Block.toCells_ne_blank _ c (List.mem_reverse.mp h)
· exact encodeBlocks_ne_blank _ c (List.mem_reverse.mp h)
obtain ⟨hlt', heq'⟩ := blank_scan_left_spec (Wp ++ [TapeSymbol.blank])
((Block.toCells newCur ++ (encodeBlocks post ++ G₅)).headD
TapeSymbol.blank)
((Block.toCells newCur ++ (encodeBlocks post ++ G₅)).tail)
rw [blankIndex_written Wp [] hWp_nb] at hlt' heq'
have hlt : ∀ k, k < Wp.length →
((moveDir HeadMove.left)^[k + 1] (T6 i)).head ≠
TapeSymbol.blank := by
intro k hk
rw [hT6i, hassoc]
exact hlt' k hk
have heq : ((moveDir HeadMove.left)^[Wp.length + 1] (T6 i)).head =
TapeSymbol.blank := by
rw [hT6i, hassoc]
exact heq'
have hR6 : Block.toCells newCur ++ (encodeBlocks post ++ G₅) =
encodeBlocks (newCur :: post) ++ G₅ := by
rw [encodeBlocks_cons]
simp [List.append_assoc]
obtain ⟨G₇, hG₇, hret7⟩ := retreat_block Wp [TapeSymbol.blank]
(newCur :: post) G₅ hG₅
have hWrev : Wp.reverse = encodeBlocks mid' ++ Block.toCells sPrv := by
rw [hWp, List.reverse_append, List.reverse_reverse,
List.reverse_reverse]
have hX7 : (moveDir HeadMove.left)^[Wp.length + 1] (T6 i) =
ParkedTape (mid' ++ sPrv :: newCur :: post) G₇ := by
rw [Function.iterate_succ_apply', hT6i, hassoc, hR6, hret7]
obtain ⟨r, R', hcons⟩ : ∃ r R',
Wp.reverse ++ (encodeBlocks (newCur :: post) ++ G₇) = r :: R' := by
rw [hWrev]
cases hx : encodeBlocks mid' ++ Block.toCells sPrv ++
(encodeBlocks (newCur :: post) ++ G₇) with
| nil =>
exfalso
have := congrArg List.length hx
simp [Block.toCells] at this
| cons a as => exact ⟨a, as, rfl⟩
rw [hcons,
show ([TapeSymbol.blank] : List TapeSymbol) =
TapeSymbol.blank :: [] from rfl,
cellsTape_moveLeft, ← hcons, hWrev, ParkedTape]
have henc : encodeBlocks (mid' ++ sPrv :: newCur :: post) =
encodeBlocks mid' ++ (Block.toCells sPrv ++
encodeBlocks (newCur :: post)) := by
rw [encodeBlocks_append, encodeBlocks_cons]
rw [henc]
simp [List.append_assoc]
set T7 := Function.update T6 i
(ParkedTape (mid' ++ sPrv :: newCur :: post) G₇) with hT7
have htp7 : (((scanToBlank i HeadMove.left).step^[Wp.length * 4 + 3])
((scanToBlank i HeadMove.left).startCfg T6)).tape = T7 := by
rw [scanToBlank_tape_of i HeadMove.left T6 Wp.length hlt heq, hT7]
show Function.update T6 i
((moveDir HeadMove.left)^[Wp.length + 1] (T6 i)) = _
rw [hX7]
have hP7 : HaltsExactly (scanToBlank i HeadMove.left)
((scanToBlank i HeadMove.left).startCfg T6) (Wp.length * 4 + 3)
false := scanToBlank_spec_of i HeadMove.left T6 Wp.length hlt heq
have hC6 := chainStep (patchRun6_spec i (flagWindow side) T5 _ _ hT5i)
htp6 hP7 htp7
have hC5 := chainStep (moveUpTo_spec i 12 HeadMove.left (by omega) T4)
htp5 hC6.1 hC6.2
have hC4 := chainStep
(patchRun6_spec i (symWindow side s false) T3 _ _ hT3i) htp4
hC5.1 hC5.2
have hC3 := chainStep (moveUpTo_spec i 6 HeadMove.left (by omega) T2)
htp3 hC4.1 hC4.2
have hC2 := chainStep hw hwt hC3.1 hC3.2
have hC1 := chainStep
(moveUpTo_spec i 1 HeadMove.right (by omega) tape) htp1 hC2.1 hC2.2
have hT7flat : T7 = Function.update tape i
(ParkedTape (mid' ++ sPrv :: newCur :: post) G₇) := by
rw [hT7, hT6, hT5, hT4, hT3, hT2, hT1]
simp only [scanTapesDir, Function.update_idem]
refine ⟨_, G₇, hG₇, hC1.1, ?_⟩
rw [leftResult_concat]
exact hC1.2.trans hT7flat
end SipserGacsLautemann