Computational Dynamical Systems

Models of digital computation, which lie at the foundation of computer science, are typically discrete, while most of our fundamental models of the physical world are essentially continuous. Nonetheless, the Church-Turing thesis [Tur39] and its physical counterparts [Gan80, CS07] state that this difference is illusory: the discrete computations we can perform reliably in the physical world should be the same as those which can be performed by a Turing machine, possibly by one having access to random bits. The validity of the physical Church-Turing thesis is a subject of debate, and a number of variants of the thesis have been proposed [Cop97]. Furthermore, from the perspective of complexity theory rather than computatibility theory, the possibility for quantum computers to solve with high probability, in polynomial time, decision problems which are not in P, is a basic motivation for research on quantum computation [NC10, ACQ22]. In a different (non-quantum) direction, there have been multiple models proposed for a definition of a computable real function [Grz55, Lac59, Blu98, Sma97, Bra05a], and using this language, it has been found that simple finite-dimensional continuous dynamical systems defined by polynomial equations with integral coefficients can exhibit non-computable dynamical properties [Moo90, BY06]. In general it is known that the existence of natural problems with no computable solution (such as the problem of recognizing presentations of the trivial group [PS]) forces complex behaviour of various continuous mathematical objects related to geometry and dynamics [Wei20, Sei08]. In yet a different direction, there has been a sequence of papers asking whether universal computation can be realized by various ordinary [Bra94] and partial differential equations, including in single-particle potential energy systems [Tao17] and in solutions to fluid dynamics equations [CMPSP21]; this was in part motivated by the hope of showing the existence of blow-up solutions to the Navier-Stokes equations by finding fluid flows which'replicate themselves' at smaller and smaller scales [Tao16]. Such works on realizing universal computation in natural continuous physical models can be seen as a continuation of Moore's earlier work [Moo98, Moo90], which realized universal computation in a simple 2-dimensional piecewise-linear map, as well as in a Lipschitz map on the interval and an analytic map on R. The relation between the computational capacity and the analytic or dynamical properties of a continuous dynamical system, such as its topological entropy or its regularity, are known to be subtle: for example, depending on the formalization, the topological entropy of a Turing-universal system can be zero [CMPS23] or can be forced to be nonnegative [BCMPS24].