1
$\begingroup$

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

$\endgroup$
8
  • 7
    $\begingroup$ From a technical point of view your question needs to be fixed: you call $P$ a function, but it is a string, and you compoes $P \circ P$ which does not make sense. Most importantly, a fixed-point theorem usually establishes the existence of a fixed point, but I fail to see how your question contains such a theorem. By the way, the non-existence of the Halting oracle is an easy consequence of Lawvere's fixed-point theorem. $\endgroup$ – Andrej Bauer Apr 11 at 13:22
  • 3
    $\begingroup$ In the bit about dynamical systems, it looks like $H$ is not the same as the one in the first part of the question. You write $H \circ f$ where you probably mean $H(f)$. Please clarify and make sure your notation makes sense. $\endgroup$ – Andrej Bauer Apr 11 at 13:25
  • 3
    $\begingroup$ This question still does not make any sense. Regarding your friend biologists, you might present to them the possibility of using each day half of available energy budget and asking them how long it will take to use up all of it. $\endgroup$ – Andrej Bauer Apr 13 at 8:22
  • 1
    $\begingroup$ You use unexplained terminology. First, it is not "given that the infinite loop is defined by a sequence of functions composed with each other". You need to explain what you mean. Next, what does it mean for a function $P$ to "define an infinite loop"? You call $P$ a "process" but it is a function, what do you mean? You need to have a clear distinction between the execution of a machine and the function it computes. $\endgroup$ – Andrej Bauer Apr 13 at 8:27
  • 1
    $\begingroup$ You may like to consult this paper of Yanofsky: A Universal Approach to Self-Referential Paradoxes, Incompleteness and Fixed Points arxiv.org/abs/math/0305282 $\endgroup$ – David Roberts Apr 15 at 9:41
4
$\begingroup$

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".

$\endgroup$
3
  • $\begingroup$ I think you are correct in pointing out that this is a meta-mathematical result. However, I have added a summary which clarifies the importance of this result for dynamical systems research. $\endgroup$ – Aidan Rocke Apr 11 at 11:35
  • 1
    $\begingroup$ What if anything has this got to do with Turing machines and the question? $\endgroup$ – Andrej Bauer Apr 13 at 8:24
  • $\begingroup$ I added some final words to further clarify what I meant. $\endgroup$ – Alessandro Della Corte Apr 13 at 9:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.