3
$\begingroup$

So i know that rule 110 from Elementary Cellular Automata is universal but i am wondering if we had other chaotic behaviors let's say there exists a system that shows nearly infinite chaotic behaviors {a structure at a time} similar to ECA structures, how can we prove or disprove universality from that system ?

Suppose we have a system with one specific rule to execute and the input can be defined by different number of cells {i.e input = 5 cells} these 5 cells for example can show (2000) chaotic behavior... 4 cells can show nearly (1800), for example to get a structure from the (1800) structures, i can change the 4 cells by changing the rule set of these 4 cells just like in ECA => 'two white cells will result in a black cell', i can define a similar rule set on the 4 cells, 5 cells or more generally on x cells where x < infinite.

That system with same input {4 cells} with different rule set can simulate most of the structures in Elementary Cellular Automata like rule 30, 90 & 60 and others, what can be proved about such system and how universality is related to it ?

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ You prove (or disprove) universality by proving that the thing can (or cannot) simulate some other universal system. $\endgroup$
    – David Richerby
    Oct 13, 2015 at 23:01
  • 1
    $\begingroup$ Can you define "chaotic behaviors", or what it means for a system to "show nearly infinite chaotic behaviors", in a precise or rigorous way? If not then you certainly can't prove a result of the form you seem to hope exists. Personally, I doubt that any such result exists. There are chaotic systems that are very simple and I doubt are universal. The question seems to be based on a hope that somehow there is some relationship between chaos vs universality, but I'm skeptical about whether that hope is actually valid. $\endgroup$
    – D.W. ♦
    Oct 13, 2015 at 23:09

1 Answer 1

Reset to default
3
$\begingroup$

Chaotic behavior does not seem to imply universality, from what I can see. I don't see any reason to expect it would.

For instance, here's an example to challenge your intuition that the two concepts are somehow related. Wikipedia lists the dynamic system given by the map $x \mapsto 4x (1-x)$ and $y \mapsto x + y \bmod 1$ as an example of a chaotic system. However I doubt that this system is universal in any meaningful sense.

As David Richerby wrote, the way you prove universality is "by proving that the thing can simulate some other universal system". I don't think "chaotic behavior" -- whatever that might mean -- is a helpful guide to determining whether a particular system is universal.

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.