Tape navigation macros: a direction-generic scan and rewind
Definitionsgl_tape_navigationTape navigation macros: the first consumer of sgl_subroutine_algebra.
Advancing a head to the end of the written region it sits in is the primitive on which block selection, copying and counter manipulation all rest.
A direction-generic engine. Rather than prove one scan per direction, scanToBlank_spec_of takes the head-move direction as a parameter together with two tape-level facts — the head reads a written cell at every distance below , and a blank at distance — and concludes that the scan is a subroutine of cost . The direction plays no role in that proof, so each concrete scan costs exactly one tape induction.
The two scans. Writing for the distance from the head to the first blank beyond it,
rightward with of the cells right of the head, leftward with of the cells to its left.
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 buys.
Rewind. rewindToStart retreats to the blank left of the written region and then steps back onto its first cell — the macro a scheduler runs between verifier calls, of cost . It is the first macro that is not itself a loop: a loop composed with straight-line code.
Method. All tape-level content is two inductions, blank_scan_right_spec and blank_scan_left_spec, each proving both halves of the scan invariant in a single pass. Everything above that line is assembled through the algebra — round specification from HaltsExactly.andThen, loop specification from repeatUntilFalse_spec — and no proof in the assembly mentions step or run. That separation is the intended style for the macros still to come: copy, xorInto, blockSelect, counter increment and compare, and the ternary majority fold, each needing its own small tape induction and then composing without further machine reasoning.
import Definitions.Def_sgl_subroutine_algebra
/-!
# Tape navigation macros
The first consumer of the subroutine algebra. A scanning macro — "advance a
head to the end of the written region it sits in" — is the primitive on which
block selection, copying and counter manipulation all rest.
Rather than prove one scan per direction, `scanToBlank_spec_of` is a single
engine parameterised by the head-move direction and by two tape-level facts;
the rightward and leftward scans are then instantiations of it, and only their
tape-level inductions differ.
On top sits `rewindToStart`, which composes a loop with straight-line code —
the first macro that is not itself a loop, and a demonstration that the
loop-to-subroutine bridge does what it was built for.
The step counts here are **functions of the tape contents**, not numerals. That
is what a finite, input-independent state space cannot express on its own, and
it is what the tape-resident loop counter of `repeatUntilFalse` buys.
-/
namespace SipserGacsLautemann
variable {tapes : Nat}
/-! ## Tape-level arithmetic
Pure statements about `Tape.move`; no machines yet. -/
/-- One head step in direction `dir`. -/
def moveDir (dir : HeadMove) (tape : Tape) : Tape := Tape.move tape dir
/-- Distance from the head to the first blank strictly beyond it, along a list
of cells. Positions past 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 moveDir_right_cons_bit (left : List TapeSymbol) (head : TapeSymbol)
(b : Bool) (rest : List TapeSymbol) :
moveDir HeadMove.right ⟨left, head, TapeSymbol.bit b :: rest⟩ =
⟨head :: left, TapeSymbol.bit b, rest⟩ := rfl
theorem moveDir_left_cons_bit (left : List TapeSymbol) (head : TapeSymbol)
(b : Bool) (right : List TapeSymbol) :
moveDir HeadMove.left ⟨TapeSymbol.bit b :: left, head, right⟩ =
⟨left, TapeSymbol.bit b, head :: right⟩ := rfl
/-- Rightward: the head reads a written cell at every distance below
`blankIndex right`, and a blank at distance `blankIndex right + 1`. Both halves
in one induction. -/
theorem blank_scan_right_spec :
∀ (right : List TapeSymbol) (left : List TapeSymbol) (head : TapeSymbol),
(∀ k, k < blankIndex right →
((moveDir HeadMove.right)^[k + 1] ⟨left, head, right⟩).head ≠
TapeSymbol.blank) ∧
((moveDir HeadMove.right)^[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, moveDir, Tape.move]
| cons symbol rest ih =>
intro left head
cases symbol with
| blank =>
refine ⟨?_, ?_⟩
· intro k hk; simp [blankIndex] at hk
· simp [blankIndex, moveDir, Tape.move]
| bit b =>
obtain ⟨ihlt, iheq⟩ := ih (head :: left) (TapeSymbol.bit b)
refine ⟨?_, ?_⟩
· intro k hk
rw [Function.iterate_succ_apply, moveDir_right_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, moveDir_right_cons_bit]
exact iheq
/-- Leftward mirror of `blank_scan_right_spec`. -/
theorem blank_scan_left_spec :
∀ (left : List TapeSymbol) (head : TapeSymbol) (right : List TapeSymbol),
(∀ k, k < blankIndex left →
((moveDir HeadMove.left)^[k + 1] ⟨left, head, right⟩).head ≠
TapeSymbol.blank) ∧
((moveDir HeadMove.left)^[blankIndex left + 1]
⟨left, head, right⟩).head = TapeSymbol.blank := by
intro left
induction left with
| nil =>
intro head right
refine ⟨?_, ?_⟩
· intro k hk; simp [blankIndex] at hk
· simp [blankIndex, moveDir, Tape.move]
| cons symbol rest ih =>
intro head right
cases symbol with
| blank =>
refine ⟨?_, ?_⟩
· intro k hk; simp [blankIndex] at hk
· simp [blankIndex, moveDir, Tape.move]
| bit b =>
obtain ⟨ihlt, iheq⟩ := ih (TapeSymbol.bit b) (head :: right)
refine ⟨?_, ?_⟩
· intro k hk
rw [Function.iterate_succ_apply, moveDir_left_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, moveDir_left_cons_bit]
exact iheq
/-! ## The scan, as a direction-generic engine -/
/-- Move tape `i`'s head one cell in direction `dir`, leaving other tapes alone. -/
def moveAction (i : Fin tapes) (dir : HeadMove) :
(Fin tapes → TapeSymbol) → (Fin tapes → TapeSymbol × HeadMove) :=
fun symbols j => (symbols j, if j = i then dir 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 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 applyAction_moveAction (tape : Fin tapes → Tape) (i : Fin tapes)
(dir : HeadMove) :
applyAction tape (moveAction i dir) =
Function.update tape i (moveDir dir (tape i)) := by
funext j
by_cases hj : j = i
· subst hj
simp [applyAction, moveAction, moveDir, Tape.write_head_self]
· simp [applyAction, moveAction, hj, Tape.write_head_self, Tape.move]
/-- The loop body: one step in direction `dir`, then ask whether we are still on
written tape. -/
def scanBody (i : Fin tapes) (dir : HeadMove) :
TypedMachine tapes (Bool ⊕ Bool × Option Bool) :=
(TypedMachine.act (moveAction i dir)).andThen
(fun _ => TypedMachine.test (notBlankAt i))
/-- Advance tape `i`'s head in direction `dir` to the first blank strictly
beyond the current cell. -/
def scanToBlank (i : Fin tapes) (dir : HeadMove) :
TypedMachine tapes (Bool ⊕ Bool × Option Bool) :=
(scanBody i dir).repeatUntilFalse
/-- Tapes after `n` rounds: tape `i` advanced `n` cells in direction `dir`. -/
def scanTapesDir (tape : Fin tapes → Tape) (i : Fin tapes) (dir : HeadMove)
(n : Nat) : Fin tapes → Tape :=
Function.update tape i ((moveDir dir)^[n] (tape i))
theorem scanTapesDir_zero (tape : Fin tapes → Tape) (i : Fin tapes)
(dir : HeadMove) : scanTapesDir tape i dir 0 = tape := by
funext j; by_cases hj : j = i <;> simp [scanTapesDir, hj]
theorem scanTapesDir_succ (tape : Fin tapes → Tape) (i : Fin tapes)
(dir : HeadMove) (n : Nat) :
applyAction (scanTapesDir tape i dir n) (moveAction i dir) =
scanTapesDir tape i dir (n + 1) := by
rw [applyAction_moveAction]
funext j
by_cases hj : j = i
· subst hj; simp [scanTapesDir, Function.iterate_succ_apply']
· simp [scanTapesDir, hj]
theorem scanTapesDir_head (tape : Fin tapes → Tape) (i : Fin tapes)
(dir : HeadMove) (n : Nat) :
((scanTapesDir tape i dir n) i).head = ((moveDir dir)^[n] (tape i)).head := by
simp [scanTapesDir]
theorem scanBody_round (i : Fin tapes) (dir : HeadMove)
(tape : Fin tapes → Tape) (m : Nat) :
HaltsExactly (scanBody i dir)
((scanBody i dir).startCfg (scanTapesDir tape i dir m)) (1 + 1 + 1)
(notBlankAt i (fun j => ((scanTapesDir tape i dir (m + 1)) j).head)) := by
have h₂ :
HaltsExactly (TypedMachine.test (notBlankAt i))
((TypedMachine.test (notBlankAt i)).startCfg
(((TypedMachine.act (moveAction i dir)).step^[1])
((TypedMachine.act (moveAction i dir)).startCfg
(scanTapesDir tape i dir m))).tape) 1
(notBlankAt i
(fun j => ((scanTapesDir tape i dir (m + 1)) j).head)) := by
rw [TypedMachine.act_tape, scanTapesDir_succ]
exact TypedMachine.test_spec (notBlankAt i) _
exact HaltsExactly.andThen
(TypedMachine.act_spec (moveAction i dir) (scanTapesDir tape i dir m)) h₂
theorem scanBody_round_tape (i : Fin tapes) (dir : HeadMove)
(tape : Fin tapes → Tape) (m : Nat) :
(((scanBody i dir).step^[1 + 1 + 1])
((scanBody i dir).startCfg (scanTapesDir tape i dir m))).tape =
scanTapesDir tape i dir (m + 1) := by
have h := TypedMachine.doWhile_round_tape
(TypedMachine.act (moveAction i dir)) (notBlankAt i)
(scanTapesDir tape i dir m) 1 true
(TypedMachine.act_spec (moveAction i dir) (scanTapesDir tape i dir m)).halts
(TypedMachine.act_spec (moveAction i dir) (scanTapesDir tape i dir m)).fresh
rw [TypedMachine.act_tape, scanTapesDir_succ] at h
exact h
/-- **The scan engine.** Given only the two tape-level facts — the head reads a
written cell at every distance below `d`, and a blank at distance `d + 1` — the
scan is a subroutine of cost `4d + 3`. The direction plays no role in the
proof, so each concrete scan costs exactly one tape induction. -/
theorem scanToBlank_spec_of (i : Fin tapes) (dir : HeadMove)
(tape : Fin tapes → Tape) (d : Nat)
(hlt : ∀ k, k < d →
((moveDir dir)^[k + 1] (tape i)).head ≠ TapeSymbol.blank)
(heq : ((moveDir dir)^[d + 1] (tape i)).head = TapeSymbol.blank) :
HaltsExactly (scanToBlank i dir) ((scanToBlank i dir).startCfg tape)
(d * 4 + 3) false := by
have hround : ∀ m, m < d →
HaltsExactly (scanBody i dir)
((scanBody i dir).startCfg (scanTapesDir tape i dir m)) (1 + 1 + 1)
true ∧
(scanBody i dir).startCfg (scanTapesDir tape i dir (m + 1)) =
⟨(scanBody i dir).start,
(((scanBody i dir).step^[1 + 1 + 1])
((scanBody i dir).startCfg (scanTapesDir tape i dir m))).tape⟩ := by
intro m hm
have hhead : ((scanTapesDir tape i dir (m + 1)) i).head ≠ TapeSymbol.blank := by
rw [scanTapesDir_head]; exact hlt m hm
refine ⟨?_, ?_⟩
· have h := scanBody_round i dir tape m
rwa [notBlankAt_true i (scanTapesDir tape i dir (m + 1)) hhead] at h
· rw [scanBody_round_tape]
rfl
have hexit :
HaltsExactly (scanBody i dir)
((scanBody i dir).startCfg (scanTapesDir tape i dir d)) (1 + 1 + 1)
false := by
have hhead : ((scanTapesDir tape i dir (d + 1)) i).head = TapeSymbol.blank := by
rw [scanTapesDir_head]; exact heq
have h := scanBody_round i dir tape d
rwa [notBlankAt_false i (scanTapesDir tape i dir (d + 1)) hhead] at h
have hloop :=
TypedMachine.repeatUntilFalse_spec (scanBody i dir)
(fun m => (scanBody i dir).startCfg (scanTapesDir tape i dir m))
(fun _ => 1 + 1 + 1) d (1 + 1 + 1) hround hexit
rw [loopCost_const] at hloop
simp only [scanTapesDir_zero] at hloop
exact hloop
/-! ## The two concrete scans -/
/-- Advance tape `i` to the first blank right of the written region, in
`4d + 3` steps where `d` is the distance to that blank. -/
theorem scanRightToBlank_spec (i : Fin tapes) (tape : Fin tapes → Tape) :
HaltsExactly (scanToBlank i HeadMove.right)
((scanToBlank i HeadMove.right).startCfg tape)
(blankIndex (tape i).right * 4 + 3) false := by
obtain ⟨hlt, heq⟩ :=
blank_scan_right_spec (tape i).right (tape i).left (tape i).head
exact scanToBlank_spec_of i HeadMove.right tape (blankIndex (tape i).right)
hlt heq
/-- Retreat tape `i` to the blank immediately left of its written region. -/
theorem scanLeftToBlank_spec (i : Fin tapes) (tape : Fin tapes → Tape) :
HaltsExactly (scanToBlank i HeadMove.left)
((scanToBlank i HeadMove.left).startCfg tape)
(blankIndex (tape i).left * 4 + 3) false := by
obtain ⟨hlt, heq⟩ :=
blank_scan_left_spec (tape i).left (tape i).head (tape i).right
exact scanToBlank_spec_of i HeadMove.left tape (blankIndex (tape i).left)
hlt heq
/-! ## Rewind: a loop composed with straight-line code -/
/-- Retreat to the blank left of the written region, then step back onto its
first cell. This is the macro a scheduler runs between verifier calls. -/
def rewindToStart (i : Fin tapes) :
TypedMachine tapes ((Bool ⊕ Bool × Option Bool) ⊕ Bool × Bool) :=
(scanToBlank i HeadMove.left).andThen
(fun _ => TypedMachine.act (moveAction i HeadMove.right))
/-- `rewindToStart` is a subroutine of cost `4d + 5`. The proof is one
application of the loop-to-subroutine bridge followed by one of
`HaltsExactly.andThen` — no tape, `step` or `run` appears in it. -/
theorem rewindToStart_spec (i : Fin tapes) (tape : Fin tapes → Tape) :
HaltsExactly (rewindToStart i)
(TypedConfiguration.inLeft
((scanToBlank i HeadMove.left).startCfg tape))
(blankIndex (tape i).left * 4 + 3 + 1 + 1) true :=
HaltsExactly.andThen (scanLeftToBlank_spec i tape)
(TypedMachine.act_spec (moveAction i HeadMove.right) _)
end SipserGacsLautemann