2
$\begingroup$

When wolfram described Elementary Cellular Automata, most of the rules appeared as triangle and lines.

Now, Rule 110 consists of triangles which is proved to be universal.

Is there a relation between these triangles and universality like rule 110, or even other geometric shapes can be related to universality?

$\endgroup$
  • 1
    $\begingroup$ No, universality is not about shapes but about the ability to simulate arbitrary computation. $\endgroup$ – Yuval Filmus Sep 28 '15 at 13:57
  • 1
    $\begingroup$ Triangles and lines aren't there really, it's just the artefact of how the output is printed (one iteration below the other). But this also gives some intuition as to what automata can do: if you see a repeating pattern, it means that this automaton has finite number of states, thus it would be equivalent to some sort of finite state machine. And when states keep changing without any discernible patter, it is likely to be something more expressive than an FSM. $\endgroup$ – wvxvw Sep 28 '15 at 15:31
  • 1
    $\begingroup$ there is some link/ relationship because with universality any "algorithmically definable" shape can be created "somewhere" $\endgroup$ – vzn Sep 28 '15 at 15:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.