Reading a hosted symbol through verdicts
Definitionsgl_read_bitsReading a hosted symbol through verdicts: the step program's read design.
A machine cannot hand rich data upward except through its state, and extracting data from the deeply nested state of a long combinator chain is fragile. But blockRead's verdict is any Boolean predicate of the block it read — and a tape symbol is two bits. So the simulation's step program reads the flagged block twice, with the two probe predicates sideBit1 and sideBit2, and pipes each bit through andThen's continuation — which is precisely a Bool-indexed family of machines. Two nested continuations later the program holds the symbol, with no state extraction anywhere.
symbolOfBits_decode shows the two probes determine the symbol; symbolOfBits_head composes this with the merge invariant's head_eq: what the machine learns at a track's flagged block is exactly the symbol the simulated machine reads on that virtual tape. The read side of the simulation is thereby semantically closed — what remains for the step program is assembly.
import Definitions.Def_sgl_merge_invariant
/-!
# Reading a hosted symbol through verdicts
Module E of the merge_empty plan, second part: how the step program learns a
hosted track's symbol.
A machine cannot hand rich data upward except through its state, and deep state
extraction is fragile. But `blockRead`'s *verdict* is any Boolean predicate of
the block it read — and a tape symbol is two bits. So the step program reads
the flagged block **twice**, with the two bit-tests below, and pipes each bit
through `andThen`'s continuation, which is precisely a `Bool`-indexed family.
Two nested continuations later it holds the symbol, with no state extraction
anywhere.
`symbolOfBits_decode` closes the loop: the two bits decode to the symbol; and
through `HostsPair.head_eq`, to the *virtual head* — so what the machine
learns is what the simulated machine would have read.
-/
namespace SipserGacsLautemann
/-- First probe: is the track's symbol `bit true`? -/
def sideBit1 (side : TrackSide) (b : Block) : Bool :=
match side.pick b with
| TapeSymbol.bit true => true
| _ => false
/-- Second probe: is the track's symbol `bit false`? -/
def sideBit2 (side : TrackSide) (b : Block) : Bool :=
match side.pick b with
| TapeSymbol.bit false => true
| _ => false
/-- Reassemble a symbol from its two probes. -/
def symbolOfBits : Bool → Bool → TapeSymbol
| true, _ => TapeSymbol.bit true
| false, true => TapeSymbol.bit false
| false, false => TapeSymbol.blank
/-- The two probes determine the symbol. -/
theorem symbolOfBits_decode (side : TrackSide) (b : Block) :
symbolOfBits (sideBit1 side b) (sideBit2 side b) = side.pick b := by
cases h : side.pick b with
| blank => simp [sideBit1, sideBit2, symbolOfBits, h]
| bit bit =>
cases bit <;> simp [sideBit1, sideBit2, symbolOfBits, h]
/-- What the probes learn is the virtual head: the two `blockRead` verdicts at
a track's flagged block decode to exactly the symbol the simulated machine
reads on that tape. -/
theorem symbolOfBits_head {blocks : List Block} {t : TrackSide → Tape}
(h : HostsPair blocks t) (side : TrackSide)
{pre : List Block} {cur : Block} {post : List Block}
(hsplit : SplitAtFlag side blocks pre cur post) :
symbolOfBits (sideBit1 side cur) (sideBit2 side cur) = (t side).head := by
rw [symbolOfBits_decode]
exact h.head_eq side hsplit
end SipserGacsLautemann