Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Walking one tape under another's guidance

Definition
sgl_guided_walk

by Henry Yuen · Jul 27, 2026 · Mathlib c5ea003 (Lean v4.30.0)

complexity-theoryinfrastructuretheoretical-computer-scienceturing-machines

Walking 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 mmm marks from its head, the walk performs exactly mmm worker actions in 5m+45m + 45m+4 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.

Definition code
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
Source
Counting primitive for the scheduler families; builds on Def_sgl_embed_clock.

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me