2026-08-21T18:02:50Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27456 2026-08-21T14:42:40Z ddc:004 open_access

Primitive Recursion Without Composition Bournez, Olivier Discrete ordinary differential equations Finite Differences Implicit complexity Recursion scheme Ordinary differential equations Models of computation Analog Computations Formal neural networks What computational mechanisms do recurrent neural networks, polynomial ordinary differential equations, and discrete polynomial maps each bring to the table, and what do they lack? All three are models of computation over the continuum: they operate on real-valued states and evolve by real-valued dynamics, even when the functions we ask them to compute are ultimately discrete. We investigate how these models compare, their strengths, their limitations, and the precise resources on which each one relies, through the lens of primitive recursive functions. We prove that the classical notion of primitive recursion admits equivalent characterizations in all three dynamical frameworks: bounded iteration of a fixed recurrent ReLU network, robust computation by a fixed polynomial ordinary differential equation, and iteration of a fixed polynomial map in discrete time with an externally supplied step-size parameter. In each case, the time bound is itself primitive recursive, composition is not postulated as a closure rule but emerges from the dynamics, and the input is given as a raw integer vector with no auxiliary encoding. At the proof level, every primitive recursive function is first compiled into bounded iteration of a single threshold-affine normal form map, which is then interpreted as a recurrent ReLU computation on the one hand, and as a robust polynomial ODE on the other. The equivalences expose a structural asymmetry between discrete and continuous polynomial computation. We prove that no fixed polynomial map can round uniformly toward the nearest integer, and that none can realize exact phase selection: two operations that polynomial ODEs perform robustly through their continuous-time flow. Each formalism compensates for a limitation that the others do not share: 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. Our equivalence theorem characterizes what each resource contributes, and opens the way to dynamical characterizations of subrecursive hierarchies and complexity classes by restricting the time bounds, polynomial degrees, or discretization resources within the same framework. More broadly, the constructions reveal that these real-valued models do not compute by composing subroutines in the classical sense: they compute by shaping the trajectory of a dynamical system, through clocks, phase selectors, stabilization mechanisms, and error correction built into the dynamics itself. This is a mode of computation that differs structurally from symbolic programming, and our equivalence theorem provides a precise framework in which the difference can be studied. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Olivier Bournez 2026 Is Part Of LIPIcs, Volume 386, 51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2026.74 urn:nbn:de:0030-drops-274564 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2026.74 eng https://creativecommons.org/licenses/by/4.0/legalcode