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

• URL: http://arxiv.org/abs/2604.24356v1
• Date: Mon, 27 Apr 2026 11:48:49 GMT
• Title: Primitive Recursion without Composition: Dynamical Characterizations, from Neural Networks to Polynomial ODEs
• Abstract summary: We study computation-real-valued states evolved by real-valued dynamics.<n>All three operate over continuum-real-valued states evolved by real-valued dynamics.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• Algebraic Operator Decomposition: A Partitioned Architecture for Noise-Resilient Quantum Computing [0.0]
  We present an operator-decomposition architecture that mathematically maps a global operator into independently executable local operators.<n>AOD complements quantum error correction and error-mitigation approaches by performing algebraic decomposition before quantum execution.
  arXiv  Detail & Related papers  (2026-09-03T16:44:39Z)
• "More Is Different'' in Neural Circuits: Algebraic Emergence of Effective Theories in Canonical Recurrent Motifs of Biological Neuronal Networks [0.0]
  We represent Canonical neural circuit motifs and their compositions as finite transformation systems.<n>We analyze the transition monoids generated by their input-conditioned updates.
  arXiv  Detail & Related papers  (2026-08-31T04:36:37Z)
• Recursion Coefficients and Krylov Dynamics in Polynomial Random Matrix Models [0.0]
  We study the Krylov dynamics in random matrix models with high- and possibly asymmetric potentials.<n>We apply this framework to an asymmetric quartic potential and the double-scaled Sachdev-Ye-Kitaev (DSSYK) model.
  arXiv  Detail & Related papers  (2026-08-10T18:00:02Z)
• Neural network realization of binary refinement iterates via a two-chart atlas selector [0.0]
  We show that every compactly supported continuous piecewise linear seed has finite refinement iterates that admit exact ReLU realizations of fixed width and depth growing linearly.<n>The construction also gives exact readout of every continuous piecewise linear circle function satisfying the natural endpoint compatibility condition.
  arXiv  Detail & Related papers  (2026-07-21T14:11:16Z)
• Generative Recursive Reasoning [67.22973831501257]
  Generative Recursive reAsoning Models (GRAM) is a framework that turns latent reasoning into probabilistic multi-trajectory.<n>GRAM supports conditional reasoning via $p_(y mid x)$ and, with fixed or absent inputs, unconditional generation via $p_(x)$.
  arXiv  Detail & Related papers  (2026-05-19T05:20:56Z)
• From Hilbert's Tenth Problem to Quantum Speedup: Explicit Oracles for Bounded Diophantine Systems [0.0]
  We introduce a fully reversible algorithmic framework to solve Diophantine equations over bounded integer domains.<n>By moving beyond abstract black-box assumptions, this explicit architectural synthesis guarantees that the necessary quantum arithmetic acts as a bounded overhead.
  arXiv  Detail & Related papers  (2026-05-13T18:01:01Z)
• Covering Number of Real Algebraic Varieties and Beyond: Improved Bounds and Applications [8.438718130535296]
  We prove upper bounds on the covering number of numerous sets in Euclidean space.<n>We illustrate the power of the result on three computational applications.
  arXiv  Detail & Related papers  (2023-11-09T03:06:59Z)
• Symmetrical SyncMap for Imbalanced General Chunking Problems [11.26120401279973]
  We show how to create dynamical equations and attractor-repeller points which are stable over the long run. Main idea is to apply equal updates from negative and positive feedback loops by symmetrical activation. Our algorithm surpasses or ties other unsupervised state-of-the-art baselines in all 12 imbalanced CGCPs.
  arXiv  Detail & Related papers  (2023-10-16T04:03:36Z)
• Deep ReLU networks and high-order finite element methods II: Chebyshev emulation [0.0]
  We show expression rates and stability in Sobolev norms of deep feedforward ReLU neural networks (NNs) Novel constructions of ReLU NN surrogates encoding function approximations in terms of Chebyshev expansion coefficients are developed. Bounds on expression rates and stability are obtained that are superior to those of constructions based on ReLU NN emulations of monomials.
  arXiv  Detail & Related papers  (2023-10-11T07:38:37Z)
• A multistep strategy for polynomial system solving over finite fields and a new algebraic attack on the stream cipher Trivium [0.3749861135832073]
  We present an implementation of this strategy in an algorithm called Multi which is designed for systems having at most one solution. We prove that an optimal complexity of Multi is achieved by using a full multistep strategy with a maximum number of steps and in turn the standard guess-and-determine strategy, which essentially is a strategy consisting of a single step, is the worst choice.
  arXiv  Detail & Related papers  (2023-04-16T16:09:14Z)
• A Recursively Recurrent Neural Network (R2N2) Architecture for Learning Iterative Algorithms [64.3064050603721]
  We generalize Runge-Kutta neural network to a recurrent neural network (R2N2) superstructure for the design of customized iterative algorithms. We demonstrate that regular training of the weight parameters inside the proposed superstructure on input/output data of various computational problem classes yields similar iterations to Krylov solvers for linear equation systems, Newton-Krylov solvers for nonlinear equation systems, and Runge-Kutta solvers for ordinary differential equations.
  arXiv  Detail & Related papers  (2022-11-22T16:30:33Z)
• Message Passing Neural PDE Solvers [60.77761603258397]
  We build a neural message passing solver, replacing allally designed components in the graph with backprop-optimized neural function approximators. We show that neural message passing solvers representationally contain some classical methods, such as finite differences, finite volumes, and WENO schemes. We validate our method on various fluid-like flow problems, demonstrating fast, stable, and accurate performance across different domain topologies, equation parameters, discretizations, etc., in 1D and 2D.
  arXiv  Detail & Related papers  (2022-02-07T17:47:46Z)
• On Function Approximation in Reinforcement Learning: Optimism in the Face of Large State Spaces [208.67848059021915]
  We study the exploration-exploitation tradeoff at the core of reinforcement learning. In particular, we prove that the complexity of the function class $mathcalF$ characterizes the complexity of the function. Our regret bounds are independent of the number of episodes.
  arXiv  Detail & Related papers  (2020-11-09T18:32:22Z)
• Graph Gamma Process Generalized Linear Dynamical Systems [60.467040479276704]
  We introduce graph gamma process (GGP) linear dynamical systems to model real multivariate time series. For temporal pattern discovery, the latent representation under the model is used to decompose the time series into a parsimonious set of multivariate sub-sequences. We use the generated random graph, whose number of nonzero-degree nodes is finite, to define both the sparsity pattern and dimension of the latent state transition matrix.
  arXiv  Detail & Related papers  (2020-07-25T04:16:34Z)
• Multipole Graph Neural Operator for Parametric Partial Differential Equations [57.90284928158383]
  One of the main challenges in using deep learning-based methods for simulating physical systems is formulating physics-based data. We propose a novel multi-level graph neural network framework that captures interaction at all ranges with only linear complexity. Experiments confirm our multi-graph network learns discretization-invariant solution operators to PDEs and can be evaluated in linear time.
  arXiv  Detail & Related papers  (2020-06-16T21:56:22Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.