Reading a block: the sweep engine
Definitionsgl_block_readReading a block: the engine of the track sweeps.
A sweep across the block region must, at each block, learn enough to decide whether to stop there. blockRead does this in twelve steps: six chained readActs carry the block's six cells into the control state while advancing the head to the next block boundary, and a supplied predicate on the decoded block becomes the machine's verdict.
A planned complication that turned out unnecessary. These sweeps were designed as state-carrying loops that accumulate what they have seen. They do not need to be. The stopping condition — is this the flagged block? — is a predicate on the current block, so an ordinary loop suffices for the walk, and whatever is found at the stopping block escapes afterwards through andThenState dispatch. Only the outer simulation loop, whose rounds carry the simulated machine's state, genuinely needs a carried loop. This is the bounded/unbounded distinction: bounded data crosses a fixed continuation structure for free, and only unboundedly-repeating structure needs state threaded through it.
Reading and moving are one step. readAct applies a tape action while recording what it read, so each of the six reads also advances the head. The chain therefore arrives at the next block boundary having seen the whole block, at no extra cost.
Formalization note. The six-deep nesting is discharged by a single lemma, readCellRight_chain, applied six times: one link of the chain, from offset to offset , with the cell just read passed to the continuation. Writing six bespoke rewriting steps instead would have been six times the work and six times the maintenance. The first link is stated separately on the original tapes, because rewriting the start configuration in the goal would also rewrite inside the verdict, which is not wanted.
import Definitions.Def_sgl_block_codec
/-!
# Reading a block
Module D of the merge_empty plan (`DESIGN_merge_empty_v2.md`), first half.
A sweep over the block region must, at each block, learn enough to decide
whether to stop there. `blockRead` does exactly that: six chained `readAct`s
carry the block's six cells into the control state while advancing the head to
the next block boundary, and a supplied predicate on the decoded block becomes
the machine's verdict.
Two things about the design are worth recording, because they are what keeps
this module small.
**The sweep needs no carried state.** I had planned these sweeps as
`loopState` instances accumulating what they had seen. They do not need to be.
The stopping condition — "is this the flagged block?" — is a predicate on the
*current* block, so a plain `repeatUntilFalse` suffices for the walk, and the
datum found at the stopping block escapes afterwards through `andThenState`
dispatch. That is the bounded/unbounded split from the plan doing real work:
only the outer simulation loop, whose rounds carry the simulated state `q`,
needs `loopState`.
**Reading and moving are the same step.** `readAct` applies an action while
recording, so each of the six reads also advances the head one cell. After the
chain the head stands at the next block boundary having seen the whole block,
at no extra cost.
-/
namespace SipserGacsLautemann
variable {tapes : Nat}
/-- Read the cell under head `i` and advance that head one cell right,
recording what was read. -/
def readCellRight (i : Fin tapes) : TypedMachine tapes (Option TapeSymbol) :=
TypedMachine.readAct
(fun symbols => (symbols i, moveAction i HeadMove.right symbols))
theorem readCellRight_fires (i : Fin tapes) (tape : Fin tapes → Tape) :
FiresExactly (fun c => c.state.isSome) (readCellRight i).step
((readCellRight i).startCfg tape) 1 :=
TypedMachine.readAct_fires _ tape
theorem readCellRight_state (i : Fin tapes) (tape : Fin tapes → Tape) :
(((readCellRight i).step^[1]) ((readCellRight i).startCfg tape)).state =
some (tape i).head := by
rw [readCellRight, TypedMachine.readAct_run_one]
theorem readCellRight_tape (i : Fin tapes) (tape : Fin tapes → Tape) :
(((readCellRight i).step^[1]) ((readCellRight i).startCfg tape)).tape =
applyAction tape (moveAction i HeadMove.right) := by
rw [readCellRight, TypedMachine.readAct_run_one]
/-- The tapes after advancing head `i` right `n` times. -/
theorem advance_succ (i : Fin tapes) (tape : Fin tapes → Tape) (n : Nat) :
applyAction (scanTapesDir tape i HeadMove.right n) (moveAction i HeadMove.right) =
scanTapesDir tape i HeadMove.right (n + 1) :=
scanTapesDir_succ tape i HeadMove.right n
/-- The symbol under head `i` after `n` advances. -/
theorem advance_head (i : Fin tapes) (tape : Fin tapes → Tape) (n : Nat) :
((scanTapesDir tape i HeadMove.right n) i).head =
((moveDir HeadMove.right)^[n] (tape i)).head :=
scanTapesDir_head tape i HeadMove.right n
/-- Decode six consecutive cells into the block they encode. -/
def blockOfCells (c₀ c₁ c₂ c₃ c₄ c₅ : TapeSymbol) : Block :=
⟨symbolOfCells c₀ c₁, symbolBit c₂, symbolOfCells c₃ c₄, symbolBit c₅⟩
theorem blockOfCells_toCells (b : Block) :
blockOfCells
((cellsOfSymbol b.symA).1) ((cellsOfSymbol b.symA).2)
(TapeSymbol.bit b.flagA)
((cellsOfSymbol b.symB).1) ((cellsOfSymbol b.symB).2)
(TapeSymbol.bit b.flagB) = b := by
simp [blockOfCells, symbolBit]
/-- Read one block, advancing to the next boundary, and report `test` of it. -/
def blockRead (i : Fin tapes) (test : Block → Bool) :=
(readCellRight i).andThenState (fun s => s.isSome) fun c₀ =>
(readCellRight i).andThenState (fun s => s.isSome) fun c₁ =>
(readCellRight i).andThenState (fun s => s.isSome) fun c₂ =>
(readCellRight i).andThenState (fun s => s.isSome) fun c₃ =>
(readCellRight i).andThenState (fun s => s.isSome) fun c₄ =>
(readCellRight i).andThenState (fun s => s.isSome) fun c₅ =>
TypedMachine.halt
(test (blockOfCells (c₀.getD TapeSymbol.blank)
(c₁.getD TapeSymbol.blank) (c₂.getD TapeSymbol.blank)
(c₃.getD TapeSymbol.blank) (c₄.getD TapeSymbol.blank)
(c₅.getD TapeSymbol.blank)))
/-- The `k`-th cell the chain reads, expressed on the original tapes. -/
def cellAt (i : Fin tapes) (tape : Fin tapes → Tape) (k : Nat) : TapeSymbol :=
((moveDir HeadMove.right)^[k] (tape i)).head
/-- One link of the chain: a `readCellRight` at block-offset `n`, followed by a
continuation that receives the cell just read. Applying this six times builds
the whole block read, so the nested chain costs one lemma rather than six. -/
theorem readCellRight_chain {S : Type} (i : Fin tapes) (tape : Fin tapes → Tape)
(n : Nat) (M₂ : Option TapeSymbol → TypedMachine tapes S) (k : Nat)
(v : Bool)
(h : HaltsExactly (M₂ (some (cellAt i tape n)))
((M₂ (some (cellAt i tape n))).startCfg
(scanTapesDir tape i HeadMove.right (n + 1))) k v) :
HaltsExactly ((readCellRight i).andThenState (fun s => s.isSome) M₂)
(TypedConfiguration.inLeftState
((readCellRight i).startCfg (scanTapesDir tape i HeadMove.right n)))
(1 + 1 + k) v := by
refine FiresExactly.andThenState_halts (readCellRight_fires i _) ?_
rw [readCellRight_state, readCellRight_tape, advance_succ, advance_head]
exact h
/-- The first link, stated directly on `tape` rather than on `scanTapesDir … 0`.
Rewriting the start configuration in the goal instead would also rewrite `tape`
inside the *verdict*, which is not what is wanted. -/
theorem readCellRight_chain_zero {S : Type} (i : Fin tapes)
(tape : Fin tapes → Tape) (M₂ : Option TapeSymbol → TypedMachine tapes S)
(k : Nat) (v : Bool)
(h : HaltsExactly (M₂ (some (cellAt i tape 0)))
((M₂ (some (cellAt i tape 0))).startCfg
(scanTapesDir tape i HeadMove.right 1)) k v) :
HaltsExactly ((readCellRight i).andThenState (fun s => s.isSome) M₂)
(TypedConfiguration.inLeftState ((readCellRight i).startCfg tape))
(1 + 1 + k) v := by
have hc := readCellRight_chain i tape 0 M₂ k v h
rwa [scanTapesDir_zero] at hc
/-- **The block-read specification.** Twelve steps; the verdict is `test`
applied to the block assembled from the six cells starting under the head, and
the head finishes at the next block boundary. -/
theorem blockRead_spec (i : Fin tapes) (test : Block → Bool)
(tape : Fin tapes → Tape) :
HaltsExactly (blockRead i test)
(TypedConfiguration.inLeftState ((readCellRight i).startCfg tape))
(1 + 1 + (1 + 1 + (1 + 1 + (1 + 1 + (1 + 1 + (1 + 1 + 0))))))
(test (blockOfCells (cellAt i tape 0) (cellAt i tape 1) (cellAt i tape 2)
(cellAt i tape 3) (cellAt i tape 4) (cellAt i tape 5))) := by
refine readCellRight_chain_zero i tape _ _ _ ?_
refine readCellRight_chain i tape 1 _ _ _ ?_
refine readCellRight_chain i tape 2 _ _ _ ?_
refine readCellRight_chain i tape 3 _ _ _ ?_
refine readCellRight_chain i tape 4 _ _ _ ?_
refine readCellRight_chain i tape 5 _ _ _ ?_
simp only [Option.getD_some]
exact TypedMachine.halt_spec _ _
end SipserGacsLautemann