6
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • $\begingroup$ What do you mean exactly by underlying Cantor set? $\endgroup$
    – Kirill Shmakov
    Commented Apr 3, 2012 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$
    – David Feldman
    Commented Apr 4, 2012 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
    Commented Nov 20, 2013 at 11:22

1 Answer 1

Reset to default
1
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • $\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
    Commented Dec 7, 2013 at 16:29
  • $\begingroup$ Continuously determining whether the machine will ever halt is definitely impossible with any of the standard simulations of universal computation in Game of Life (if looking at infinite configurations). $\endgroup$
    – Ville Salo
    Commented Feb 28, 2022 at 5:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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