patternMinor
What is the relation between universality and chaotic behavior in Elementary Cellular Automata?
Viewed 0 times
thewhatcellularbehaviorautomatachaoticbetweenuniversalityelementaryand
Problem
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 ?
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 ?
Solution
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.
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.
Context
StackExchange Computer Science Q#48239, answer score: 3
Revisions (0)
No revisions yet.