The segment shifter
Definitionsgl_shift_segThe segment shifter: the primitive for in-place input dilation under a three-symbol alphabet.
shiftSeg5 i expects the head on the rightmost cell of a non-blank segment. Each eleven-step cycle picks the cell up (erasing it), carries it five cells right, drops it, and retreats to the cell left of the vacated one; a pickup that reads blank halts the machine. Right-to-left order is what makes the target always blank — cells to the right have already moved. shiftSeg5_spec runs it over a whole segment: cost , every cell translated five right, head parked on the boundary blank, with the vacated cells left explicitly blank.
The probe. The zipper representation records only cells actually visited, so a segment's right context may be a materialised-blank history of any length — the visited-blank problem, again. moveDir_probe5 resolves it without touching the shift machine: walking five right and five back changes no content but forces at least five cells beyond the head to exist explicitly, after which every cycle can use the explicit six-cell window form. One lemma, pure tape algebra, no machine case analysis.
A design simplification found while building this. The dilation needs no separate shift-by-one pre-pass: running this same shifter once over the whole input creates a five-blank separator region, and the block-writing loop maintains five-blank separators invariantly — each iteration's six-cell block overwrites the five separators plus the harvested cell, and the shift vacates the next five. One primitive machine serves the entire dilation.
import Definitions.Def_sgl_merge_solution
/-!
# Shifting a segment right by five
Module G1 of DESIGN_finish_mission: the primitive for in-place input dilation.
`shiftSeg5 i` expects the head on the rightmost cell of a non-blank segment
whose right context is blank far enough out. Each eleven-step cycle picks the
cell up (erasing it), carries it five cells right, drops it, and returns to
the cell to the left of the vacated one; when the pickup reads blank the
machine halts. Right-to-left order is what makes the target cell always
blank: cells to the right have already moved.
-/
namespace SipserGacsLautemann
variable {tapes : Nat}
/-- Carry one cell five to the right, repeatedly, right to left. -/
def shiftSeg5 (i : Fin tapes) : TypedMachine tapes (Fin 12 × TapeSymbol) where
start := (⟨0, by omega⟩, TapeSymbol.blank)
transition := fun s symbols =>
if _h0 : s.1.val = 0 then
if symbols i = TapeSymbol.blank then
((⟨11, by omega⟩, TapeSymbol.blank),
fun j => (symbols j, HeadMove.stay))
else
((⟨1, by omega⟩, symbols i),
fun j =>
(if j = i then TapeSymbol.blank else symbols j,
if j = i then HeadMove.right else HeadMove.stay))
else if _h4 : s.1.val ≤ 4 then
((⟨s.1.val + 1, by omega⟩, s.2),
fun j => (symbols j, if j = i then HeadMove.right else HeadMove.stay))
else if _h5 : s.1.val = 5 then
((⟨6, by omega⟩, TapeSymbol.blank),
fun j =>
(if j = i then s.2 else symbols j,
if j = i then HeadMove.left else HeadMove.stay))
else if _h9 : s.1.val ≤ 9 then
((⟨s.1.val + 1, by omega⟩, TapeSymbol.blank),
fun j => (symbols j, if j = i then HeadMove.left else HeadMove.stay))
else if _h10 : s.1.val = 10 then
((⟨0, by omega⟩, TapeSymbol.blank),
fun j => (symbols j, if j = i then HeadMove.left else HeadMove.stay))
else (s, fun j => (symbols j, HeadMove.stay))
result := fun s => if s.1.val = 11 then some false else none
/-! ## Step equations -/
theorem shiftSeg5_step_halt (i : Fin tapes) (t : Fin tapes → Tape)
(hb : (t i).head = TapeSymbol.blank) :
(shiftSeg5 i).step ⟨(⟨0, by omega⟩, TapeSymbol.blank), t⟩ =
⟨(⟨11, by omega⟩, TapeSymbol.blank), t⟩ := by
have hres : (shiftSeg5 i).result (⟨0, by omega⟩, TapeSymbol.blank) = none := by
simp [shiftSeg5]
simp only [TypedMachine.step, hres]
simp only [shiftSeg5, hb]
norm_num
funext j
simp [Tape.write_head_self, Tape.move]
theorem shiftSeg5_step_pick (i : Fin tapes) (t : Fin tapes → Tape)
(hb : (t i).head ≠ TapeSymbol.blank) :
(shiftSeg5 i).step ⟨(⟨0, by omega⟩, TapeSymbol.blank), t⟩ =
⟨(⟨1, by omega⟩, (t i).head),
Function.update t i
(moveDir HeadMove.right (Tape.write (t i) TapeSymbol.blank))⟩ := by
have hres : (shiftSeg5 i).result (⟨0, by omega⟩, TapeSymbol.blank) = none := by
simp [shiftSeg5]
simp only [TypedMachine.step, hres]
simp only [shiftSeg5]
norm_num [hb]
funext j
by_cases hj : j = i
· subst hj
simp [moveDir]
· simp [hj, Function.update_of_ne hj, Tape.write_head_self, Tape.move]
theorem shiftSeg5_step_right (i : Fin tapes) (t : Fin tapes → Tape)
(k : Nat) (hk1 : 1 ≤ k) (hk4 : k ≤ 4) (x : TapeSymbol) :
(shiftSeg5 i).step ⟨(⟨k, by omega⟩, x), t⟩ =
⟨(⟨k + 1, by omega⟩, x),
Function.update t i (moveDir HeadMove.right (t i))⟩ := by
have hres : (shiftSeg5 i).result (⟨k, by omega⟩, x) = none := by
simp only [shiftSeg5]
exact if_neg (by omega)
simp only [TypedMachine.step, hres]
simp only [shiftSeg5]
rw [dif_neg (show ¬ (k = 0) by omega)]
rw [dif_pos (show k ≤ 4 from hk4)]
congr 1
funext j
by_cases hj : j = i
· subst hj
simp [moveDir, Tape.write_head_self]
· simp [hj, Function.update_of_ne hj, Tape.write_head_self, Tape.move]
theorem shiftSeg5_step_drop (i : Fin tapes) (t : Fin tapes → Tape)
(x : TapeSymbol) :
(shiftSeg5 i).step ⟨(⟨5, by omega⟩, x), t⟩ =
⟨(⟨6, by omega⟩, TapeSymbol.blank),
Function.update t i (moveDir HeadMove.left (Tape.write (t i) x))⟩ := by
have hres : (shiftSeg5 i).result (⟨5, by omega⟩, x) = none := by
simp [shiftSeg5]
simp only [TypedMachine.step, hres]
simp only [shiftSeg5]
norm_num
funext j
by_cases hj : j = i
· subst hj
simp [moveDir]
· simp [hj, Function.update_of_ne hj, Tape.write_head_self, Tape.move]
theorem shiftSeg5_step_left (i : Fin tapes) (t : Fin tapes → Tape)
(k : Nat) (hk6 : 6 ≤ k) (hk9 : k ≤ 9) (x : TapeSymbol) :
(shiftSeg5 i).step ⟨(⟨k, by omega⟩, x), t⟩ =
⟨(⟨k + 1, by omega⟩, TapeSymbol.blank),
Function.update t i (moveDir HeadMove.left (t i))⟩ := by
have hres : (shiftSeg5 i).result (⟨k, by omega⟩, x) = none := by
simp only [shiftSeg5]
exact if_neg (by omega)
simp only [TypedMachine.step, hres]
simp only [shiftSeg5]
rw [dif_neg (show ¬ (k = 0) by omega), dif_neg (show ¬ (k ≤ 4) by omega),
dif_neg (show ¬ (k = 5) by omega), dif_pos (show k ≤ 9 from hk9)]
congr 1
funext j
by_cases hj : j = i
· subst hj
simp [moveDir, Tape.write_head_self]
· simp [hj, Function.update_of_ne hj, Tape.write_head_self, Tape.move]
theorem shiftSeg5_step_home (i : Fin tapes) (t : Fin tapes → Tape)
(x : TapeSymbol) :
(shiftSeg5 i).step ⟨(⟨10, by omega⟩, x), t⟩ =
⟨(⟨0, by omega⟩, TapeSymbol.blank),
Function.update t i (moveDir HeadMove.left (t i))⟩ := by
have hres : (shiftSeg5 i).result (⟨10, by omega⟩, x) = none := by
simp [shiftSeg5]
simp only [TypedMachine.step, hres]
simp only [shiftSeg5]
norm_num
funext j
by_cases hj : j = i
· subst hj
simp [moveDir, Tape.write_head_self]
· simp [hj, Function.update_of_ne hj, Tape.write_head_self, Tape.move]
/-! ## Blank-context move helpers -/
theorem moveDir_right_blank (L R : List TapeSymbol) (hR : AllBlank R) :
moveDir HeadMove.right (cellsTape L R) =
cellsTape (TapeSymbol.blank :: L) R.tail := by
cases R with
| nil => exact cellsTape_moveRight_nil L
| cons r R' =>
have hr : r = TapeSymbol.blank := hR r (by simp)
rw [show cellsTape L (r :: R') = cellsTape L (TapeSymbol.blank :: R') by
rw [hr]]
exact cellsTape_moveRight L TapeSymbol.blank R'
theorem write_cellsTape (L R : List TapeSymbol) (y : TapeSymbol) :
Tape.write (cellsTape L R) y = cellsTape L (y :: R.tail) := by
cases R <;> rfl
/-! ## One eleven-step cycle, explicit-cons right context -/
set_option maxHeartbeats 1000000 in
/-- One cycle over a six-cell window: the head cell moves five right, the
window's other five cells are preserved, the head retreats one left of the
vacated cell. -/
theorem shiftSeg5_cycle (i : Fin tapes) (T : Fin tapes → Tape)
(c y r₁ r₂ r₃ r₄ r₅ : TapeSymbol) (L Q : List TapeSymbol)
(hy : y ≠ TapeSymbol.blank)
(hTi : T i = cellsTape (c :: L) (y :: r₁ :: r₂ :: r₃ :: r₄ :: r₅ :: Q)) :
(((shiftSeg5 i).step^[11]) ⟨(⟨0, by omega⟩, TapeSymbol.blank), T⟩ :
TypedConfiguration tapes (Fin 12 × TapeSymbol)) =
⟨(⟨0, by omega⟩, TapeSymbol.blank),
Function.update T i
(cellsTape L (c :: TapeSymbol.blank :: r₁ :: r₂ :: r₃ :: r₄ ::
y :: Q))⟩ ∧
∀ j, j < 11 →
((((shiftSeg5 i).step^[j]) ⟨(⟨0, by omega⟩, TapeSymbol.blank), T⟩ :
TypedConfiguration tapes (Fin 12 × TapeSymbol))).state.1.val ≠ 11 := by
have hy' : (T i).head = y := by rw [hTi]; rfl
have e0 := shiftSeg5_step_pick i T (by rw [hy']; exact hy)
rw [hy'] at e0
set T1 := Function.update T i
(cellsTape (TapeSymbol.blank :: c :: L)
(r₁ :: r₂ :: r₃ :: r₄ :: r₅ :: Q)) with hT1
have e0' : (shiftSeg5 i).step ⟨(⟨0, by omega⟩, TapeSymbol.blank), T⟩ =
⟨(⟨1, by omega⟩, y), T1⟩ := by
rw [e0, hT1, hTi, write_cellsTape]
rw [show (y :: r₁ :: r₂ :: r₃ :: r₄ :: r₅ :: Q).tail =
r₁ :: r₂ :: r₃ :: r₄ :: r₅ :: Q from rfl]
rw [cellsTape_moveRight]
have hT1i : T1 i = cellsTape (TapeSymbol.blank :: c :: L)
(r₁ :: r₂ :: r₃ :: r₄ :: r₅ :: Q) := by rw [hT1]; simp
-- four carries right
have e1 := shiftSeg5_step_right i T1 1 (by omega) (by omega) y
set T2 := Function.update T1 i
(cellsTape (r₁ :: TapeSymbol.blank :: c :: L) (r₂ :: r₃ :: r₄ :: r₅ :: Q))
with hT2
have e1' : (shiftSeg5 i).step ⟨(⟨1, by omega⟩, y), T1⟩ =
⟨(⟨2, by omega⟩, y), T2⟩ := by
rw [e1, hT2, hT1i, cellsTape_moveRight]
have hT2i : T2 i = cellsTape (r₁ :: TapeSymbol.blank :: c :: L)
(r₂ :: r₃ :: r₄ :: r₅ :: Q) := by rw [hT2]; simp
have e2 := shiftSeg5_step_right i T2 2 (by omega) (by omega) y
set T3 := Function.update T2 i
(cellsTape (r₂ :: r₁ :: TapeSymbol.blank :: c :: L) (r₃ :: r₄ :: r₅ :: Q))
with hT3
have e2' : (shiftSeg5 i).step ⟨(⟨2, by omega⟩, y), T2⟩ =
⟨(⟨3, by omega⟩, y), T3⟩ := by
rw [e2, hT3, hT2i, cellsTape_moveRight]
have hT3i : T3 i = cellsTape (r₂ :: r₁ :: TapeSymbol.blank :: c :: L)
(r₃ :: r₄ :: r₅ :: Q) := by rw [hT3]; simp
have e3 := shiftSeg5_step_right i T3 3 (by omega) (by omega) y
set T4 := Function.update T3 i
(cellsTape (r₃ :: r₂ :: r₁ :: TapeSymbol.blank :: c :: L)
(r₄ :: r₅ :: Q)) with hT4
have e3' : (shiftSeg5 i).step ⟨(⟨3, by omega⟩, y), T3⟩ =
⟨(⟨4, by omega⟩, y), T4⟩ := by
rw [e3, hT4, hT3i, cellsTape_moveRight]
have hT4i : T4 i = cellsTape (r₃ :: r₂ :: r₁ :: TapeSymbol.blank :: c :: L)
(r₄ :: r₅ :: Q) := by rw [hT4]; simp
have e4 := shiftSeg5_step_right i T4 4 (by omega) (by omega) y
set T5 := Function.update T4 i
(cellsTape (r₄ :: r₃ :: r₂ :: r₁ :: TapeSymbol.blank :: c :: L)
(r₅ :: Q)) with hT5
have e4' : (shiftSeg5 i).step ⟨(⟨4, by omega⟩, y), T4⟩ =
⟨(⟨5, by omega⟩, y), T5⟩ := by
rw [e4, hT5, hT4i, cellsTape_moveRight]
have hT5i : T5 i = cellsTape
(r₄ :: r₃ :: r₂ :: r₁ :: TapeSymbol.blank :: c :: L) (r₅ :: Q) := by
rw [hT5]; simp
-- drop
have e5 := shiftSeg5_step_drop i T5 y
set T6 := Function.update T5 i
(cellsTape (r₃ :: r₂ :: r₁ :: TapeSymbol.blank :: c :: L)
(r₄ :: y :: Q)) with hT6
have e5' : (shiftSeg5 i).step ⟨(⟨5, by omega⟩, y), T5⟩ =
⟨(⟨6, by omega⟩, TapeSymbol.blank), T6⟩ := by
rw [e5, hT6, hT5i, write_cellsTape]
rw [show (r₅ :: Q).tail = Q from rfl]
rw [cellsTape_moveLeft]
have hT6i : T6 i = cellsTape (r₃ :: r₂ :: r₁ :: TapeSymbol.blank :: c :: L)
(r₄ :: y :: Q) := by rw [hT6]; simp
-- five retreats
have e6 := shiftSeg5_step_left i T6 6 (by omega) (by omega) TapeSymbol.blank
set T7 := Function.update T6 i
(cellsTape (r₂ :: r₁ :: TapeSymbol.blank :: c :: L)
(r₃ :: r₄ :: y :: Q)) with hT7
have e6' : (shiftSeg5 i).step ⟨(⟨6, by omega⟩, TapeSymbol.blank), T6⟩ =
⟨(⟨7, by omega⟩, TapeSymbol.blank), T7⟩ := by
rw [e6, hT7, hT6i, cellsTape_moveLeft]
have hT7i : T7 i = cellsTape (r₂ :: r₁ :: TapeSymbol.blank :: c :: L)
(r₃ :: r₄ :: y :: Q) := by rw [hT7]; simp
have e7 := shiftSeg5_step_left i T7 7 (by omega) (by omega) TapeSymbol.blank
set T8 := Function.update T7 i
(cellsTape (r₁ :: TapeSymbol.blank :: c :: L)
(r₂ :: r₃ :: r₄ :: y :: Q)) with hT8
have e7' : (shiftSeg5 i).step ⟨(⟨7, by omega⟩, TapeSymbol.blank), T7⟩ =
⟨(⟨8, by omega⟩, TapeSymbol.blank), T8⟩ := by
rw [e7, hT8, hT7i, cellsTape_moveLeft]
have hT8i : T8 i = cellsTape (r₁ :: TapeSymbol.blank :: c :: L)
(r₂ :: r₃ :: r₄ :: y :: Q) := by rw [hT8]; simp
have e8 := shiftSeg5_step_left i T8 8 (by omega) (by omega) TapeSymbol.blank
set T9 := Function.update T8 i
(cellsTape (TapeSymbol.blank :: c :: L)
(r₁ :: r₂ :: r₃ :: r₄ :: y :: Q)) with hT9
have e8' : (shiftSeg5 i).step ⟨(⟨8, by omega⟩, TapeSymbol.blank), T8⟩ =
⟨(⟨9, by omega⟩, TapeSymbol.blank), T9⟩ := by
rw [e8, hT9, hT8i, cellsTape_moveLeft]
have hT9i : T9 i = cellsTape (TapeSymbol.blank :: c :: L)
(r₁ :: r₂ :: r₃ :: r₄ :: y :: Q) := by rw [hT9]; simp
have e9 := shiftSeg5_step_left i T9 9 (by omega) (by omega) TapeSymbol.blank
set T10 := Function.update T9 i
(cellsTape (c :: L)
(TapeSymbol.blank :: r₁ :: r₂ :: r₃ :: r₄ :: y :: Q)) with hT10
have e9' : (shiftSeg5 i).step ⟨(⟨9, by omega⟩, TapeSymbol.blank), T9⟩ =
⟨(⟨10, by omega⟩, TapeSymbol.blank), T10⟩ := by
rw [e9, hT10, hT9i, cellsTape_moveLeft]
have hT10i : T10 i = cellsTape (c :: L)
(TapeSymbol.blank :: r₁ :: r₂ :: r₃ :: r₄ :: y :: Q) := by
rw [hT10]; simp
have e10 := shiftSeg5_step_home i T10 TapeSymbol.blank
set T11 := Function.update T10 i
(cellsTape L
(c :: TapeSymbol.blank :: r₁ :: r₂ :: r₃ :: r₄ :: y :: Q)) with hT11
have e10' : (shiftSeg5 i).step ⟨(⟨10, by omega⟩, TapeSymbol.blank), T10⟩ =
⟨(⟨0, by omega⟩, TapeSymbol.blank), T11⟩ := by
rw [e10, hT11, hT10i, cellsTape_moveLeft]
-- assemble
have hflat : T11 = Function.update T i
(cellsTape L (c :: TapeSymbol.blank :: r₁ :: r₂ :: r₃ :: r₄ ::
y :: Q)) := by
rw [hT11, hT10, hT9, hT8, hT7, hT6, hT5, hT4, hT3, hT2, hT1]
simp only [Function.update_idem]
set M := shiftSeg5 i
set c₀ : TypedConfiguration tapes (Fin 12 × TapeSymbol) :=
⟨(⟨0, by omega⟩, TapeSymbol.blank), T⟩ with hc₀
have p1 : (M.step^[1]) c₀ = ⟨(⟨1, by omega⟩, y), T1⟩ := by
rw [Function.iterate_one, hc₀, e0']
have p2 : (M.step^[2]) c₀ = ⟨(⟨2, by omega⟩, y), T2⟩ := by
show (M.step^[1+1]) c₀ = _
rw [Function.iterate_add_apply, p1, Function.iterate_one, e1']
have p3 : (M.step^[3]) c₀ = ⟨(⟨3, by omega⟩, y), T3⟩ := by
show (M.step^[1+2]) c₀ = _
rw [Function.iterate_add_apply, p2, Function.iterate_one, e2']
have p4 : (M.step^[4]) c₀ = ⟨(⟨4, by omega⟩, y), T4⟩ := by
show (M.step^[1+3]) c₀ = _
rw [Function.iterate_add_apply, p3, Function.iterate_one, e3']
have p5 : (M.step^[5]) c₀ = ⟨(⟨5, by omega⟩, y), T5⟩ := by
show (M.step^[1+4]) c₀ = _
rw [Function.iterate_add_apply, p4, Function.iterate_one, e4']
have p6 : (M.step^[6]) c₀ = ⟨(⟨6, by omega⟩, TapeSymbol.blank), T6⟩ := by
show (M.step^[1+5]) c₀ = _
rw [Function.iterate_add_apply, p5, Function.iterate_one, e5']
have p7 : (M.step^[7]) c₀ = ⟨(⟨7, by omega⟩, TapeSymbol.blank), T7⟩ := by
show (M.step^[1+6]) c₀ = _
rw [Function.iterate_add_apply, p6, Function.iterate_one, e6']
have p8 : (M.step^[8]) c₀ = ⟨(⟨8, by omega⟩, TapeSymbol.blank), T8⟩ := by
show (M.step^[1+7]) c₀ = _
rw [Function.iterate_add_apply, p7, Function.iterate_one, e7']
have p9 : (M.step^[9]) c₀ = ⟨(⟨9, by omega⟩, TapeSymbol.blank), T9⟩ := by
show (M.step^[1+8]) c₀ = _
rw [Function.iterate_add_apply, p8, Function.iterate_one, e8']
have p10 : (M.step^[10]) c₀ = ⟨(⟨10, by omega⟩, TapeSymbol.blank), T10⟩ := by
show (M.step^[1+9]) c₀ = _
rw [Function.iterate_add_apply, p9, Function.iterate_one, e9']
have p11 : (M.step^[11]) c₀ = ⟨(⟨0, by omega⟩, TapeSymbol.blank), T11⟩ := by
show (M.step^[1+10]) c₀ = _
rw [Function.iterate_add_apply, p10, Function.iterate_one, e10']
refine ⟨by rw [p11, hflat], ?_⟩
intro j hj
interval_cases j
· simp [hc₀]
· rw [p1]; simp
· rw [p2]; simp
· rw [p3]; simp
· rw [p4]; simp
· rw [p5]; simp
· rw [p6]; simp
· rw [p7]; simp
· rw [p8]; simp
· rw [p9]; simp
· rw [p10]; simp
/-! ## The probe: normalising the right context
Walking five right and five back leaves the tape's *content* untouched but
forces at least five cells beyond the head to exist explicitly in the zipper —
materialised blanks become real. This is what lets every shift cycle use the
explicit-cons form regardless of excursion history. -/
theorem allBlank_eq_replicate {G : List TapeSymbol} (hG : AllBlank G) :
G = List.replicate G.length TapeSymbol.blank := by
induction G with
| nil => rfl
| cons c G' ih =>
have hc : c = TapeSymbol.blank := hG c (by simp)
have hG' : AllBlank G' := fun x hx => hG x (by simp [hx])
rw [List.length_cons, List.replicate_succ, hc]
exact congrArg _ (by conv_lhs => rw [ih hG'])
set_option maxHeartbeats 1000000 in
theorem moveDir_probe5 (c y : TapeSymbol) (L G : List TapeSymbol)
(hG : AllBlank G) :
((moveDir HeadMove.left)^[5]) (((moveDir HeadMove.right)^[5])
(cellsTape (c :: L) (y :: G))) =
cellsTape (c :: L)
(y :: List.replicate 5 TapeSymbol.blank ++ G.drop 5) := by
rw [allBlank_eq_replicate hG]
rcases Nat.lt_or_ge G.length 5 with h5 | h5
· interval_cases h : G.length <;>
simp [List.replicate, cellsTape, moveDir, Tape.move,
Function.iterate_succ_apply, Function.iterate_zero]
· obtain ⟨d, hd⟩ := Nat.exists_eq_add_of_le h5
rw [hd]
rw [show List.replicate (5 + d) TapeSymbol.blank =
List.replicate 5 TapeSymbol.blank ++ List.replicate d TapeSymbol.blank
from (List.replicate_add 5 d _).symm ▸ rfl]
rw [show (List.replicate 5 TapeSymbol.blank ++
List.replicate d TapeSymbol.blank).drop 5 =
List.replicate d TapeSymbol.blank by
rw [List.drop_append_of_le_length (by simp)]
simp]
-- five explicit cells: round trip is the identity
simp only [List.replicate, List.cons_append, List.nil_append]
simp [Function.iterate_succ_apply, cellsTape_moveRight,
cellsTape_moveLeft, moveDir, Tape.move, cellsTape]
/-! ## The whole segment -/
theorem shiftSeg5_run (i : Fin tapes) :
∀ (ls : List TapeSymbol) (h : TapeSymbol) (B Q : List TapeSymbol)
(T : Fin tapes → Tape),
h ≠ TapeSymbol.blank → (∀ c ∈ ls, c ≠ TapeSymbol.blank) →
T i = cellsTape (ls ++ TapeSymbol.blank :: B)
(h :: List.replicate 5 TapeSymbol.blank ++ Q) →
(((shiftSeg5 i).step^[11 * (ls.length + 1)])
⟨(⟨0, by omega⟩, TapeSymbol.blank), T⟩ :
TypedConfiguration tapes (Fin 12 × TapeSymbol)) =
⟨(⟨0, by omega⟩, TapeSymbol.blank),
Function.update T i
(cellsTape B (TapeSymbol.blank ::
List.replicate 5 TapeSymbol.blank ++ (ls.reverse ++ h :: Q)))⟩ ∧
∀ j, j < 11 * (ls.length + 1) →
((((shiftSeg5 i).step^[j])
⟨(⟨0, by omega⟩, TapeSymbol.blank), T⟩ :
TypedConfiguration tapes (Fin 12 × TapeSymbol))).state.1.val ≠ 11 := by
intro ls
induction ls with
| nil =>
intro h B Q T hh _ hTi
have hshape : T i = cellsTape (TapeSymbol.blank :: B)
(h :: TapeSymbol.blank :: TapeSymbol.blank :: TapeSymbol.blank ::
TapeSymbol.blank :: TapeSymbol.blank :: Q) := by
rw [hTi]; rfl
obtain ⟨hrun, hfresh⟩ := shiftSeg5_cycle i T TapeSymbol.blank h
TapeSymbol.blank TapeSymbol.blank TapeSymbol.blank TapeSymbol.blank
TapeSymbol.blank B Q hh hshape
constructor
· rw [show 11 * (([] : List TapeSymbol).length + 1) = 11 by simp, hrun]
rfl
· intro j hj
exact hfresh j (by simpa using hj)
| cons l ls' ih =>
intro h B Q T hh hls hTi
have hl : l ≠ TapeSymbol.blank := hls l (by simp)
have hls' : ∀ c ∈ ls', c ≠ TapeSymbol.blank :=
fun c hc => hls c (by simp [hc])
have hshape : T i = cellsTape (l :: (ls' ++ TapeSymbol.blank :: B))
(h :: TapeSymbol.blank :: TapeSymbol.blank :: TapeSymbol.blank ::
TapeSymbol.blank :: TapeSymbol.blank :: Q) := by
rw [hTi]; rfl
obtain ⟨hcyc, hcfresh⟩ := shiftSeg5_cycle i T l h
TapeSymbol.blank TapeSymbol.blank TapeSymbol.blank TapeSymbol.blank
TapeSymbol.blank (ls' ++ TapeSymbol.blank :: B) Q hh hshape
set T' := Function.update T i
(cellsTape (ls' ++ TapeSymbol.blank :: B)
(l :: TapeSymbol.blank :: TapeSymbol.blank :: TapeSymbol.blank ::
TapeSymbol.blank :: TapeSymbol.blank :: h :: Q)) with hT'
have hT'i : T' i = cellsTape (ls' ++ TapeSymbol.blank :: B)
(l :: List.replicate 5 TapeSymbol.blank ++ (h :: Q)) := by
rw [hT']; simp
obtain ⟨hrun', hfresh'⟩ := ih l B (h :: Q) T' hl hls' hT'i
have hsplit : 11 * ((l :: ls').length + 1) =
11 * (ls'.length + 1) + 11 := by simp [List.length_cons]; ring
constructor
· rw [hsplit, Function.iterate_add_apply, hcyc, hrun', hT']
simp only [Function.update_idem]
rw [show ls'.reverse ++ l :: (h :: Q) =
(l :: ls').reverse ++ h :: Q by simp]
· intro j hj
rcases Nat.lt_or_ge j 11 with hj11 | hj11
· exact hcfresh j hj11
· obtain ⟨j', rfl⟩ := Nat.exists_eq_add_of_le hj11
rw [Nat.add_comm, Function.iterate_add_apply, hcyc]
exact hfresh' j' (by rw [hsplit] at hj; omega)
/-- **The segment shifter, as a subroutine.** `ls` is the segment's cells
left of the head cell `h`, nearest first; everything moves five right, the
head retreats to the boundary blank. -/
theorem shiftSeg5_spec (i : Fin tapes) (ls : List TapeSymbol)
(h : TapeSymbol) (B Q : List TapeSymbol) (T : Fin tapes → Tape)
(hh : h ≠ TapeSymbol.blank) (hls : ∀ c ∈ ls, c ≠ TapeSymbol.blank)
(hTi : T i = cellsTape (ls ++ TapeSymbol.blank :: B)
(h :: List.replicate 5 TapeSymbol.blank ++ Q)) :
HaltsExactly (shiftSeg5 i) ((shiftSeg5 i).startCfg T)
(11 * (ls.length + 1) + 1) false ∧
(((shiftSeg5 i).step^[11 * (ls.length + 1) + 1])
((shiftSeg5 i).startCfg T)).tape =
Function.update T i
(cellsTape B (TapeSymbol.blank ::
List.replicate 5 TapeSymbol.blank ++ (ls.reverse ++ h :: Q))) := by
obtain ⟨hrun, hfresh⟩ := shiftSeg5_run i ls h B Q T hh hls hTi
have hstart : (shiftSeg5 i).startCfg T =
(⟨(⟨0, by omega⟩, TapeSymbol.blank), T⟩ :
TypedConfiguration tapes (Fin 12 × TapeSymbol)) := rfl
set Tf := Function.update T i
(cellsTape B (TapeSymbol.blank ::
List.replicate 5 TapeSymbol.blank ++ (ls.reverse ++ h :: Q))) with hTf
have hTfi : (Tf i).head = TapeSymbol.blank := by
rw [hTf]; simp; rfl
have hlast : (((shiftSeg5 i).step^[11 * (ls.length + 1) + 1])
((shiftSeg5 i).startCfg T) :
TypedConfiguration tapes (Fin 12 × TapeSymbol)) =
⟨(⟨11, by omega⟩, TapeSymbol.blank), Tf⟩ := by
rw [Function.iterate_succ_apply', hstart, hrun, shiftSeg5_step_halt i Tf hTfi]
refine ⟨⟨?_, ?_⟩, ?_⟩
· rw [hlast]
rfl
· intro j hj
rcases Nat.lt_or_ge j (11 * (ls.length + 1)) with hlt | hge
· have hne := hfresh j hlt
rw [hstart]
exact if_neg hne
· have hj' : j = 11 * (ls.length + 1) := by omega
subst hj'
rw [hstart, hrun]
rfl
· rw [hlast]
end SipserGacsLautemann