Imagine you are given the exact mathematical equation for a simple, deterministic dynamical system—for instance, a one-dimensional population model. The equation is perfectly computable; you can write a short computer program to calculate the next state from the current one with arbitrary precision. If you run this system for a long time, it will eventually settle into a steady-state behavior, tracing out a shape in space known as an attractor.
Intuitively, you might expect that because the local rules of the system are simple and computable, its long-term global behavior must be computable too. If we can simulate the system step-by-step, surely we can compute its final destination.
A profound body of research in computable analysis reveals that this intuition is fundamentally wrong. There is a deep theoretical gap between knowing the local rules of a chaotic system and computing its asymptotic behavior. More surprisingly, there is an equally vast gap between computing the geometric shape of an attractor and computing its statistical properties. Even when a computer can perfectly map out the spatial boundaries of a system's final state, it can be mathematically impossible to calculate how frequently the system visits different regions within those boundaries.
The Breakdown from Local Rules to Global States
The core of the problem lies in how local computation scales over infinite time. When we simulate a dynamical system, we apply a computable transition function over and over again. However, the symbolic existence of a steady state does not guarantee its algorithmic availability.
As demonstrated by Galatolo et al., a system defined by entirely computable functions can yield long-term statistical properties—represented mathematically as invariant measures—that are completely non-computable. Knowing the local rules allows you to simulate a single trajectory, but it does not grant you the ability to algorithmically approximate the system's aggregate, long-term distribution.
[ Computable Local Rules ]
│
▼ (Infinite Iteration)
[ Global Steady State / Invariant Measure ] ──► Can be fundamentally non-computable!
This complexity is not just a matter of high-dimensional chaos or missing information. In a companion paper, Galatolo et al. proved that one can construct computable dynamical systems where physically relevant steady states, such as Sinai-Ruelle-Bowen (SRB) measures, are algorithmically inaccessible. In the most extreme "pathological" cases, the system exhibits a total failure of computability: every single possible invariant measure the system could possess is non-computable. The local rules simply do not contain a computationally accessible blueprint of the global equilibrium.
Geometry vs. Statistics: Why Monte Carlo Fails
To understand why this gap exists, we must separate the where of a dynamical system from the how often.
- The Geometric Attractor: The set of all points in space that the system eventually visits.
- The Statistical Attractor (Invariant Measure): The probability distribution describing the fraction of time the system spends in any given subset of the geometric attractor.
A common assumption in computational physics is that if you can compute the geometric attractor, you can find the statistical distribution by simply running a long simulation—a standard Monte Carlo approach. However, Yampolsky et al. shattered this assumption by demonstrating that even simple, one-dimensional non-linear systems can possess unique physical measures that are fundamentally non-computable.
In these systems, the geometric shape of the attractor might be straightforward to compute, but the density of states across that shape is not. The system's dynamics inherently concentrate the probability distribution around non-computable real numbers. Crucially, this non-computability is not caused by parameter uncertainty; even if the governing parameters are provided with infinite precision, the resulting long-term distribution cannot be calculated by any algorithm. This represents a theoretical breaking point for Monte Carlo simulations: no matter how long you run the simulation, it will never converge to a computable representation of the true physical measure.
This tension is further explored by Binder et al. through the lens of complex dynamics, specifically looking at the Brolin-Lyubich measure. They investigate the inverse problem: determining whether the statistical distribution on a chaotic attractor can remain computable even when the geometric shape of the attractor itself is mathematically "un-drawable" or non-computable. Together, these works show that geometry and statistics carry entirely different computational currencies.
Conflicting Hardness and the Limits of Simplification
Why can't we just simplify these complex systems into manageable, computable pieces? The mathematical framework governing these systems resists easy reduction.
In topological dynamics, the computational complexity you encounter depends heavily on how you choose to define the "end state" of your system. As Mathieu Sablik points out, different definitions of an attractor yield conflicting levels of algorithmic hardness. A system might possess a topologically simple, easily bounded limit set, while its metric or statistical distribution remains infinitely complex. This lack of uniform bounds means that a simulation strategy that works perfectly for finding the spatial boundaries of an attractor will fail entirely when tasked with calculating its statistical averages.
Furthermore, this non-computability is highly contagious and difficult to filter out. In symbolic dynamics, a common technique is to study a complex system by looking at its "topological factors"—essentially, simplified projections or coarser representations of the original system. However, Barbieri et al. demonstrated that the property of computability is not preserved under these factors.
[ Computable High-Dimensional System ] ───(Topological Factor)───► [ Simplified System ]
│
▼
Computability can be
completely lost!
If you take a perfectly computable, effective dynamical system and project it into a lower-dimensional space or a simpler symbolic model, that simplified version can actually lose its computability. Because the class of effective systems is not closed under these standard topological operations, we cannot rely on simplification to bypass the inherent non-computability of complex dynamics.
The Universal Footprint of Undecidability
This computational barrier is not unique to continuous equations or smooth physics models; it is a universal feature of iterative systems, extending directly into discrete computer science.
By establishing a formal bridge between cellular automata and logic programming, Marcus Völker demonstrated that predicting whether the iterative application of a logic program's fixed-point operator will eventually settle into a repeating cycle of states (the discrete equivalent of an attractor) is completely undecidable.
Whether you are tracking the continuous flow of a chaotic differential equation, the discrete steps of a cellular automaton, or the execution of a logic program, the core mechanism remains identical: simple, computable local transitions compound over infinite horizons to create global, steady-state structures whose statistical and geometric properties defy algorithmic prediction.
Key Foundational Work
Dynamics and abstract computability: computing invariant measures (2009) — contributed 5 concept elements to this direction.
Statistical properties of dynamical systems – Simulation and abstract computation (2011) — contributed 2 concept elements to this direction.
Computability of Brolin-Lyubich Measure (2011) — contributed 1 concept elements to this direction.