Primitive Recursion Without Composition: A Dynamic Equivalence Characterization from Neural Networks to Polynomial ODEs

When Computation Theory Meets Continuous Dynamics

What is the essence of computation? When we shift our gaze from classical Turing machines and discrete logic circuits to continuous dynamical systems, a fundamental question emerges: what computational power do recurrent neural networks (RNNs), polynomial ordinary differential equations (Polynomial ODEs), and discrete polynomial maps—three seemingly distinct continuous computation models—each bring to the table, and what do they lack?

A recently published paper on arXiv (arXiv:2604.24356v1) provides a stunning unified answer. The researchers prove that primitive recursion—one of the most foundational constructs in computation theory—can be equivalently characterized across all three frameworks, without relying on function composition, an operation typically considered indispensable.

Core Discovery: Equivalence Across Three Frameworks

The paper's central contribution lies in establishing an equivalence theorem spanning three different dynamical systems. Specifically, the researchers demonstrated that the following three computational approaches are equivalent in expressing primitive recursive functions:

• Bounded iteration of recurrent ReLU neural networks: Primitive recursive function computation can be achieved by repeatedly executing forward propagation within a fixed number of steps through a recurrent neural network with fixed-structure ReLU activation.
• Polynomial ordinary differential equations (Polynomial ODEs): Continuous-time dynamical systems defined by polynomial vector fields can encode primitive recursion by solving initial value problems.
• Discrete polynomial maps: Repeatedly applying polynomial maps over discrete time steps can likewise capture the full computational power of primitive recursion.

These three models share a common characteristic: they all operate on the "continuum"—states are real-valued, and evolution rules are real-valued—even though the target functions to be computed are ultimately discrete. The paper reveals a profound fact: there is no insurmountable chasm between continuous dynamics and discrete computation.

What Does "Without Composition" Mean?

In classical recursive function theory, primitive recursion is typically constructed from three basic operations: initial functions, composition, and the primitive recursion operator (bounded iteration). Among these, the composition operation allows the output of one function to serve as the input of another, acting as the critical "glue" for building complex functions.

However, the paper's title explicitly states "without composition." This means that within the continuous dynamics framework, relying solely on bounded iteration—repeatedly executing the same fixed dynamical step—is sufficient to capture the full computational power of primitive recursion. The role of composition has been "internalized" by the dynamical system's own evolution process.

This discovery carries significant theoretical implications. It demonstrates that the computational power of recurrent neural networks does not stem from complex network topologies or multi-layer function nesting, but rather from the power of iteration itself. A structurally fixed ReLU network, as long as it is allowed to execute a sufficient (but bounded) number of steps, can complete any primitive recursive computation.

A Bridge Connecting Three Fields

The unique value of this research lies in its simultaneous bridging of three typically independent research domains:

From a machine learning perspective, the result provides a new lens for understanding the theoretical computational capabilities of recurrent neural networks. The ReLU activation function, as the most widely used nonlinear unit in current deep learning, now has its computational boundaries in recurrent architectures precisely characterized mathematically.

From a dynamical systems theory perspective, polynomial ODEs, as a natural form of continuous-time dynamical systems, have long been used to model physical and biological processes. This paper directly links them to computability theory, injecting new vitality into the theoretical foundations of analog computation.

From a computation theory perspective, the class of primitive recursive functions is an important subclass of computable functions, encompassing virtually all computable functions that arise in practice. Precisely characterizing them in continuous models helps us understand the intrinsic computational capabilities of physical systems.

The Broader Theoretical Landscape

This work continues a classic and far-reaching research direction in computation theory: exploring equivalences between different computational models. Just as the Church-Turing thesis unified lambda calculus, Turing machines, and recursive functions under the concept of "computability," this paper attempts to incorporate continuous dynamical systems into the same theoretical framework.

Notably, the paper focuses on "primitive recursion" rather than full "general recursion" (i.e., Turing-complete computation). This choice is deliberate: primitive recursion guarantees that all computations terminate, corresponding to the class of programs that "always halt." This makes bounded iteration a natural and safe computational mode, avoiding the theoretical complexities introduced by infinite loops.

Outlook: The Future of Continuous Computation

As neural networks continue to succeed in practical applications, understanding their theoretical computational limits becomes increasingly important. The results of this paper suggest that even structurally very simple recurrent neural networks harbor computational power beyond what one might imagine.

Future research may proceed in several directions: first, extending the equivalence results from primitive recursion to stronger computational classes; second, exploring the practical implications of these theoretical results for neural network architecture design; and third, further investigating potential applications of polynomial ODEs in "analog-digital hybrid computation."

This paper once again reminds us that the boundaries of computation are far more flexible than we imagine, and the bridge between the continuous and the discrete may be hidden within the most fundamental mathematical structures.