Bit-query and graph languages for implicit natural-number arithmetic
DefinitionAPSCounting893_Main_BinaryOracleArithmeticapsbinary-arithmeticcounting-hierarchyoracle-machines
Let assign a natural number to each finite binary word. The bit language records queries whose answer is the th binary digit of . The graph language accepts an input consisting of a framed word followed by little-endian candidate bits exactly when that candidate represents .
These interfaces permit implicit arithmetic values to be used in finite-oracle-machine constructions. Bit positions use the published length-delimited natural-number encoding. Graph candidates may contain trailing zero bits; the total decoder interprets them as the same natural number.
Definition code
import Definitions.Def_APSCounting893_Main_OracleProofPrimitives import Definitions.Def_Complexitylib_0ebd467_Computability_Machines_Turing_MultiTape_Encodings_Nat_Words set_option autoImplicit false namespace APSCounting893.Main def naturalBitQuery (x : Word) (q : ℕ) : Word := Turing.MultiTapeTM.frame x++encodeNat q def NaturalBitLanguage (F : Word → ℕ) : Language := fun w => ∃ x q,w=naturalBitQuery x q ∧ (F x).testBit q=true def NaturalGraphLanguage (F : Word → ℕ) : Language := fun w => F (Turing.MultiTapeTM.unframe w)=Turing.MultiTapeTM.ofBits (Turing.MultiTapeTM.dropFrame w) end APSCounting893.Main
Source
Hesse, Allender and Barrington, Uniform Constant-Depth Threshold Circuits for Division and Iterated Multiplication, JCSS 65(4), 2002, Section 4, pp. 8–11 of the author manuscript, especially Lemmas 4.1–4.3, https://www.cs.rutgers.edu/~allender/papers/division.pdf; implicit short-value interfaces for the arithmetic-to-threshold step in Agarwal, Hari, Pandey and Shukla, STOC 2027 submission #893, Theorem 6.4, pp. 25–26, https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/893.pdf.