Source-linked AI summary
Step Recursion: Exact Depth Does Not Determine Algebraic Expressiveness
Kirill Osipov
TL;DR
The paper asks whether knowing every input's exact recursion depth determines the expressive power of step recursion. It compares generators with identical depth maps and varies predecessor choices within depth levels, finding that exact depth does not determine the resulting algebra.
Problem
The paper asks whether pointwise equality of exact depth maps implies equality of step-recursion algebras, even though the maps fix every stage count and orbit endpoint.
Source: §1 · p. 2Method
The paper fixes an exact depth profile while varying predecessor assignments within its depth levels, including an explicit basis-zero comparison and a general multiplicity result.
Source: §1 · p. 2, §6 · p. 13Results
The explicit generators b and p have equal depth maps but different step-recursion algebras, and flexible exact-depth profiles can support continuum many distinct algebras.
Source: §1 · p. 2, §6 · p. 13Takeaways & Limitations
Exact depth is an informative resource coordinate but not a complete semantic invariant because it omits algebraically visible predecessor geometry within depth levels.
Source: §6 · p. 13The effective construction guarantees computability, not a low complexity bound.
Source: §5 · p. 12
Abstract
from arXiv · showhide
Step recursion is a form of bounded recursion in which each recursive call moves from an input y to a prescribed predecessor $ρ_g(y)$. Its depth $D_g(y)$ is the exact number of such moves needed to reach zero. A natural question is whether knowing this depth for every input determines the expressive power of the resulting function algebra. We prove that it does not. We first construct two simple generators with exactly the same depth map but different step-recursion algebras. One gives ordinary binary halving, $b(x)=2x+1$; the other is $p(0)=1$, $p(x)=x+2^{λ(x)}$ for $x>0$, where $λ$ is binary length. Although $D_p=D_b$ pointwise, the predecessor $ρ_p$ cannot be defined from any fixed-stride binary-halving descent at basis zero. Thus two recursion schemes may take exactly the same number of steps on every input and still have different expressive power. The phenomenon is much larger than this example. Whenever infinitely many depth levels allow more than one predecessor arrangement, a single exact depth profile supports $2^{\aleph_0}$ distinct step-recursion algebras over every countable basis containing zero and the projections. In the computable setting the corresponding effective family has exactly $\aleph_0$ distinct algebras. Hence exact recursion depth is an informative resource measure, but it is not a complete invariant: the geometry of predecessor choices inside each depth level carries additional algebraic information.
1 Introduction
The introduction asks whether a pointwise exact depth map determines a step-recursion algebra. It argues that predecessor choices within depth levels remain algebraically visible, even when the depth map is fixed.
1 Introduction
- Prior work introduced Step Recursion [6] and developed generalized-inverse depth profiles and orbit semantics [7], but did not settle whether pointwise depth determines the algebra.Source: §1 · pp. 1–2
- Pointwise equality of depth maps fixes every stage count and orbit endpoint, yet leaves predecessor choices within depth levels free.The paper contrasts this with earlier fixed-stride separations, which do not fix every stage count.Source: §1 · p. 2
- At basis zero, the generators b(x)=2x+1 and p have identical depth maps: for every k, p[k](0)=b[k](0)=2k−1, hence Dp=Db.The witness p is a linear-time binary transduction, so the separation is not an artefact of an intractable generator.Source: §1 · p. 2
- When infinitely many depth levels are flexible, a single exact-depth profile can have maximal algebraic multiplicity over every countable basis containing zero and the projections.Source: §1 · p. 2
- Exact depth is a resource coordinate, not a complete semantic classification, because it omits within-level predecessor geometry.Source: §1 · p. 2
2 Framework
The framework treats a generator’s generalized inverse as the predecessor schedule for bounded step recursion. Exact depth fixes every orbit endpoint but forgets local parent choices within depth levels.
2 Framework
- A generator is strictly increasing with g(x) ≥ x + 1; its generalized inverse supplies a descent and its depth map records the resulting recursion depth.The framework considers bounded step recursion along such a descent, with algebras formed by composition and bounded step recursion.Source: §2 · pp. 2–3
- Two generators have the same exact depth map exactly when their iterated orbit endpoints from zero agree at every stage.The inputs of depth at most k form the threshold set from zero through the kth orbit endpoint.Source: §2 · p. 3
- Exact-depth equivalence retains every predecessor stage count while forgetting local parent information inside each depth level.The relation is defined by equality of depth maps.Source: §2 · p. 3
- For a basis containing zero and projections, every descent is definable in its bounded step-recursion algebra.The descent is obtained by bounded step recursion and composition with zero and projections.Source: §2 · p. 4
- Each fixed descent over a countable initial basis generates a countable algebra, and the descent determines its generator.Distinct generators therefore have distinct generalized inverses.Source: §2 · p. 4
3 An explicit exact-depth separation
The explicit example gives generators with identical exact depth but different bounded step-recursion algebras. The separation arises because fixed-stride halving cannot define the plateau predecessor.
3 An explicit exact-depth separation
- On each dyadic block, p(x) = x + 2^k, a binary prefix operation that makes p linear-time computable.Its first parent in each nontrivial level receives a large child block, while the remaining parents receive one child each.Source: §3 · p. 4
- The shared orbit endpoints establish equal depth, while the plateau arrangement changes which parent is assigned to inputs within a level.The orbit identity follows by induction, and the depth formula follows from the threshold law.Source: §3 · pp. 4–5
- The separation proof uses one-source conservation and a polynomial bound on the source-free correction to rule out representing ρp.The symbolic argument combines a qualitative conservation lemma with a quantitative evaluation bound.Source: §3 · pp. 5–8
- Every fixed-stride derivation has a source–offset normal form with one large root source and polynomially bounded fields.This is a structural restriction, not merely a running-time bound; the plateau predecessor violates it.Source: §3 · pp. 7–8
- D_p = D_b, yet A_ρp(B0) differs from A_ρb(B0) because ρp is excluded from every fixed-stride binary-halving class.The descent ρp belongs to its own algebra, while it is not in the basis-zero algebra for fixed-stride halving.Source: §3 · pp. 4, 8
4 Exact-depth fibres and algebraic multiplicity
A fixed depth profile can admit many generators because it leaves room to rearrange parent assignments within flexible levels. With infinitely many such levels, the resulting algebraic multiplicity is maximal.
4 Exact-depth fibres and algebraic multiplicity
- Independent binary choices at infinitely many flexible levels yield 2^ℵ0 distinct generators that retain the same depth profile.The depth-preserving assignments vary positive child counts while preserving the total size of each level.Source: §4 · p. 9
- If a generator-realizable depth profile has infinitely many flexible levels, it supports 2^ℵ0 distinct step-recursion algebras over any countable basis containing zero and projections.The theorem obtains continuum many generators and partitions them into countable algebra classes.Source: §4 · pp. 9–10
- The algebra count is continuum because each algebra is countable and distinct generators have distinct descents definable in their algebras.Countability of each algebra and injectivity from generators to descents bound the size of each class.Source: §4 · p. 10
- Binary depth has continuum many algebras for every fixed Grzegorczyk basis level.For binary depth, every level k ≥ 2 is flexible, so the multiplicity theorem applies.Source: §4 · pp. 9–10
5 Effective algebraic multiplicity
For computable depth profiles with infinitely many flexible levels, the paper constructs computably many distinct algebras through effective diagonalization. The family has exactly countable multiplicity, though the construction gives no low complexity bound.
5 Effective algebraic multiplicity
- For computable depth profiles, level sizes and flexibility are computable, and infinitely many flexible levels can be effectively enumerated.The level endpoints can be found by search from the depth map.Source: §5 · p. 10
- Effective avoidance constructs a computable generator whose predecessor is absent from a given uniformly computable list of unary functions.At each flexible level, child counts are chosen to make the predecessor disagree with the selected function while preserving the depth profile.Source: §5 · pp. 10–11
- Raw step terms over an effective basis admit an effective enumeration and total computable universal evaluator.Their evaluation terminates because each recursive call replaces a positive input y by a smaller descent value.Source: §5 · p. 11
- A computable generator-realizable depth profile with infinitely many flexible levels has exactly ℵ0 algebras over an effective basis.The upper bound follows from countably many computable generators, and the lower bound constructs infinitely many distinct algebras.Source: §5 · p. 12
- The effective construction guarantees computability, not a low complexity bound; the explicit plateau generator is a separate low-complexity witness.The plateau generator is described as a linear-time binary transduction.Source: §5 · p. 12
6 Discussion and conclusion
Exact depth fixes each input’s level and orbit endpoint but omits which parent is chosen. The discussion frames this lost predecessor geometry as algebraically consequential and identifies finer invariants as an open direction.
6 Discussion and conclusion
- One exact-depth fibre can support continuum many distinct algebras, while the effective theorem shows the ambiguity is not merely a cardinality effect.The explicit plateau example and Theorem 20 establish maximal ambiguity over every countable basis containing zero and the projections.Source: §6 · p. 13
- A proposed next step is a basis-dependent invariant finer than depth but coarser than the full predecessor map, such as child-count distributions.The open problem is to classify equality and inclusion for fixed Bm and computable D.Source: §6 · p. 13
- At basis zero, fixed-stride halving cannot reproduce a macroscopic concentration of children within a level, showing how omitted predecessor geometry remains algebraically visible.The discussion treats exact depth as one coordinate of recursion power, not a complete semantic invariant.Source: §6 · p. 13