sgl_counter_stable
DefinitionDefinition code
import Definitions.Def_sgl_offset_loop
/-!
# The counter shape the loop can actually iterate
`bumpCounter_spec` consumes a counter with a blank written explicitly to its
left and returns one without. That is usable **once**: the result no longer
matches the hypothesis, so a second bump cannot be applied — and a loop needs
arbitrarily many.
The stable shape is the one with *nothing* to the left. A leftward step off
the end of the zipper materialises a blank, so `cellsTape [] R` behaves exactly
as though a blank sat to its left, and the shape is reproduced verbatim after
each bump. The counter is a scratch tape never written left of its origin, so
this is the shape it genuinely has: the loop invariant is a fixed point rather
than a chain that degrades after one use.
-/
namespace SipserGacsLautemann
variable {tapes : Nat}
set_option maxHeartbeats 1000000 in
/-- **The counter grows by one, repeatably.** Same three steps as
`bumpCounter_spec`, but stated on the shape that reproduces itself. -/
theorem bumpCounter_nil (i : Fin tapes) (m : Nat) (Rc : List TapeSymbol)
(T : Fin tapes → Tape)
(hT : T i = cellsTape []
(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 []
(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 [] (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]
rfl
have hT1i : T1 i = cellsTape [] (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 []
(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 [] (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]
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