🌀 nonlinear sciences

Analog and Symbolic Computation through the Koopman Framework

This paper establishes a unifying Koopman operator framework that characterizes the computational properties of dynamical systems by linking halting, reachability, and decidability to spectral features such as eigenfunctions and invariant subspaces, thereby bridging symbolic and analog computation through operator-theoretic signatures.

Original authors: Francesco Caravelli, Jean-Charles Delvenne

Published 2026-10-15

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Francesco Caravelli, Jean-Charles Delvenne

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

Computation is often thought of as a purely digital affair, a sequence of ones and zeros marching through silicon chips. Yet, at its deepest level, computation is simply a process of change over time. A computer, whether it is a modern laptop or a simple mechanical calculator, is a machine that moves from one state to another based on rules. If you can describe how a system changes, you can describe how it computes. This idea bridges two worlds that usually stay apart: the world of abstract logic, where mathematicians define what is possible to calculate, and the world of physical dynamics, where scientists study how fluids flow, planets orbit, or circuits switch. The question that has long puzzled researchers is whether we can find a single, unified way to describe the "stop" button for any kind of machine, from the simplest calculator to the most complex, continuous physical system.

In a new study, researchers Francesco Caravelli and Jean-Charles Delvenne propose a powerful new lens to answer this question. They turn to a mathematical tool called the Koopman operator, which acts like a translator between the messy, often unpredictable behavior of physical systems and the clean, orderly language of linear algebra. Instead of tracking the exact position of every particle or the specific value of every variable as time passes, this method watches how the "observables"—the measurable properties of the system—evolve. By lifting the problem into this higher, abstract space, the researchers show that the difficult question of whether a machine will ever stop running can be translated into a question about the system's spectrum, or its set of fundamental frequencies. They find that for many systems, the answer to "will it halt?" is not a simple yes or no, but a property that can be listed out step-by-step, much like counting numbers. However, for a specific class of stable, predictable systems, they prove that the answer can be determined with certainty.

The researchers began by looking at the classic "halting problem," a famous puzzle in computer science that asks whether a given program will eventually finish or run forever. For standard digital computers, this is known to be impossible to solve for every possible program. Caravelli and Delvenne asked if this difficulty exists in the physical world, specifically in systems that evolve continuously, like analog computers or fluid dynamics. To investigate, they treated these systems as if they were machines moving through a vast landscape of possibilities. They used the Koopman operator to create a map of this landscape, not by tracking the path of a single point, but by tracking how the entire shape of the landscape changes. In this view, the question of whether a system reaches a specific destination becomes a question of whether a certain mathematical relationship exists between two points in this abstract space.

Their analysis revealed a striking connection between the behavior of a machine and the mathematical structure of its operator. They showed that if a system has a "halting state"—a condition where the machine stops and stays stopped, like a light switch that has been flipped off and cannot be turned back on—this state appears as a specific, unchanging feature in the operator's spectrum. It is a fixed point that does not shift or fade. If a system has such a state, the mathematical tool reveals it as a special frequency that repeats itself perfectly. Conversely, if a system is constantly cycling or wandering without ever settling, the mathematical signature is different. The researchers proved that for systems that are highly stable and do not react wildly to tiny changes in their starting conditions, the question of whether they will reach a target is always solvable. These systems are too orderly to perform the full range of complex calculations that a universal computer can do.

This finding places a clear boundary on what different types of systems can achieve. The study demonstrates that the ability to perform universal computation—solving any problem a computer can solve—requires a certain level of sensitivity and complexity. If a system is too smooth and predictable, it cannot be a universal computer. The researchers also showed how the familiar diagrams used to map out computer logic, with their boxes and arrows, emerge naturally from this continuous framework. The loops and cycles in a computer's logic graph correspond to specific mathematical constraints in the operator's spectrum. When a system cycles back to a previous state, the mathematics forces a balance, ensuring that the system's behavior remains consistent.

The work offers a new way to think about the power of computation. It suggests that the difficulty of solving a problem is not just a logical hurdle but a physical one, written into the very way the system moves. If a problem is hard, the system describing it might exhibit chaotic behavior, where tiny differences in the start lead to wildly different outcomes. The researchers propose that the Koopman operator can serve as a systematic tool to measure this difficulty, looking at the "spectral structure" of the system to see if it contains the signatures of complex computation. While the study does not claim to solve the halting problem for all machines, it provides a rigorous framework for understanding why some systems are capable of universal computation while others are not. By unifying the study of digital logic and physical dynamics under a single mathematical roof, the paper opens the door to analyzing the computational power of a much broader class of systems, from biological networks to analog solvers, using the same language of operators and spectra.

Technical Summary: Analog and Symbolic Computation through the Koopman Framework

Problem Statement
The paper addresses the challenge of unifying the study of computation across disparate paradigms: symbolic systems (e.g., Turing machines, finite automata) and analog systems (e.g., continuous dynamical systems, differential equations). While classical computation theory relies on discrete state transitions and reachability, analog computation involves continuous trajectories where defining "halting" or "decidability" is non-trivial due to issues of infinite precision and the lack of a consensus on how to formalize termination in uncountable state spaces. The authors seek a high-level, operator-theoretic lens to characterize computational properties—specifically halting and reachability—without resolving the underlying debates on the nature of analog computation, but rather by reframing them through spectral analysis.

Methodology
The authors employ the Koopman operator framework, which lifts nonlinear dynamics into an infinite-dimensional linear operator acting on a space of observables (functions of the state).

Operator Formulation: For a dynamical system $x_{t+1} = F(x_t)$ , the Koopman operator $K$ acts on observables $g$ via $(Kg)(x) = g(F(x))$ . This allows nonlinear dynamics to be studied via linear spectral theory.
Computable Structure: The authors assume the space of observables $C(X)$ possesses a computable structure in the sense of Pour-El and Richards, utilizing a dense, countable family of observables $(g_k)$ with computable norms and operations.
Generalized Halting Problem: They define the Koopman Halting Problem as a decision problem regarding the resolvent of the Koopman operator: given observables $g_a$ and $g_b$ (representing sets $A$ and $B$ ) and a rational $\lambda$ with $|\lambda| > 1$ , does $g_a (\lambda I - K)^{-1} g_b \neq 0$ ? This condition is equivalent to determining if a trajectory starting in set $A$ eventually reaches set $B$ .
Coarse-Graining: For systems with external inputs (non-autonomous), the authors extend the state space to include inputs, defining a Koopman operator on the extended space. They analyze how coarse-graining continuous phase spaces into discrete logical states (regions $\Omega_q$ ) maps to the operator action on characteristic functions.

Key Contributions and Results

The Koopman Halting Problem: The paper establishes that the reachability problem in general computable dynamical systems can be recast as a question about the resolvent of the Koopman operator.
- Recursive Enumerability: The authors prove that for general computable dynamical systems, the Koopman Halting Problem is recursively enumerable (r.e.). This is demonstrated by showing that if the resolvent condition holds (reachability exists), the Neumann series expansion allows for an effective, finite-time certification of non-zero values.
- Decidability in Equicontinuous Systems: For equicontinuous symbolic systems (where nearby initial conditions remain close), the authors prove the Koopman Halting Problem is decidable. In these systems, the span of iterates of piecewise constant observables is finite-dimensional, allowing algorithmic determination of reachability. This implies such systems cannot achieve computational universality (Turing completeness).
Spectral Characterization of Halting and Cycles:
- Absorbing States: The paper demonstrates that halting states (absorbing regions) in finite automata or driven systems correspond to eigenfunctions of the Koopman operator with eigenvalue $\lambda = 1$ . Specifically, the characteristic function of a halting basin is an invariant eigenfunction.
- Multiplicity: The multiplicity of the eigenvalue 1 is at least the number of distinct halting states (absorbing basins).
- Cyclic Constraints: The authors show that cycles in the transition graph of an automaton impose algebraic constraints on the Koopman spectrum. For a directed cycle of length $m$ , the product of the eigenvalues associated with the transitions along the cycle must equal 1.
Unification of Discrete and Continuous: The framework successfully embeds classical automata (finite and pushdown) into the Koopman formalism. Discrete states are mapped to partitions of a continuous phase space, and transition functions are mapped to the action of the Koopman operator on characteristic observables. This provides a rigorous bridge between set-theoretic automata theory and operator-theoretic dynamical systems.

Significance and Claims
The paper claims to provide a unifying perspective on computation in both symbolic and analog systems. By translating computational concepts (halting, reachability, decidability) into spectral properties (resolvents, eigenvalues, invariant subspaces), the authors argue that:

Computational Universality is reflected in the complexity of the operator spectrum and the undecidability of the Koopman Halting Problem.
Computational Hardness in analog systems may admit "dynamical signatures," such as chaotic dynamics or specific spectral structures, which can be analyzed via the Koopman operator.
Structural Continuity: There is a fundamental continuity between symbolic dynamics (defined on Cantor space with clopen sets) and analog models (defined on Euclidean spaces), both of which can be analyzed through the same operator-theoretic lens.

The authors position this work as a "modest step" toward a broader operator-theoretic language for computation, suggesting that the Koopman framework offers a systematic tool to classify computational power and potentially link computational complexity to dynamical phase transitions (e.g., the onset of chaos). They do not claim to solve the halting problem for all systems but rather to provide a rigorous framework for analyzing when and how such problems become decidable or enumerable based on the system's spectral and topological properties.

Technical Summary: Analog and Symbolic Computation through the Koopman Framework

More like this