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:
Church, Alonzo (1936). “An Unsolvable Problem of Elementary Number Theory”. American Journal of Mathematics. 58 (2): 345–363. doi:10.2307/2371045. JSTOR 2371045.
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
Steven H. Strogatz. Nonlinear Dynamics and Chaos. CRC Press; 2nd edition. 2015.
John W. Milnor (2006) Attractor. Scholarpedia, 1(11):1815.
Emmanuel Hainry. Decidability and Undecidability in Dynamical Systems. [Research Report] 2009, pp.27. ffinria-00429965f
