The delegate, over a used tape
Definitionsgl_embed_clock2The delegate, over a used tape. sgl_embed_clock states the delegate over a clock whose left context is empty — a fresh tape. A scheduler's second round has no such tape: the clock carries the previous round's spent marks to the left of the head, and every later round carries more.
So the published form, though true, cannot be applied inside the loop it was built for. This module threads a left context Lc through the same statements and proofs. The generalisation is sound for a reason specific to this machine: the clock's action is right at every single step, so nothing to its left is ever read.
This is the fifth time in this campaign that a specification came out true but unusable, and the cause is the same each time — a quantity fixed at a value the consumer cannot supply. Here it was an implicit [] sitting inside a definition rather than a hypothesis, which is the hardest variety to notice: nothing in the statement looks over-specific until a caller has to produce a tape that has never been written to.
import Definitions.Def_sgl_skip_ahead
/-!
# The delegate, over a used tape
`sgl_embed_clock` states the delegate over a clock tape whose left context is
empty — a *fresh* tape. A scheduler's second round has no such tape: the
clock carries the previous round's spent marks to the left of the head.
The generalisation is sound because the clock's action is `right` at every
step, so nothing to its left is ever read. Threading a left context `Lc`
through the same proofs makes the delegate usable inside a loop, which is the
only place it was ever going to be used.
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}
/-- The physical tapes carrying a simulated configuration. -/
noncomputable def clockTapesL (ι : Fin k → Fin n) (clk : Fin n)
(outer : Fin n → Tape) (inner : Fin k → Tape) (Lc : List TapeSymbol)
(t : Nat) : Fin n → Tape :=
fun i =>
if i = clk then
cellsTape (List.replicate t (TapeSymbol.bit true) ++ Lc) []
else if h : ∃ j, ι j = i then inner h.choose
else outer i
/-- The simulated tapes are read back unchanged. -/
theorem clockTapesL_inner (ι : Fin k → Fin n) (clk : Fin n)
(hinj : Function.Injective ι) (hclk : ∀ j, ι j ≠ clk)
(outer : Fin n → Tape) (inner : Fin k → Tape) (Lc : List TapeSymbol)
(t : Nat) (j : Fin k) :
clockTapesL ι clk outer inner Lc t (ι j) = inner j := by
classical
rw [clockTapesL]
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 clockTapesL_clk (ι : Fin k → Fin n) (clk : Fin n)
(outer : Fin n → Tape) (inner : Fin k → Tape) (Lc : List TapeSymbol)
(t : Nat) :
clockTapesL ι clk outer inner Lc t clk =
cellsTape (List.replicate t (TapeSymbol.bit true) ++ Lc) [] := by
rw [clockTapesL, if_pos rfl]
/-- The value at a selected index, without naming which one. -/
theorem clockTapesL_at_sel (ι : Fin k → Fin n) (clk : Fin n)
(hclk : ∀ j, ι j ≠ clk) (outer : Fin n → Tape) (inner : Fin k → Tape)
(Lc : List TapeSymbol) (t : Nat) (i : Fin n) (hex : ∃ j, ι j = i) :
clockTapesL ι clk outer inner Lc t i = inner hex.choose := by
classical
have hne : i ≠ clk := by
obtain ⟨j, hj⟩ := hex
rw [← hj]
exact hclk j
rw [clockTapesL, if_neg hne, dif_pos hex]
/-- Tapes outside the simulation are untouched. -/
theorem clockTapesL_outer (ι : Fin k → Fin n) (clk : Fin n)
(outer : Fin n → Tape) (inner : Fin k → Tape) (Lc : List TapeSymbol) (t : Nat) (i : Fin n)
(hi : i ≠ clk) (hni : ¬ ∃ j, ι j = i) :
clockTapesL ι clk outer inner Lc t i = outer i := by
classical
rw [clockTapesL, if_neg hi, dif_neg hni]
/-! ## The clock ticks -/
theorem clockTapeL_tick (Lc : List TapeSymbol) (t : Nat) :
moveDir HeadMove.right
(Tape.write (cellsTape (List.replicate t (TapeSymbol.bit true) ++ Lc)
[]) (TapeSymbol.bit true)) =
cellsTape (List.replicate (t + 1) (TapeSymbol.bit true) ++ Lc) [] := by
rw [write_cellsTape]
rw [show ([] : List TapeSymbol).tail = [] from rfl]
rw [cellsTape_moveRight, List.replicate_succ]
rfl
/-! ## 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 embedClockL_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)
(Lc : List TapeSymbol) (t : Nat) (s : Fin states) (hlive : M.result s = none) :
(embedClock ι clk M).step
⟨s, clockTapesL ι clk outer inner Lc t⟩ =
⟨(M.step ⟨s, inner⟩).state,
clockTapesL ι clk outer (M.step ⟨s, inner⟩).tape Lc (t + 1)⟩ := by
classical
have hres : (embedClock ι clk M).result s = none := hlive
have hsym : (fun j => (clockTapesL ι clk outer inner Lc t (ι j)).head) =
(fun j => (inner j).head) := by
funext j
rw [clockTapesL_inner ι clk hinj hclk outer inner Lc 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 => (clockTapesL ι clk outer inner Lc t i).head)).1 =
(M.transition s (fun j => (inner j).head)).1 := by
show (M.transition s (fun j =>
(clockTapesL ι clk outer inner Lc t (ι j)).head)).1 = _
rw [hsym]
have haction : ∀ i : Fin n,
((embedClock ι clk M).transition s
(fun i => (clockTapesL ι clk outer inner Lc 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 ((clockTapesL ι clk outer inner Lc 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 =>
(clockTapesL ι clk outer inner Lc 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 [clockTapesL_clk, clockTapesL_clk]
simp only [if_pos rfl]
exact clockTapeL_tick Lc t
· rw [if_neg hi]
by_cases hex : ∃ j, ι j = i
· rw [dif_pos hex]
rw [clockTapesL_at_sel ι clk hclk outer inner Lc t i hex,
clockTapesL_at_sel ι clk hclk outer _ Lc (t + 1) i hex]
· rw [dif_neg hex]
rw [clockTapesL_outer ι clk outer inner Lc t i hi hex,
clockTapesL_outer ι clk outer _ Lc (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 embedClockL_run (ι : Fin k → Fin n) (clk : Fin n)
(hinj : Function.Injective ι) (hclk : ∀ j, ι j ≠ clk)
(M : Machine k states) (outer : Fin n → Tape) (Lc : List TapeSymbol) :
∀ (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, clockTapesL ι clk outer inner Lc t⟩ :
TypedConfiguration n (Fin states)) =
⟨((M.step^[r]) ⟨s, inner⟩).state,
clockTapesL ι clk outer ((M.step^[r]) ⟨s, inner⟩).tape Lc (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 [embedClockL_step ι clk hinj hclk M outer inner Lc 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 embedClockL_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 embedClockL_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)
(Lc : List TapeSymbol) (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 (clockTapesL ι clk outer inner Lc 0)) T v ∧
(((embedClock ι clk M).step^[T])
((embedClock ι clk M).startCfg
(clockTapesL ι clk outer inner Lc 0))).tape =
clockTapesL ι clk outer ((M.step^[T]) ⟨M.start, inner⟩).tape Lc T := by
have hstart : (embedClock ι clk M).startCfg
(clockTapesL ι clk outer inner Lc 0) =
(⟨M.start, clockTapesL ι clk outer inner Lc 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 (clockTapesL ι clk outer inner Lc 0)) :
TypedConfiguration n (Fin states)) =
⟨((M.step^[r]) ⟨M.start, inner⟩).state,
clockTapesL ι clk outer ((M.step^[r]) ⟨M.start, inner⟩).tape Lc r⟩ := by
intro r hr
rw [hstart]
have := embedClockL_run ι clk hinj hclk M outer Lc 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