The read phase, canonical shape
Definitionsgl_read_phase_exThe read phase in the canonical, self-composing shape.
The earlier readPhase_bounded demands its continuation halt at one fixed time for every tape whose host is the parked region — which a continuation whose runtime depends on the identity tapes cannot supply; that mismatch is what blocked the per-step composition. Here the statement is per identity class: inputs are for fixed base and varying ghost; the continuation's time is an explicit argument, uniform over the ghost (legitimate, because at a fixed identity class the machine's actions are determined and the ghost is never read); and the conclusion is the same shape one level up, with a cost bounded by and the terminal configuration exposed as the seven-layer tower whose exponent is that same — so a consumer rewrites the continuation's own configuration equation under the tower, and read phases nest with the execute tail's specification fitting verbatim.
The junction body is readPhase_bounded's; only the quantifier prefix moved. The general principle, learned the hard way across four failed interfaces: every quantity in a phase specification must be fixed exactly after the data it depends on and before the data it doesn't.
import Definitions.Def_sgl_exec_full
/-!
# The read phase, canonical shape
Module E5b of DESIGN_step_spec_endgame.
`readPhase_bounded` demands its continuation halt at one fixed time for
*every* tape whose host is the parked region — which a continuation whose
runtime depends on the identity tapes cannot supply. Here the statement is
per **identity class**: the input tapes are `Function.update base i (ParkedTape
blocks G)` for a fixed `base` and varying ghost, the continuation's time `k`
is an explicit argument uniform over the ghost, and the conclusion is the same
shape one level up with the tower's exponent being that same `k` — so a
consumer can rewrite the continuation's own configuration equation under the
tower, and read phases nest. The execute tail's specification is verbatim the
hypothesis.
The junction body is the one from `readPhase_bounded`; only the quantifier
prefix moved.
-/
namespace SipserGacsLautemann
variable {tapes : Nat}
set_option maxHeartbeats 4000000 in
/-- **The read phase over an identity class.** -/
theorem readPhase_ex (side : TrackSide) (i : Fin tapes) {S : Type}
(cont : TapeSymbol → TypedMachine tapes S)
(mid : List Block) (cur : Block) (post : List Block)
(hmid : ∀ b ∈ mid, side.getFlag b = false)
(hcur : side.getFlag cur = true)
(k : Nat) (v : Bool) (base : Fin tapes → Tape)
(hcont : ∀ (G' : List TapeSymbol), AllBlank G' →
HaltsExactly (cont (side.pick cur))
((cont (side.pick cur)).startCfg
(Function.update base i (ParkedTape (mid ++ cur :: post) G'))) k v) :
∃ (cost : Nat),
cost ≤ 100 * (mid ++ cur :: post).length + 300 + k ∧
∀ (G : List TapeSymbol), AllBlank G →
∃ G', AllBlank G' ∧
HaltsExactly (readPhase side i cont)
((readPhase side i cont).startCfg
(Function.update base i (ParkedTape (mid ++ cur :: post) G)))
cost v ∧
((readPhase side i cont).step^[cost])
((readPhase side i cont).startCfg
(Function.update base i (ParkedTape (mid ++ cur :: post) G))) =
TypedConfiguration.inRight true (TypedConfiguration.inRight false
(TypedConfiguration.inRight true (TypedConfiguration.inRight
(sideBit1 side cur) (TypedConfiguration.inRight true
(TypedConfiguration.inRight (sideBit2 side cur)
(TypedConfiguration.inRight false
(((cont (side.pick cur)).step^[k])
((cont (side.pick cur)).startCfg
(Function.update base i
(ParkedTape (mid ++ cur :: post) G')))))))))) := by
have hcontB := hcont
refine ⟨1 + 1 + ((loopCost (fun _ => blockReadSteps) mid.length +
blockReadSteps) + 1 + (6 + 1 + (blockReadSteps + 1 + (6 + 1 +
(blockReadSteps + 1 +
((((Block.toCells cur).reverse ++
(encodeBlocks mid).reverse).length) * 4 + 3 + 1 + k)))))),
?_, ?_⟩
· rw [loopCost_const, blockReadSteps_eq]
simp only [List.length_append, List.length_reverse,
Block.toCells_length, encodeBlocks_length, List.length_cons]
omega
intro G hG
set tape := Function.update base i (ParkedTape (mid ++ cur :: post) G)
with htape
have hi : tape i = ParkedTape (mid ++ cur :: post) G := by
rw [htape]; simp
have hcollapse : ∀ Gx, Function.update base i
(ParkedTape (mid ++ cur :: post) Gx) =
Function.update tape i (ParkedTape (mid ++ cur :: post) Gx) := by
intro Gx
rw [htape, Function.update_idem]
simp only [hcollapse]
have hcont : ∀ (G' : List TapeSymbol), AllBlank G' →
HaltsExactly (cont (side.pick cur))
((cont (side.pick cur)).startCfg
(Function.update tape i (ParkedTape (mid ++ cur :: post) G'))) k v := by
intro G' hG'
rw [← hcollapse G']
exact hcontB G' hG'
classical
have hCl : (Block.toCells cur).length = 6 := Block.toCells_length cur
-- ===== 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 to 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: first probe =====
have hread1 : HaltsExactly (blockRead i (sideBit1 side))
((blockRead i (sideBit1 side)).startCfg T3) blockReadSteps
(sideBit1 side cur) := by
have h := blockRead_spec i (sideBit1 side) T3
rwa [blockOfCells_cellsTape i T3 _ _ cur hT3i] at h
set T4 := Function.update T3 i
(cellsTape ((Block.toCells cur).reverse ++
((encodeBlocks mid).reverse ++ [TapeSymbol.blank]))
(encodeBlocks post ++ G₃)) with hT4
have htp4 : (((blockRead i (sideBit1 side)).step^[blockReadSteps])
((blockRead i (sideBit1 side)).startCfg T3)).tape = T4 := by
have h := blockRead_tape i (sideBit1 side) T3
rw [show (blockRead i (sideBit1 side)).startCfg T3 =
TypedConfiguration.inLeftState
((readCellRight i).startCfg T3) from rfl] at *
rw [h, hT4]
funext j
by_cases hj : j = i
· subst hj
rw [scanTapesDir_self, hT3i,
show (6 : Nat) = (Block.toCells cur).length from hCl.symm,
cellsTape_advance]
simp
· simp [scanTapesDir, hj]
have hT4i : T4 i = cellsTape
((Block.toCells cur).reverse ++
((encodeBlocks mid).reverse ++ [TapeSymbol.blank]))
(encodeBlocks post ++ G₃) := by
rw [hT4]; simp
-- ===== junction 5: back again =====
obtain ⟨G₅, hG₅, hret5⟩ := retreat_block (Block.toCells cur).reverse
((encodeBlocks mid).reverse ++ [TapeSymbol.blank]) post G₃ hG₃
set T5 := Function.update T4 i
(cellsTape ((encodeBlocks mid).reverse ++ [TapeSymbol.blank])
(Block.toCells cur ++ (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 cur).reverse).length by simp [hCl]]
rw [hret5, List.reverse_reverse]
have hT5i : T5 i = cellsTape
((encodeBlocks mid).reverse ++ [TapeSymbol.blank])
(Block.toCells cur ++ (encodeBlocks post ++ G₅)) := by
rw [hT5]; simp
-- ===== junction 6: second probe =====
have hread2 : HaltsExactly (blockRead i (sideBit2 side))
((blockRead i (sideBit2 side)).startCfg T5) blockReadSteps
(sideBit2 side cur) := by
have h := blockRead_spec i (sideBit2 side) T5
rwa [blockOfCells_cellsTape i T5 _ _ cur hT5i] at h
set T6 := Function.update T5 i
(cellsTape ((Block.toCells cur).reverse ++
((encodeBlocks mid).reverse ++ [TapeSymbol.blank]))
(encodeBlocks post ++ G₅)) with hT6
have htp6 : (((blockRead i (sideBit2 side)).step^[blockReadSteps])
((blockRead i (sideBit2 side)).startCfg T5)).tape = T6 := by
have h := blockRead_tape i (sideBit2 side) T5
rw [show (blockRead i (sideBit2 side)).startCfg T5 =
TypedConfiguration.inLeftState
((readCellRight i).startCfg T5) from rfl] at *
rw [h, hT6]
funext j
by_cases hj : j = i
· subst hj
rw [scanTapesDir_self, hT5i,
show (6 : Nat) = (Block.toCells cur).length from hCl.symm,
cellsTape_advance]
simp
· simp [scanTapesDir, hj]
have hT6i : T6 i = cellsTape
((Block.toCells cur).reverse ++
((encodeBlocks mid).reverse ++ [TapeSymbol.blank]))
(encodeBlocks post ++ G₅) := by
rw [hT6]; simp
-- ===== junction 7: park =====
set Wp := (Block.toCells cur).reverse ++ (encodeBlocks mid).reverse
with hWp
have hassoc : (Block.toCells cur).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 : ∀ j, j < Wp.length →
((moveDir HeadMove.left)^[j + 1] (T6 i)).head ≠ TapeSymbol.blank := by
intro j hj
rw [hT6i, hassoc]
exact hlt' j hj
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 cur := by
rw [hWp, List.reverse_append, List.reverse_reverse, List.reverse_reverse]
have hX7 : (moveDir HeadMove.left)^[Wp.length + 1] (T6 i) =
ParkedTape (mid ++ cur :: 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 cur ++
(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 ++ cur :: post) =
encodeBlocks mid ++ (Block.toCells cur ++ encodeBlocks post) := by
rw [encodeBlocks_append, encodeBlocks_cons]
rw [henc]
simp [List.append_assoc]
set T7 := Function.update T6 i (ParkedTape (mid ++ cur :: 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
-- ===== the continuation's start =====
have hT7flat : T7 = Function.update tape i
(ParkedTape (mid ++ cur :: post) G₇) := by
rw [hT7, hT6, hT5, hT4, hT3, hT2, hT1]
simp only [scanTapesDir, Function.update_idem]
have hK := hcont G₇ hG₇
rw [← hT7flat] at hK
-- ===== assemble, inside out =====
have hsym : symbolOfBits (sideBit1 side cur) (sideBit2 side cur) =
side.pick cur := symbolOfBits_decode side cur
have hC7 := chainStepD
(M₂ := fun _ => cont (symbolOfBits (sideBit1 side cur)
(sideBit2 side cur)))
hP7 htp7 (by rw [hsym]; exact hK)
have hC6 := chainStepD
(M₂ := fun b₂ => (scanToBlank i HeadMove.left).andThen fun _ =>
cont (symbolOfBits (sideBit1 side cur) b₂))
hread2 htp6 hC7.1
have hC5 := chainStepC (moveUpTo_spec i 6 HeadMove.left (by omega) T4)
htp5 hC6.1
have hC4 := chainStepD
(M₂ := fun b₁ => (moveUpTo i 6 HeadMove.left).andThen fun _ =>
(blockRead i (sideBit2 side)).andThen fun b₂ =>
(scanToBlank i HeadMove.left).andThen fun _ =>
cont (symbolOfBits b₁ b₂))
hread1 htp4 hC5.1
have hC3 := chainStepC (moveUpTo_spec i 6 HeadMove.left (by omega) T2)
htp3 hC4.1
have hC2 := chainStepC hw hwt hC3.1
have hC1 := chainStepC (moveUpTo_spec i 1 HeadMove.right (by omega) tape)
htp1 hC2.1
rw [show cont (side.pick cur) = cont (symbolOfBits (sideBit1 side cur)
(sideBit2 side cur)) by rw [hsym]]
refine ⟨G₇, hG₇, hC1.1, ?_⟩
have hfin := hC1.2
rw [hC2.2] at hfin
rw [hC3.2] at hfin
rw [hC4.2] at hfin
rw [hC5.2] at hfin
rw [hC6.2] at hfin
rw [hC7.2] at hfin
rw [hT7flat] at hfin
exact hfin
end SipserGacsLautemann