Tape macros and the loop-to-subroutine bridge
Definitionsgl_machine_macrosTape macros built on sgl_machine_algebra, together with the generic bridge from a loop to a subroutine specification.
The loop as a subroutine. repeatUntilFalse_rounds locates a loop at its round boundaries, but to feed a loop into HaltsExactly.andThen one also needs that it does not halt in between. repeatUntilFalse_spec closes that gap once and for all: given per-round specifications and a final round reporting false, the entire loop is a subroutine of cost
and therefore composes with everything else. loopCost_const evaluates this to for a constant per-round cost.
The scanning macro. scanRightToBlank i advances tape 's head to the first blank strictly to the right of its current position, leaving every other tape untouched. Writing for the distance to that blank, its specification is
The step count is a function of the tape contents, not a numeral. This is the situation a finite, input-independent state space cannot express by itself, and it is precisely what the tape-resident loop counter of repeatUntilFalse buys: locating the end of a written region is the primitive on which block selection, copying and counter manipulation all rest.
Method. The tape-level content is a single induction, blank_scan_spec, proving in one pass that the head reads a written cell at every distance below and a blank at distance . Everything above that line is assembled through the algebra: the round specification comes from HaltsExactly.andThen, the loop specification from repeatUntilFalse_spec, and no proof in the assembly mentions step or run at all. That separation is the intended working style for the remaining macros — rewind, copy, xorInto, blockSelect, counter increment and compare, and the majority fold — each of which needs its own small tape induction and then composes without further machine reasoning.
import Definitions.Def_sgl_machine_algebra
/-!
# Tape macros built on the machine algebra
The algebra of `Def_sgl_machine_algebra` reduces machine construction to
straight-line code, branching and bounded iteration. This module is the first
consumer: it builds the scanning macro every scheduler needs — "advance a head
to the end of the string it is sitting on" — and proves its `HaltsExactly`
specification, with an **input-dependent** step count, entirely through the
algebra.
The point of interest is that the step count is not a numeral: it is
`4 * blankIndex r + 3`, a function of the tape contents. That is exactly the
situation a finite state space cannot express by itself, and it is handled here
by `repeatUntilFalse`, whose loop counter lives on the tape.
-/
namespace SipserGacsLautemann
variable {tapes : Nat}
/-! ## Tape-level arithmetic
Pure statements about `Tape.move`; no machines yet. -/
/-- One step of the head to the right. -/
def moveRight (tape : Tape) : Tape := Tape.move tape .right
/-- Distance from the head to the first blank strictly to its right. Cells past
the end of the written region are blank, so this is total. -/
def blankIndex : List TapeSymbol → Nat
| [] => 0
| TapeSymbol.blank :: _ => 0
| TapeSymbol.bit _ :: rest => blankIndex rest + 1
theorem moveRight_cons_bit (left : List TapeSymbol) (head : TapeSymbol)
(b : Bool) (rest : List TapeSymbol) :
moveRight ⟨left, head, TapeSymbol.bit b :: rest⟩ =
⟨head :: left, TapeSymbol.bit b, rest⟩ := rfl
/-- Before reaching the first blank the head always reads a written cell, and at
distance `blankIndex r + 1` it reads a blank. Both halves at once, so the
induction on the tape's right-hand contents runs only once. -/
theorem blank_scan_spec :
∀ (right : List TapeSymbol) (left : List TapeSymbol) (head : TapeSymbol),
(∀ k, k < blankIndex right →
(moveRight^[k + 1] ⟨left, head, right⟩).head ≠ TapeSymbol.blank) ∧
(moveRight^[blankIndex right + 1] ⟨left, head, right⟩).head =
TapeSymbol.blank := by
intro right
induction right with
| nil =>
intro left head
refine ⟨?_, ?_⟩
· intro k hk; simp [blankIndex] at hk
· simp [blankIndex, moveRight, Tape.move]
| cons symbol rest ih =>
intro left head
cases symbol with
| blank =>
refine ⟨?_, ?_⟩
· intro k hk; simp [blankIndex] at hk
· simp [blankIndex, moveRight, Tape.move]
| bit b =>
obtain ⟨ihlt, iheq⟩ := ih (head :: left) (TapeSymbol.bit b)
refine ⟨?_, ?_⟩
· intro k hk
rw [Function.iterate_succ_apply, moveRight_cons_bit]
cases k with
| zero => simp
| succ k =>
exact ihlt k (by simp [blankIndex] at hk; omega)
· rw [show blankIndex (TapeSymbol.bit b :: rest) + 1
= (blankIndex rest + 1) + 1 by simp [blankIndex]]
rw [Function.iterate_succ_apply, moveRight_cons_bit]
exact iheq
/-! ## The scanning macro -/
/-- Move tape `i`'s head one cell right, leaving every other tape alone. -/
def moveRightAction (i : Fin tapes) :
(Fin tapes → TapeSymbol) → (Fin tapes → TapeSymbol × HeadMove) :=
fun symbols j => (symbols j, if j = i then HeadMove.right else HeadMove.stay)
/-- "Tape `i`'s head is not on a blank." -/
def notBlankAt (i : Fin tapes) : (Fin tapes → TapeSymbol) → Bool :=
fun symbols => match symbols i with
| TapeSymbol.blank => false
| TapeSymbol.bit _ => true
theorem applyAction_moveRightAction (tape : Fin tapes → Tape) (i : Fin tapes) :
applyAction tape (moveRightAction i) =
Function.update tape i (moveRight (tape i)) := by
funext j
by_cases hj : j = i
· subst hj
simp [applyAction, moveRightAction, moveRight, Tape.write_head_self]
· simp [applyAction, moveRightAction, hj, Tape.write_head_self, Tape.move]
/-- The loop body: step right, then ask whether we are still on written tape. -/
def scanRightBody (i : Fin tapes) :
TypedMachine tapes (Bool ⊕ Bool × Option Bool) :=
(TypedMachine.act (moveRightAction i)).andThen
(fun _ => TypedMachine.test (notBlankAt i))
/-- Advance tape `i`'s head to the first blank at or to the right of the next
cell. Every other tape is untouched. -/
def scanRightToBlank (i : Fin tapes) :
TypedMachine tapes (Bool ⊕ Bool × Option Bool) :=
(scanRightBody i).repeatUntilFalse
/-- Tapes after `n` rounds of the scan: tape `i` advanced `n` cells. -/
def scanTapes (tape : Fin tapes → Tape) (i : Fin tapes) (n : Nat) :
Fin tapes → Tape :=
Function.update tape i (moveRight^[n] (tape i))
theorem scanTapes_zero (tape : Fin tapes → Tape) (i : Fin tapes) :
scanTapes tape i 0 = tape := by
funext j; by_cases hj : j = i <;> simp [scanTapes, hj]
theorem scanTapes_succ (tape : Fin tapes → Tape) (i : Fin tapes) (n : Nat) :
applyAction (scanTapes tape i n) (moveRightAction i) =
scanTapes tape i (n + 1) := by
rw [applyAction_moveRightAction]
funext j
by_cases hj : j = i
· subst hj
simp [scanTapes, Function.iterate_succ_apply']
· simp [scanTapes, hj]
/-- One round of the scan costs three steps, advances tape `i` by one cell, and
reports whether to continue. -/
theorem scanRightBody_spec (i : Fin tapes) (tape : Fin tapes → Tape) :
HaltsExactly (scanRightBody i)
((scanRightBody i).startCfg tape) (1 + 1 + 1)
(notBlankAt i (fun j => ((applyAction tape (moveRightAction i)) j).head)) := by
have h₂ :
HaltsExactly (TypedMachine.test (notBlankAt i))
((TypedMachine.test (notBlankAt i)).startCfg
(((TypedMachine.act (moveRightAction i)).step^[1])
((TypedMachine.act (moveRightAction i)).startCfg tape)).tape) 1
(notBlankAt i
(fun j => ((applyAction tape (moveRightAction i)) j).head)) := by
rw [TypedMachine.act_tape]
exact TypedMachine.test_spec (notBlankAt i) _
exact HaltsExactly.andThen (TypedMachine.act_spec (moveRightAction i) tape) h₂
theorem scanRightBody_tape (i : Fin tapes) (tape : Fin tapes → Tape) :
(((scanRightBody i).step^[1 + 1 + 1])
((scanRightBody i).startCfg tape)).tape =
applyAction tape (moveRightAction i) := by
have h := TypedMachine.doWhile_round_tape
(TypedMachine.act (moveRightAction i)) (notBlankAt i) tape 1 true
(TypedMachine.act_spec (moveRightAction i) tape).halts
(TypedMachine.act_spec (moveRightAction i) tape).fresh
rw [TypedMachine.act_tape] at h
exact h
/-! ## Generic loop specifications
`repeatUntilFalse_rounds` locates the machine at round boundaries; to feed a
loop into `HaltsExactly.andThen` one also needs that it does not halt in
between. These three lemmas close that gap once, generically. -/
variable {S : Type}
/-- Strictly before the body halts, the loop has not halted either. -/
theorem TypedMachine.repeatUntilFalse_pre_fresh
(body : TypedMachine tapes S) (c : TypedConfiguration tapes S)
(a : Nat) (v : Bool) (h : HaltsExactly body c a v) :
∀ t, t < a →
body.repeatUntilFalse.result
((body.repeatUntilFalse.step^[t]) c).state = none := by
intro t ht
rw [body.repeatUntilFalse_iterate_fresh c t (fun j hj => h.fresh j (by omega))]
simp [TypedMachine.repeatUntilFalse, h.fresh t ht]
/-- A round that ends in `true` does not halt the loop: it restarts it. -/
theorem TypedMachine.repeatUntilFalse_round_fresh
(body : TypedMachine tapes S) (c : TypedConfiguration tapes S)
(a : Nat) (h : HaltsExactly body c a true) :
∀ t, t < a + 1 →
body.repeatUntilFalse.result
((body.repeatUntilFalse.step^[t]) c).state = none := by
intro t ht
rcases Nat.lt_or_ge t a with hlt | hge
· exact body.repeatUntilFalse_pre_fresh c a true h t hlt
· have hta : t = a := by omega
subst hta
rw [body.repeatUntilFalse_iterate_fresh c t h.fresh]
simp [TypedMachine.repeatUntilFalse, h.halts]
theorem TypedMachine.repeatUntilFalse_rounds_fresh
(body : TypedMachine tapes S)
(config : Nat → TypedConfiguration tapes S) (cost : Nat → Nat) (rounds : Nat)
(hround : ∀ i, i < rounds →
HaltsExactly body (config i) (cost i) true ∧
config (i + 1) = ⟨body.start, ((body.step^[cost i]) (config i)).tape⟩) :
∀ j, j < loopCost cost rounds →
body.repeatUntilFalse.result
((body.repeatUntilFalse.step^[j]) (config 0)).state = none := by
induction rounds with
| zero => intro j hj; simp [loopCost] at hj
| succ rounds ih =>
intro j hj
rcases Nat.lt_or_ge j (loopCost cost rounds) with hlt | hge
· exact ih (fun i hi => hround i (by omega)) j hlt
· obtain ⟨t, ht⟩ := Nat.exists_eq_add_of_le hge
have htlt : t < cost rounds + 1 := by
rw [loopCost] at hj; omega
rw [ht, Nat.add_comm, Function.iterate_add_apply,
body.repeatUntilFalse_rounds config cost rounds
(fun i hi => hround i (by omega))]
exact body.repeatUntilFalse_round_fresh (config rounds) (cost rounds)
(hround rounds (by omega)).1 t htlt
/-- **The loop as a subroutine.** Given per-round specs and a final round that
reports `false`, the whole loop is a `HaltsExactly` subroutine of cost
`loopCost cost rounds + a` — and therefore composes with `andThen`. -/
theorem TypedMachine.repeatUntilFalse_spec
(body : TypedMachine tapes S)
(config : Nat → TypedConfiguration tapes S) (cost : Nat → Nat)
(rounds : Nat) (a : Nat)
(hround : ∀ i, i < rounds →
HaltsExactly body (config i) (cost i) true ∧
config (i + 1) = ⟨body.start, ((body.step^[cost i]) (config i)).tape⟩)
(hexit : HaltsExactly body (config rounds) a false) :
HaltsExactly body.repeatUntilFalse (config 0)
(loopCost cost rounds + a) false := by
have hrun := body.repeatUntilFalse_rounds config cost rounds hround
constructor
· rw [Nat.add_comm, Function.iterate_add_apply, hrun]
exact body.repeatUntilFalse_exit (config rounds) a hexit
· intro j hj
rcases Nat.lt_or_ge j (loopCost cost rounds) with hlt | hge
· exact body.repeatUntilFalse_rounds_fresh config cost rounds hround j hlt
· obtain ⟨t, ht⟩ := Nat.exists_eq_add_of_le hge
have htlt : t < a := by omega
rw [ht, Nat.add_comm, Function.iterate_add_apply, hrun]
exact body.repeatUntilFalse_pre_fresh (config rounds) a false hexit t htlt
theorem loopCost_const (c : Nat) :
∀ n : Nat, loopCost (fun _ => c) n = n * (c + 1) := by
intro n
induction n with
| zero => simp [loopCost]
| succ n ih => rw [loopCost, ih, Nat.succ_mul]
/-! ## The scan, specified
Assembling the pieces. Note that nothing below reasons about `step` or `run`:
the round spec comes from `HaltsExactly.andThen`, the loop spec from
`repeatUntilFalse_spec`, and the tape facts from `blank_scan_spec`. -/
theorem notBlankAt_true (i : Fin tapes) (t : Fin tapes → Tape)
(h : (t i).head ≠ TapeSymbol.blank) :
notBlankAt i (fun j => (t j).head) = true := by
show (match (t i).head with
| TapeSymbol.blank => false
| TapeSymbol.bit _ => true) = true
cases hcase : (t i).head with
| blank => exact absurd hcase h
| bit b => rfl
theorem notBlankAt_false (i : Fin tapes) (t : Fin tapes → Tape)
(h : (t i).head = TapeSymbol.blank) :
notBlankAt i (fun j => (t j).head) = false := by
show (match (t i).head with
| TapeSymbol.blank => false
| TapeSymbol.bit _ => true) = false
rw [h]
theorem scanTapes_head (tape : Fin tapes → Tape) (i : Fin tapes) (n : Nat) :
((scanTapes tape i n) i).head = (moveRight^[n] (tape i)).head := by
simp [scanTapes]
/-- Round `m` of the scan continues precisely when cell `m + 1` is written. -/
theorem scanRightBody_round (i : Fin tapes) (tape : Fin tapes → Tape) (m : Nat) :
HaltsExactly (scanRightBody i)
((scanRightBody i).startCfg (scanTapes tape i m)) (1 + 1 + 1)
(notBlankAt i (fun j => ((scanTapes tape i (m + 1)) j).head)) := by
have h := scanRightBody_spec i (scanTapes tape i m)
rwa [scanTapes_succ] at h
theorem scanRightBody_round_tape (i : Fin tapes) (tape : Fin tapes → Tape)
(m : Nat) :
(((scanRightBody i).step^[1 + 1 + 1])
((scanRightBody i).startCfg (scanTapes tape i m))).tape =
scanTapes tape i (m + 1) := by
rw [scanRightBody_tape, scanTapes_succ]
/-- **The scanning macro, specified.** Starting anywhere, `scanRightToBlank i`
advances tape `i` to the first blank strictly to the right of the head, in
`4 · d + 3` steps where `d` is the distance to that blank. The step count is a
function of the tape contents, not a numeral — which is exactly what a finite
state space cannot express on its own. -/
theorem scanRightToBlank_spec (i : Fin tapes) (tape : Fin tapes → Tape) :
HaltsExactly (scanRightToBlank i)
((scanRightToBlank i).startCfg tape)
(blankIndex (tape i).right * 4 + 3) false := by
set d := blankIndex (tape i).right with hd
obtain ⟨hlt, heq⟩ :=
blank_scan_spec (tape i).right (tape i).left (tape i).head
have htape : (⟨(tape i).left, (tape i).head, (tape i).right⟩ : Tape) = tape i := rfl
rw [htape] at hlt heq
have hround : ∀ m, m < d →
HaltsExactly (scanRightBody i)
((scanRightBody i).startCfg (scanTapes tape i m)) (1 + 1 + 1) true ∧
(scanRightBody i).startCfg (scanTapes tape i (m + 1)) =
⟨(scanRightBody i).start,
(((scanRightBody i).step^[1 + 1 + 1])
((scanRightBody i).startCfg (scanTapes tape i m))).tape⟩ := by
intro m hm
have hhead : ((scanTapes tape i (m + 1)) i).head ≠ TapeSymbol.blank := by
rw [scanTapes_head]; exact hlt m hm
have hverdict :
notBlankAt i (fun j => ((scanTapes tape i (m + 1)) j).head) = true := by
exact notBlankAt_true i (scanTapes tape i (m + 1)) hhead
refine ⟨?_, ?_⟩
· have h := scanRightBody_round i tape m
rwa [hverdict] at h
· rw [scanRightBody_round_tape]
rfl
have hexit :
HaltsExactly (scanRightBody i)
((scanRightBody i).startCfg (scanTapes tape i d)) (1 + 1 + 1) false := by
have hhead : ((scanTapes tape i (d + 1)) i).head = TapeSymbol.blank := by
rw [scanTapes_head]; exact heq
have hverdict :
notBlankAt i (fun j => ((scanTapes tape i (d + 1)) j).head) = false := by
exact notBlankAt_false i (scanTapes tape i (d + 1)) hhead
have h := scanRightBody_round i tape d
rwa [hverdict] at h
have hloop :=
TypedMachine.repeatUntilFalse_spec (scanRightBody i)
(fun m => (scanRightBody i).startCfg (scanTapes tape i m))
(fun _ => 1 + 1 + 1) d (1 + 1 + 1) hround hexit
rw [loopCost_const] at hloop
simp only [scanTapes_zero] at hloop
exact hloop
end SipserGacsLautemann