Assessing complexity in cellular automata using information theory

ABSTRACT

We discuss two ways in which information theory can be used to assess complexity in a system of interacting agents. In the first part, we adopt a global viewpoint and propose a characterization of complexity based on successive maximum entropy estimations of the probability density describing the system, thereby quantifying the respective role played by low and high orders of interaction. In the second part we reconsider the question from a local perspective, focussing on the statistical dependencies between neighbouring agents. These tools are tried on simple cellular automata in order to put them in perspective with other notions of complexity usually employed for such systems. We show that these approaches are hardly comparable, despite some overlap in simple cases. However this allows to interpret complexity in terms of interactions at work in a system (instead of making reference to any particular realization of this dynamics), and to shed some light on the role of initial conditions in complex systems.

Clustering of the 88 non-equivalent Elementary Cellular Automata according to their position in the space of information processing features. Rules are coloured according to their Wolfram class. ECA in class I are shown in black, class II in red, chaotic automata (class III) in green and automata displaying complex behaviour (class IV) in blue. In spite of some important important differences, information features and Wolfram class are seen to overlap to a certain extent.

Graphical Abstract

Keywords:

• Complex systems
• cellular automata
• maximum entropy models
• non-equilibrium statistical mechanics

Notes

No potential conflict of interest was reported by the authors.

1 If the support of p is unbounded we have to impose finite mean and variance in order to recover a meaningful distribution (which turns out to be Gaussian).

2 Note that the use of the principle of maximum entropy was introduced in the context of cellular automata by [19] and developed in [20], though from a different perspective to the one presented here.

3 As an aside, note that the sum could be started from , in which case it would add up to the KL distance between p and the uniform distribution. This would make necessary to assign null interdependence to uniform distributions only, and not to factorizable ones.

Additional information

Funding

The authors would like to acknowledge funding from the European Union Seventh Framework Programme [grant agreement 317534] (Sophocles).