Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Growing the offset counter

Definition
sgl_bump_counter

by Henry Yuen · Jul 27, 2026 · Mathlib 0df444a (Lean v4.33.1)

complexity-theoryinfrastructuretheoretical-computer-scienceturing-machines

Growing the offset counter. Supersedes the bumpCounter in sgl_post_round, which was wrong.

A round leaves the counter untouched, so the loop advances it — and the obvious way to do that is wrong.

Scanning to the blank past the marks and writing one there fails at zero marks: scanToBlank looks strictly beyond the head, so on an empty counter it overshoots and the mark lands at position one with position zero still blank. That gap reads back as an empty counter, so the loop would never advance. The first round is exactly the empty-counter case, so this is not a corner that could be left for later.

Prepending has no such edge. The head sits on the counter's first mark — or on the blank, when empty — so stepping left onto the cell before it and writing there makes the run one longer and leaves the head on its new first mark. Two steps, no scan, no case analysis, uniform in the count. The counter's left context is all-blank scratch, so there is always a cell to take.

Worth naming the general shape: when a construction needs a case split to handle an empty structure, it is worth asking whether a different construction avoids the empty case altogether. Here the scan-based version needed the same split as the clock's parking scan; the prepending version needs none.

Definition code
import Definitions.Def_sgl_round_cost

/-!
# Between rounds

A round leaves the offset counter and the loop guide untouched, so the loop
must advance both itself.

`bumpCounter` appends one mark to the unary counter and returns the head to
the counter's first mark — so round `r+1` reads a counter of `r+1` marks in
exactly the shape round `r` read one of `r`.

The guide is a consumable copy of the third input: advancing it one cell per
round makes the loop run once per mark plus a final round, which is offsets
`0 … |input₂|` exactly.  That is why no length comparison is needed anywhere
in this construction — the guide *is* the bound.
-/

namespace SipserGacsLautemann

variable {tapes : Nat}

/-! ## Growing the counter

The obvious increment — scan to the blank past the marks, write one there —
is **wrong at zero marks**.  `scanToBlank` looks strictly beyond the head, so
on an empty counter it overshoots by one and the mark lands at position one
with position zero still blank: a gap, which reads back as an empty counter.
The first round is exactly the empty-counter case, so this is not a corner
that could be ignored.

Prepending has no such edge.  The head sits on the counter's first mark (or on
the blank, when empty); stepping left onto the cell before it and writing there
makes the run one longer and leaves the head on its new first mark, in two
steps, with no scan and no case analysis.  The counter's left context is
all-blank scratch, so there is always a cell to take.
-/

/-- Prepend one mark to a unary counter; the head ends on the new first mark. -/
def bumpCounter (i : Fin tapes) :=
  (moveUpTo i 1 HeadMove.left).andThen fun _ =>
    TypedMachine.act (fun symbols j =>
      if j = i then (TapeSymbol.bit true, HeadMove.stay)
      else (symbols j, HeadMove.stay))

set_option maxHeartbeats 1000000 in
/-- **The counter grows by one**, in two steps, uniformly in `m`. -/
theorem bumpCounter_spec (i : Fin tapes) (m : Nat) (Lc Rc : List TapeSymbol)
    (T : Fin tapes → Tape)
    (hT : T i = cellsTape (TapeSymbol.blank :: Lc)
      (List.replicate m (TapeSymbol.bit true) ++ TapeSymbol.blank :: Rc)) :
    HaltsExactly (bumpCounter i) ((bumpCounter i).startCfg T) (1 + 1 + 1) true ∧
    (((bumpCounter i).step^[1 + 1 + 1]) ((bumpCounter i).startCfg T)).tape =
      Function.update T i
        (cellsTape Lc
          (List.replicate (m + 1) (TapeSymbol.bit true) ++
            TapeSymbol.blank :: Rc)) := by
  classical
  have hA := moveUpTo_spec i 1 HeadMove.left (by omega) T
  set T1 := Function.update T i
    (cellsTape Lc (TapeSymbol.blank ::
      (List.replicate m (TapeSymbol.bit true) ++ TapeSymbol.blank :: Rc)))
    with hT1
  have hAt : (((moveUpTo i 1 HeadMove.left).step^[1])
      ((moveUpTo i 1 HeadMove.left).startCfg T)).tape = T1 := by
    rw [moveUpTo_tape i 1 HeadMove.left (by omega) T, hT1]
    congr 1
    rw [Function.iterate_one, hT]
    obtain ⟨r, R, hcons⟩ : ∃ r R,
        List.replicate m (TapeSymbol.bit true) ++ TapeSymbol.blank :: Rc
          = r :: R := by
      cases m with
      | zero => exact ⟨TapeSymbol.blank, Rc, rfl⟩
      | succ a => exact ⟨TapeSymbol.bit true,
          List.replicate a (TapeSymbol.bit true) ++ TapeSymbol.blank :: Rc,
          by rw [List.replicate_succ]; rfl⟩
    rw [hcons, cellsTape_moveLeft, ← hcons]
  have hT1i : T1 i = cellsTape Lc (TapeSymbol.blank ::
      (List.replicate m (TapeSymbol.bit true) ++ TapeSymbol.blank :: Rc)) := by
    rw [hT1]; simp
  have hB := TypedMachine.act_spec
    (fun symbols : Fin tapes → TapeSymbol => fun j =>
      if j = i then (TapeSymbol.bit true, HeadMove.stay)
      else (symbols j, HeadMove.stay)) T1
  have hBt : (((TypedMachine.act
      (fun symbols : Fin tapes → TapeSymbol => fun j =>
        if j = i then (TapeSymbol.bit true, HeadMove.stay)
        else (symbols j, HeadMove.stay))).step^[1])
      ((TypedMachine.act
        (fun symbols : Fin tapes → TapeSymbol => fun j =>
          if j = i then (TapeSymbol.bit true, HeadMove.stay)
          else (symbols j, HeadMove.stay))).startCfg T1)).tape =
      Function.update T i
        (cellsTape Lc
          (List.replicate (m + 1) (TapeSymbol.bit true) ++
            TapeSymbol.blank :: Rc)) := by
    rw [Function.iterate_one]
    funext j
    by_cases hj : j = i
    · rw [hj]
      have hcell : Tape.move (Tape.write (T1 i) (TapeSymbol.bit true))
          HeadMove.stay =
          cellsTape Lc (List.replicate (m + 1) (TapeSymbol.bit true) ++
            TapeSymbol.blank :: Rc) := by
        rw [hT1i, write_cellsTape, List.replicate_succ]
        rfl
      simp [TypedMachine.step, TypedMachine.act, TypedMachine.startCfg, hcell]
    · simp [TypedMachine.step, TypedMachine.act, TypedMachine.startCfg, hj,
        Tape.write_head_self, Tape.move, hT1, Function.update_of_ne hj]
  have hchain := chainStepC hA hAt hB
  refine ⟨hchain.1, ?_⟩
  have hfin : ((bumpCounter i).step^[1 + 1 + 1])
      ((bumpCounter i).startCfg T) = _ := hchain.2
  rw [hfin]
  exact hBt

end SipserGacsLautemann
Source
Counter increment for the scheduler loop; builds on Def_sgl_round_cost.

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