Between rounds
Definitionsgl_post_roundBetween 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 reads a counter of marks in exactly the shape round read one of . The guide is a consumable copy of the third input, advanced one cell per round — which makes the loop run once per mark plus a final round, i.e. offsets exactly. That is why this construction needs no length comparison anywhere: the guide is the bound.
counterAdvance gives the head's position after steps. It exists because the scan distance here is , not : with marks the head starts on mark and the blank sits at position , and scanToBlank looks strictly beyond the head. That is the same off-by-one the clock's parking scan showed, and it makes a genuine edge — with no marks the head is already on a blank and the scan runs past it. Recording the position as a single lemma lets both cases be discharged from one place rather than rediscovered in each.
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}
/-- Write a mark at the head and step right. -/
def markAction (i : Fin tapes) :
(Fin tapes → TapeSymbol) → (Fin tapes → TapeSymbol × HeadMove) :=
fun symbols j =>
if j = i then (TapeSymbol.bit true, HeadMove.right)
else (symbols j, HeadMove.stay)
/-- Append one mark to a unary counter, head back at its first mark. -/
def bumpCounter (i : Fin tapes) :=
(scanToBlank i HeadMove.right).andThen fun _ =>
(TypedMachine.act (markAction i)).andThen fun _ =>
rewindRun i
theorem markAction_tape (i : Fin tapes) (T : Fin tapes → Tape) :
applyAction T (markAction i) =
Function.update T i
(moveDir HeadMove.right (Tape.write (T i) (TapeSymbol.bit true))) := by
funext j
by_cases hj : j = i
· subst hj
simp [applyAction, markAction, moveDir]
· simp [applyAction, markAction, hj, Tape.write_head_self, Tape.move]
/-! ## The scan distance, for the next step
`bumpCounter`'s first stage scans to the blank past the marks. With `m` marks
the head starts on mark 0 and the blank sits at position `m`, so
`scanToBlank`'s distance parameter is `m - 1`, not `m` — the machine looks
*strictly* beyond the head, which is the same off-by-one the clock's parking
scan showed. It follows that `m = 0` is a genuine edge: with no marks the head
is already on a blank and the scan runs past it, exactly as `clockScan_spec`
had to case-split. `counterAdvance` records the head's position after `k`
steps so both cases can be discharged from one lemma.
-/
theorem counterAdvance (i : Fin tapes) (m k : Nat) (Lc Rc : List TapeSymbol)
(T : Fin tapes → Tape) (hk : k ≤ m)
(hT : T i = cellsTape (TapeSymbol.blank :: Lc)
(List.replicate m (TapeSymbol.bit true) ++ TapeSymbol.blank :: Rc)) :
((moveDir HeadMove.right)^[k]) (T i) =
cellsTape (List.replicate k (TapeSymbol.bit true) ++
(TapeSymbol.blank :: Lc))
(List.replicate (m - k) (TapeSymbol.bit true) ++
TapeSymbol.blank :: Rc) := by
obtain ⟨d, rfl⟩ := Nat.exists_eq_add_of_le hk
rw [hT]
have hsplit : List.replicate (k + d) (TapeSymbol.bit true) ++
TapeSymbol.blank :: Rc =
List.replicate k (TapeSymbol.bit true) ++
(List.replicate d (TapeSymbol.bit true) ++ TapeSymbol.blank :: Rc) := by
rw [List.replicate_add, List.append_assoc]
rw [hsplit]
have hadv := cellsTape_advance (List.replicate k (TapeSymbol.bit true))
(TapeSymbol.blank :: Lc)
(List.replicate d (TapeSymbol.bit true) ++ TapeSymbol.blank :: Rc)
simp only [List.length_replicate] at hadv
rw [hadv]
congr 2
· simp [List.reverse_replicate]
· simp
end SipserGacsLautemann