Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

The clock-ticking delegate

Definition
sgl_embed_clock

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

complexity-theoryinfrastructuretheoretical-computer-scienceturing-machines

Running an arbitrary machine as a subroutine, on a clock. embedClock ι clk M runs a Machine k inside a larger tape space: tape ι(j)\iota(j)ι(j) plays the simulated machine's tape jjj, and one extra tape records a unary mark per simulated step.

Why the clock. The scheduler families all need loops that re-run a machine on modified inputs, which means erasing the working tapes between rounds. That is impossible by scanning: after a delegated run the tapes hold garbage whose written region may contain internal blanks, so no blank-seeking walk bounds its extent. The clock bounds it. A machine that has run ttt steps has moved each head at most ttt cells from its origin, and the clock holds exactly ttt contiguous marks — which is scannable. A clock-guided sweep therefore erases the garbage, and the next round starts clean. The closing observation is that a fully blank tape needs no origin: the next round's copy defines a fresh one wherever the head stands.

embedClock_step is the bisimulation — one embedded step is one simulated step, clock advanced, every other tape untouched — and embedClock_spec lifts it: if the simulated machine halts at time TTT with verdict vvv, the embedded machine does too, leaving TTT marks and the simulated final tapes in place.

The selector ι\iotaι is required injective and to miss the clock, so the simulated tapes are distinct from each other and from the clock. Reading a selected tape without naming its index needs clockTapes_at_sel: a lemma stated so that no rewriting of the index occurs, since the index appears in the choice term's own type and rewriting it breaks the motive.

Definition code
import Definitions.Def_sgl_elim_solution

/-!
# Running a machine as a subroutine, on a clock

Module I0's core.  `embedClock ι clk M` runs an arbitrary `Machine k` inside a
larger tape space: tape `ι j` plays the simulated machine's tape `j`, and one
extra tape `clk` records a unary mark per simulated step.

The clock is what makes a *loop* possible.  After a delegated run the working
tapes hold garbage whose extent cannot be found by scanning — the written
region may contain internal blanks, so no blank-seeking walk bounds it.  The
clock does bound it: a machine that has run `t` steps has moved each head at
most `t` cells from its origin, and the clock is exactly `t` contiguous marks,
which *is* scannable.  A clock-guided sweep therefore erases the garbage, and
the next round starts clean.

`ι` is required injective and to miss `clk`, so the simulated tapes are
distinct from each other and from the clock.
-/

namespace SipserGacsLautemann

open Classical

variable {n k states : Nat}

/-- Simulate `M` on the `ι`-selected tapes, ticking `clk` each step. -/
noncomputable def embedClock (ι : Fin k → Fin n) (clk : Fin n)
    (M : Machine k states) : TypedMachine n (Fin states) where
  start := M.start
  transition := fun s symbols =>
    ((M.transition s (fun j => symbols (ι j))).1,
      fun i =>
        if i = clk then (TapeSymbol.bit true, HeadMove.right)
        else if h : ∃ j, ι j = i then
          (M.transition s (fun j => symbols (ι j))).2 h.choose
        else (symbols i, HeadMove.stay))
  result := fun s => M.result s

/-- The physical tapes carrying a simulated configuration. -/
noncomputable def clockTapes (ι : Fin k → Fin n) (clk : Fin n)
    (outer : Fin n → Tape) (inner : Fin k → Tape) (t : Nat) : Fin n → Tape :=
  fun i =>
    if i = clk then
      cellsTape (List.replicate t (TapeSymbol.bit true)) []
    else if h : ∃ j, ι j = i then inner h.choose
    else outer i

/-- The simulated tapes are read back unchanged. -/
theorem clockTapes_inner (ι : Fin k → Fin n) (clk : Fin n)
    (hinj : Function.Injective ι) (hclk : ∀ j, ι j ≠ clk)
    (outer : Fin n → Tape) (inner : Fin k → Tape) (t : Nat) (j : Fin k) :
    clockTapes ι clk outer inner t (ι j) = inner j := by
  classical
  rw [clockTapes]
  rw [if_neg (hclk j)]
  have hex : ∃ j', ι j' = ι j := ⟨j, rfl⟩
  rw [dif_pos hex]
  congr 1
  exact hinj hex.choose_spec

/-- …and the clock reads its own marks. -/
@[simp] theorem clockTapes_clk (ι : Fin k → Fin n) (clk : Fin n)
    (outer : Fin n → Tape) (inner : Fin k → Tape) (t : Nat) :
    clockTapes ι clk outer inner t clk =
      cellsTape (List.replicate t (TapeSymbol.bit true)) [] := by
  rw [clockTapes, if_pos rfl]

/-- The value at a selected index, without naming which one. -/
theorem clockTapes_at_sel (ι : Fin k → Fin n) (clk : Fin n)
    (hclk : ∀ j, ι j ≠ clk) (outer : Fin n → Tape) (inner : Fin k → Tape)
    (t : Nat) (i : Fin n) (hex : ∃ j, ι j = i) :
    clockTapes ι clk outer inner t i = inner hex.choose := by
  classical
  have hne : i ≠ clk := by
    obtain ⟨j, hj⟩ := hex
    rw [← hj]
    exact hclk j
  rw [clockTapes, if_neg hne, dif_pos hex]

/-- Tapes outside the simulation are untouched. -/
theorem clockTapes_outer (ι : Fin k → Fin n) (clk : Fin n)
    (outer : Fin n → Tape) (inner : Fin k → Tape) (t : Nat) (i : Fin n)
    (hi : i ≠ clk) (hni : ¬ ∃ j, ι j = i) :
    clockTapes ι clk outer inner t i = outer i := by
  classical
  rw [clockTapes, if_neg hi, dif_neg hni]


/-! ## The clock ticks -/

theorem clockTape_tick (t : Nat) :
    moveDir HeadMove.right
        (Tape.write (cellsTape (List.replicate t (TapeSymbol.bit true)) [])
          (TapeSymbol.bit true)) =
      cellsTape (List.replicate (t + 1) (TapeSymbol.bit true)) [] := by
  rw [write_cellsTape]
  rw [show ([] : List TapeSymbol).tail = [] from rfl]
  rw [cellsTape_moveRight, List.replicate_succ]

/-! ## One simulated step -/

set_option maxHeartbeats 1000000 in
/-- **The bisimulation step.**  A step of the embedded machine is a step of
the simulated one on the selected tapes, with the clock advanced by one and
every other tape untouched. -/
theorem embedClock_step (ι : Fin k → Fin n) (clk : Fin n)
    (hinj : Function.Injective ι) (hclk : ∀ j, ι j ≠ clk)
    (M : Machine k states) (outer : Fin n → Tape) (inner : Fin k → Tape)
    (t : Nat) (s : Fin states) (hlive : M.result s = none) :
    (embedClock ι clk M).step
        ⟨s, clockTapes ι clk outer inner t⟩ =
      ⟨(M.step ⟨s, inner⟩).state,
        clockTapes ι clk outer (M.step ⟨s, inner⟩).tape (t + 1)⟩ := by
  classical
  have hres : (embedClock ι clk M).result s = none := hlive
  have hsym : (fun j => (clockTapes ι clk outer inner t (ι j)).head) =
      (fun j => (inner j).head) := by
    funext j
    rw [clockTapes_inner ι clk hinj hclk outer inner t j]
  simp only [TypedMachine.step, hres]
  rw [Machine.step_of_result_none M ⟨s, inner⟩ hlive]
  have hstate : ((embedClock ι clk M).transition s
      (fun i => (clockTapes ι clk outer inner t i).head)).1 =
      (M.transition s (fun j => (inner j).head)).1 := by
    show (M.transition s (fun j =>
      (clockTapes ι clk outer inner t (ι j)).head)).1 = _
    rw [hsym]
  have haction : ∀ i : Fin n,
      ((embedClock ι clk M).transition s
        (fun i => (clockTapes ι clk outer inner t i).head)).2 i =
      (if i = clk then (TapeSymbol.bit true, HeadMove.right)
        else if h : ∃ j, ι j = i then
          (M.transition s (fun j => (inner j).head)).2 h.choose
        else ((clockTapes ι clk outer inner t i).head, HeadMove.stay)) := by
    intro i
    show (if i = clk then _ else if h : ∃ j, ι j = i then
      (M.transition s (fun j =>
        (clockTapes ι clk outer inner t (ι j)).head)).2 h.choose
      else _) = _
    rw [hsym]
  refine congrArg₂ TypedConfiguration.mk hstate ?_
  funext i
  rw [haction i]
  by_cases hi : i = clk
  · subst hi
    rw [clockTapes_clk, clockTapes_clk]
    simp only [if_pos rfl]
    exact clockTape_tick t
  · rw [if_neg hi]
    by_cases hex : ∃ j, ι j = i
    · rw [dif_pos hex]
      rw [clockTapes_at_sel ι clk hclk outer inner t i hex,
        clockTapes_at_sel ι clk hclk outer _ (t + 1) i hex]
    · rw [dif_neg hex]
      rw [clockTapes_outer ι clk outer inner t i hi hex,
        clockTapes_outer ι clk outer _ (t + 1) i hi hex]
      simp [Tape.write_head_self, Tape.move]


/-! ## The run -/

set_option maxHeartbeats 1000000 in
/-- **The bisimulation.**  While the simulated machine is live, `r` steps of
the embedded machine are `r` steps of the simulated one, with the clock
holding exactly `r` marks. -/
theorem embedClock_run (ι : Fin k → Fin n) (clk : Fin n)
    (hinj : Function.Injective ι) (hclk : ∀ j, ι j ≠ clk)
    (M : Machine k states) (outer : Fin n → Tape) :
    ∀ (r : Nat) (inner : Fin k → Tape) (s : Fin states) (t : Nat),
      (∀ m, m < r → M.result ((M.step^[m]) ⟨s, inner⟩).state = none) →
      (((embedClock ι clk M).step^[r]) ⟨s, clockTapes ι clk outer inner t⟩ :
        TypedConfiguration n (Fin states)) =
        ⟨((M.step^[r]) ⟨s, inner⟩).state,
          clockTapes ι clk outer ((M.step^[r]) ⟨s, inner⟩).tape (t + r)⟩ := by
  intro r
  induction r with
  | zero => intro inner s t _; simp
  | succ r ih =>
      intro inner s t hlive
      rw [Function.iterate_succ_apply]
      have h0 : M.result s = none := by
        have := hlive 0 (by omega)
        simpa using this
      rw [embedClock_step ι clk hinj hclk M outer inner t s h0]
      have hnext : ∀ m, m < r →
          M.result ((M.step^[m]) (M.step ⟨s, inner⟩)).state = none := by
        intro m hm
        have := hlive (m + 1) (by omega)
        rwa [Function.iterate_succ_apply] at this
      have hcfg : (M.step ⟨s, inner⟩) =
          ⟨(M.step ⟨s, inner⟩).state, (M.step ⟨s, inner⟩).tape⟩ := rfl
      rw [ih (M.step ⟨s, inner⟩).tape (M.step ⟨s, inner⟩).state (t + 1)
        (by intro m hm; rw [← hcfg]; exact hnext m hm)]
      rw [Function.iterate_succ_apply]
      congr 2
      · omega

/-- The embedded machine's verdict is the simulated machine's. -/
@[simp] theorem embedClock_result (ι : Fin k → Fin n) (clk : Fin n)
    (M : Machine k states) (s : Fin states) :
    (embedClock ι clk M).result s = M.result s := rfl

set_option maxHeartbeats 1000000 in
/-- **The delegate, as a subroutine.**  If the simulated machine halts at
time `T` with verdict `v`, so does the embedded one — leaving `T` clock marks
and the simulated final tapes in place. -/
theorem embedClock_spec (ι : Fin k → Fin n) (clk : Fin n)
    (hinj : Function.Injective ι) (hclk : ∀ j, ι j ≠ clk)
    (M : Machine k states) (outer : Fin n → Tape) (inner : Fin k → Tape)
    (T : Nat) (v : Bool)
    (hlive : ∀ m, m < T → M.result ((M.step^[m]) ⟨M.start, inner⟩).state = none)
    (hhalt : M.result ((M.step^[T]) ⟨M.start, inner⟩).state = some v) :
    HaltsExactly (embedClock ι clk M)
      ((embedClock ι clk M).startCfg (clockTapes ι clk outer inner 0)) T v ∧
    (((embedClock ι clk M).step^[T])
      ((embedClock ι clk M).startCfg
        (clockTapes ι clk outer inner 0))).tape =
      clockTapes ι clk outer ((M.step^[T]) ⟨M.start, inner⟩).tape T := by
  have hstart : (embedClock ι clk M).startCfg
      (clockTapes ι clk outer inner 0) =
      (⟨M.start, clockTapes ι clk outer inner 0⟩ :
        TypedConfiguration n (Fin states)) := rfl
  have hrun : ∀ r, (∀ m, m < r →
      M.result ((M.step^[m]) ⟨M.start, inner⟩).state = none) →
      (((embedClock ι clk M).step^[r])
        ((embedClock ι clk M).startCfg (clockTapes ι clk outer inner 0)) :
        TypedConfiguration n (Fin states)) =
        ⟨((M.step^[r]) ⟨M.start, inner⟩).state,
          clockTapes ι clk outer ((M.step^[r]) ⟨M.start, inner⟩).tape r⟩ := by
    intro r hr
    rw [hstart]
    have := embedClock_run ι clk hinj hclk M outer r inner M.start 0 hr
    simpa using this
  refine ⟨⟨?_, ?_⟩, ?_⟩
  · rw [hrun T hlive]
    exact hhalt
  · intro j hj
    rw [hrun j (fun m hm => hlive m (by omega))]
    exact hlive j hj
  · rw [hrun T hlive]

end SipserGacsLautemann
Source
Delegate combinator for the scheduler families; builds on Def_sgl_elim_solution.

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