The dilation pre-pass
Definitionsgl_dilation_precomplexity-theoryinfrastructuretheoretical-computer-scienceturing-machines
The pre-pass: from the raw input tape to the first round's layout.
One left step materialises the home blank; one right step returns to position zero; the whole input is then shifted five right by the same primitive the rounds use, which simultaneously opens the first five-blank separator and leaves the head on home; a final right step lands on the separator start. prePass_spec: cost at most , ending exactly on the round invariant with no blocks written — which is what the loop consumes.
This is where the design collapse recorded earlier pays off: the planned shift-by-one pre-pass machine, with its own cycle and correctness proofs, was never needed. Shifting by five with the existing shifter does both jobs at once.
Definition code
import Definitions.Def_sgl_dilation_loop
/-!
# The pre-pass
Module G2's last machine: from the raw input tape to the first round's layout.
One left step materialises the home blank; one right step returns to position
zero; then the whole input is shifted five right by the same primitive the
rounds use, which both creates the first five-blank separator and leaves the
head on home; a final right step lands on the separator start.
-/
namespace SipserGacsLautemann
variable {tapes : Nat}
theorem ofBits_eq_cellsTape (xs : List Bool) :
Tape.ofBits xs = cellsTape [] (bitCells xs) := by
cases xs with
| nil => rfl
| cons x xs' => rfl
set_option maxHeartbeats 1000000 in
/-- Home, then position zero. -/
theorem prePass_enter (i : Fin tapes) (xs : List Bool) (G : List TapeSymbol)
(T : Fin tapes → Tape)
(hT : T i = cellsTape [] (bitCells xs ++ G)) :
((moveDir HeadMove.right) ((moveDir HeadMove.left) (T i))) =
cellsTape [TapeSymbol.blank] (bitCells xs ++ G) := by
rw [hT]
cases h : bitCells xs ++ G with
| nil =>
show moveDir HeadMove.right (moveDir HeadMove.left
(cellsTape [] [])) = _
rfl
| cons c R =>
show moveDir HeadMove.right (moveDir HeadMove.left
(cellsTape [] (c :: R))) = _
rw [show moveDir HeadMove.left (cellsTape [] (c :: R)) =
cellsTape [] (TapeSymbol.blank :: c :: R) from rfl]
rw [cellsTape_moveRight]
set_option maxHeartbeats 4000000 in
/-- **The pre-pass on a non-empty input.** Five blanks are opened before the
input and the head lands on the first separator: the round invariant with no
blocks written. -/
theorem prePass_spec (i : Fin tapes) (x : Bool) (rest : List Bool)
(G : List TapeSymbol) (T : Fin tapes → Tape) (hG : AllBlank G)
(hT : T i = cellsTape [] (bitCells (x :: rest) ++ G)) :
∃ (cost : Nat) (G' : List TapeSymbol), AllBlank G' ∧
cost ≤ 15 * rest.length + 40 ∧
HaltsExactly (prePass i) ((prePass i).startCfg T) cost true ∧
(((prePass i).step^[cost]) ((prePass i).startCfg T)).tape =
Function.update T i (dilTape [] (x :: rest) G') := by
classical
-- A: one left
have hA := moveUpTo_spec i 1 HeadMove.left (by omega) T
set T1 := Function.update T i ((moveDir HeadMove.left) (T i)) with hT1
have hAt : (((moveUpTo i 1 HeadMove.left).step^[1])
((moveUpTo i 1 HeadMove.left).startCfg T)).tape = T1 := by
rw [moveUpTo_tape i 1 HeadMove.left (by omega) T, hT1]
rfl
-- B: one right, back to position zero
have hB := moveUpTo_spec i 1 HeadMove.right (by omega) T1
set T2 := Function.update T i
(cellsTape [TapeSymbol.blank] (bitCells (x :: rest) ++ G)) with hT2
have hBt : (((moveUpTo i 1 HeadMove.right).step^[1])
((moveUpTo i 1 HeadMove.right).startCfg T1)).tape = T2 := by
rw [moveUpTo_tape i 1 HeadMove.right (by omega) T1, hT2, hT1]
simp only [Function.update_idem, Function.update_self]
congr 1
rw [Function.iterate_one]
exact prePass_enter i (x :: rest) G T hT
have hT2i : T2 i =
cellsTape [TapeSymbol.blank] (bitCells (x :: rest) ++ G) := by
rw [hT2]; simp
-- C: scan right to the end of the input
set d := rest.length with hd
have hadv : ∀ k, k ≤ d →
((moveDir HeadMove.right)^[k + 1]) (T2 i) =
cellsTape ((bitCells ((x :: rest).take (k + 1))).reverse ++
[TapeSymbol.blank]) (bitCells ((x :: rest).drop (k + 1)) ++ G) := by
intro k hk
rw [hT2i]
have hsplit : bitCells (x :: rest) ++ G =
bitCells ((x :: rest).take (k + 1)) ++
(bitCells ((x :: rest).drop (k + 1)) ++ G) := by
rw [← List.append_assoc, ← bitCells_append, List.take_append_drop]
have hlen : (bitCells ((x :: rest).take (k + 1))).length = k + 1 := by
simp [bitCells, List.length_take]
omega
rw [hsplit]
have hc := cellsTape_advance (bitCells ((x :: rest).take (k + 1)))
[TapeSymbol.blank] (bitCells ((x :: rest).drop (k + 1)) ++ G)
rw [hlen] at hc
exact hc
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, (x :: rest).drop (k + 1) = y :: ys := by
cases hdk : (x :: rest).drop (k + 1) 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 (x :: rest).drop (d + 1) = [] by
rw [hd]; simp]
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 (x :: rest)).reverse ++ [TapeSymbol.blank]) 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 (x :: rest).drop (d + 1) = [] by rw [hd]; simp,
show (x :: rest).take (d + 1) = x :: rest by rw [hd]; simp]
simp
have hT3i : T3 i =
cellsTape ((bitCells (x :: rest)).reverse ++ [TapeSymbol.blank]) G := by
rw [hT3]; simp
-- D: one left, onto the last input cell
have hbc : (bitCells (x :: rest)).reverse =
(bitCells (x :: rest)).reverse := rfl
obtain ⟨lc, Lr, hLr⟩ : ∃ lc Lr,
(bitCells (x :: rest)).reverse = lc :: Lr := by
cases hrv : (bitCells (x :: rest)).reverse with
| nil =>
exfalso
have := congrArg List.length hrv
simp [bitCells] at this
| cons a t => exact ⟨a, t, rfl⟩
obtain ⟨G₂, hG₂, hmv⟩ := moveDir_left_allBlank lc (Lr ++ [TapeSymbol.blank])
G hG
have hD := moveUpTo_spec i 1 HeadMove.left (by omega) T3
set T4 := Function.update T3 i
(cellsTape (Lr ++ [TapeSymbol.blank]) (lc :: 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, hLr]
show moveDir HeadMove.left
(cellsTape (lc :: (Lr ++ [TapeSymbol.blank])) G) = _
rw [hmv]
have hT4i : T4 i = cellsTape (Lr ++ [TapeSymbol.blank]) (lc :: G₂) := by
rw [hT4]; simp
-- E,F: the probe
obtain ⟨cc, Lr2, hcL⟩ : ∃ cc Lr2, Lr ++ [TapeSymbol.blank] = cc :: Lr2 := by
cases hL : Lr with
| nil => exact ⟨TapeSymbol.blank, [], by simp⟩
| cons a t => exact ⟨a, t ++ [TapeSymbol.blank], 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 (Lr ++ [TapeSymbol.blank])
(lc :: 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 lc Lr2 G₂ hG₂
have hT6i : T6 i = cellsTape (Lr ++ [TapeSymbol.blank])
(lc :: List.replicate 5 TapeSymbol.blank ++ G₂.drop 5) := by
rw [hT6]; simp
-- G: the shift
have hT6i' : T6 i = cellsTape (Lr ++ TapeSymbol.blank :: [])
(lc :: List.replicate 5 TapeSymbol.blank ++ G₂.drop 5) := by
rw [hT6i]
have hLrnb : ∀ c ∈ Lr, c ≠ TapeSymbol.blank := by
intro c hc
have : c ∈ (bitCells (x :: rest)).reverse := by
rw [hLr]; exact List.mem_cons_of_mem _ hc
exact bitCells_ne_blank _ c (List.mem_reverse.mp this)
have hlcnb : lc ≠ TapeSymbol.blank := by
have : lc ∈ (bitCells (x :: rest)).reverse := by rw [hLr]; simp
exact bitCells_ne_blank _ lc (List.mem_reverse.mp this)
obtain ⟨hGh, hGt⟩ := shiftSeg5_spec i Lr lc [] (G₂.drop 5) T6
hlcnb hLrnb hT6i'
set T7 := Function.update T6 i
(cellsTape [] (TapeSymbol.blank ::
List.replicate 5 TapeSymbol.blank ++ (Lr.reverse ++ lc :: G₂.drop 5)))
with hT7
have hGt' : (((shiftSeg5 i).step^[11 * (Lr.length + 1) + 1])
((shiftSeg5 i).startCfg T6)).tape = T7 := by
rw [hGt, hT7]
have hrev : Lr.reverse ++ lc :: G₂.drop 5 =
bitCells (x :: rest) ++ G₂.drop 5 := by
have h1 : (lc :: Lr).reverse = bitCells (x :: rest) := by
rw [← hLr, List.reverse_reverse]
have h2 : (lc :: Lr).reverse = Lr.reverse ++ [lc] := by simp
rw [← h1, h2, List.append_assoc]
rfl
have hT7i : T7 i = cellsTape [] (TapeSymbol.blank ::
List.replicate 5 TapeSymbol.blank ++
(bitCells (x :: rest) ++ G₂.drop 5)) := by
rw [hT7]
simp only [Function.update_self]
rw [hrev]
-- H: one right, onto the separator start
have hH := moveUpTo_spec i 1 HeadMove.right (by omega) T7
set T8 := Function.update T7 i
(cellsTape [TapeSymbol.blank] (List.replicate 5 TapeSymbol.blank ++
(bitCells (x :: rest) ++ G₂.drop 5))) with hT8
have hHt : (((moveUpTo i 1 HeadMove.right).step^[1])
((moveUpTo i 1 HeadMove.right).startCfg T7)).tape = T8 := by
rw [moveUpTo_tape i 1 HeadMove.right (by omega) T7, hT8]
congr 1
rw [Function.iterate_one, hT7i]
exact cellsTape_moveRight [] TapeSymbol.blank _
-- assemble
have c7 := chainStepC hGh hGt' hH
have c6 := chainStepC hF hFt c7.1
have c5 := chainStepC hE hEt c6.1
have c4 := chainStepC hD hDt c5.1
have c3 := chainStepC hC hCt' c4.1
have c2 := chainStepC hB hBt c3.1
have c1 := chainStepC hA hAt c2.1
refine ⟨1 + 1 + (1 + 1 + (d * 4 + 3 + 1 + (1 + 1 + (5 + 1 + (5 + 1 +
((11 * (Lr.length + 1) + 1) + 1 + 1)))))), G₂.drop 5, hG₂.drop 5,
?_, c1.1, ?_⟩
· have hLrlen : Lr.length = rest.length := by
have := congrArg List.length hLr
simp [bitCells] at this
omega
rw [hLrlen, hd]
omega
· have hfin := c1.2
rw [c2.2] at hfin
rw [c3.2] at hfin
rw [c4.2] at hfin
rw [c5.2] at hfin
rw [c6.2] at hfin
rw [c7.2] at hfin
have hfin' : ((prePass i).step^[1 + 1 + (1 + 1 + (d * 4 + 3 + 1 +
(1 + 1 + (5 + 1 + (5 + 1 +
((11 * (Lr.length + 1) + 1) + 1 + 1))))))])
((prePass i).startCfg T) = _ := hfin
rw [hfin']
show (((moveUpTo i 1 HeadMove.right).step^[1])
((moveUpTo i 1 HeadMove.right).startCfg T7)).tape = _
rw [hHt, hT8, hT7, hT6, hT5, hT4, hT3, hT2]
simp only [Function.update_idem]
rw [dilTape]
congr 1
end SipserGacsLautemann
Source
Pre-pass for in-place dilation; builds on Def_sgl_dilation_loop.