Motivation:
-----------


It recently occurred to me that Turing's analysis of the halting problem may be formulated as a fixed-point theorem. Might this intuition from theoretical computer science have informed important developments in the theory of dynamical systems?


This question is motivated by discussions with computational biologists concerning the question of whether Turing machines may be used to model dynamical systems. A common objection among members of this community is that dynamical systems with a finite energy budget always halt, unlike Turing machines.


However, a fixed-point formulation of Turing's analysis of the halting problem demonstrates that the source of this asymmetry is not that dynamical systems may not be simulated by computers, it is that there are fundamental limits to what Turing machines(and therefore humans) can know about dynamical systems.


Turing's fixed-point theorem:
-----------------------------


### Statement of the theorem:


Given $f$ from the space of computable functions $F$ and the metrisable space $X$, if we define the dynamical system:


\begin{equation}
\forall x\_n \in X, x\_{n+1} = f \circ x\_n \tag{1}
\end{equation}


then the existence of a general method $H$ for deciding whether $\Lambda \subset X$ contains all attractors of $f$ implies the existence of the fixed-point:


\begin{equation}
f \circ f^\* = f^\* \tag{2}
\end{equation}


where $f^\* \in F$.


Unfortunately, it may be shown that there is no such general method $H$ which is guaranteed to halt within a finite number of operations.


### Proof:


Let's suppose we have a dynamical system given by:


\begin{equation}
\forall x\_n \in X, x\_{n+1} = f \circ x\_n \tag{3}
\end{equation}


where $X$ is assumed to be a metrisable space and the nth term $x\_n \in X$ is given by the iterated composition of functions:


\begin{equation}
x\_n = f^n \circ x\_0 \tag{4}
\end{equation}


\begin{equation}
\forall n \in \mathbb{N}, f^{n+1} = f \circ f^n \tag{5}
\end{equation}


then (4) defines a finite loop provided that $n < \infty$.


Now, if the space of attractors $\Lambda \subset X$ is given by:


\begin{equation}
\Lambda = \{x\_0 \in X: \forall \epsilon > 0 \exists N \in \mathbb{N} \forall n \geq N, \lVert f^n \circ x\_0 - f^{n+1} \circ x\_0 \rVert < \epsilon \} \tag{6}
\end{equation}


we may distinguish finite loops from infinite loops if there exists a general stopping criterion $H$:


\begin{equation}
H \circ f = \text{Bool} \circ \{\forall \epsilon > 0 \forall x\_0 \in \Lambda \exists n \in \mathbb{N}, \lVert f^{\infty} \circ x\_0 - f^n \circ x\_0 \rVert < \epsilon \} \tag{7}
\end{equation}


Assuming the existence of $H$, the question of whether $\Lambda$ contains all the attractors of $f$ is a decidable problem. Moreover, given $H$ we may define:


\begin{equation}
\forall x\_0 \in \Lambda, f^\* \circ x\_0 = \lim\_{n \to \infty} f^n \circ x\_0 \tag{8}
\end{equation}


and using (5) this results in the fixed-point:


\begin{equation}
f \circ f^\* = f^\* \tag{9}
\end{equation}


\begin{equation}
f^\*: \Lambda \rightarrow \Lambda \tag{10}
\end{equation}


where $f,f^\* \in F$.


However, $H$ requires an infinite number of function calls in its definition so we have:


\begin{equation}
H \circ f = 0 \implies \text{infinite loop} \tag{11}
\end{equation}


\begin{equation}
H \circ f = 1 \implies \text{infinite loop} \tag{12}
\end{equation}


and so we may conclude that there is no general method $H$ that is guaranteed to halt within a finite number of operations.


### Turing's fixed-point theorem from a dynamical systems perspective:


Turing's fixed-point theorem implies that there is no general analytical method for determining the complete set of attractors of a dynamical system. Therefore, computer simulations or what some call *experimental mathematics* is essential for making progress in such investigations.


While this might be a meta-mathematical result, I think it has important implications for dynamical systems theory and makes me wonder whether other important results in theoretical computer science might place important constraints on what can be known about dynamical systems using the tools available to a classical mathematician i.e. a mathematician that doesn't have access to powerful computers.


Discussion:
-----------


The above result may be extended to another definition of attractor in terms of compact sets $T \subset X$, as presented in [4]:


\begin{equation}
\Lambda = \bigcup\_{T \subset X} \bigcap\_{n=0}^\infty f^n(T) \tag{13}
\end{equation}


\begin{equation}
f^0 \circ T = T \tag{14}
\end{equation}


and given that $\Lambda$ may be expressed as the countable union of pair-wise disjoint compact sets $\Lambda = \bigcup\_{n=1}^\infty \Lambda\_n$, if $\Lambda\_n \neq \emptyset$:


\begin{equation}
f \circ f^\*(\Lambda\_n) = f^\*(\Lambda\_n) \tag{15}
\end{equation}


Such a general undecidability result would motivate the study of universal theories of computation within the dynamical systems community. However, from my inspection of [5] and conversations with dynamical systems researchers it appears that the original proposition


\begin{equation}
\textit{Proving that $\Lambda \subset X$ contains all the attractors of $f$ is generally undecidable} \tag{16}
\end{equation}


is not widely known assuming that it has been rigorously proven elsewhere.


References:
-----------


1. Church, Alonzo (1936). “An Unsolvable Problem of Elementary Number Theory”. American Journal of Mathematics. 58 (2): 345–363. doi:10.2307/2371045. JSTOR 2371045.
2. Alan Turing, On Computable Numbers, with an Application to the Entscheidungsproblem. A Correction, Proceedings of the London Mathematical Society, Series 2, Volume 43 (1938), pp 544–546
3. Steven H. Strogatz. Nonlinear Dynamics and Chaos. CRC Press; 2nd edition. 2015.
4. John W. Milnor (2006) Attractor. Scholarpedia, 1(11):1815.
5. Emmanuel Hainry. Decidability and Undecidability in Dynamical Systems. [Research Report] 2009,
pp.27. ffinria-00429965f



Turing's fixed-point theorem
I am not sure about what do you mean, precisely, when you write that what you showed "anticipates in a profound sense the development of Chaos theory and its applications to weather forecasting". Maybe it's just that the question is a bit too meta-mathematical for me.


The first result in chaos theory can be considered that period 3 (for continuous maps of the interval) implies Li-Yorke chaos. The latter is a precise requirement about the asymptotic behavior of pairs of points, which ensures that you cannot guess the asymptotic distance between them by extrapolating from any finite time history - this is more or less the extent to which forecasting is concerned. Very fine changes in the definition of your continuous interval map (so that, for instance, the 3-periodic point appears) may lead to the emergence of this form of chaos (or others). My gut feeling is that what you are invoking is too general to cover a phenomenon like this, but maybe if you elaborate a bit more I would change my mind.


**Update**: after reading your summary, it seems to me that, as it's often the case with decidability issues, you are safe as long as you are presented with an explicitly defined dynamical system. In this sense, it seems to me that the relation between your reformulation and the theory of, say, topological dynamical systems, is more or less the same as the relation between decidability theory and ring theory: sure enough, it is useful at times to know in advance if some combination of finitely many matrices as factors can be the null matrix, but the fact that the *general* problem is undecidable has little to do with the developments of the theory of matrix rings, or for the problems for which they are studied. This is not intended to suggest that your question is not interesting, but only that perhaps it can provide intriguing thoughts on some *decidability aspects* of dynamical systems more than alternative paths to the theory of chaos.


So concerning your question: "Might this intuition from theoretical computer science have informed important developments in the theory of dynamical systems?", my short answer is "probably no".


