Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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". – Raphael Nov 13 '10 at 18:24
That's exactly what I wanted to imply. – Hans Stricker Nov 13 '10 at 19:04
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. – Carl Mummert Apr 4 '11 at 1:49

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.

share|cite|improve this answer

Your Answer


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.