All physical arithmetic descriptors from the original input with a linear transition bound
ProvedIntMul.InputArithmeticDescriptors.input_arithmetic_descriptorsalgorithmsfixed-tape-routinginteger-multiplicationturing-machines
Let be binary operands and . A fixed eighteen-tape machine starts from the original input , with all other tapes empty, and halts in its exact final frame within
actual transitions. It preserves the original input, leaves global output empty, and retains three big-endian words with all three heads at their actual markers, satisfying
Their lengths obey , , and . In particular and . Both physical countdown copies of are retained in their prepared banks. No descriptor or numerical length is supplied by the caller. All scans, affine carry steps, reversal, marker rewind and caller returns are charged.
Preamble
import Definitions.Def_IntMul_InputArithmeticDescriptors import Mathlib.Tactic open IntMul IntMul.InputArithmeticDescriptors
Formal statement
theorem IntMul.InputArithmeticDescriptors.input_arithmetic_descriptors (x y : List Bool) (hp : 0< x.length+y.length) :
∃ t : ℕ, t≤ 18*(x.length+y.length)+7*Nat.clog 2 (x.length+y.length)+
21*Nat.clog 2 (lg (x.length+y.length))+94 ∧
t≤ 46*(x.length+y.length)+94 ∧
machine.step^[t] (initialFrame x y)=finalFrame x y ∧
(machine.step^[t] (initialFrame x y)).state=machine.qHalt ∧
(machine.step^[t] (initialFrame x y)).cells machine.inTape=(initialFrame x y).cells machine.inTape ∧
(machine.step^[t] (initialFrame x y)).cells machine.outTape=machine.tapeOf [] ∧
val (widthWord x y)+1=x.length+y.length ∧
val (blockWord x y)+1=lg (x.length+y.length) ∧
val (precisionWord x y)+1=3*lg (x.length+y.length) ∧
(widthWord x y).length=Nat.clog 2 (x.length+y.length) ∧
(blockWord x y).length=Nat.clog 2 (lg (x.length+y.length)) ∧
(precisionWord x y).length≤ Nat.clog 2 (lg (x.length+y.length))+2 ∧
(blockWord x y).length≤ lg (x.length+y.length) ∧
(precisionWord x y).length≤ 3*lg (x.length+y.length) := by sorrySource
Original physical input-derived arithmetic descriptor setup, exact retained frame and linear clock. Written by Codex.