Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

sgl_loop_reads

Definition

by Henry Yuen · Jul 27, 2026 · Mathlib 0df444a (Lean v4.33.1)

Definition code
import Definitions.Def_sgl_offset_inv

/-!
# Reading both of the body's answers, at every round

`loopBody_reads` names the guide's answer and the guide-stepping machine's exit
code with the same letter.  Nothing in the conclusion depends on that code —
`peelB` discards a layer's Boolean tag and keeps only the inner state — but as a
*hypothesis* the shared name forces them equal, and `moveUpTo` always halts
`true`.  So the published lemma applies only when the guide still carries a
mark: it covers every round except the last, which is precisely the round the
loop stops on.

The repair is to give the layer its own variable.  The proof is unchanged,
because the tag was never used.

This is the seventh time in this campaign a statement has been true but
unusable, and the second where the flaw was an accidental identification rather
than an over-specific constant.  The tell is the same each time: a hypothesis
that pins a quantity the conclusion never mentions.
-/

namespace SipserGacsLautemann

variable {n : Nat}

/-- **Both readings, at any round.**  The round's verdict sits in the outermost
dispatch; the guide's answer is the test's own state, three layers in.  The
intervening exit codes are free. -/
theorem loopBody_reads' {S₁ S₂ S₃ : Type} (v u w g : Bool)
    (cg : TypedConfiguration n (Option Bool))
    (cm : TypedConfiguration n (S₃ ⊕ Bool × Option Bool))
    (cb : TypedConfiguration n (S₂ ⊕ Bool × (S₃ ⊕ Bool × Option Bool)))
    (hcm : cm = TypedConfiguration.inRight w cg)
    (hcb : cb = TypedConfiguration.inRight u cm)
    (hg : cg.state = some g) :
    roundVerdict (S₁ := S₁) (TypedConfiguration.inRight v cb).state = v ∧
      guideLeft (S₁ := S₁) (TypedConfiguration.inRight v cb).state = g := by
  subst hcm
  subst hcb
  refine ⟨rfl, ?_⟩
  show ((((peelB (TypedConfiguration.inRight v
    (TypedConfiguration.inRight u
      (TypedConfiguration.inRight w cg))).state).bind peelB).bind
      peelB).bind id).getD false = g
  rw [peelB_inRight]
  simp only [Option.bind_some]
  rw [peelB_inRight]
  simp only [Option.bind_some]
  rw [peelB_inRight]
  simp only [Option.bind_some]
  rw [hg]
  rfl

/-- The test's terminal state is its verdict.  This is the `hg` every use of
`loopBody_reads'` needs, in the form `chainStepC` hands it over. -/
theorem test_state (p : (Fin n → TapeSymbol) → Bool) (T : Fin n → Tape) :
    (((TypedMachine.test p).step^[1])
      ((TypedMachine.test p).startCfg T)).state =
      some (p (fun i => (T i).head)) := by
  simp [TypedMachine.test, TypedMachine.startCfg, TypedMachine.step]

end SipserGacsLautemann

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