The clock-ticking delegate
Definitionsgl_embed_clockRunning an arbitrary machine as a subroutine, on a clock. embedClock ι clk M runs a Machine k inside a larger tape space: tape plays the simulated machine's tape , 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 steps has moved each head at most cells from its origin, and the clock holds exactly 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 with verdict , the embedded machine does too, leaving marks and the simulated final tapes in place.
The selector 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.
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