Polynomial-time finite carry-certificate query machine
ProvedAPSCounting893.Main.native_long_sum_carry_queryapsbinary-arithmeticcounting-hierarchyimplicit-sums
For each pair of fixed natural numbers , the explicit carry-certificate query function is computable by an ordinary uniform finite multitape Turing machine in polynomial time:
Its input consists of a framed binary bit query and bounded binary fields for the carry certificate. The machine reads and checks the fields, performs binary arithmetic and chooses a single tagged block-value query or a Boolean constant. The assertion concerns the actual finite-machine semantics and imposes no oracle assumption on this preprocessing function. This implementation is used to turn the generating-carry and propagating-carry criterion for iterated addition into a bounded-quantifier language.
Preamble
import Definitions.Def_APSCounting893_Main_LongSumCarryMachine set_option autoImplicit false open APSCounting893.Main
Formal statement
theorem APSCounting893.Main.native_long_sum_carry_query (a b : ℕ) :
Turing.MultiTapeTM.ComputableTidilyInPolyTime (longSumMatrixQuery a b)
Turing.MultiTapeTM.encBits Turing.MultiTapeTM.encBits := by sorrySource
Hesse, Allender and Barrington, Uniform Constant-Depth Threshold Circuits for Division and Iterated Multiplication, JCSS 65(4), 2002, Section 3, iterated addition discussion, author manuscript p. 7, and Section 4, Lemma 4.3, https://www.cs.rutgers.edu/~allender/papers/division.pdf. Explicit finite-machine carry-certificate implementation for the coefficient arithmetic in Agarwal, Hari, Pandey and Shukla, STOC 2027 submission #893, Theorem 6.4, pp. 25–26.