arxiv: 2604.24356 · v1 · submitted 2026-04-27 · 💻 cs.CC · cs.LG· cs.LO· cs.NE

Recognition: unknown

Primitive Recursion without Composition: Dynamical Characterizations, from Neural Networks to Polynomial ODEs

Olivier Bournez

Authors on Pith no claims yet

Pith reviewed 2026-05-07 17:16 UTC · model grok-4.3

classification 💻 cs.CC cs.LGcs.LOcs.NE

keywords primitive recursionrecurrent neural networkspolynomial ODEsdynamical systemssubrecursive hierarchiescomputation without compositionReLU networkspolynomial maps

0 comments

The pith

Primitive recursion can be realized by iterating a fixed ReLU network, solving a fixed polynomial ODE, or iterating a polynomial map with an external step-size parameter.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper shows that every primitive recursive function arises from bounded iteration of one fixed system in each of three continuous models rather than from closing under composition as a separate rule. In the first model the system is a recurrent ReLU network; in the second it is the flow of a polynomial ODE that remains robust under small perturbations; in the third it is a polynomial map whose iteration count is controlled by an externally supplied step-size parameter. Inputs remain ordinary integer vectors and the time bound itself stays primitive recursive. A reader might care because the result replaces the symbolic operation of composition with concrete dynamical mechanisms such as clocks and phase selection that are built directly into the evolution.

Core claim

Every primitive recursive function can first be compiled into bounded iteration of a single threshold-affine normal form; that normal form then admits equivalent interpretations as the iteration of a fixed recurrent ReLU network, as the robust solution of a fixed polynomial ODE, and as the iteration of a fixed polynomial map supplied with an external step-size parameter. In each case composition is not imposed from outside but emerges from the dynamics themselves, and the time bound remains primitive recursive.

What carries the argument

The threshold-affine normal form obtained by compiling any primitive recursive function into bounded iteration of a single such form; it translates uniformly into the ReLU, ODE, and map models while preserving exact equivalence.

If this is right

Subrecursive hierarchies become definable by restricting time bounds, polynomial degrees, or discretization resources inside a single dynamical framework.
No fixed polynomial map can round uniformly to the nearest integer or realize exact phase selection, whereas polynomial ODEs perform both operations robustly via continuous flow.
Each model compensates for a limitation of the others: the ReLU gate supplies exact branching, continuous time supplies autonomous rounding and control, and the external step-size supplies both at the price of discretization.
These characterizations apply directly to raw integer inputs and produce outputs that remain exactly integer-valued.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

Restricting the polynomial degree in the ODE model may yield natural dynamical counterparts of known subrecursive classes such as elementary functions.
The structural asymmetry between discrete maps and continuous flows suggests that physical systems governed by differential equations can perform certain control operations without explicit discretization steps.
One could attempt to embed standard complexity classes inside these models by further restricting the allowed time bounds or the degree of the polynomials.
The approach opens the possibility of studying computation in neural or physical hardware by examining the trajectories of a single fixed dynamical system rather than by assembling discrete programs.

Load-bearing premise

That every primitive recursive function can be compiled into bounded iteration of one threshold-affine normal form whose interpretations as a ReLU network, polynomial ODE, and polynomial map all remain exactly equivalent without hidden precision losses.

What would settle it

Exhibit a primitive recursive function that cannot be obtained by any fixed ReLU network iterated a primitive-recursive number of times, or show that the compiled normal form fails to compute the correct integer output under the polynomial ODE flow for some integer input vector.

read the original abstract

What do recurrent neural networks, polynomial ODEs, and discrete polynomial maps each bring to computation, and what do they lack? All three operate over the continuum--real-valued states evolved by real-valued dynamics--even when the target functions are discrete. We study them through primitive recursion. We prove that primitive recursion admits equivalent characterizations in all three frameworks: bounded iteration of a fixed recurrent ReLU network, robust computation by a fixed polynomial ODE, and iteration of a fixed polynomial map with an externally supplied step-size parameter. In each, the time bound is itself primitive recursive, composition emerges from the dynamics rather than as a closure rule, and inputs are raw integer vectors. Every primitive recursive function is first compiled into bounded iteration of a single threshold-affine normal form, then interpreted as a ReLU computation and as a polynomial ODE. The equivalences expose a structural asymmetry: no fixed polynomial map can round uniformly to the nearest integer or realize exact phase selection--operations polynomial ODEs perform robustly via continuous-time flow. Each formalism compensates for a limitation the others lack: the ReLU gate provides exact branching, continuous time provides autonomous rounding and control, and the step-size parameter recovers both at the cost of discretization precision. This opens dynamical characterizations of subrecursive hierarchies and complexity classes by restricting time bounds, polynomial degrees, or discretization resources within one framework. More broadly, these models do not compute by composing subroutines: they shape the trajectory of a dynamical system through clocks, phase selectors, and error correction built into the dynamics. This differs structurally from symbolic programming, and our theorem gives a precise framework to study the difference.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper reduces primitive recursion to bounded iteration of one threshold-affine normal form and then realizes it in ReLU networks, polynomial ODEs, and step-size polynomial maps, while noting an asymmetry in rounding.

read the letter

The main result is that every primitive recursive function has equivalent descriptions in three continuous settings: bounded iteration of a fixed recurrent ReLU network, robust computation by a fixed polynomial ODE, and iteration of a fixed polynomial map supplied with an external step-size parameter. The route is to compile the function first into bounded iteration over a single threshold-affine normal form, then interpret that form in each model. Time bounds stay primitive recursive and inputs remain raw integer vectors. Composition is not imposed as a separate rule; it emerges from the dynamics themselves.

Referee Report

0 major / 2 minor

Summary. The paper claims that every primitive recursive function admits equivalent characterizations as bounded iteration of a fixed recurrent ReLU network, robust computation by a fixed polynomial ODE, and iteration of a fixed polynomial map with an externally supplied step-size parameter. It proceeds by compiling any PR function into bounded iteration of a single threshold-affine normal form and then interpreting that form in each dynamical setting. The work emphasizes structural asymmetries between the models (e.g., ReLU for exact branching, continuous time for autonomous rounding and phase selection, step-size for recovering both at the cost of discretization precision) and notes that composition emerges from the dynamics rather than as a closure rule, with inputs as raw integer vectors and time bounds themselves primitive recursive.

Significance. If the equivalences hold, the result supplies dynamical characterizations of primitive recursion and subrecursive hierarchies by restricting time bounds, polynomial degrees, or discretization resources within one framework, rather than via symbolic composition. It gives explicit credit to the reduction to a threshold-affine normal form and the precise analysis of how each formalism compensates for limitations the others lack. This provides a concrete framework for studying computation as trajectory shaping in continuous systems (with clocks, phase selectors, and error correction built into the dynamics) versus traditional subroutine composition.

minor comments (2)

[Abstract] Abstract: the claim that equivalences are proved would be more traceable if the abstract referenced the main theorem numbers or sections containing the derivations and normal-form reductions.
The manuscript should explicitly address discretization and rounding edge cases in the polynomial-map model (including any precision losses under the external step-size parameter) to fully support the robustness claims made for the ODE interpretation.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive and accurate summary of our results, including the emphasis on structural asymmetries between the ReLU, ODE, and step-size models, the emergence of composition from dynamics, and the framework for subrecursive hierarchies. No specific major comments were raised in the report.

Circularity Check

0 steps flagged

No significant circularity; equivalences via explicit normal-form compilation

full rationale

The derivation proceeds by first compiling every primitive recursive function into bounded iteration of a single threshold-affine normal form, then interpreting that form as a recurrent ReLU network, a polynomial ODE, and a polynomial map with external step-size. These steps are presented as constructive reductions that preserve exact equivalence, with no equations or claims reducing the target characterizations to fitted parameters, self-definitions, or load-bearing self-citations. The paper explicitly notes structural asymmetries between the models and uses them to explain why each supplies a missing feature, rather than forcing equivalence by construction. The central result is therefore self-contained against external benchmarks of primitive recursion.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

Based on abstract only; the work relies on standard real-number arithmetic and recursion-theory background but no explicit free parameters or invented entities are mentioned.

axioms (2)

standard math Standard properties of real arithmetic and polynomial functions over the reals
Invoked when defining polynomial ODEs and maps.
domain assumption Existence of a threshold-affine normal form for primitive recursive functions
Central compilation step stated in the abstract.

pith-pipeline@v0.9.0 · 5604 in / 1292 out tokens · 50994 ms · 2026-05-07T17:16:16.032693+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

21 extracted references · 18 canonical work pages

[1]

A new characterization of FAC 0 via discrete ordinary differential equations

1 Melissa Antonelli, Arnaud Durand, and Juha Kontinen. A new characterization of FAC 0 via discrete ordinary differential equations. In Rastislav Královic and Antonín Kucera, editors,49th International Symposium on Mathematical Foundations of Computer Science, MFCS 2024, Bratislava, Slovakia, August 26-30, 2024, volume 306 ofLIPIcs, pages 10:1–10:18. Schl...

2024
[2]

2 Melissa Antonelli, Arnaud Durand, and Juha Kontinen

URL: https://doi.org/10.4230/LIPIcs.MFCS.2024.10, doi:10.4230/ LIPICS.MFCS.2024.10. 2 Melissa Antonelli, Arnaud Durand, and Juha Kontinen. Characterizing small circuit classes from FAC0 to FAC1 via discrete ordinary differential equations. In Pawel Gawrychowski, Filip Mazowiecki, and Michal Skrzypczak, editors,50th International Symposium on Mathematical ...

work page doi:10.4230/lipics.mfcs.2024.10 2024
[3]

2025.10,doi:10.4230/LIPICS.MFCS.2025.10

URL: https://doi.org/10.4230/LIPIcs.MFCS. 2025.10,doi:10.4230/LIPICS.MFCS.2025.10. 3 Melissa Antonelli, Arnaud Durand, and Juha Kontinen. Towards new characterizations of small circuit classes via discrete ordinary differential equations.Theor. Comput. Sci., 1062:115655,

work page doi:10.4230/lipics.mfcs 2025
[4]

4 José L

URL: https://doi.org/10.1016/j.tcs.2025.115655,doi:10.1016/J.TCS.2025.115655. 4 José L. Balcázar, Ricard Gavaldà, Hava T. Siegelmann, and Eduardo D. Sontag. Some structural complexity aspects of neural computation. InProceedings of the Eigth Annual Structure in Complexity Theory Conference, San Diego, CA, USA, May 18-21, 1993, pages 253–265. IEEE Computer...

work page doi:10.1016/j.tcs.2025.115655 2025
[5]

To appear

Accepted for publication. To appear. URL: http://logicandanalysis.org/ index.php/jla/article/view/505. 7 Lenore Blum, Mike Shub, and Steve Smale. On a theory of computation and complexity over the real numbers; NP completeness, recursive functions and universal machines.Bulletin of the American Mathematical Society, 21(1):1–46, jul 1989.doi:10.1142/978981...

work page doi:10.1142/9789812792839 1989
[6]

11 Olivier Bournez, Riccardo Gozzi, Daniel Silva Graça, and Amaury Pouly

doi:10.1007/s00037-023-00240-1. 11 Olivier Bournez, Riccardo Gozzi, Daniel Silva Graça, and Amaury Pouly. A continuous characterization of PSPACE using polynomial ordinary differential equations.Journal of Complexity, 77:101755, august 2023.doi:10.1016/j.jco.2023.101755. 12 Olivier Bournez, Riccardo Gozzi, Daniel Silva Graça, and Amaury Pouly. A continuou...

work page doi:10.1007/s00037-023-00240-1 2023
[7]

13 Olivier Bournez, Daniel Silva Graça, and Amaury Pouly

doi: 10.1016/j.jco.2023.101755. 13 Olivier Bournez, Daniel Silva Graça, and Amaury Pouly. Polynomial time corresponds to solutions of polynomial ordinary differential equations of polynomial length: The general purpose analog computer and computable analysis are two efficiently equivalent models of computations. In Ioannis Chatzigiannakis, Michael Mitzenm...

work page doi:10.1016/j.jco.2023.101755 2023
[8]

14 Olivier Bournez, Daniel Silva Graça, and Amaury Pouly

ICALP’2016 Track B, Best Paper Award.doi:10.4230/LIPIcs.ICALP.2016.109. 14 Olivier Bournez, Daniel Silva Graça, and Amaury Pouly. Polynomial time corresponds to solutions of polynomial ordinary differential equations of polynomial length.Journal of the ACM, 64(6):38:1–38:76, 2017.doi:10.1145/3127496. 15 Olivier Bournez, Daniel Silva Graça, Amaury Pouly, a...

work page doi:10.4230/lipics.icalp.2016.109 2016
[9]

Springer, 2013.doi:10.1007/978-3-642-39053-1\\_2

Proceedings, volume 7921 ofLecture Notes in Computer Science, pages 12–21. Springer, 2013.doi:10.1007/978-3-642-39053-1\\_2. 16 Olivier Bournez and Emmanuel Hainry. Elementarily computable functions over the real numbers and r-sub-recursive functions.Theoretical Computer Science, 348(2-3):130–147,

work page doi:10.1007/978-3-642-39053-1 2013
[10]

Aggarwal, Y

doi:10.1016/j. tcs.2005.09.010. 17 Olivier Bournez and Amaury Pouly. A survey on analog models of computation. In Vasco Brattka and Peter Hertling, editors,Handbook of Computability and Complexity in Analysis. Springer,

work page doi:10.1016/j 2005
[11]

18 Michael S

doi:10.1007/978-3-030-59234-9\_6. 18 Michael S. Branicky. Universal computation and other capabilities of hybrid and continuous dynamical systems.Theoretical Computer Science, 138(1):67–100, 6~feb

work page doi:10.1007/978-3-030-59234-9
[12]

19 Manuel L

doi:10.1016/0304-3975(94) 00147-B. 19 Manuel L. Campagnolo.Computational complexity of real valued recursive functions and analog circuits. Thèse de doctorat, IST, Universidade Técnica de Lisboa,

work page doi:10.1016/0304-3975(94
[13]

Texts in Theoretical Computer Science

21 Peter Clote and Evangelos Kranakis.Boolean Functions and Computation Models. Texts in Theoretical Computer Science. An EATCS Series. Springer, 2002.doi:10.1007/978-3-662-04943-3. 22 Alan Cobham. The intrinsic computational difficulty of functions. In Y . Bar-Hillel, editor,Proceedings of the International Conference on Logic, Methodology, and Philosoph...

work page doi:10.1007/978-3-662-04943-3 2002
[14]

Robust simulations of turing machines with analytic maps and flows

24 Daniel Silva Graça, Manuel Lameiras Campagnolo, and Jorge Buescu. Robust simulations of turing machines with analytic maps and flows. In S. Barry Cooper, Benedikt Löwe, and Leen Torenvliet, editors, New Computational Paradigms, First Conference on Computability in Europe, CiE 2005, Amsterdam, The Netherlands, June 8-12, 2005, Proceedings, volume 3526 o...

2005
[15]

XX:26 Primitive Recursion without Composition 25 Daniel Silva Graça and José Félix Costa

URL: https://doi.org/10.1007/11494645\\_21, doi: 10.1007/11494645\\\_21. XX:26 Primitive Recursion without Composition 25 Daniel Silva Graça and José Félix Costa. Analog computers and recursive functions over the reals.J. Complex., 19(5):644–664, 2003.doi:10.1016/S0885-064X(03)00034-7. 26A. Grzegorczyk. Some classes of recursive functions. InRozprawy Mate...

work page doi:10.1007/11494645 2003
[16]

28 Ker-I Ko.Complexity theory of real functions, volume 3 ofProgress in theoretical computer science

doi: 10.4064/fm-42-1-168-202. 28 Ker-I Ko.Complexity theory of real functions, volume 3 ofProgress in theoretical computer science. Birkhäuser, Boston, 1991.doi:10.1007/978-1-4684-6802-1. 29 Daniel Leivant and Jean-Yves Marion. Predicative functional recurrence and poly-space. In Michel Bidoit and Max Dauchet, editors,TAPSOFT’97: Theory and Practice of So...

work page doi:10.4064/fm-42-1-168-202 1991
[17]

30 Wolfgang Maass

doi:10.1007/BFb0030611. 30 Wolfgang Maass. Bounds for the computational power and learning complexity of analog neural nets. In S. Rao Kosaraju, David S. Johnson, and Alok Aggarwal, editors,Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, May 16-18, 1993, San Diego, CA, USA, pages 335–344. ACM, 1993.doi:10.1145/167088.167193. 3...

work page doi:10.1007/bfb0030611 1993
[18]

32 Jerzy Mycka and José Félix Costa

Association for Computing Machinery.doi:10.1145/800196.806014. 32 Jerzy Mycka and José Félix Costa. A new conceptual framework for analog computation.Theor. Comput. Sci., 374(1-3):277–290, 2007.doi:10.1016/j.tcs.2007.01.005. 33P. Odifreddi.Classical Recursion Theory, volume

work page doi:10.1145/800196.806014 2007
[19]

https://pastel.archives- ouvertes.fr/tel-01223284, Prix de Thèse de l’Ecole Polyechnique 2016, Ackermann Award

2016
[20]

35 Claude E. Shannon. Mathematical theory of the differential analyser.Journal of Mathematics and Physics MIT, 20:337–354, 1941.doi:10.1002/sapm1941201337. 36 Hava T. Siegelmann.Neural networks and analog computation - beyond the Turing limit. Progress in theoretical computer science. Birkhäuser,

work page doi:10.1002/sapm1941201337 1941
[21]

Siegelmann and Eduardo D

37 Hava T. Siegelmann and Eduardo D. Sontag. Analog computation via neural networks.Theoretical Computer Science, 131(2):331–360, sep 1994.doi:10.1016/0304-3975(94)90178-3. 38 Hava T. Siegelmann and Eduardo D. Sontag. On the computational power of neural nets.Journal of Computer and System Sciences, 50(1):132–150, feb 1995.doi:10.1006/jcss.1995.1013. 39 D...

work page doi:10.1016/0304-3975(94)90178-3 1994