🤖 machine learning

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

This paper establishes that recurrent neural networks, polynomial ODEs, and polynomial maps are all equivalent frameworks for computing primitive recursive functions, revealing how each system compensates for the others' structural limitations—such as branching, rounding, or discretization—through their specific dynamical properties.

Original authors: Olivier Bournez

Published 2026-04-28

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Olivier Bournez

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to explain how to build a machine that can solve math problems. Usually, when we think of computers, we think of Lego blocks: you take a small piece (a subroutine), snap it onto another piece (composition), and keep building until you have a complex machine. This is how traditional programming works.

But this paper, written by Olivier Bournez, asks a different question: "Can we build a machine that doesn't use Legos, but instead uses 'Flow'?"

Instead of snapping pieces together, imagine a machine that works like a water system or a musical instrument. You don't "compose" a song by snapping notes together; you create a system (like a piano or a flute) where, if you blow air or press a key in a certain way, the sound "evolves" naturally into a melody.

The paper proves that three very different "flow-based" systems are actually all capable of doing the exact same level of math (specifically, a class called "Primitive Recursion").

Here are the three "machines" the paper compares:

1. The "Light Switch" Machine (Neural Networks)

Imagine a series of rooms connected by hallways. In each room, there is a light switch. Depending on how much light is currently in the room, the switch either stays off or flips on (this is the ReLU activation). You send a signal through these rooms, and it bounces back and forth.

The Secret Sauce: It uses "thresholds"—the sudden "click" of a switch—to make decisions.

2. The "River" Machine (Polynomial ODEs)

Imagine a landscape of hills and valleys. You drop a marble at a certain starting point, and gravity pulls it along a path. The shape of the hills is defined by smooth, mathematical curves (polynomials). The marble doesn't "click" or "switch"; it just flows.

The Secret Sauce: It uses Continuous Time. Because the marble is always moving smoothly, the "hills" can naturally guide the marble into specific "buckets" (rounding to the nearest integer) without needing a light switch.

3. The "Strobe Light" Machine (Discrete Polynomial Maps)

Imagine the same marble in the same landscape, but instead of a smooth flow, you are looking at it through a strobe light. You see the marble, then flash—it jumps to a new spot. You see it again, then flash—it jumps again.

The Secret Sauce: Because the "jumps" are sudden, the marble might miss the "buckets" entirely. To fix this, you have to adjust the speed of the flashes (the step-size). If you flash fast enough, you can mimic the smooth river.

The Big Discovery: The "Asymmetry"

The most interesting part of the paper is a "clash" between the River and the Strobe Light.

The author proves that the River (Continuous Time) is actually "smarter" than the Strobe Light (Discrete Time) in one specific way: Rounding.

In a River, if a marble is slightly off-center, the curve of the hill naturally nudges it back into the center of the valley. It "self-corrects."
In a Strobe Light, if the marble is slightly off-center, the next flash might find it in a completely different valley. It has no way to "nudge" itself back smoothly; it just jumps.

Why does this matter?

Usually, computer scientists think of computation as a series of logical steps: "If X, then do Y."

This paper shows that computation can also be seen as shaping a trajectory. You don't need to write a list of instructions; you just need to design the right "landscape" (the dynamics) so that the answer emerges naturally as the system evolves.

It bridges the gap between the world of Artificial Intelligence (which uses neural networks) and the world of Physics/Engineering (which uses differential equations), proving they are speaking the same mathematical language.

Technical Summary: Primitive Recursion without Composition

Title: Primitive Recursion without Composition: Dynamical Characterizations, from Neural Networks to Polynomial ODEs
Author: Olivier Bournez (Institut Polytechnique de Paris)

1. The Problem: Computation over the Continuum

Classical computability theory (Turing machines, $\lambda$ -calculus) is built on discrete symbolic manipulation and explicit composition of subroutines. However, modern models of computation—specifically Recurrent Neural Networks (RNNs) and Polynomial Ordinary Differential Equations (ODEs)—operate on real-valued states and evolve through continuous or discrete-time dynamics.

The fundamental question is: What is the computational power of these dynamical systems, and how do they differ from classical symbolic models? Specifically, the paper seeks to find a classical function class that sits at the intersection of these diverse dynamical frameworks, without relying on the "postulate" of composition as a closure rule.

2. Methodology: The Dynamical Lens

The author shifts the focus from syntactic composition (writing code as a sequence of subroutines) to dynamical shaping (designing a state space, feedback mechanisms, and flows).

The paper employs a "normal form" approach. Instead of proving equivalences between all models directly, the author identifies a central structural bridge: the Threshold-Affine Normal Form. This form represents a computation as a single fixed map where nonlinearity is provided only by threshold gates ( $\Theta$ ) acting on integer-valued registers.

The methodology follows a three-step architecture:

Compilation: Translating classical primitive recursive (PR) programs (specifically LOOP programs) into the threshold-affine normal form.
Hard Model Equivalence: Proving that this normal form is equivalent to recurrent ReLU networks (where the threshold is realized by a ReLU gadget).
Smooth Model Bridging: Using "shadowing" techniques (ensuring a continuous or discretized trajectory stays within a "decoding basin" of the intended integer trajectory) to link the discrete threshold models to continuous polynomial ODEs and smooth $\rho$ -activations.

3. Key Contributions

Identification of the "Composition Gap": The paper proves that in dynamical systems, composition is not an external rule but an emergent property of the dynamics (e.g., through iteration and state-space design).
The Asymmetry Principle: A major theoretical contribution is the proof that discrete-time polynomial maps and continuous-time polynomial ODEs are fundamentally asymmetric. The author proves that uniform rounding and exact phase selection are "free" in continuous time (via contraction toward lattices) but are provably impossible for fixed polynomial maps in discrete time.
Introduction of the Step-Size Resource: To bridge the gap between continuous ODEs and discrete polynomial maps, the author introduces the step-size parameter ( $h = 2^{-s}$ ) as a formal computational resource.

4. Main Results (The Equivalence Theorem)

The paper establishes that for a function $f: \mathbb{N}^d \to \mathbb{N}^e$ , the following are equivalent:

Classical Primitive Recursion (PR).
Recurrent ReLU Computation: Bounded iteration of a fixed ReLU network.
Recurrent $\rho$ -Computation: Bounded iteration of a fixed network with any "admissible" smooth activation (like sigmoid or tanh) over a compact domain.
Robust Polynomial ODE Representation: Computation via the flow of a fixed polynomial vector field.
Step-Size-Controlled Polynomial Representation: Iteration of a fixed polynomial map where the discretization step size is provided as an external parameter.

Crucially, in all cases, the "boundedness" (time, precision, or domain) is itself a primitive recursive function of the input, and the input is provided as a "raw" integer vector without auxiliary encoding.

5. Significance and Implications

Foundational Theory of Neural Networks: It provides a rigorous complexity-theoretic foundation for RNNs, showing that their power is exactly captured by the class of primitive recursive functions when the number of iterations is controlled.
Unification of Analog and Digital Computation: The work provides a mathematical bridge between the General Purpose Analog Computer (GPAC) tradition and modern machine learning, showing they are different "resource-cost" versions of the same computational class.
Complexity Class Characterization: The paper opens a new pathway to characterize subrecursive hierarchies (like P-Time or P-Space) by restricting dynamical resources (e.g., polynomial degree, discretization precision, or observation time) rather than restricting recursion schemes.
Shift in Computational Logic: It moves the study of computation away from "symbolic programming" toward "dynamical systems engineering," where computation is viewed as the stabilization of a trajectory within a specific basin of attraction.