The dilation machine and its round's core
Definitionsgl_dilation_coreThe in-place dilation machine and the proved core of its round.
dilation i converts a tape holding raw input bits into the parked two-track region hosting that input beside an empty track — the initialization eliminate_last_scratch_tape needs, forced by the three-symbol alphabet. Structure: a one-step read dispatches empty input to initRegion through the new TypedMachine.either combinator (branches of different state types run on their sum — the missing dispatch primitive); otherwise a pre-pass shifts the whole input five right, and a loopState round harvests one cell, shifts the remainder five right, and writes one six-cell block over the five separators plus the harvested cell. A round that reads blank writes the all-blank flag-clear exitBlock — PadEq absorbs it — and the loop stops on the symbol captured in the terminal state, read by the generic stateRead peel.
dilCont_spec_bit, proved in both branches, is the phase's centerpiece: the post-read chain — scan right, step back, probe, shift, five left, write — runs in at most steps and lands exactly on the next round's invariant, the head at the new separator start over blocks-so-far extended by the new block. The empty-remainder branch runs the same chain with the shifter halting at once, which is what makes the loop's last round uniform with the others.
One elaboration point worth recording: writeRun's state type carries the cell list's length, so a family over the captured symbol is only type-uniform because Block.toCells is a literal six-cell list — its length reduces definitionally even on stuck arguments. The dilWrite wrapper pins that down once.
import Definitions.Def_sgl_machine_either
/-!
# In-place input dilation
Module G2 of DESIGN_finish_mission: convert a tape holding raw input bits into
the parked two-track region hosting (that input, the empty scratch tape).
Layout invariant before round `i` (head at the separator start, position
`6(i−1)` relative to the block region's origin): blocks written so far to the
left, five blank separators under and right of the head, the next input cell
five right, the compact remainder after it, blanks beyond. One round harvests
the cell, shifts the remainder five right (vacating the next separators),
and writes the six-cell block over the old separators plus the harvested cell.
A round that reads blank instead of an input bit writes the all-blank
`exitBlock` (flags clear — `PadEq` absorbs it) and the loop stops on the
captured symbol. The empty input never enters the loop: a top-level read
dispatches it to `initRegion` through `TypedMachine.either`.
-/
namespace SipserGacsLautemann
variable {tapes : Nat}
/-- The block hosting one input cell on track A, empty track B. -/
def inputBlock (b : Bool) (first : Bool) : Block :=
⟨TapeSymbol.bit b, first, TapeSymbol.blank, first⟩
/-- The block a blank read writes: both tracks blank, flags clear. -/
def exitBlock : Block :=
⟨TapeSymbol.blank, false, TapeSymbol.blank, false⟩
/-- The block a round writes, from the captured symbol. -/
def blockFor (rec : Option TapeSymbol) (first : Bool) : Block :=
match rec with
| some (TapeSymbol.bit b) => inputBlock b first
| _ => ⟨TapeSymbol.blank, first, TapeSymbol.blank, first⟩
/-- The region the dilation builds for a *non-empty* input. -/
def dilBlocks : List Bool → List Block
| [] => [exitBlock]
| x :: xs => inputBlock x true ::
(xs.map fun b => inputBlock b false) ++ [exitBlock]
/-- The region for arbitrary input (empty input gets the merge-init block). -/
def encodeInputBlocks (xs : List Bool) : List Block :=
match xs with
| [] => [initBlock]
| _ => dilBlocks xs
/-- Input bits as tape symbols. -/
def bitCells (xs : List Bool) : List TapeSymbol :=
xs.map fun b => TapeSymbol.bit b
/-- The round invariant: head at the separator start. -/
def dilTape (done : List Block) (rest : List Bool) (G : List TapeSymbol) :
Tape :=
cellsTape ((encodeBlocks done).reverse ++ [TapeSymbol.blank])
(List.replicate 5 TapeSymbol.blank ++ bitCells rest ++ G)
/-! ## The machines -/
/-- Read the head symbol, erase it, stay. -/
def eraseRead (i : Fin tapes) :=
TypedMachine.readAct (fun syms =>
(syms i,
fun j => (if j = i then TapeSymbol.blank else syms j, HeadMove.stay)))
/-- The block write, at its reduced state type. -/
def dilWrite (i : Fin tapes) (rec : Option TapeSymbol) (first : Bool) :
TypedMachine tapes (Fin 7) :=
writeRun i (Block.toCells (blockFor rec first))
/-- The post-read chain of one round. -/
def dilCont (i : Fin tapes) (rec : Option TapeSymbol) (first : Bool) :=
(scanToBlank i HeadMove.right).andThen fun _ =>
(moveUpTo i 1 HeadMove.left).andThen fun _ =>
(moveUpTo i 5 HeadMove.right).andThen fun _ =>
(moveUpTo i 5 HeadMove.left).andThen fun _ =>
(shiftSeg5 i).andThen fun _ =>
(moveUpTo i 5 HeadMove.left).andThen fun _ =>
dilWrite i rec first
/-- One dilation round. -/
def dilBody (i : Fin tapes) (first : Bool) :=
(moveUpTo i 5 HeadMove.right).andThen fun _ =>
(eraseRead i).andThenState (fun s => s.isSome) fun rec =>
dilCont i rec first
/-- Recover the captured symbol from a terminal body state (generic in the
layers around the `andThenState` junction). -/
def stateRead {S₁ S₂ : Type}
(s : S₁ ⊕ Bool × (Option TapeSymbol ⊕ Option TapeSymbol × S₂)) :
Option TapeSymbol :=
match s with
| .inr (_, .inr (rec, _)) => rec
| _ => none
@[simp] theorem stateRead_inr {S₁ S₂ : Type} (b : Bool)
(rec : Option TapeSymbol) (s : S₂) :
stateRead (S₁ := S₁) (Sum.inr (b, Sum.inr (rec, s))) = rec := rfl
/-- Was the captured symbol an input bit? -/
def isBitO : Option TapeSymbol → Bool
| some (TapeSymbol.bit _) => true
| _ => false
/-- The dilation loop: run rounds while the read is an input bit. -/
def dilLoop (i : Fin tapes) :=
TypedMachine.loopState (fun first => dilBody i first)
(fun _ _ => false)
(fun _ b => !(isBitO (stateRead b)))
(fun _ _ => false)
true
/-- The pre-pass: materialise home, shift the whole input right by five. -/
def prePass (i : Fin tapes) :=
(moveUpTo i 1 HeadMove.left).andThen fun _ =>
(moveUpTo i 1 HeadMove.right).andThen fun _ =>
(scanToBlank i HeadMove.right).andThen fun _ =>
(moveUpTo i 1 HeadMove.left).andThen fun _ =>
(moveUpTo i 5 HeadMove.right).andThen fun _ =>
(moveUpTo i 5 HeadMove.left).andThen fun _ =>
(shiftSeg5 i).andThen fun _ =>
moveUpTo i 1 HeadMove.right
/-- The whole non-empty path: pre-pass, loop, park. -/
def dilMain (i : Fin tapes) :=
(prePass i).andThen fun _ =>
(dilLoop i).andThen fun _ =>
scanToBlank i HeadMove.left
/-- **The dilation machine**: dispatch on the first cell. -/
def dilation (i : Fin tapes) :=
(TypedMachine.readAct (fun syms =>
(syms i, fun j => (syms j, HeadMove.stay)))).andThenState
(fun s => s.isSome) fun rec =>
(dilMain i).either (initRegion i) (isBitO rec)
/-! ## Support lemmas -/
/-- The shifter on a blank head: one step, halt, tape unchanged. -/
theorem shiftSeg5_halt_spec (i : Fin tapes) (T : Fin tapes → Tape)
(hb : (T i).head = TapeSymbol.blank) :
HaltsExactly (shiftSeg5 i) ((shiftSeg5 i).startCfg T) 1 false ∧
(((shiftSeg5 i).step^[1]) ((shiftSeg5 i).startCfg T)).tape = T := by
have hstep : ((shiftSeg5 i).step^[1]) ((shiftSeg5 i).startCfg T) =
⟨(⟨11, by omega⟩, TapeSymbol.blank), T⟩ := by
rw [Function.iterate_one]
exact shiftSeg5_step_halt i T hb
refine ⟨⟨?_, ?_⟩, ?_⟩
· rw [hstep]; rfl
· intro j hj
have : j = 0 := by omega
subst this
rfl
· rw [hstep]
/-- The erase-read's tape action. -/
theorem applyAction_erase (i : Fin tapes) (T : Fin tapes → Tape) :
applyAction T (fun syms j =>
(if j = i then TapeSymbol.blank else syms j, HeadMove.stay)) =
Function.update T i (Tape.write (T i) TapeSymbol.blank) := by
funext j
by_cases hj : j = i
· subst hj
simp [applyAction, Tape.move]
· simp [applyAction, hj, Tape.write_head_self, Tape.move]
/-- A tape parked over an all-blank right context reads blank. -/
theorem cellsTape_head_allBlank (L G : List TapeSymbol) (hG : AllBlank G) :
(cellsTape L G).head = TapeSymbol.blank := by
cases G with
| nil => rfl
| cons g G' => exact hG g (by simp)
/-- Five retreats over the separator cells. -/
theorem retreat5 (L R : List TapeSymbol) (r : TapeSymbol) :
((moveDir HeadMove.left)^[5])
(cellsTape (List.replicate 5 TapeSymbol.blank ++ L) (r :: R)) =
cellsTape L (List.replicate 5 TapeSymbol.blank ++ r :: R) := by
have h := cellsTape_retreat (List.replicate 5 TapeSymbol.blank) L R r
simpa using h
@[simp] theorem bitCells_ne_blank (xs : List Bool) :
∀ c ∈ bitCells xs, c ≠ TapeSymbol.blank := by
intro c hc
simp only [bitCells, List.mem_map] at hc
obtain ⟨b, -, rfl⟩ := hc
simp
@[simp] theorem bitCells_nil : bitCells [] = [] := rfl
@[simp] theorem bitCells_cons (x : Bool) (xs : List Bool) :
bitCells (x :: xs) = TapeSymbol.bit x :: bitCells xs := rfl
theorem bitCells_append (xs ys : List Bool) :
bitCells (xs ++ ys) = bitCells xs ++ bitCells ys := by
simp [bitCells]
theorem encodeBlocks_snoc (bs : List Block) (b : Block) :
encodeBlocks (bs ++ [b]) = encodeBlocks bs ++ Block.toCells b := by
rw [encodeBlocks_append]
simp
/-! ## Left-move over an all-blank right context -/
theorem moveDir_left_allBlank (c : TapeSymbol) (L R : List TapeSymbol)
(hR : AllBlank R) :
∃ R₂, AllBlank R₂ ∧
moveDir HeadMove.left (cellsTape (c :: L) R) = cellsTape L (c :: R₂) := by
cases R with
| nil =>
exact ⟨[TapeSymbol.blank], AllBlank.single, cellsTape_moveLeft_nil L c⟩
| cons r R' =>
exact ⟨r :: R', hR, cellsTape_moveLeft L c r R'⟩
set_option maxHeartbeats 4000000 in
/-- **The post-read chain on an input bit**: shift the remainder five right,
write the block, land at the next separator start over the round invariant. -/
theorem dilCont_spec_bit (i : Fin tapes) (first x : Bool)
(done : List Block) (rest : List Bool) (G : List TapeSymbol)
(T2 : Fin tapes → Tape) (hG : AllBlank G)
(hT2 : T2 i = cellsTape
(List.replicate 5 TapeSymbol.blank ++
((encodeBlocks done).reverse ++ [TapeSymbol.blank]))
(TapeSymbol.blank :: bitCells rest ++ G)) :
∃ (cost : Nat) (G' : List TapeSymbol), AllBlank G' ∧
cost ≤ 15 * rest.length + 40 ∧
HaltsExactly (dilCont i (some (TapeSymbol.bit x)) first)
((dilCont i (some (TapeSymbol.bit x)) first).startCfg T2) cost true ∧
(((dilCont i (some (TapeSymbol.bit x)) first).step^[cost])
((dilCont i (some (TapeSymbol.bit x)) first).startCfg T2)).tape =
Function.update T2 i (cellsTape
((encodeBlocks (done ++ [inputBlock x first])).reverse ++
[TapeSymbol.blank])
(List.replicate 5 TapeSymbol.blank ++ bitCells rest ++ G')) := by
classical
set L0 := (encodeBlocks done).reverse ++ [TapeSymbol.blank] with hL0
set L2 := List.replicate 5 TapeSymbol.blank ++ L0 with hL2
set d := rest.length with hd
-- ===== stage C: scan right over the remainder =====
have hadv : ∀ k, k ≤ d →
((moveDir HeadMove.right)^[k + 1]) (T2 i) =
cellsTape ((TapeSymbol.blank :: bitCells (rest.take k)).reverse ++ L2)
(bitCells (rest.drop k) ++ G) := by
intro k hk
have hsplit : TapeSymbol.blank :: bitCells rest ++ G =
(TapeSymbol.blank :: bitCells (rest.take k)) ++
(bitCells (rest.drop k) ++ G) := by
rw [show TapeSymbol.blank :: bitCells (rest.take k) ++
(bitCells (rest.drop k) ++ G) =
TapeSymbol.blank :: (bitCells (rest.take k) ++ bitCells (rest.drop k))
++ G by simp]
rw [← bitCells_append, List.take_append_drop]
have hlen : (TapeSymbol.blank :: bitCells (rest.take k)).length = k + 1 := by
simp [bitCells, List.length_take]
omega
rw [hT2, hsplit, ← hlen, cellsTape_advance]
have hlt : ∀ k, k < d →
(((moveDir HeadMove.right)^[k + 1]) (T2 i)).head ≠ TapeSymbol.blank := by
intro k hk
rw [hadv k (by omega)]
obtain ⟨y, ys, hdrop⟩ : ∃ y ys, rest.drop k = y :: ys := by
cases hdk : rest.drop k with
| nil =>
exfalso
have := congrArg List.length hdk
simp [List.length_drop] at this
omega
| cons y ys => exact ⟨y, ys, rfl⟩
rw [hdrop]
simp [cellsTape]
have heq : (((moveDir HeadMove.right)^[d + 1]) (T2 i)).head =
TapeSymbol.blank := by
rw [hadv d le_rfl]
rw [show rest.drop d = [] by rw [hd]; exact List.drop_length]
exact cellsTape_head_allBlank _ G hG
have hC := scanToBlank_spec_of i HeadMove.right T2 d hlt heq
have hCt := scanToBlank_tape_of i HeadMove.right T2 d hlt heq
set T3 := Function.update T2 i
(cellsTape ((bitCells rest).reverse ++ [TapeSymbol.blank] ++ L2) G)
with hT3
have hCt' : (((scanToBlank i HeadMove.right).step^[d * 4 + 3])
((scanToBlank i HeadMove.right).startCfg T2)).tape = T3 := by
rw [hCt, hT3]
show scanTapesDir T2 i HeadMove.right (d + 1) = _
rw [scanTapesDir]
congr 1
rw [hadv d le_rfl]
rw [show rest.drop d = [] by rw [hd]; exact List.drop_length,
show rest.take d = rest by rw [hd]; exact List.take_length]
simp
have hT3i : T3 i =
cellsTape ((bitCells rest).reverse ++ [TapeSymbol.blank] ++ L2) G := by
rw [hT3]; simp
-- ===== stages D–I, by the shape of the remainder =====
rcases List.eq_nil_or_concat rest with hrest | ⟨ws, w, hrest⟩
case inl =>
subst hrest
-- ----- D: one left -----
obtain ⟨G₂, hG₂, hmv⟩ := moveDir_left_allBlank TapeSymbol.blank L2 G hG
have hD := moveUpTo_spec i 1 HeadMove.left (by omega) T3
set T4 := Function.update T3 i (cellsTape L2 (TapeSymbol.blank :: G₂))
with hT4
have hDt : (((moveUpTo i 1 HeadMove.left).step^[1])
((moveUpTo i 1 HeadMove.left).startCfg T3)).tape = T4 := by
rw [moveUpTo_tape i 1 HeadMove.left (by omega) T3, hT4]
congr 1
rw [Function.iterate_one, hT3i]
show moveDir HeadMove.left
(cellsTape (TapeSymbol.blank :: L2) G) = _
rw [hmv]
have hT4i : T4 i = cellsTape L2 (TapeSymbol.blank :: G₂) := by
rw [hT4]; simp
-- ----- E,F: the probe -----
have hE := moveUpTo_spec i 5 HeadMove.right (by omega) T4
set T5 := Function.update T4 i
((moveDir HeadMove.right)^[5] (T4 i)) with hT5
have hEt : (((moveUpTo i 5 HeadMove.right).step^[5])
((moveUpTo i 5 HeadMove.right).startCfg T4)).tape = T5 := by
rw [moveUpTo_tape i 5 HeadMove.right (by omega) T4, hT5]
have hF := moveUpTo_spec i 5 HeadMove.left (by omega) T5
set T6 := Function.update T5 i
(cellsTape L2 (TapeSymbol.blank ::
List.replicate 5 TapeSymbol.blank ++ G₂.drop 5)) with hT6
have hFt : (((moveUpTo i 5 HeadMove.left).step^[5])
((moveUpTo i 5 HeadMove.left).startCfg T5)).tape = T6 := by
rw [moveUpTo_tape i 5 HeadMove.left (by omega) T5, hT6, hT5]
simp only [Function.update_idem, Function.update_self]
congr 1
rw [hT4i, hL2]
show ((moveDir HeadMove.left)^[5])
(((moveDir HeadMove.right)^[5]) (cellsTape
(TapeSymbol.blank :: (List.replicate 4 TapeSymbol.blank ++ L0))
(TapeSymbol.blank :: G₂))) = _
rw [moveDir_probe5 TapeSymbol.blank TapeSymbol.blank _ G₂ hG₂]
rfl
have hT6i : T6 i = cellsTape L2 (TapeSymbol.blank ::
List.replicate 5 TapeSymbol.blank ++ G₂.drop 5) := by
rw [hT6]; simp
-- ----- G: the shifter halts at once -----
obtain ⟨hGh, hGt⟩ := shiftSeg5_halt_spec i T6 (by rw [hT6i]; rfl)
-- ----- H: five left -----
have hH := moveUpTo_spec i 5 HeadMove.left (by omega) T6
set T7 := Function.update T6 i
(cellsTape L0 (List.replicate 5 TapeSymbol.blank ++ TapeSymbol.blank ::
List.replicate 5 TapeSymbol.blank ++ G₂.drop 5)) with hT7
have hHt : (((moveUpTo i 5 HeadMove.left).step^[5])
((moveUpTo i 5 HeadMove.left).startCfg T6)).tape = T7 := by
rw [moveUpTo_tape i 5 HeadMove.left (by omega) T6, hT7]
congr 1
rw [hT6i, hL2]
exact retreat5 L0 _ TapeSymbol.blank
have hT7i : T7 i = cellsTape L0
(List.replicate 5 TapeSymbol.blank ++ TapeSymbol.blank ::
List.replicate 5 TapeSymbol.blank ++ G₂.drop 5) := by
rw [hT7]; simp
-- ----- I: write the block -----
have hI := writeRun_spec i
(Block.toCells (blockFor (some (TapeSymbol.bit x)) first)) T7 _ _ hT7i
have hIt := writeRun_tape i
(Block.toCells (blockFor (some (TapeSymbol.bit x)) first)) T7 _ _ hT7i
-- ----- assemble -----
have c6 := chainStepC hH hHt hI
have c5 := chainStepC hGh hGt c6.1
have c4 := chainStepC hF hFt c5.1
have c4a := chainStepC hE hEt c4.1
have c3 := chainStepC hD hDt c4a.1
have c2 := chainStepC hC hCt' c3.1
refine ⟨d * 4 + 3 + 1 + (1 + 1 + (5 + 1 + (5 + 1 + (1 + 1 +
(5 + 1 + 6))))), G₂.drop 5, hG₂.drop 5, ?_, ?_, ?_⟩
· have hd0 : d = 0 := by rw [hd]; rfl
omega
· exact c2.1
· have hfin := c2.2
rw [c3.2] at hfin
rw [c4a.2] at hfin
rw [c4.2] at hfin
rw [c5.2] at hfin
rw [c6.2] at hfin
have hfin' : ((dilCont i (some (TapeSymbol.bit x)) first).step^[
d * 4 + 3 + 1 + (1 + 1 + (5 + 1 + (5 + 1 + (1 + 1 +
(5 + 1 + 6)))))])
((dilCont i (some (TapeSymbol.bit x)) first).startCfg T2) = _ :=
hfin
rw [hfin']
show (((writeRun i (Block.toCells (blockFor (some (TapeSymbol.bit x))
first))).step^[(Block.toCells (blockFor (some (TapeSymbol.bit x))
first)).length]) ((writeRun i (Block.toCells (blockFor
(some (TapeSymbol.bit x)) first))).startCfg T7)).tape = _
rw [hIt]
rw [hT7, hT6, hT5, hT4, hT3]
simp only [Function.update_idem]
congr 1
rw [show (List.replicate 5 TapeSymbol.blank ++ TapeSymbol.blank ::
List.replicate 5 TapeSymbol.blank ++ G₂.drop 5).drop
(Block.toCells (blockFor (some (TapeSymbol.bit x)) first)).length =
List.replicate 5 TapeSymbol.blank ++ G₂.drop 5 by
rw [Block.toCells_length]
rfl]
rw [hL0, show blockFor (some (TapeSymbol.bit x)) first =
inputBlock x first from rfl]
rw [show (Block.toCells (inputBlock x first)).reverse ++
((encodeBlocks done).reverse ++ [TapeSymbol.blank]) =
(encodeBlocks (done ++ [inputBlock x first])).reverse ++
[TapeSymbol.blank] by
rw [encodeBlocks_snoc, List.reverse_append]
simp]
simp
case inr =>
rw [List.concat_eq_append] at hrest
subst hrest
have hbc : (bitCells (ws ++ [w])).reverse =
TapeSymbol.bit w :: (bitCells ws).reverse := by
rw [bitCells_append]
simp
-- ----- D: one left, onto the remainder's last cell -----
obtain ⟨G₂, hG₂, hmv⟩ := moveDir_left_allBlank (TapeSymbol.bit w)
((bitCells ws).reverse ++ [TapeSymbol.blank] ++ L2) G hG
have hD := moveUpTo_spec i 1 HeadMove.left (by omega) T3
set T4 := Function.update T3 i
(cellsTape ((bitCells ws).reverse ++ [TapeSymbol.blank] ++ L2)
(TapeSymbol.bit w :: G₂)) with hT4
have hDt : (((moveUpTo i 1 HeadMove.left).step^[1])
((moveUpTo i 1 HeadMove.left).startCfg T3)).tape = T4 := by
rw [moveUpTo_tape i 1 HeadMove.left (by omega) T3, hT4]
congr 1
rw [Function.iterate_one, hT3i, hbc]
show moveDir HeadMove.left (cellsTape (TapeSymbol.bit w ::
((bitCells ws).reverse ++ [TapeSymbol.blank] ++ L2)) G) = _
rw [hmv]
have hT4i : T4 i = cellsTape
((bitCells ws).reverse ++ [TapeSymbol.blank] ++ L2)
(TapeSymbol.bit w :: G₂) := by
rw [hT4]; simp
-- ----- E,F: the probe -----
obtain ⟨cc, Lr, hcL⟩ : ∃ cc Lr,
(bitCells ws).reverse ++ [TapeSymbol.blank] ++ L2 = cc :: Lr := by
cases hws : (bitCells ws).reverse with
| nil => exact ⟨TapeSymbol.blank, L2, by simp⟩
| cons a t => exact ⟨a, t ++ [TapeSymbol.blank] ++ L2, by simp⟩
have hE := moveUpTo_spec i 5 HeadMove.right (by omega) T4
set T5 := Function.update T4 i
((moveDir HeadMove.right)^[5] (T4 i)) with hT5
have hEt : (((moveUpTo i 5 HeadMove.right).step^[5])
((moveUpTo i 5 HeadMove.right).startCfg T4)).tape = T5 := by
rw [moveUpTo_tape i 5 HeadMove.right (by omega) T4, hT5]
have hF := moveUpTo_spec i 5 HeadMove.left (by omega) T5
set T6 := Function.update T5 i
(cellsTape ((bitCells ws).reverse ++ [TapeSymbol.blank] ++ L2)
(TapeSymbol.bit w ::
List.replicate 5 TapeSymbol.blank ++ G₂.drop 5)) with hT6
have hFt : (((moveUpTo i 5 HeadMove.left).step^[5])
((moveUpTo i 5 HeadMove.left).startCfg T5)).tape = T6 := by
rw [moveUpTo_tape i 5 HeadMove.left (by omega) T5, hT6, hT5]
simp only [Function.update_idem, Function.update_self]
congr 1
rw [hT4i, hcL]
exact moveDir_probe5 cc (TapeSymbol.bit w) Lr G₂ hG₂
have hT6i : T6 i = cellsTape
((bitCells ws).reverse ++ [TapeSymbol.blank] ++ L2)
(TapeSymbol.bit w ::
List.replicate 5 TapeSymbol.blank ++ G₂.drop 5) := by
rw [hT6]; simp
-- ----- G: the shift -----
have hT6i' : T6 i = cellsTape
((bitCells ws).reverse ++ TapeSymbol.blank :: L2)
(TapeSymbol.bit w ::
List.replicate 5 TapeSymbol.blank ++ G₂.drop 5) := by
rw [hT6i]
congr 1
simp
obtain ⟨hGh, hGt⟩ := shiftSeg5_spec i (bitCells ws).reverse
(TapeSymbol.bit w) L2 (G₂.drop 5) T6 (by simp)
(fun c hc => bitCells_ne_blank ws c (List.mem_reverse.mp hc)) hT6i'
-- ----- H: five left -----
set T7g := Function.update T6 i
(cellsTape L2 (TapeSymbol.blank ::
List.replicate 5 TapeSymbol.blank ++
((bitCells ws).reverse.reverse ++ TapeSymbol.bit w ::
G₂.drop 5))) with hT7g
have hGt' : (((shiftSeg5 i).step^[11 * ((bitCells ws).reverse.length + 1)
+ 1]) ((shiftSeg5 i).startCfg T6)).tape = T7g := by
rw [hGt, hT7g]
have hT7gi : T7g i = cellsTape L2 (TapeSymbol.blank ::
List.replicate 5 TapeSymbol.blank ++
(bitCells (ws ++ [w]) ++ G₂.drop 5)) := by
rw [hT7g]
simp only [Function.update_self]
congr 2
rw [List.reverse_reverse, bitCells_append]
simp
have hH := moveUpTo_spec i 5 HeadMove.left (by omega) T7g
set T8 := Function.update T7g i
(cellsTape L0 (List.replicate 5 TapeSymbol.blank ++ TapeSymbol.blank ::
List.replicate 5 TapeSymbol.blank ++
(bitCells (ws ++ [w]) ++ G₂.drop 5))) with hT8
have hHt : (((moveUpTo i 5 HeadMove.left).step^[5])
((moveUpTo i 5 HeadMove.left).startCfg T7g)).tape = T8 := by
rw [moveUpTo_tape i 5 HeadMove.left (by omega) T7g, hT8]
congr 1
rw [hT7gi, hL2]
exact retreat5 L0 _ TapeSymbol.blank
have hT8i : T8 i = cellsTape L0
(List.replicate 5 TapeSymbol.blank ++ TapeSymbol.blank ::
List.replicate 5 TapeSymbol.blank ++
(bitCells (ws ++ [w]) ++ G₂.drop 5)) := by
rw [hT8]; simp
-- ----- I: write the block -----
have hI := writeRun_spec i
(Block.toCells (blockFor (some (TapeSymbol.bit x)) first)) T8 _ _ hT8i
have hIt := writeRun_tape i
(Block.toCells (blockFor (some (TapeSymbol.bit x)) first)) T8 _ _ hT8i
-- ----- assemble -----
have c6 := chainStepC hH hHt hI
have c5 := chainStepC hGh hGt' c6.1
have c4 := chainStepC hF hFt c5.1
have c4a := chainStepC hE hEt c4.1
have c3 := chainStepC hD hDt c4a.1
have c2 := chainStepC hC hCt' c3.1
refine ⟨d * 4 + 3 + 1 + (1 + 1 + (5 + 1 + (5 + 1 +
((11 * ((bitCells ws).reverse.length + 1) + 1) + 1 +
(5 + 1 + 6))))), G₂.drop 5, hG₂.drop 5, ?_, ?_, ?_⟩
· have hd0 : d = ws.length + 1 := by
rw [hd]
simp
have hlen : (bitCells ws).reverse.length = ws.length := by
simp [bitCells]
rw [hd0, hlen]
omega
· exact c2.1
· have hfin := c2.2
rw [c3.2] at hfin
rw [c4a.2] at hfin
rw [c4.2] at hfin
rw [c5.2] at hfin
rw [c6.2] at hfin
have hfin' : ((dilCont i (some (TapeSymbol.bit x)) first).step^[
d * 4 + 3 + 1 + (1 + 1 + (5 + 1 + (5 + 1 +
((11 * ((bitCells ws).reverse.length + 1) + 1) + 1 +
(5 + 1 + 6)))))])
((dilCont i (some (TapeSymbol.bit x)) first).startCfg T2) = _ :=
hfin
rw [hfin']
show (((writeRun i (Block.toCells (blockFor (some (TapeSymbol.bit x))
first))).step^[(Block.toCells (blockFor (some (TapeSymbol.bit x))
first)).length]) ((writeRun i (Block.toCells (blockFor
(some (TapeSymbol.bit x)) first))).startCfg T8)).tape = _
rw [hIt]
rw [hT8, hT7g, hT6, hT5, hT4, hT3]
simp only [Function.update_idem]
congr 1
rw [show (List.replicate 5 TapeSymbol.blank ++ TapeSymbol.blank ::
List.replicate 5 TapeSymbol.blank ++
(bitCells (ws ++ [w]) ++ G₂.drop 5)).drop
(Block.toCells (blockFor (some (TapeSymbol.bit x)) first)).length =
List.replicate 5 TapeSymbol.blank ++
(bitCells (ws ++ [w]) ++ G₂.drop 5) by
rw [Block.toCells_length]
rfl]
rw [hL0, show blockFor (some (TapeSymbol.bit x)) first =
inputBlock x first from rfl]
rw [show (Block.toCells (inputBlock x first)).reverse ++
((encodeBlocks done).reverse ++ [TapeSymbol.blank]) =
(encodeBlocks (done ++ [inputBlock x first])).reverse ++
[TapeSymbol.blank] by
rw [encodeBlocks_snoc, List.reverse_append]
simp]
simp
end SipserGacsLautemann