The ternary majority fold
Definitionsgl_vote_foldThe ternary majority fold: reading cells into the machine's control state.
The amplification scheduler reduces leaf votes to a single answer by passes, each replacing consecutive triples by their majority. The primitive it needs is "read three consecutive cells and write their majority".
Reading a cell into control is where the branching half of andThen earns its keep. Because the continuation is a function of the previous verdict, test ⟶ fun b => … carries the bit read at a cell into the remainder of the program with no tape bookkeeping at all. Three reads nest three deep, and the majority
is then simply a parameter of a single write action.
voteFoldStep src dst performs one such fold in eleven steps, leaving src past the triple and dst past the written cell. Its specification is five applications of HaltsExactly.andThen and mentions neither step nor run — a demonstration that control-flow-carrying data, not just straight-line code and loops, is expressible through the algebra alone.
import Definitions.Def_sgl_tape_transfer
/-!
# The ternary majority fold
The amplification scheduler reduces `3ᵈ` leaf votes to one by `d` passes, each
replacing consecutive triples by their majority. The primitive it needs is
"read three consecutive cells and write their majority".
Reading a cell *into the machine's control* is where `andThen`'s branching earns
its keep: the continuation is a function of the previous verdict, so
`test ⟶ fun b => …` carries the bit read at that cell into the rest of the
program without any tape bookkeeping. Three reads nest three deep, and the
majority is then a parameter of a single write action.
Nothing here reasons about `step` or `run`: the whole specification is five
applications of `HaltsExactly.andThen`.
-/
namespace SipserGacsLautemann
variable {tapes : Nat}
/-- Majority of three bits. -/
def majority3 (a b c : Bool) : Bool := (a && b) || (a && c) || (b && c)
/-- The bit under head `i`, blanks reading as `false`. -/
def bitAt (i : Fin tapes) : (Fin tapes → TapeSymbol) → Bool :=
fun symbols => symbolBit (symbols i)
/-- Write a fixed bit onto `dst` and advance both heads. -/
def emitBitAction (src dst : Fin tapes) (bit : Bool) :
(Fin tapes → TapeSymbol) → (Fin tapes → TapeSymbol × HeadMove) :=
fun symbols j =>
(if j = dst then TapeSymbol.bit bit else symbols j,
if j = src then HeadMove.right
else if j = dst then HeadMove.right else HeadMove.stay)
/-- Advance `src` by one cell. -/
def advance (src : Fin tapes) : TypedMachine tapes Bool :=
TypedMachine.act (moveAction src HeadMove.right)
/-- Read three consecutive cells under `src` and write their majority onto
`dst`, leaving `src` past the triple and `dst` past the written cell. -/
def voteFoldStep (src dst : Fin tapes) :
TypedMachine tapes
(Option Bool ⊕ Bool ×
(Bool ⊕ Bool ×
(Option Bool ⊕ Bool ×
(Bool ⊕ Bool ×
(Option Bool ⊕ Bool × Bool))))) :=
(TypedMachine.test (bitAt src)).andThen fun b₁ =>
(advance src).andThen fun _ =>
(TypedMachine.test (bitAt src)).andThen fun b₂ =>
(advance src).andThen fun _ =>
(TypedMachine.test (bitAt src)).andThen fun b₃ =>
TypedMachine.act (emitBitAction src dst (majority3 b₁ b₂ b₃))
/-! ## Tapes at each stage of the triple read -/
/-- Tapes after advancing `src` once from `tape`. -/
def advanced (tape : Fin tapes → Tape) (src : Fin tapes) : Fin tapes → Tape :=
applyAction tape (moveAction src HeadMove.right)
theorem advance_tape (src : Fin tapes) (tape : Fin tapes → Tape) :
(((advance src).step^[1]) ((advance src).startCfg tape)).tape =
advanced tape src :=
TypedMachine.act_tape (moveAction src HeadMove.right) tape
theorem advance_spec (src : Fin tapes) (tape : Fin tapes → Tape) :
HaltsExactly (advance src) ((advance src).startCfg tape) 1 true :=
TypedMachine.act_spec (moveAction src HeadMove.right) tape
/-- **The fold step, specified.** Eleven steps; the bit written to `dst` is the
majority of the three cells read, each read carried in the control state. -/
theorem voteFoldStep_spec (src dst : Fin tapes) (tape : Fin tapes → Tape) :
HaltsExactly (voteFoldStep src dst)
(TypedConfiguration.inLeft
((TypedMachine.test (bitAt src)).startCfg tape))
(1 + 1 + (1 + 1 + (1 + 1 + (1 + 1 + (1 + 1 + 1))))) true := by
-- the three cells, read off the tapes at the three successive positions
set t₀ := tape with ht₀
set t₁ := advanced t₀ src with ht₁
set t₂ := advanced t₁ src with ht₂
set b₁ := bitAt src (fun j => (t₀ j).head) with hb₁
set b₂ := bitAt src (fun j => (t₁ j).head) with hb₂
set b₃ := bitAt src (fun j => (t₂ j).head) with hb₃
-- innermost: emit the majority
have h₆ :
HaltsExactly
(TypedMachine.act (emitBitAction src dst (majority3 b₁ b₂ b₃)))
((TypedMachine.act
(emitBitAction src dst (majority3 b₁ b₂ b₃))).startCfg t₂) 1 true :=
TypedMachine.act_spec _ t₂
-- third read
have h₅ :
HaltsExactly
((TypedMachine.test (bitAt src)).andThen fun b =>
TypedMachine.act (emitBitAction src dst (majority3 b₁ b₂ b)))
(TypedConfiguration.inLeft
((TypedMachine.test (bitAt src)).startCfg t₂))
(1 + 1 + 1) true := by
refine HaltsExactly.andThen (TypedMachine.test_spec (bitAt src) t₂) ?_
rw [TypedMachine.test_tape]
exact h₆
-- second advance
have h₄ :
HaltsExactly
((advance src).andThen fun _ =>
(TypedMachine.test (bitAt src)).andThen fun b =>
TypedMachine.act (emitBitAction src dst (majority3 b₁ b₂ b)))
(TypedConfiguration.inLeft ((advance src).startCfg t₁))
(1 + 1 + (1 + 1 + 1)) true := by
refine HaltsExactly.andThen (advance_spec src t₁) ?_
rw [advance_tape]
exact h₅
-- second read
have h₃ :
HaltsExactly
((TypedMachine.test (bitAt src)).andThen fun b =>
(advance src).andThen fun _ =>
(TypedMachine.test (bitAt src)).andThen fun b' =>
TypedMachine.act (emitBitAction src dst (majority3 b₁ b b')))
(TypedConfiguration.inLeft
((TypedMachine.test (bitAt src)).startCfg t₁))
(1 + 1 + (1 + 1 + (1 + 1 + 1))) true := by
refine HaltsExactly.andThen (TypedMachine.test_spec (bitAt src) t₁) ?_
rw [TypedMachine.test_tape]
exact h₄
-- first advance
have h₂ :
HaltsExactly
((advance src).andThen fun _ =>
(TypedMachine.test (bitAt src)).andThen fun b =>
(advance src).andThen fun _ =>
(TypedMachine.test (bitAt src)).andThen fun b' =>
TypedMachine.act (emitBitAction src dst (majority3 b₁ b b')))
(TypedConfiguration.inLeft ((advance src).startCfg t₀))
(1 + 1 + (1 + 1 + (1 + 1 + (1 + 1 + 1)))) true := by
refine HaltsExactly.andThen (advance_spec src t₀) ?_
rw [advance_tape]
exact h₃
-- first read
refine HaltsExactly.andThen (TypedMachine.test_spec (bitAt src) t₀) ?_
rw [TypedMachine.test_tape]
exact h₂
end SipserGacsLautemann