Complete physical product recovery and exact requested width at any sufficient coefficient precision
ProvedIntMul.WideNormalizedProduct.wide_normalized_productalgorithmsfixed-tape-routinginteger-multiplicationturing-machines
From an explicit prepared convolution-coefficient frame, let and let be any sufficient coefficient precision, meaning . A retained word specifies the requested product width . The fixed sixteen-tape machine globally halts in its exact final frame and outputs exactly
Its actual transition bound is
This includes actual carry normalization, all reusable scratch cleanup, physical desired-width countdown preparation, output conversion and caller returns. Coefficient generation, coefficient loading and descriptor construction remain explicit upstream obligations.
Preamble
import Definitions.Def_IntMul_WideNormalizedProduct import Mathlib.Tactic import Definitions.Def_IntMul_BinaryAdder import Definitions.Def_IntMul_MultitapeModel import Mathlib.Data.Nat.Bits open IntMul IntMul.WideNormalizedProduct
Formal statement
theorem IntMul.WideNormalizedProduct.wide_normalized_product (base : machine.Cfg) (pre x y z l d : List Bool)
(hl : CarryProduct.coefficientWidth (CarryStep.blockSize z) x y≤ val l+1)
(hd : FixedOutputWidth.width d=x.length+y.length) :
∃ t : ℕ,
t ≤ (DigitConvolution.blockCount (CarryStep.blockSize z) x+
DigitConvolution.blockCount (CarryStep.blockSize z) y)*
(41*(val l+1)+32*CarryStep.blockSize z+
21*z.length+4*l.length+126)+10*FixedOutputWidth.width d+6*d.length+63 ∧
machine.step^[t] (initialFrame base pre x y z l d)=finalFrame base pre x y z l d ∧
(machine.step^[t] (initialFrame base pre x y z l d)).state=machine.qHalt ∧
(machine.step^[t] (initialFrame base pre x y z l d)).cells 1=
machine.tapeOf ((bin (x.length+y.length) (val x*val y)).map machine.bitSym) := by sorrySource
Original complete physical product output at arbitrary sufficient coefficient precision and exact requested width. Written by Codex.