Assessing complexity in cellular automata using information theory

Article Article scientifique Article Assessing complexity in cellular automata using information theory eng 2019 author Chliamovitch Gregor 644690 author Velasquez Reynaga Lino Ivan 678536 author Falcone Jean-Luc 0000-0003-0748-6069 502912 author Chopard Bastien 22320 142-160 10.1080/17445760.2017.1337901 1744-5779 https://www.tandfonline.com/doi/full/10.1080/17445760.2017.1337901 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. Complex systems Cellular automata Maximum entropy models Non-equilibrium statistical mechanics Dewey 025.063 Dewey 500.2 Autre European Union Seventh Framework Programme [grant agreement 317534] (Sophocles) 13 Centre universitaire d'informatique 0D3 37 Département de physique théorique 133 32 Département d'informatique 18 false 728 Scientific and Parallel Computing International Journal of Parallel, Emergent and Distributed Systems 34 1 1b46eeba-5235-4eef-b8ac-8dbed00d1e4c Article (Published version) Restricted 2019Chliamovitch_Assessing_complexity_cellular.pdf 2040006 application/pdf restrictedAccess Centres et instituts / Centre universitaire d'informatique Faculté des sciences / Section de physique / Département de physique théorique Faculté des sciences / Département d'informatique

Title	Published in	Access level	OA Policy	Year	Views	Downloads

Assessing complexity in cellular automata using information theory	International Journal of Parallel, Emergent and Distributed Systems			2019	356	0

Archive ouverte UNIGE

Velasquez Reynaga, Lino Ivan