Transfer macros: copy, XOR, and the unary counter
Definitionsgl_tape_transferTransfer macros: copy, XOR, constant write, and the unary counter.
Each macro is a local action fed to cellwiseLoop, or a scan composed with straight-line code. Because the engine is opaque to the action, the only obligation per macro is how its guard tape evolves — and every guard here merely walks right, so cellwise_guard_of_scan discharges it against the scan invariant.
Copy. copyBlock src dst writes the region under src onto dst, advancing both heads, at cost where is the region's length.
XOR. xorBlock lhs rhs dst writes the cellwise exclusive-or of two regions onto a third. This is the Lautemann shift , one cell at a time, at the same cost.
For both, a companion theorem gives the output tapes as the corresponding action iterated times.
Unary counter. A counter is a run of written cells. counterIncrement appends one, at cost ; counterIsEmpty retreats past the run and reports whether anything was written. Both are a scan composed with straight-line code, so both proofs are a single application of HaltsExactly.andThen.
No theorem in this module reasons about step, run, or transition: the machine-level plumbing is complete below it, and what remains for any further macro is pure tape combinatorics.
import Definitions.Def_sgl_cellwise_engine
/-!
# Transfer macros: copy, XOR, write, and the unary counter
Each macro below is a local action fed to `cellwiseLoop`, or a composition of a
scan with straight-line code. Because the engine is opaque to the action, the
only thing left to prove per macro is how its *guard tape* evolves — and for
every macro here the guard tape merely walks right, so the obligation
discharges against `blank_scan_right_spec`.
That is the point at which the machine-level plumbing is finished: no theorem
in this file mentions `step`, `run`, or `TypedMachine.transition`.
-/
namespace SipserGacsLautemann
variable {tapes : Nat}
/-! ## The local actions -/
/-- The bit carried by a cell; blanks read as `false`. -/
def symbolBit : TapeSymbol → Bool
| TapeSymbol.blank => false
| TapeSymbol.bit b => b
/-- Copy the cell under `src` onto `dst`, then advance both heads. -/
def copyStepAction (src dst : Fin tapes) :
(Fin tapes → TapeSymbol) → (Fin tapes → TapeSymbol × HeadMove) :=
fun symbols j =>
(if j = dst then symbols src else symbols j,
if j = src then HeadMove.right
else if j = dst then HeadMove.right else HeadMove.stay)
/-- Write the XOR of the cells under `lhs` and `rhs` onto `dst`, then advance all
three heads. This is the Lautemann shift `u ⊕ tᵢ`, one cell at a time. -/
def xorStepAction (lhs rhs dst : Fin tapes) :
(Fin tapes → TapeSymbol) → (Fin tapes → TapeSymbol × HeadMove) :=
fun symbols j =>
(if j = dst then
TapeSymbol.bit (symbolBit (symbols lhs) != symbolBit (symbols rhs))
else symbols j,
if j = lhs then HeadMove.right
else if j = rhs then HeadMove.right
else if j = dst then HeadMove.right else HeadMove.stay)
/-- Overwrite the cell under `i`, leaving every head where it is. -/
def writeSymbolAction (i : Fin tapes) (symbol : TapeSymbol) :
(Fin tapes → TapeSymbol) → (Fin tapes → TapeSymbol × HeadMove) :=
fun symbols j => (if j = i then symbol else symbols j, HeadMove.stay)
/-! ## Guard evolution
For each macro the guard tape is one that only ever moves right, so its
trajectory is the scan trajectory and the engine's hypotheses come straight from
`blank_scan_right_spec`. These are the only inductions the macros need. -/
theorem actTapes_copy_guard (tape : Fin tapes → Tape) (src dst : Fin tapes)
(hne : src ≠ dst) :
∀ n, (actTapes tape (copyStepAction src dst) n) src =
(moveDir HeadMove.right)^[n] (tape src) := by
intro n
induction n with
| zero => rfl
| succ n ih =>
rw [actTapes, Function.iterate_succ_apply', ← ih]
simp [applyAction, copyStepAction, hne, moveDir, Tape.write_head_self]
theorem actTapes_xor_guard (tape : Fin tapes → Tape) (lhs rhs dst : Fin tapes)
(hne : lhs ≠ dst) :
∀ n, (actTapes tape (xorStepAction lhs rhs dst) n) lhs =
(moveDir HeadMove.right)^[n] (tape lhs) := by
intro n
induction n with
| zero => rfl
| succ n ih =>
rw [actTapes, Function.iterate_succ_apply', ← ih]
simp [applyAction, xorStepAction, hne, moveDir, Tape.write_head_self]
/-- The engine's two hypotheses, for any macro whose guard tape walks right. -/
theorem cellwise_guard_of_scan
(action : (Fin tapes → TapeSymbol) → (Fin tapes → TapeSymbol × HeadMove))
(guard : Fin tapes) (tape : Fin tapes → Tape)
(hguard : ∀ n, (actTapes tape action n) guard =
(moveDir HeadMove.right)^[n] (tape guard)) :
(∀ k, k < blankIndex (tape guard).right →
((actTapes tape action (k + 1)) guard).head ≠ TapeSymbol.blank) ∧
((actTapes tape action (blankIndex (tape guard).right + 1)) guard).head =
TapeSymbol.blank := by
obtain ⟨hlt, heq⟩ :=
blank_scan_right_spec (tape guard).right (tape guard).left (tape guard).head
constructor
· intro k hk; rw [hguard]; exact hlt k hk
· rw [hguard]; exact heq
/-! ## The macros -/
/-- Copy the written region under `src` onto `dst`, advancing both heads. -/
def copyBlock (src dst : Fin tapes) :
TypedMachine tapes (Bool ⊕ Bool × Option Bool) :=
cellwiseLoop (copyStepAction src dst) src
/-- Write the cellwise XOR of `lhs` and `rhs` onto `dst`. -/
def xorBlock (lhs rhs dst : Fin tapes) :
TypedMachine tapes (Bool ⊕ Bool × Option Bool) :=
cellwiseLoop (xorStepAction lhs rhs dst) lhs
/-- `copyBlock` is a subroutine of cost `4d + 3`, where `d` is the length of the
region under `src`. -/
theorem copyBlock_spec (src dst : Fin tapes) (hne : src ≠ dst)
(tape : Fin tapes → Tape) :
HaltsExactly (copyBlock src dst) ((copyBlock src dst).startCfg tape)
(blankIndex (tape src).right * 4 + 3) false := by
obtain ⟨hlt, heq⟩ :=
cellwise_guard_of_scan (copyStepAction src dst) src tape
(actTapes_copy_guard tape src dst hne)
exact cellwiseLoop_spec_of (copyStepAction src dst) src tape _ hlt heq
/-- …and its output tapes are the copy action iterated `d + 1` times. -/
theorem copyBlock_tape (src dst : Fin tapes) (hne : src ≠ dst)
(tape : Fin tapes → Tape) :
(((copyBlock src dst).step^[blankIndex (tape src).right * 4 + 3])
((copyBlock src dst).startCfg tape)).tape =
actTapes tape (copyStepAction src dst)
(blankIndex (tape src).right + 1) := by
obtain ⟨hlt, heq⟩ :=
cellwise_guard_of_scan (copyStepAction src dst) src tape
(actTapes_copy_guard tape src dst hne)
exact cellwiseLoop_tape_of (copyStepAction src dst) src tape _ hlt heq
/-- `xorBlock` is a subroutine of cost `4d + 3`, where `d` is the length of the
region under `lhs`. -/
theorem xorBlock_spec (lhs rhs dst : Fin tapes) (hne : lhs ≠ dst)
(tape : Fin tapes → Tape) :
HaltsExactly (xorBlock lhs rhs dst) ((xorBlock lhs rhs dst).startCfg tape)
(blankIndex (tape lhs).right * 4 + 3) false := by
obtain ⟨hlt, heq⟩ :=
cellwise_guard_of_scan (xorStepAction lhs rhs dst) lhs tape
(actTapes_xor_guard tape lhs rhs dst hne)
exact cellwiseLoop_spec_of (xorStepAction lhs rhs dst) lhs tape _ hlt heq
theorem xorBlock_tape (lhs rhs dst : Fin tapes) (hne : lhs ≠ dst)
(tape : Fin tapes → Tape) :
(((xorBlock lhs rhs dst).step^[blankIndex (tape lhs).right * 4 + 3])
((xorBlock lhs rhs dst).startCfg tape)).tape =
actTapes tape (xorStepAction lhs rhs dst)
(blankIndex (tape lhs).right + 1) := by
obtain ⟨hlt, heq⟩ :=
cellwise_guard_of_scan (xorStepAction lhs rhs dst) lhs tape
(actTapes_xor_guard tape lhs rhs dst hne)
exact cellwiseLoop_tape_of (xorStepAction lhs rhs dst) lhs tape _ hlt heq
/-! ## The unary counter
A counter is a run of written cells; incrementing appends one. Both operations
are a scan composed with straight-line code, so their proofs are one line. -/
/-- Append one cell to the run under head `i`. -/
def counterIncrement (i : Fin tapes) :
TypedMachine tapes ((Bool ⊕ Bool × Option Bool) ⊕ Bool × Bool) :=
(scanToBlank i HeadMove.right).andThen
(fun _ => TypedMachine.act (writeSymbolAction i (TapeSymbol.bit true)))
/-- Incrementing costs `4d + 5`, where `d` is the counter's current value. -/
theorem counterIncrement_spec (i : Fin tapes) (tape : Fin tapes → Tape) :
HaltsExactly (counterIncrement i)
(TypedConfiguration.inLeft
((scanToBlank i HeadMove.right).startCfg tape))
(blankIndex (tape i).right * 4 + 3 + 1 + 1) true :=
HaltsExactly.andThen (scanRightToBlank_spec i tape)
(TypedMachine.act_spec (writeSymbolAction i (TapeSymbol.bit true)) _)
/-- The tapes left behind by a leftward scan. -/
def scanLeftOutput (i : Fin tapes) (tape : Fin tapes → Tape) : Fin tapes → Tape :=
(((scanToBlank i HeadMove.left).step^[blankIndex (tape i).left * 4 + 3])
((scanToBlank i HeadMove.left).startCfg tape)).tape
/-- Retreat past the run and report whether anything was written: the counter's
zero test. -/
def counterIsEmpty (i : Fin tapes) :
TypedMachine tapes ((Bool ⊕ Bool × Option Bool) ⊕ Bool × Option Bool) :=
(scanToBlank i HeadMove.left).andThen
(fun _ => TypedMachine.test (notBlankAt i))
theorem counterIsEmpty_spec (i : Fin tapes) (tape : Fin tapes → Tape) :
HaltsExactly (counterIsEmpty i)
(TypedConfiguration.inLeft
((scanToBlank i HeadMove.left).startCfg tape))
(blankIndex (tape i).left * 4 + 3 + 1 + 1)
(notBlankAt i (fun j => (scanLeftOutput i tape j).head)) :=
HaltsExactly.andThen (scanLeftToBlank_spec i tape)
(TypedMachine.test_spec (notBlankAt i) _)
end SipserGacsLautemann