Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

One round of the bounded-existential scheduler

Definition
sgl_offset_round

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

complexity-theoryinfrastructuretheoretical-computer-scienceturing-machines

One round of the bounded-existential scheduler — the machine, its tape roles, and the conditions those roles must satisfy.

The loop deciding ∃ offset≤∣input2∣, P(input0,input1,input2,1offset)\exists\,\mathrm{offset} \le |{\rm input}_2|,\ P({\rm input}_0,{\rm input}_1,{\rm input}_2,1^{\rm offset})∃offset≤∣input2​∣, P(input0​,input1​,input2​,1offset) runs one round per offset: reposition, restore the inputs, build 1offset1^{\rm offset}1offset 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.

Definition code
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
Source
Round machine and tape layout for the bounded-exists scheduler; builds on Def_sgl_embed_clock2.

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