Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

The ternary majority fold

Definition
sgl_vote_fold

by Henry Yuen · Jul 25, 2026 · Mathlib c5ea003 (Lean v4.30.0)

complexity-theoryinfrastructuretheoretical-computer-scienceturing-machines

The ternary majority fold: reading cells into the machine's control state.

The amplification scheduler reduces 3d3^d3d leaf votes to a single answer by ddd 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

maj(b1,b2,b3)=(b1∧b2)∨(b1∧b3)∨(b2∧b3)\mathrm{maj}(b_1,b_2,b_3) = (b_1 \wedge b_2) \vee (b_1 \wedge b_3) \vee (b_2 \wedge b_3)maj(b1​,b2​,b3​)=(b1​∧b2​)∨(b1​∧b3​)∨(b2​∧b3​)

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.

Definition code
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
Source
Ternary majority amplification as used in the Sipser–Gács–Lautemann development; built on Def_sgl_tape_transfer.

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me