Walking one tape under another's guidance
Definitionsgl_guided_walkWalking one tape under another's guidance — the counting primitive the scheduler families need.
guidedWalk g w dir wr walks the guide tape rightwards over a run of non-blank marks; for each mark it applies one action to the worker tape — a move in direction dir, optionally writing first. guidedWalk_spec: if the guide carries marks from its head, the walk performs exactly worker actions in steps and halts with the guide on the blank past them.
Why this is the crux of counting. A machine cannot count to an input-dependent bound in its finite state. It can, however, count against marks already written on a tape — and the clock left by embedClock carries exactly one mark per simulated step. A guided walk therefore performs a number of worker steps proportional to the simulated running time, which is precisely the bound needed to erase the worker's garbage. The guide is left standing on the blank past its marks; walking it back is another guided walk in the other direction, so the same primitive both counts and rewinds.
A structural note on the loop body. The composition algebra takes a round's verdict from its last machine, so a body that must both test and act cannot simply test first — the action's verdict would overwrite the decision. Ending each branch with an explicit halt of the intended verdict fixes it, and gives the right behaviour at zero marks for free: the walk exits immediately without acting.
import Definitions.Def_sgl_embed_clock
/-!
# Walking one tape under another's guidance
`guidedWalk g w dir wr` walks the *guide* tape `g` rightwards over a run of
non-blank marks; for each mark it applies one action to the *worker* tape `w`
— a move in direction `dir`, optionally writing `wr` first.
This is the counting primitive the scheduler families need. A machine cannot
count to an input-dependent bound in its finite state, but it can count against
marks already on a tape: the clock left by `embedClock` has exactly one mark
per simulated step, so a guided walk performs a number of worker steps
proportional to the simulated running time — which is exactly the bound needed
to erase the worker's garbage.
The guide is left standing on the blank past its marks; walking it back is
another guided walk in the opposite direction.
-/
namespace SipserGacsLautemann
variable {tapes : Nat}
/-- The action of one round: guide right, worker moved (and maybe written). -/
def guidedAction (g w : Fin tapes) (dir : HeadMove) (wr : Option TapeSymbol) :
(Fin tapes → TapeSymbol) → (Fin tapes → TapeSymbol × HeadMove) :=
fun symbols i =>
if i = g then (symbols i, HeadMove.right)
else if i = w then
((match wr with | some c => c | none => symbols i), dir)
else (symbols i, HeadMove.stay)
/-- One round: test the guide's mark; act and continue, or stop. -/
def guidedBody (g w : Fin tapes) (dir : HeadMove) (wr : Option TapeSymbol) :=
(TypedMachine.test (notBlankAt g)).andThen fun b =>
if b then
(TypedMachine.act (guidedAction g w dir wr)).andThen fun _ =>
TypedMachine.halt (tapes := tapes) true
else
(TypedMachine.act (fun symbols i => (symbols i, HeadMove.stay))).andThen
fun _ => TypedMachine.halt (tapes := tapes) false
/-- Walk the guide over its marks, acting on the worker each time. -/
def guidedWalk (g w : Fin tapes) (dir : HeadMove) (wr : Option TapeSymbol) :=
(guidedBody g w dir wr).repeatUntilFalse
/-- The tapes after one round. -/
def guidedStep (g w : Fin tapes) (dir : HeadMove) (wr : Option TapeSymbol)
(T : Fin tapes → Tape) : Fin tapes → Tape :=
fun i =>
if i = g then moveDir HeadMove.right (T g)
else if i = w then
moveDir dir (match wr with
| some c => Tape.write (T w) c
| none => T w)
else T i
theorem guidedStep_eq (g w : Fin tapes) (hgw : g ≠ w) (dir : HeadMove)
(wr : Option TapeSymbol) (T : Fin tapes → Tape) :
applyAction T (guidedAction g w dir wr) = guidedStep g w dir wr T := by
funext i
show applyAction T (guidedAction g w dir wr) i =
(if i = g then moveDir HeadMove.right (T g)
else if i = w then
moveDir dir (match wr with
| some c => Tape.write (T w) c
| none => T w)
else T i)
by_cases hi : i = g
· subst hi
simp [applyAction, guidedAction, Tape.write_head_self, moveDir]
· rw [if_neg hi]
by_cases hi2 : i = w
· subst hi2
cases wr with
| none => simp [applyAction, guidedAction, hi, Tape.write_head_self, moveDir]
| some c => simp [applyAction, guidedAction, hi, moveDir]
· simp [applyAction, guidedAction, hi, hi2, Tape.write_head_self, Tape.move]
/-! ## One round -/
set_option maxHeartbeats 1000000 in
/-- A round on a marked guide cell: three steps, both tapes advanced,
verdict `true`. -/
theorem guidedBody_mark (g w : Fin tapes) (hgw : g ≠ w) (dir : HeadMove)
(wr : Option TapeSymbol) (T : Fin tapes → Tape)
(hmark : (T g).head ≠ TapeSymbol.blank) :
HaltsExactly (guidedBody g w dir wr)
((guidedBody g w dir wr).startCfg T) (1 + 1 + (1 + 1 + 0)) true ∧
(((guidedBody g w dir wr).step^[1 + 1 + (1 + 1 + 0)])
((guidedBody g w dir wr).startCfg T)).tape =
guidedStep g w dir wr T := by
have htest := TypedMachine.test_spec (notBlankAt g) T
rw [notBlankAt_true g T hmark] at htest
have htestt : (((TypedMachine.test (notBlankAt g)).step^[1])
((TypedMachine.test (notBlankAt g)).startCfg T)).tape = T := by
rw [Function.iterate_one]
funext j
simp [TypedMachine.step, TypedMachine.test, TypedMachine.startCfg,
Tape.write_head_self, Tape.move]
have hact := TypedMachine.act_spec (guidedAction g w dir wr) T
have hactt : (((TypedMachine.act (guidedAction g w dir wr)).step^[1])
((TypedMachine.act (guidedAction g w dir wr)).startCfg T)).tape =
guidedStep g w dir wr T := by
rw [Function.iterate_one, ← guidedStep_eq g w hgw]
funext j
simp [TypedMachine.step, TypedMachine.act, TypedMachine.startCfg,
applyAction]
have hhalt := TypedMachine.halt_spec (tapes := tapes) true
((TypedMachine.halt (tapes := tapes) true).startCfg
(guidedStep g w dir wr T))
have hinner := chainStepC hact hactt hhalt
have hmain := chainStepD
(M₂ := fun b =>
if b then
(TypedMachine.act (guidedAction g w dir wr)).andThen fun _ =>
TypedMachine.halt (tapes := tapes) true
else
(TypedMachine.act (fun symbols i => (symbols i, HeadMove.stay))).andThen
fun _ => TypedMachine.halt (tapes := tapes) false)
htest htestt (by simpa using hinner.1)
refine ⟨hmain.1, ?_⟩
have hfin := hmain.2
have hfin' : ((guidedBody g w dir wr).step^[1 + 1 + (1 + 1 + 0)])
((guidedBody g w dir wr).startCfg T) = _ := hfin
rw [hfin']
have hi := hinner.2
show (TypedConfiguration.inRight true
(((if true then
(TypedMachine.act (guidedAction g w dir wr)).andThen fun _ =>
TypedMachine.halt (tapes := tapes) true
else
(TypedMachine.act (fun symbols i =>
(symbols i, HeadMove.stay))).andThen
fun _ => TypedMachine.halt (tapes := tapes) false).step^[1 + 1 + 0])
((if true then
(TypedMachine.act (guidedAction g w dir wr)).andThen fun _ =>
TypedMachine.halt (tapes := tapes) true
else
(TypedMachine.act (fun symbols i =>
(symbols i, HeadMove.stay))).andThen
fun _ => TypedMachine.halt (tapes := tapes) false).startCfg
T))).tape = _
simp only [if_true]
rw [hi]
rfl
set_option maxHeartbeats 1000000 in
/-- A round on a blank guide cell: the loop's exit. Nothing moves. -/
theorem guidedBody_blank (g w : Fin tapes) (dir : HeadMove)
(wr : Option TapeSymbol) (T : Fin tapes → Tape)
(hblank : (T g).head = TapeSymbol.blank) :
HaltsExactly (guidedBody g w dir wr)
((guidedBody g w dir wr).startCfg T) (1 + 1 + (1 + 1 + 0)) false ∧
(((guidedBody g w dir wr).step^[1 + 1 + (1 + 1 + 0)])
((guidedBody g w dir wr).startCfg T)).tape = T := by
have htest := TypedMachine.test_spec (notBlankAt g) T
rw [notBlankAt_false g T hblank] at htest
have htestt : (((TypedMachine.test (notBlankAt g)).step^[1])
((TypedMachine.test (notBlankAt g)).startCfg T)).tape = T := by
rw [Function.iterate_one]
funext j
simp [TypedMachine.step, TypedMachine.test, TypedMachine.startCfg,
Tape.write_head_self, Tape.move]
have hact := TypedMachine.act_spec
(fun symbols : Fin tapes → TapeSymbol => fun i =>
(symbols i, HeadMove.stay)) T
have hactt : (((TypedMachine.act
(fun symbols : Fin tapes → TapeSymbol => fun i =>
(symbols i, HeadMove.stay))).step^[1])
((TypedMachine.act
(fun symbols : Fin tapes → TapeSymbol => fun i =>
(symbols i, HeadMove.stay))).startCfg T)).tape = T := by
rw [Function.iterate_one]
funext j
simp [TypedMachine.step, TypedMachine.act, TypedMachine.startCfg,
applyAction, Tape.write_head_self, Tape.move]
have hhalt := TypedMachine.halt_spec (tapes := tapes) false
((TypedMachine.halt (tapes := tapes) false).startCfg T)
have hinner := chainStepC hact hactt hhalt
have hmain := chainStepD
(M₂ := fun b =>
if b then
(TypedMachine.act (guidedAction g w dir wr)).andThen fun _ =>
TypedMachine.halt (tapes := tapes) true
else
(TypedMachine.act (fun symbols i => (symbols i, HeadMove.stay))).andThen
fun _ => TypedMachine.halt (tapes := tapes) false)
htest htestt (by simpa using hinner.1)
refine ⟨hmain.1, ?_⟩
have hfin := hmain.2
have hfin' : ((guidedBody g w dir wr).step^[1 + 1 + (1 + 1 + 0)])
((guidedBody g w dir wr).startCfg T) = _ := hfin
rw [hfin']
simp only [Bool.false_eq_true, if_false]
rw [hinner.2]
rfl
/-! ## The walk -/
set_option maxHeartbeats 1000000 in
/-- **The guided walk.** If the guide carries `m` marks from its head, the
walk performs exactly `m` worker actions and halts with the guide on the
blank past them. -/
theorem guidedWalk_spec (g w : Fin tapes) (hgw : g ≠ w) (dir : HeadMove)
(wr : Option TapeSymbol) (m : Nat) (T : Fin tapes → Tape)
(hmarks : ∀ r, r < m →
((((guidedStep g w dir wr)^[r]) T) g).head ≠ TapeSymbol.blank)
(hexit : ((((guidedStep g w dir wr)^[m]) T) g).head = TapeSymbol.blank) :
HaltsExactly (guidedWalk g w dir wr)
((guidedWalk g w dir wr).startCfg T) (m * 5 + 4) false ∧
(((guidedWalk g w dir wr).step^[m * 5 + 4])
((guidedWalk g w dir wr).startCfg T)).tape =
((guidedStep g w dir wr)^[m]) T := by
classical
set body := guidedBody g w dir wr with hbody
set cfg : Nat → TypedConfiguration tapes _ :=
fun r => body.startCfg (((guidedStep g w dir wr)^[r]) T) with hcfg
have hround : ∀ r, r < m →
HaltsExactly body (cfg r) 4 true ∧
cfg (r + 1) = ⟨body.start, ((body.step^[4]) (cfg r)).tape⟩ := by
intro r hr
obtain ⟨hh, ht⟩ := guidedBody_mark g w hgw dir wr
(((guidedStep g w dir wr)^[r]) T) (hmarks r hr)
have hh4 : HaltsExactly body (cfg r) 4 true := by
rw [hcfg, hbody]; simpa using hh
have ht4 : ((body.step^[4]) (cfg r)).tape =
((guidedStep g w dir wr)^[r + 1]) T := by
rw [hcfg, hbody]
rw [show (4 : Nat) = 1 + 1 + (1 + 1 + 0) from rfl]
rw [ht, Function.iterate_succ_apply']
refine ⟨hh4, ?_⟩
show body.startCfg (((guidedStep g w dir wr)^[r + 1]) T) = _
rw [← ht4]
rfl
have hexitr : HaltsExactly body (cfg m) 4 false := by
have := (guidedBody_blank g w dir wr (((guidedStep g w dir wr)^[m]) T)
hexit).1
rw [hcfg, hbody]; simpa using this
have hspec := TypedMachine.repeatUntilFalse_spec body cfg (fun _ => 4) m 4
hround hexitr
have hcost : loopCost (fun _ => 4) m + 4 = m * 5 + 4 := by
rw [loopCost_const]
rw [hcost] at hspec
have hrun := TypedMachine.repeatUntilFalse_rounds body cfg (fun _ => 4) m
hround
rw [loopCost_const] at hrun
refine ⟨by rw [hcfg] at hspec; exact hspec, ?_⟩
have hstart : (guidedWalk g w dir wr).startCfg T = cfg 0 := by
rw [hcfg]; rfl
rw [hstart, show m * 5 + 4 = 4 + m * (4 + 1) by omega,
Function.iterate_add_apply]
show ((guidedWalk g w dir wr).step^[4]
(((guidedWalk g w dir wr).step^[m * (4 + 1)]) (cfg 0))).tape = _
rw [show (guidedWalk g w dir wr) = body.repeatUntilFalse from rfl, hrun]
have htp : ((body.repeatUntilFalse.step^[4]) (cfg m)).tape =
((body.step^[4]) (cfg m)).tape := by
rw [body.repeatUntilFalse_iterate_fresh (cfg m) 4 hexitr.fresh]
rw [htp, hcfg, hbody]
exact (guidedBody_blank g w dir wr (((guidedStep g w dir wr)^[m]) T)
hexit).2
end SipserGacsLautemann