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.

  • $\begingroup$ What do you mean exactly by underlying Cantor set? $\endgroup$ Apr 3 '12 at 21:33
  • $\begingroup$ @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. $\endgroup$ Apr 4 '12 at 0:34
  • $\begingroup$ Total number of Turing machines are countable but the set of topological spaces is not, So the answer appears to be : no. $\endgroup$
    – ARi
    Nov 20 '13 at 11:22

It would seem that points in the space can be taken to be machine states, and (though I'm rusty in this area), the topology allows a homeomorphism to make any countable 1-1 mapping between states.

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.

Ie. starting with a space in which computation can be represented doesn't mean that an arbitrary conjugacy will preserve this notion. You have to restrict the conjugacy itself to be computable.

... so it would seem the answer is: "no". :)

  • $\begingroup$ Note that if you don't restrict the homeomorphism, then you get a non-standard model for computation, which are also objects of interest in computability theory. They might be able to solve the standard halting problem, but they have their own. One can define hierarchies of such models.... $\endgroup$
    – shaunc
    Dec 7 '13 at 16:29

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.