A New Kind of Science: The NKS Forum : Powered by vBulletin version 2.3.0 A New Kind of Science: The NKS Forum > News & Announcements > Spectra of logic functions in ECAs
  Last Thread   Next Thread
Thread Post New Thread    Post A Reply
Jason Cawley
Wolfram Science Group
Phoenix, AZ USA

Registered: Aug 2003
Posts: 712

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

Old Post 01-19-2005 06:06 PM
Jason Cawley is offline Click Here to See the Profile for Jason Cawley Click here to Send Jason Cawley a Private Message Edit/Delete Message Reply w/Quote
Post New Thread    Post A Reply
  Last Thread   Next Thread
Show Printable Version | Email this Page | Subscribe to this Thread


wolframscience.com  |  wolfram atlas  |  NKS online  |  Wolfram|Alpha  |  Wolfram Science Summer School  |  web resources  |  contact us

Forum Sponsored by Wolfram Research

© 2004-16 Wolfram Research, Inc. | Powered by vBulletin 2.3.0 © 2000-2002 Jelsoft Enterprises, Ltd. | Disclaimer | Archives