4
$\begingroup$

This is a follow-up to the question Undecidability in Conway’s Game of Life I posted at mathoverflow.

For some cellular automata it can be proven that they can simulate a Turing machine, normally by explicit construction. For some of them it can be proven that they can not simulate a Turing machine.

Are there computable sufficient conditions on a cellular automaton to be Turing-complete (besides of being one of the known cases)? (My guess is: No.)

If not: Why not?

If not: Can non-computable sufficient conditions be named?

What about necessary conditions?

What's the "standard" way of showing that a cellular automaton is not Turing-complete?

Improve this question
$\endgroup$
3
  • $\begingroup$ Are you implying that you want a Turing machine to prove that another model is as powerful Turing machines? If not, please clarify what you mean by "computable sufficient conditions". $\endgroup$ – Raphael Nov 13 '10 at 18:24
  • $\begingroup$ That's exactly what I wanted to imply. $\endgroup$ – Hans-Peter Stricker Nov 13 '10 at 19:04
  • $\begingroup$ There is no one definition of what it means for a cellular automaton to be Turing complete, because the input/output conventions tend to be defined in an ad hoc way for each automaton. For example, the Rule 110 automaton is only known to be "Turing complete" if we allow an infinite number of nonzero cells at the moment it starts running. So you'd have to start by giving a rigorous definition of what you mean for a cellular automaton to be Turing complete. $\endgroup$ – Carl Mummert Apr 4 '11 at 1:49
1
$\begingroup$

I recently read this paper that seems related to your question "Communication Complexity and Intrinsic Universality in Cellular Automata"

There are some classes of cellular automatas (having some decidable properties) for which non-turing completeness can be proved.

Improve this answer
$\endgroup$

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.