Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
    
What do you mean exactly by underlying Cantor set? –  Kirill Shmakov 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. –  David Feldman 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

1 Answer 1

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

share|improve this answer
    
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.... –  shaunc Dec 7 '13 at 16:29

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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