Polynomial charge bounds for unary counter arithmetic
ProvedMetricSelfDualRuntime.basicNatCostsalgorithmscomputabilityruntime
The fixed tree-stack routines for addition, comparison and equality of unary-coded natural counters have polynomial charge and polynomial output volume. The successor and predecessor routines have linear charge and output volume. All bounds are uniform over the counter values and use the published finite routines, rather than an abstract arithmetic oracle. These primitive counter operations support the uniform code-construction algorithms.
Preamble
import Mathlib import Definitions.Def_MetricSelfDualRuntime_CostInterfaces
Formal statement
namespace MetricSelfDualRuntime
open OAI.ThreeMachine.StackCompiler ExactAmpDich.BinaryMachine
theorem basicNatCosts :
PolynomialRealizer Realizer.add ∧ PolynomialRealizer Realizer.le ∧
LinearRealizer Realizer.succ ∧ PolynomialRealizer Realizer.eqNat ∧
LinearRealizer Realizer.pred := by sorry
end MetricSelfDualRuntimeSource
OAI.ThreeMachine.StackCompiler.Realizer published add/le/succ/eqNat/pred definitions and their exact charge bounds (Definitions.Def_OAIThreeMachineSched01); unary counter arithmetic for Lemma12 of STOC2027 #5, printed p.10 / PDF p.12.