Classifying Cellular Automata Automatically

Andy Wuensche

Working Papers from Santa Fe Institute

Abstract: "Glider" dynamics in cellular automata (CA), where coherent configurations emerge and interact, provide a stark instance of self-organization in a simple system. Such behaviour was classified as class 4 or complex (as opposed to ordered or chaotic) by Wolfram, and was one of the original motivations for Artificial Life. Because glider dynamics is relatively rare in CA rule spaces, much study has focused on the few known complex rules. However, a more general theory would benefit from many examples, which are now available for 1d CA found by the methods described.

Cellular automata rules can be classified automatically for a spectrum of ordered, complex, and chaotic dynamics, by a measure of the variance of input-entropy over time. The method allows screening out rules that display glider dynamics and related complex rules, giving an unlimited source for further study. The method also shows the distribution of rule classes in the rule-spaces of varying neighbourhood sizes. The classification produced seems to correspond to our subjective view of space-time dynamics, and to global measures on the ``bushiness'' of typical sub-trees in attractor basins, characterized by the distribution of in-degree sizes in their branching structure. The paper explains the methods and presents results for 1d CA.

Keywords: Cellular automata; complex rules; self-organization; emergent interacting configurations; input-entropy variance; rule-space (search for similar items in EconPapers)
Date: 1998-02
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wop:safiwp:98-02-018

Access Statistics for this paper

More papers in Working Papers from Santa Fe Institute Contact information at EDIRC.
Bibliographic data for series maintained by Thomas Krichel ().