On generative morphological diversity of elementary cellular automata

Abstract

Purpose

Studies in complexity of cellular automata do usually deal with measures taken on integral dynamics or statistical measures of space‐time configurations. No one has tried to analyze a generative power of cellular‐automaton machines. The purpose of this paper is to fill the gap and develop a basis for future studies in generative complexity of large‐scale spatially extended systems.

Design/methodology/approach

Let all but one cell be in alike state in initial configuration of a one‐dimensional cellular automaton. A generative morphological diversity of the cellular automaton is a number of different three‐by‐three cell blocks occurred in the automaton's space‐time configuration.

Findings

The paper builds a hierarchy of generative diversity of one‐dimensional cellular automata with binary cell‐states and ternary neighborhoods, discusses necessary conditions for a cell‐state transition rule to be on top of the hierarchy, and studies stability of the hierarchy to initial conditions.

Research limitations/implications

The method developed will be used – in conjunction with other complexity measures – to built a complete complexity maps of one‐ and two‐dimensional cellular automata, and to select and breed local transition functions with highest degree of generative morphological complexity.

Originality/value

The hierarchy built presents the first ever approach to formally characterize generative potential of cellular automata.

Citation

Adamatzky, A. and Martinez, G.J. (2010), "On generative morphological diversity of elementary cellular automata", Kybernetes, Vol. 39 No. 1, pp. 72-82. https://doi.org/10.1108/03684921011021282