Growing the offset counter
Definitionsgl_bump_counterGrowing 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.
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