# Turing's fixed-point theorem

## 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:

$$$$\forall x_n \in X, x_{n+1} = f \circ x_n \tag{1}$$$$

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:

$$$$f \circ f^* = f^* \tag{2}$$$$

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:

$$$$\forall x_n \in X, x_{n+1} = f \circ x_n \tag{3}$$$$

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:

$$$$x_n = f^n \circ x_0 \tag{4}$$$$

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

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

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

$$$$\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}$$$$

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

$$$$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}$$$$

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:

$$$$\forall x_0 \in \Lambda, f^* \circ x_0 = \lim_{n \to \infty} f^n \circ x_0 \tag{8}$$$$

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

$$$$f \circ f^* = f^* \tag{9}$$$$

$$$$f^*: \Lambda \rightarrow \Lambda \tag{10}$$$$

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

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

$$$$H \circ f = 0 \implies \text{infinite loop} \tag{11}$$$$

$$$$H \circ f = 1 \implies \text{infinite loop} \tag{12}$$$$

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]:

$$$$\Lambda = \bigcup_{T \subset X} \bigcap_{n=0}^\infty f^n(T) \tag{13}$$$$

$$$$f^0 \circ T = T \tag{14}$$$$

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$$:

$$$$f \circ f^*(\Lambda_n) = f^*(\Lambda_n) \tag{15}$$$$

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

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

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

• 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. Apr 11 at 13:22
• 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. Apr 11 at 13:25
• 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. Apr 13 at 8:22
• 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. Apr 13 at 8:27
• 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 Apr 15 at 9:41