One round of the bounded-existential scheduler
Definitionsgl_offset_roundOne round of the bounded-existential scheduler — the machine, its tape roles, and the conditions those roles must satisfy.
The loop deciding runs one round per offset: reposition, restore the inputs, build from the persistent counter, delegate.
Two facts established while building the primitives dictate the shape. A delegated run leaves garbage of unknown extent, so working tapes are advanced past it rather than cleaned — the region ahead is untouched by construction. And the clock is a monotone accumulator: its marks are never erased, so successive rounds' marks sit contiguously and a rewind walks back over all of them at once. That is not a defect but a convenience — the accumulated count is at least the last run's length, and advancing further than necessary is always safe. It also keeps the clock's shape uniform across rounds, which is what the left-context generalisation needs.
RoundLayout names the tape roles and Wf bundles their distinctness once, so no stage's statement carries the conditions. stdLayout is the concrete nine-tape assignment — three inputs first, so withScratch supplies the rest blank — proved well-formed.
import Definitions.Def_sgl_embed_clock2
/-!
# One round of the bounded-existential scheduler
The loop deciding `∃ offset ≤ |input₂|, P(input₀, input₁, input₂, 1^offset)`
runs one of these per offset.
The round's shape is dictated by two facts established while building the
primitives. A delegated run leaves garbage of unknown extent, so the working
tapes are *advanced past* it rather than cleaned — the region ahead is
untouched by construction. And the clock is a **monotone accumulator**: its
marks are never erased, so successive rounds' marks sit contiguously and a
rewind walks back over all of them at once. That is harmless and in fact
convenient — the accumulated count is at least the last run's length, and
advancing further than necessary is always safe.
Stages, in order:
1. `rewindRun clk` — the delegate left the clock past its marks; go back.
2. `skipAhead clk dⱼ` for each working tape — advance past the garbage.
3. `copyBack` the three inputs onto their working tapes.
4. `markBack cnt d₃` — build `1^offset` from the persistent counter.
5. `scanToBlank clk right` — put the clock back on virgin territory.
6. `embedClock` — run the delegate, which ticks the clock as it goes.
-/
namespace SipserGacsLautemann
open Classical
variable {n k states : Nat}
/-- The tape roles a round acts on. -/
structure RoundLayout (n : Nat) where
src : Fin 3 → Fin n
dst : Fin 4 → Fin n
clk : Fin n
cnt : Fin n
/-- The four tapes the delegate sees. -/
def RoundLayout.sel (L : RoundLayout n) : Fin 4 → Fin n := L.dst
/-- Advance every working tape past the previous round's garbage. -/
def advanceAll (L : RoundLayout n) :=
(skipAhead L.clk (L.dst 0)).andThen fun _ =>
(skipAhead L.clk (L.dst 1)).andThen fun _ =>
(skipAhead L.clk (L.dst 2)).andThen fun _ =>
skipAhead L.clk (L.dst 3)
/-- Restore the three inputs onto their working tapes. -/
def restoreInputs (L : RoundLayout n) :=
(copyBack (L.src 0) (L.dst 0)).andThen fun _ =>
(copyBack (L.src 1) (L.dst 1)).andThen fun _ =>
copyBack (L.src 2) (L.dst 2)
/-- One round: reposition, restore, build the offset tape, delegate. -/
noncomputable def offsetRound (L : RoundLayout n)
(M : Machine 4 states) :=
(rewindRun L.clk).andThen fun _ =>
(advanceAll L).andThen fun _ =>
(restoreInputs L).andThen fun _ =>
(markBack L.cnt (L.dst 3)).andThen fun _ =>
(scanToBlank L.clk HeadMove.right).andThen fun _ =>
embedClock L.sel L.clk M
/-! ## When a layout is usable
Every stage needs its two tapes distinct, and the delegate needs its four
selected tapes distinct from each other and from the clock. Bundling the
conditions once keeps them out of every stage's statement.
-/
/-- The roles are pairwise distinct where the stages require it. -/
structure RoundLayout.Wf (L : RoundLayout n) : Prop where
dst_inj : Function.Injective L.dst
clk_dst : ∀ j, L.dst j ≠ L.clk
cnt_dst : ∀ j, L.dst j ≠ L.cnt
src_dst : ∀ i j, L.src i ≠ L.dst j
clk_cnt : L.clk ≠ L.cnt
/-- The delegate's hypotheses, from a well-formed layout. -/
theorem RoundLayout.Wf.sel_inj {L : RoundLayout n} (h : L.Wf) :
Function.Injective L.sel := h.dst_inj
theorem RoundLayout.Wf.sel_clk {L : RoundLayout n} (h : L.Wf) :
∀ j, L.sel j ≠ L.clk := h.clk_dst
/-- Each stage's distinctness obligation. -/
theorem RoundLayout.Wf.skip_ne {L : RoundLayout n} (h : L.Wf) (j : Fin 4) :
L.clk ≠ L.dst j := fun hc => (h.clk_dst j) hc.symm
theorem RoundLayout.Wf.copy_ne {L : RoundLayout n} (h : L.Wf)
(i : Fin 3) (j : Fin 4) : L.src i ≠ L.dst j := h.src_dst i j
theorem RoundLayout.Wf.mark_ne {L : RoundLayout n} (h : L.Wf) (j : Fin 4) :
L.cnt ≠ L.dst j := fun hc => (h.cnt_dst j) hc.symm
/-! ## A concrete layout
Three inputs, four working tapes, a clock and a counter: nine tapes, the
inputs first so that `withScratch` supplies the rest blank.
-/
/-- Tape `j` of nine, by role. -/
def stdLayout : RoundLayout 9 where
src := fun i => ⟨i.val, by omega⟩
dst := fun j => ⟨3 + j.val, by omega⟩
clk := ⟨7, by omega⟩
cnt := ⟨8, by omega⟩
theorem stdLayout_wf : stdLayout.Wf := by
constructor
· intro a b hab
have := congrArg Fin.val hab
simp [stdLayout] at this
exact Fin.ext (by omega)
· intro j
intro hc
have := congrArg Fin.val hc
simp [stdLayout] at this
omega
· intro j
intro hc
have := congrArg Fin.val hc
simp [stdLayout] at this
omega
· intro i j
intro hc
have := congrArg Fin.val hc
simp [stdLayout] at this
omega
· intro hc
have := congrArg Fin.val hc
simp [stdLayout] at this
end SipserGacsLautemann