Actual physical product recovery from a prepared convolution coefficient frame
ProvedIntMul.WideCarryProduct.wide_carry_productLet be binary operand words and let be the positive block size. Let be a declared coefficient precision satisfying
where are the operand block counts. From the explicit prepared frame containing all padded convolution coefficients as -bit words and an -bit zero carry, the fixed fifteen-tape carry/output machine globally halts in its exact terminal frame, outputs exactly
and leaves the final carry as the canonical -bit zero word. Its actual transition bound is
All coefficient reading, actual binary addition, carry propagation, scratch cleanup, physical output reversal and caller returns are charged. Coefficient generation, loading and descriptor preparation are explicit upstream obligations. The result allows any sufficient precision, including the simple choice for logarithmic block sizes.
import Definitions.Def_IntMul_BinaryAdder import Definitions.Def_IntMul_MultitapeModel import Mathlib.Data.Nat.Bits import Mathlib.Tactic import Definitions.Def_IntMul_WideCarryProduct open IntMul IntMul.WideCarryProduct
theorem IntMul.WideCarryProduct.wide_carry_product (pre x y z l : List Bool)
(hN : CarryProduct.coefficientWidth (CarryStep.blockSize z) x y≤ val l+1) :
∃ t : ℕ,
t ≤ (DigitConvolution.blockCount (CarryStep.blockSize z) x+
DigitConvolution.blockCount (CarryStep.blockSize z) y)*
(41*(val l+1)+21*CarryStep.blockSize z+
21*z.length+4*l.length+126)+21 ∧
machine.step^[t] (initialFrame pre x y z l)=finalFrame pre x y z l ∧
(machine.step^[t] (initialFrame pre x y z l)).state=machine.qHalt ∧
(machine.step^[t] (initialFrame pre x y z l)).cells 1=
machine.tapeOf ((bin (CarryStep.blockSize z*
(DigitConvolution.blockCount (CarryStep.blockSize z) x+
DigitConvolution.blockCount (CarryStep.blockSize z) y)) (val x*val y)).map machine.bitSym) ∧
(machine.step^[t] (initialFrame pre x y z l)).cells 12=
machine.tapeOf ((bin ((val l+1)) 0).map machine.bitSym) := by sorry