Summary
This paper focuses on how certain step-by-step processes or recursions behave when applied to numbers on the real number line, especially with rational steps. The authors show exact conditions under which one set of these step processes is contained within another based on the denominators of the rational steps. They also uncover deep relationships between bounded and unbounded cases of these processes and classify them using number theory ideas like least common denominators and greatest common divisors. Some problems around deciding certain equalities remain unresolved, but the work clarifies the complexity and structure of these recursive systems over real numbers.
What this means in practice
- •For programming language designers: Help define and understand recursion semantics with rational steps in language constructs over real numbers.
- •For formal verification engineers: Use the classification of recursive step functions to analyze the complexity and inclusion properties of numeric programs.
A theory result. No direct application yet.
Abstract
We study finite-terminating, address-only step recursion on the nonnegative reals, from zero, unit successor and projections. For reduced positive rational strides $s=a/q$ and $t=b/v$, we prove $\mathcal{C}s\subseteq\mathcal{C}t$ if and only if $q$ divides $v$, for both the bounded and unbounded algebras $\mathcal{C}\in{\mathcal{B},\mathcal{U}}$. The bounded compiler preserves earlier global majorants on every auxiliary input. Mixed rational stride sets are classified by least common denominators and supernatural denominators. Primitive-recursive translated-coordinate grid codes characterize the unbounded algebras and yield $\mathcal{U}{1/q}\cap\mathcal{U}{1/v}=\mathcal{U}{1/\gcd(q,v)}$. For bounded intersections, we prove an exact reduction: all corresponding identities hold if and only if the single identity $\mathcal{B}{1/2}\cap\mathcal{B}_{1/3}=\mathcal{B}_1$ holds, equivalently if the Boolean parts of the integer successor and addition algebras under scalar bounded recursion coincide. A Boolean reconstruction reduces general functions to predicates; a clipped fine-grid simulation with a frozen global resource bound identifies the union of predicate precision classes with the addition level. These reductions do not decide the resulting predicate equality, so literal bounded intersections remain unresolved. We also prove that unbounded-program equality is $Π^0_1$-complete and extensional bounded-algebra membership is $Σ^0_2$-complete. The model has no free real arithmetic or Zeno limits; semantic majorant validity is distinguished from syntax transformation.