The exit round's chain
Definitionsgl_dilation_exitcomplexity-theoryinfrastructuretheoretical-computer-scienceturing-machines
The post-read chain when the read finds blank: the same seven stages as a bit round, with the shifter halting at once, writing the round's block for the captured blank. Split out for verification size — the platform verifier budgets per request, and these junction proofs are individually expensive.
Definition code
import Definitions.Def_sgl_dilation_core
/-!
# The exit round's chain
The post-read chain when the read finds blank: the same seven stages as a
bit round, with the shifter halting at once, writing the round's block for the
captured blank.
Split out for verification size — the platform verifier budgets per request,
and these junction proofs are individually expensive.
-/
namespace SipserGacsLautemann
variable {tapes : Nat}
set_option maxHeartbeats 4000000 in
/-- **The post-read chain on a blank**: the exit round. Same chain, the
shifter halting at once, writing the round's block for the captured blank. -/
theorem dilCont_spec_blank (i : Fin tapes) (first : Bool)
(done : List Block) (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 :: G)) :
∃ (cost : Nat) (G' : List TapeSymbol), AllBlank G' ∧
cost ≤ 40 ∧
HaltsExactly (dilCont i (some TapeSymbol.blank) first)
((dilCont i (some TapeSymbol.blank) first).startCfg T2) cost true ∧
(((dilCont i (some TapeSymbol.blank) first).step^[cost])
((dilCont i (some TapeSymbol.blank) first).startCfg T2)).tape =
Function.update T2 i (cellsTape
((encodeBlocks (done ++
[blockFor (some TapeSymbol.blank) first])).reverse ++
[TapeSymbol.blank])
(List.replicate 5 TapeSymbol.blank ++ G')) := by
classical
set L0 := (encodeBlocks done).reverse ++ [TapeSymbol.blank] with hL0
set L2 := List.replicate 5 TapeSymbol.blank ++ L0 with hL2
set rest : List Bool := [] with hrest
set d := rest.length with hd
have hT2' : T2 i = cellsTape L2 (TapeSymbol.blank :: bitCells rest ++ G) := by
rw [hT2, hrest]
rfl
-- stage C, as in the bit case
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 hk0 : k = 0 := by
rw [hd, hrest] at hk
simpa using hk
subst hk0
simp only [Nat.zero_add]
rw [hT2']
rw [show TapeSymbol.blank :: bitCells rest ++ G =
(TapeSymbol.blank :: bitCells (rest.take 0)) ++
(bitCells (rest.drop 0) ++ G) by simp [hrest]]
rw [show (1 : Nat) =
(TapeSymbol.blank :: bitCells (rest.take 0)).length by simp [hrest]]
rw [cellsTape_advance]
have hlt : ∀ k, k < d →
(((moveDir HeadMove.right)^[k + 1]) (T2 i)).head ≠ TapeSymbol.blank := by
intro k hk
exfalso
rw [hd, hrest] at hk
simp at hk
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
have hrest' : rest = [] := 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.blank) first)) T7 _ _ hT7i
have hIt := writeRun_tape i
(Block.toCells (blockFor (some TapeSymbol.blank) 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.blank) first).step^[
d * 4 + 3 + 1 + (1 + 1 + (5 + 1 + (5 + 1 + (1 + 1 +
(5 + 1 + 6)))))])
((dilCont i (some TapeSymbol.blank) first).startCfg T2) = _ :=
hfin
rw [hfin']
show (((writeRun i (Block.toCells (blockFor (some TapeSymbol.blank)
first))).step^[(Block.toCells (blockFor (some TapeSymbol.blank)
first)).length]) ((writeRun i (Block.toCells (blockFor
(some TapeSymbol.blank) 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.blank) first)).length =
List.replicate 5 TapeSymbol.blank ++ G₂.drop 5 by
rw [Block.toCells_length]
rfl]
rw [hL0]
rw [show (Block.toCells (blockFor (some TapeSymbol.blank) first)).reverse ++
((encodeBlocks done).reverse ++ [TapeSymbol.blank]) =
(encodeBlocks (done ++
[blockFor (some TapeSymbol.blank) first])).reverse ++
[TapeSymbol.blank] by
rw [encodeBlocks_snoc, List.reverse_append]
simp]
end SipserGacsLautemann
Source
In-place dilation for eliminate_last_scratch_tape.