The loop over offsets
Definitionsgl_offset_loopThe loop over offsets. One body per offset: run the round, grow the counter, step the guide, and ask whether the guide still carries a mark.
The body must report two things — whether the delegate accepted, and whether any offsets remain — but a composed machine's verdict is only its last component's. So the delegate's answer is read back out of the terminal control state: each andThen records the Boolean it dispatched on, and roundVerdict recovers the outermost one. The guide's answer is the body's own verdict, three layers in. loopBody_reads proves both recoveries.
The loop stops when either fires, and reports the delegate's answer — which is true exactly when some offset accepted, since a round that accepts stops the loop at once and a guide that runs out leaves the last round's answer standing. It uses the computed-verdict form of the loop combinator: the published one ties a loop's verdict to its body's exit code, and here the exit code is the guide test rather than the answer.
Reading a value out of a terminal state rather than threading it through a verdict is the same technique the merge campaign used to carry a simulated machine's next state through a composition. It is worth naming as a general move: when a composition can only return one Boolean and you need two, put the second in the state and peel it.
import Definitions.Def_sgl_bump_counter
/-!
# The loop over offsets
One body per offset: run the round, grow the counter, step the guide, and ask
whether the guide still carries a mark.
The body has to report *two* things — whether the delegate accepted, and
whether any offsets remain — but a composed machine's verdict is only its last
component's. So the delegate's answer is read back out of the terminal control
state instead: each `andThen` records the verdict it dispatched on, and
`roundVerdict` recovers the outermost one. The guide's answer is the body's
own verdict, three layers in.
The loop then stops when *either* fires, and reports the delegate's answer —
which is `true` exactly when some offset accepted, since a round that accepts
stops the loop immediately and a guide that runs out leaves the last round's
answer standing.
-/
namespace SipserGacsLautemann
open Classical
variable {n states : Nat}
/-- The Boolean an `andThen` dispatched on. -/
def peelVerdict {S₁ S₂ : Type} : S₁ ⊕ Bool × S₂ → Option Bool
| .inr (b, _) => some b
| .inl _ => none
@[simp] theorem peelVerdict_inRight {S₁ S₂ : Type} (b : Bool)
(c : TypedConfiguration n S₂) :
peelVerdict (S₁ := S₁) (TypedConfiguration.inRight b c).state = some b :=
rfl
/-- One iteration: the round, then the loop's own bookkeeping. -/
noncomputable def loopBody (L : RoundLayout n) (gd : Fin n)
(M : Machine 4 states) :=
(offsetRound L M).andThen fun _ =>
(bumpCounter L.cnt).andThen fun _ =>
(moveUpTo gd 1 HeadMove.right).andThen fun _ =>
TypedMachine.test (notBlankAt gd)
/-- Did the delegate accept this round? -/
def roundVerdict {S₁ S₂ : Type} (s : S₁ ⊕ Bool × S₂) : Bool :=
(peelVerdict s).getD false
/-- Are there offsets left? -/
def guideLeft {S₁ S₂ S₃ : Type}
(s : S₁ ⊕ Bool × (S₂ ⊕ Bool × (S₃ ⊕ Bool × Option Bool))) : Bool :=
((((peelB s).bind peelB).bind peelB).bind id).getD false
/-! ## The loop -/
/-- The scheduler: iterate the body until the delegate accepts or the offsets
run out, reporting the delegate's answer. -/
noncomputable def offsetLoop (L : RoundLayout n) (gd : Fin n)
(M : Machine 4 states) :=
TypedMachine.loopState (fun _ : Unit => loopBody L gd M)
(fun _ _ => ())
(fun _ b => roundVerdict b || !(guideLeft b))
(fun _ b => roundVerdict b)
()
/-- **Both readings are visible in the body's terminal configuration.** The
round's verdict sits in the outermost dispatch; the guide's answer is the test's
own state, three layers in. -/
theorem loopBody_reads {S₁ S₂ S₃ : Type} (v u 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 g 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 g 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
end SipserGacsLautemann