The step program, with its read phases proven
Definitionsgl_step_programThe step program: one simulated step of the -tape machine on physical tapes — defined in full, with its read phases proven.
The shape, the simulated state a construction parameter supplied by the outer loop's carry:
hostSyms assembles the simulated machine's full symbol view — physical heads for the identity-mapped tapes, the two learned symbols for the hosted ones — and execAction applies the machine's writes and moves to the identity-mapped tapes in a single step, the host tape waiting for the update phases. The whole program elaborates with data-only dependence on runtime values, the dividend of the fixed-state-type discipline maintained since the counter machines.
readPhase_spec, proven here, is the module's substance. From the parked region, a read phase halts with its continuation's verdict; its terminal configuration is an explicit seven-layer tower ending in the continuation's own run; the continuation receives exactly the track's virtual head symbol (the two probe verdicts decode to it); and the region survives untouched up to ghost growth. The proof chains seven junctions with full configurations — the two probe junctions identify their verdicts by reading the flagged block at the split, and the parking scan reassembles the identical region.
What remains for the per-step theorem is assembly: instantiate the read phases twice, compose the execute readAct and the two proven track updates through the configuration-tracking chain, and case on the simulated machine's head-moves to select the matching update specifications and invariant preservations.
import Definitions.Def_sgl_step_chain
/-!
# The step program
Module E of the merge_empty plan, fourth part: one simulated step of the
`(tapes' + 2)`-tape machine, as a program on `tapes' + 1` physical tapes.
The shape, with the simulated state `q` a construction parameter supplied by
the outer loop's carry:
```
readPhase A (fun sA => -- learn virtual tape A's head symbol
readPhase B (fun sB => -- learn virtual tape B's head symbol
exec q sA sB ⟶ -- read heads 0..tapes'-1, apply M's action
updateTrack A ⟶ -- write + flag-move for track A
updateTrack B ⟶ -- write + flag-move for track B
carryQ q')) -- park the next state for the loop
```
Each `readPhase` learns its symbol through two Boolean block-reads piped
through `andThen`'s continuations (`sgl_read_bits`), so no state extraction
occurs anywhere inside the chain; the single extraction — the loop's `next`
reading `q'` — peels the fixed nesting to the `carryQ` payload at the end.
-/
namespace SipserGacsLautemann
variable {tapes : Nat}
/-! ## The read phase -/
/-- Learn a hosted track's head symbol and hand it to the continuation:
enter, walk to the flag, step back, probe bit one, step back, probe bit two,
park, continue. Content-preserving; the symbol travels through the two
`Bool`-indexed continuations. -/
def readPhase (side : TrackSide) (i : Fin tapes) {S : Type}
(cont : TapeSymbol → TypedMachine tapes S) :=
(moveUpTo i 1 HeadMove.right).andThen fun _ =>
(walkToFlag side i).andThen fun _ =>
(moveUpTo i 6 HeadMove.left).andThen fun _ =>
(blockRead i (sideBit1 side)).andThen 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₂)
/-! ## The execute phase -/
/-- Assemble the simulated machine's full symbol view: physical heads for the
identity-mapped tapes, the two learned symbols for the hosted ones. -/
def hostSyms (tapes' : Nat) (syms : Fin (tapes' + 1) → TapeSymbol)
(sA sB : TapeSymbol) : Fin (tapes' + 2) → TapeSymbol :=
fun k =>
if h : k.val < tapes' then syms ⟨k.val, by omega⟩
else if k.val = tapes' then sA else sB
/-- Apply the simulated machine's writes and moves to the identity-mapped
tapes; the host tape waits for the update phases. -/
def execAction {states : Nat} (tapes' : Nat)
(M : Machine (tapes' + 2) states) (q : Fin states) (sA sB : TapeSymbol) :
(Fin (tapes' + 1) → TapeSymbol) →
(Fin (tapes' + 1) → TapeSymbol × HeadMove) :=
fun syms j =>
if h : j.val < tapes' then
(M.transition q (hostSyms tapes' syms sA sB)).2 ⟨j.val, by omega⟩
else (syms j, HeadMove.stay)
/-- The virtual index of a hosted track. -/
def hostIdx (tapes' : Nat) : TrackSide → Fin (tapes' + 2)
| .A => ⟨tapes', by omega⟩
| .B => ⟨tapes' + 1, by omega⟩
/-! ## The step program -/
/-- One simulated step, from parked to parked, ending with the next simulated
state parked in a `carryQ` for the loop's `next` to read. -/
def stepProgram {states : Nat} (tapes' : Nat)
(M : Machine (tapes' + 2) states) (q : Fin states) :=
readPhase TrackSide.A (Fin.last tapes') fun sA =>
readPhase TrackSide.B (Fin.last tapes') fun sB =>
(TypedMachine.readAct
(fun syms => (syms, execAction tapes' M q sA sB syms))).andThenState
(fun s => s.isSome) fun rec =>
match rec with
| some syms =>
(updateTrack TrackSide.A (Fin.last tapes')
((M.transition q (hostSyms tapes' syms sA sB)).2
(hostIdx tapes' .A)).1
((M.transition q (hostSyms tapes' syms sA sB)).2
(hostIdx tapes' .A)).2).andThen fun _ =>
(updateTrack TrackSide.B (Fin.last tapes')
((M.transition q (hostSyms tapes' syms sA sB)).2
(hostIdx tapes' .B)).1
((M.transition q (hostSyms tapes' syms sA sB)).2
(hostIdx tapes' .B)).2).andThen fun _ =>
carryQ (M.transition q (hostSyms tapes' syms sA sB)).1
| none =>
(updateTrack TrackSide.A (Fin.last tapes') TapeSymbol.blank
HeadMove.stay).andThen fun _ =>
(updateTrack TrackSide.B (Fin.last tapes') TapeSymbol.blank
HeadMove.stay).andThen fun _ =>
carryQ q
/-! ## Peeling the next state out -/
/-- Seven `andThen` layers of one read phase. -/
def peel7 {S₁ S₂ S₃ S₄ S₅ S₆ S₇ S : Type}
(st : S₁ ⊕ Bool × (S₂ ⊕ Bool × (S₃ ⊕ Bool × (S₄ ⊕ Bool ×
(S₅ ⊕ Bool × (S₆ ⊕ Bool × (S₇ ⊕ Bool × S))))))) : Option S :=
(peelB st).bind fun st => (peelB st).bind fun st => (peelB st).bind fun st =>
(peelB st).bind fun st => (peelB st).bind fun st =>
(peelB st).bind fun st => peelB st
/-- The full extraction: through both read phases, the execute dispatch, the
two updates, into the `carryQ` payload; `q` if anything is off-shape (it never
is on the terminal term the specification pins). -/
def stepPeel {states : Nat} (tapes' : Nat) {ST₁ ST₂ SX SU₁ SU₂ : Type}
(q : Fin states)
(st : ST₁ ⊕ Bool × (ST₂ ⊕ Bool × (SX ⊕ SX ×
(SU₁ ⊕ Bool × (SU₂ ⊕ Bool × Option (Fin states)))))) : Fin states :=
(((peelB st).bind fun st => (peelB st).bind fun st =>
(peelS st).bind fun st => (peelB st).bind fun st =>
(peelB st).bind fun st => st).getD q)
/-! ## The read phase, specified -/
set_option maxHeartbeats 4000000 in
/-- **The read phase implements its contract**: from the parked region it
halts with the continuation's verdict, its terminal configuration is the
seven-layer tower ending in the continuation's run, the continuation receives
exactly the track's virtual head symbol, and the region survives untouched up
to ghost growth. -/
theorem readPhase_spec (side : TrackSide) (i : Fin tapes) {S : Type}
(cont : TapeSymbol → TypedMachine tapes S)
(tape : Fin tapes → Tape) (mid : List Block) (cur : Block)
(post : List Block) (G : List TapeSymbol) (hG : AllBlank G)
(hmid : ∀ b ∈ mid, side.getFlag b = false)
(hcur : side.getFlag cur = true)
(hi : tape i = ParkedTape (mid ++ cur :: post) G)
{k : Nat} {v : Bool}
(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) :
∃ (cost : Nat) (G' : List TapeSymbol), AllBlank G' ∧
HaltsExactly (readPhase side i cont)
((readPhase side i cont).startCfg tape) cost v ∧
((readPhase side i cont).step^[cost])
((readPhase side i cont).startCfg tape) =
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 tape i
(ParkedTape (mid ++ cur :: post) G')))))))))) := by
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