# Topological dynamics and Turing complete automata

One can look at, say, Conway's Game of Life in at least two ways:

1) as a cellular automaton; and

2) as a discrete topological dynamical system (on an underlying Cantor set).

Famously, Conway showed how to build a register machine inside the Game of Life, thus showing the Game of Life, viewed as a cellular automaton, Turing complete.

My question: Suppose we have another discrete topological dynamical system S, on a Cantor set C, connected to the Game of Life by a topological conjugacy. Does that guarantee that we can view S as a Turing complete automaton?

I'll assume that C comes in the form of the topological product of finite sets. If necessary, I'll also assume also that C has a computable update rule.

Certainly strong assumptions on the conjugacy (including at least computability) would allow for the translation of problems about the fate of Game of Life configuration into questions about the fate of C configurations. But I don't see what would make all such conjugacies computable or any appropriate way to carry out Conway's argument in purely dynamical terms.

• What do you mean exactly by underlying Cantor set? Apr 3 '12 at 21:33
• @Kirill At a particular time, each cell has a state in {Alive, Dead}. The set of functions {Alive, Dead}${}^{{\Bbb Z}^2}$ has the topological type of a Cantor set. Apr 4 '12 at 0:34
• Total number of Turing machines are countable but the set of topological spaces is not, So the answer appears to be : no.
– ARi
Nov 20 '13 at 11:22

If this is correct then we could define a homeomorphism that mapped states into $\{0\dots,1\dots\}$ based on whether the state in the domain represents a halting configuration.