3
$\begingroup$

I was looking over stephen wolfram's work mainly about Elementary Cellular Automata, i see that for all rules with N steps {i.e 200 steps} they show the same pattern {i,e rule 90 running on 20 steps and 100 steps are the same, like Here}.

Unlike rule 110 which shows different behavior when N = 20, 100 or 200, i know that it is universal but does that mean if a cellular automaton structure does not halt {continue to show different pattern when changing N steps} does that means it is always universal ?

Improve this question
$\endgroup$
8
  • 2
    $\begingroup$ No, there is absolute no reason that the dichotomy you mention covers all cases. It is probably not difficult to find examples, once you tel us what you mean by "show the same structure". $\endgroup$
    – Yuval Filmus
    Oct 16, 2015 at 14:22
  • 1
    $\begingroup$ i mean for example rule 90 when running on 100 steps it is the same as if you run rule 90 on 200 steps. $\endgroup$
    – Magnda
    Oct 16, 2015 at 14:23
  • 3
    $\begingroup$ I still don't know what you mean. Try to express yourself formally. According to Wikipedia's account on rule 90, When started from a random initial configuration, its configuration remains random at each time step, whatever that means. This seems to contradict any natural interpretation of your claim. $\endgroup$
    – Yuval Filmus
    Oct 16, 2015 at 14:25
  • 2
    $\begingroup$ We cannot refute your conjectured dichotomy unless you state it formally. $\endgroup$
    – Yuval Filmus
    Oct 16, 2015 at 14:35
  • 3
    $\begingroup$ The example on Wolfram Alpha starts with an empty tape except for a black box in one place. It's true: this leads to a repeating pattern, for some appropriate definition of 'repeating pattern'. However, the universality of rule 110 has to do with initialising the tape so that it codes some problem and having the 110 ECA compute a value. For example, you can paint the tape such that 110 will compute the prime divisors of 15. Many initial conditions of 110 appear chaotic but aren't, and many other rules (e.g. rule 30) appear chaotic (and never repeat) but aren't very meaningful. $\endgroup$
    – Lieuwe Vinkhuijzen
    Oct 16, 2015 at 14:59

1 Answer 1

Reset to default
2
$\begingroup$

Your problem is formalized in research as follows: given a CA, is it "Turing complete"? This has been proved for a limited set of CAs including rule 110 in the early 2000s by Cook in a notable proof. it was probably first proved for a CA for the game of life by Conway in the 1970s. There are empirical ways of analyzing CAs that can rule out Turing completeness, and "signs/ circumstantial evidence" that a CA might be Turing complete, but no CA can be proved Turing complete or not from a finite number of example cases.

TMs can execute an arbitrary number of steps and then halt, so that is a characteristic required of the CA simulation. But there is no standard way of defining whether a CA "halts" and thats up to the universality mapping. There is currently no general theory of CA←→TM mappings. There are different mappings in the literature and Cooks mapping is also called "weakly Turing complete" because it requires infinitely recurring patterns specified on the CA input.

There is no general way to find whether particular CAs and rules are universal. This is essentially equivalent to the halting problem in general.

Unfortunately Wikipedia does not highlight Turing completeness in CAs. Here are two useful alternative references.

Improve this answer
$\endgroup$

Your Answer

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

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