Wolfram Science Group
Phoenix, AZ USA
Registered: Aug 2003
Spectra of logic functions in ECAs
A paper by Eduardo Mizraji appeared in Complexity, vol. 9 number 6, pp. 33-42, entitled "The emergence of dynamical complexity: an exploration using elementary cellular automaton", that I thought might be of some interest to others here.
Basically he analyses the rule table for ECAs into the logical operations they perform over 1 or 2 steps, then looks at "spectra" of the logic operations (AND, OR, XOR, NOT, etc) they can effectively perform on their "inputs", at that small scale. He then looks for correspondances between the resulting spectra and the complexity seen in that particular CA's evolution.
This work concerns the interaction between two classical problems: the forecasting of the dynamical behaviors of elementary cellular automata (ECA) from its intrinsic mathematical laws and the conditions that determine the emergence of complex dynamics. To approach these problems, and inspired by the theory of reversible logical gates, we decompose the ECA laws in a spectrum of dyadic Boolean gates. Emergent properties due to interactions are captured generating another spectrum of logical gates. The combined analysis of both spectra shows the existence of characteristic bias in the distribution of Boolean gates for ECA belonging to different dynamical classes. These results suggest the existence of signatures capable to indicate the propensity to develop complex dynamics. Logical gates exclusive-or and equivalence are among these signatures of complexity. An important conclusion is that within ECA space, interactions are not capable to generate signatures of complexity in the case these signatures are absent in the intrinsic law of the automaton.
Here is a link -
Report this post to a moderator | IP: Logged