Actual zero-carry initialization from binary countdown templates with a linear clock
ProvedIntMul.CountedZero.generate_zero_wordalgorithmsfixed-tape-routinginteger-multiplicationturing-machines
Let be any finite binary word and put . A fixed four-tape machine starts with an empty output at its marker and two physically prepared copies of the marked countdown word . The original input cells and head come from an arbitrary caller frame. Without a supplied zero payload, it globally halts in its exact final frame within
actual transitions, with output exactly and the output cursor at . Both countdown and saved template are fully restored, with heads at their original descriptor-end cursors. Original input cells and head are retained. Empty descriptor words and leading zeros are allowed. Descriptor preparation and physical return of the generated word to another bank remain separate caller stages.
Preamble
import Definitions.Def_IntMul_CountedStream import Mathlib.Tactic import Definitions.Def_IntMul_CountedZero import Mathlib.Data.List.GetD open IntMul IntMul.CountedZero
Formal statement
theorem IntMul.CountedZero.generate_zero_word (base : machine.Cfg) (z : List Bool) :
∃ t : ℕ, t≤ 6*(val z+1)+4*z.length+3 ∧
machine.step^[t] (initialFrame base z)=finalFrame base z ∧
(machine.step^[t] (initialFrame base z)).cells machine.inTape=base.cells machine.inTape ∧
(machine.step^[t] (initialFrame base z)).head machine.inTape=base.head machine.inTape ∧
(machine.step^[t] (initialFrame base z)).cells machine.outTape=
machine.tapeOf ((bin (val z+1) 0).map machine.bitSym) ∧
(machine.step^[t] (initialFrame base z)).state=machine.qHalt ∧
(machine.step^[t] (initialFrame base z)).head machine.outTape=val z+2 := by sorrySource
Original complete physical binary-counted zero-word generator and exact retained frame. Written by Codex.