sgl_loop_reads
DefinitionDefinition 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