Cellular Automata and Discrete Complex Systems

Hector Zenil

► To cite this version:

Hector Zenil. Cellular Automata and Discrete Complex Systems: 26th IFIP WG 1.5 International Workshop, AUTOMATA 2020, Stockholm, Sweden, August 10–12, 2020, Proceedings. Springer International Publishing, LNCS-12286, 2020, Lecture Notes in Computer Science, 978-3-030-61587-1. 10.1007/978-3-030-61588-8. hal-03659461

HAL Id: hal-03659461

https://inria.hal.science/hal-03659461

Submitted on 5 May 2022

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Founding Editors

Gerhard Goos

Karlsruhe Institute of Technology, Karlsruhe, Germany

Juris Hartmanis

Cornell University, Ithaca, NY, USA

Editorial Board Members

Elisa Bertino

Purdue University, West Lafayette, IN, USA

Wen Gao

Peking University, Beijing, China

Bernhard Steffen

TU Dortmund University, Dortmund, Germany

Gerhard Woeginger

RWTH Aachen, Aachen, Germany

Moti Yung

Columbia University, New York, NY, USA
More information about this series at http://www.springer.com/series/7407
Cellular Automata
and Discrete
Complex Systems

26th IFIP WG 1.5 International Workshop, AUTOMATA 2020
Stockholm, Sweden, August 10–12, 2020
Proceedings

<figure><img src="image_2.png" /></figure>
Editor

Hector Zenil

<figure><img src="image_3.png" /></figure>

Oxford Immune Algorithmics

Reading, UK

ISSN 0302-9743

ISSN 1611-3349 (electronic)

Lecture Notes in Computer Science

ISBN 978-3-030-61587-1

ISBN 978-3-030-61588-8 (eBook)

https://doi.org/10.1007/978-3-030-61588-8

LNCS Sublibrary: SL1 – Theoretical Computer Science and General Issues

© IFIP International Federation for Information Processing 2020, corrected publication 2021

This work is subject to copyright. All rights are reserved by the Publisher, whether the whole or part of the material is concerned, specifically the rights of translation, reprinting, reuse of illustrations, recitation, broadcasting, reproduction on microfilms or in any other physical way, and transmission or information storage and retrieval, electronic adaptation, computer software, or by similar or dissimilar methodology now known or hereafter developed.

The use of general descriptive names, registered names, trademarks, service marks, etc. in this publication does not imply, even in the absence of a specific statement, that such names are exempt from the relevant protective laws and regulations and therefore free for general use.

The publisher, the authors and the editors are safe to assume that the advice and information in this book are believed to be true and accurate at the date of publication. Neither the publisher nor the authors or the editors give a warranty, expressed or implied, with respect to the material contained herein or for any errors or omissions that may have been made. The publisher remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

This Springer imprint is published by the registered company Springer Nature Switzerland AG

The registered company address is: Gewerbestrasse 11, 6330 Cham, Switzerland
Preface

This volume contains the papers accepted and presented at the 26th International Workshop on Cellular Automata (CA) and Discrete Complex Systems (DCS), AUTOMATA 2020, held during August 10–12, 2020, hosted online by the Algorithmic Dynamics Lab, Karolinska Institute, Stockholm, Sweden; and Oxford Immune Algorithmics, Reading, UK. The conference is the official annual event of the International Federation for Information Processing (IFIP), Working Group 5, on CA and DCS, of the Technical Committee 1, on Foundations of Computer Science.

AUTOMATA 2020 is part of an annual series established in 1995 as a collaboration
forum between researchers in CA and DCS. Current topics of the conference include,
but are not limited to, dynamical, topological, ergodic and algebraic aspects of CA and
DCS, algorithmic and complexity issues, emergent properties, formal languages,
symbolic dynamics, tilings, models of parallelism and distributed systems, timing
schemes, synchronous versus asynchronous models, phenomenological descriptions,
scientific modeling, and practical applications.

While AUTOMATA 2020 was innovating on several aspects, including remote attendance because of concerns around carbon footprint, due to the pandemic this is the first time AUTOMATA took place fully online.

AUTOMATA 2020 hosted seven invited speakers, including, Alyssa Adams, Genaro Martínez, Chiara Marletto, Samira El Yacoubi, Rodrigo Torres-Aviles, Andrew Wuensche, and Stephen Wolfram; we sincerely thank them for accepting the invitation. The abstracts of the invited talks are included in this volume.

The conference received 21 submissions and each submission was reviewed by at least three members of the Program or Steering Committees. Based on these reviews and an open discussion, 11 papers were accepted to be presented at the conference and to be included in the proceedings. We thank all authors for their contributions and hard work that made this event possible. The conference program also involved short presentations from exploratory papers not included in these proceedings, and we wish to extend our thanks to the authors of the exploratory submissions.

This year, AUTOMATA also included a special session on Algorithmic Information Dynamics, an exciting new area of research.

We are indebted to the Steering Committee, Program Committee, and additional reviewers for their valuable help during the last months. We acknowledge the generous support and funding provided by IFIP, Oxford Immune Algorithmics, and the FQXi by way of the Silicon Valley Community Foundation.

We are also very grateful for the support of the Local Organizing Committee, in particular Martin Lind, Narsis A. Kiani, and Mariana González Castellón; and to the
Lecture Notes in Computer Science team from Springer for their support in producing
this volume.

August 2020

Hector Zenil
## Organization

### Steering Committee

<table><tr><td>Jan Baetens</td><td>Ghent University, Belgium</td></tr><tr><td>Alonso Castillo-Ramírez</td><td>University of Guadalajara, Mexico</td></tr><tr><td>Alberto Dennunzio</td><td>Università degli Studi di Milano, Italy</td></tr><tr><td>Jarkko Kari</td><td>University of Turku, Finland</td></tr><tr><td>Pedro de Oliveira</td><td>Mackenzie Presbyterian University, Brazil</td></tr></table>

### Program Committee

<table><tr><td>Hector Zenil (Chair)</td><td>Oxford Immune Algorithmics, UK, Karolinska Institute, Sweden, and Algorithmic Nature Group, France</td></tr><tr><td>Gilles Dowek</td><td>ENS Paris-Saclay, France</td></tr><tr><td>Alonso Castillo-Ramírez</td><td>University of Guadalajara, Mexico</td></tr><tr><td>Nazim Fatés</td><td>Inria Nancy, France</td></tr><tr><td>Paola Flocchini</td><td>University of Ottawa, Canada</td></tr><tr><td>Enrico Formenti</td><td>Université Nice Sophia Antipolis, France</td></tr><tr><td>Anahí Gajardo</td><td>University of Concepción, Chile</td></tr><tr><td>Eric Goles</td><td>Adolfo Ibáñez University, Chile</td></tr><tr><td>Jarkko Kari</td><td>University of Turku, Finland</td></tr><tr><td>Martin Kutrib</td><td>Universität Gießen, Germany</td></tr><tr><td>Andreas Malcher</td><td>Universität Gießen, Germany</td></tr><tr><td>David A. Rosenblueth</td><td>Universidad Nacional Autónoma de México, Mexico</td></tr><tr><td>Genaro Martínez</td><td>Instituto Politécnico Nacional, Mexico, and University of the West of England, UK</td></tr><tr><td>Hiroshi Umeo</td><td>Osaka Electro-Communication University, Japan</td></tr><tr><td>Kenichi Morita</td><td>Hiroshima University, Japan</td></tr><tr><td>Pedro de Oliveira</td><td>Mackenzie Presbyterian University, Brazil</td></tr><tr><td>Nicolas Ollinger</td><td>Université d'Orléans, France</td></tr><tr><td>Narsis A. Kiani</td><td>Karolinska Institute, Sweden, and Algorithmic Nature Group, France</td></tr><tr><td>Ivan Rapaport</td><td>Universidad de Chile, Chile</td></tr><tr><td>Hiroshi Umeo</td><td>University of Osaka Electro-Communication, Japan</td></tr><tr><td>Jürgen Riedel</td><td>Algorithmic Nature Group, LABORES, France, and Oxford Immune Algorithmics, UK</td></tr><tr><td>Andrew Adamatzky</td><td>University of the West of England, UK</td></tr><tr><td>Francisco Hernández-Quiroz</td><td>Universidad Nacional Autónoma de México, Mexico</td></tr></table>
Jan Baetens Ghent University, Belgium

Fernando Soler-Toscano University of Seville, Spain, and Algorithmic Nature Group, LABORES, France

**Organizing Committee**

Hector Zenil (Chair) Oxford Immune Algorithmics, UK, Karolinska Institute, Sweden, and Algorithmic Nature Group, France

Narsis A. Kiani Karolinska Institute, Sweden, and Algorithmic Nature Group, France

Jürgen Riedel LABORES, France, and Oxford Immune Algorithmics, UK

Jesper Tegnér Karolinska Institute, Sweden, and King Abdullah University of Science and Technology, Saudi Arabia

Martin Lind Automacoin Foundation, UK

M. T. I. Mariana Oxford Immune Algorithmics, UK

G. Castellón
Abstracts of Invited Talks
# Constructor Theory of Life and Its Applications

Chiara Marletto

University of Oxford, UK

Current explanations for the emergence of life rely crucially on the possibility of certain physical processes: mainly, gene replication and natural selection. What is required of the laws of physics for those processes to be allowed? I will use constructor theory's new mode of explanation to answer this question and to explore the implications for von Neumann's original theory of self-reproducing automata. Under no-design laws, an accurate replicator requires the existence of a 'vehicle' constituting, together with the replicator, a self-reproducer.
# The Role of Emergence in Open-Ended Systems

Alyssa Adams

University of Wisconsin-Madison, USA

Biological systems are notorious for their complex behavior within short timescales (e.g., metabolic activity) and longer time scales (e.g., evolutionary selection), along with their complex spatial organization. Because of their complexity and their ability to innovate with respect to their environment, living systems are considered to be open-ended. Historically, it has been difficult to model open-ended evolution and innovation. As a result, our understanding of the exact mechanisms that distinguish open-ended living systems from non-living ones is limited. One of the biggest barriers is understanding how multiple, complex parts within a single system interact and contribute to the complex, emergent behavior of the system as a whole. In biology, this is essential for understanding systems such as the human gut, which contain multiple microbial communities that contribute to the overall health of a person. How do interactions between parts of a system lead to more complex behavior of the system as a whole? What types of interactions contribute to open-ended behavior? In this talk, two interacting cellular automata (CA) are used as an abstract model to address the effects of complex interactions between two individual entities embedded within a larger system. Unlike elementary CA, these CA are state-dependent because they change their update rules as a function of the system's state as a whole. The resulting behavior of the two-CA system suggests that complex interaction rules between the two CA have little to no effect on the complexity of each component CA. However, having an interaction rule that is random results in open-ended evolution regardless of the specific type of state-dependency. This suggests that randomness does indeed contribute to open-ended evolution, but not by random perturbations of the states as previously speculated.
Collision-Based Computing with Cellular Automata

Genaro J. Martínez<fnref n="1" />,<fnref n="2" />

Unconventional and natural computing has the capacity to handle information at an atomic and molecular level. Examples of these developments can be found in collision-based computers, reaction-diffusion computers, Physarum computers, quantum computers, molecular computing, and DNA computers. In this way, the cellular automata theory conceived by John von Neumann as a tool of super computation which work with indivisible elements and they are inherently and massively parallel. The second essential element and problem on these abstract machines is controller and design reliable components from unreliable organisms. Indeed, this issue is the nature of any unconventional computing architecture.

In theoretical computer science there are several models of unconventional computing, which are based on processes in spatially extended non-linear media with different physics and non-classical logics. In this talk, we will discuss how a collision-based computer employs mobile compact finite patterns represented as mobile self-localized excitations (as particles, gliders, waves, signals) to represent quanta of information in an active non-linear medium. Information values are given by either absence or presence of the particles or other parameters of the localizations. The particles travel in space and when they collide the occuring result can be interpreted as a computation. In this way, any part of the medium space can be used as a wire, particles can collide anywhere within a space sample, there are no fixed positions at which specific operations occur, nor location specified gates with fixed operations. The particles undergo transformations and form bound states, annihilate, or fuse when they interact with other particles. Information values of particles are transformed as a result of the collision.

Particles in complex one-dimensional cellular automata are compact sets of non-quiescent patterns translating along evolution space. These non-trivial patterns can be coded as binary strings or symbols traveling along a one-dimensional ring, interacting with each other and changing their states, or symbolic values, as a result of interactions and computation.

Typically, we can find all types of localizations manifested in cellular automata particles, including positive, negative, and with neutral displacements. This phenomenon can be found in an ample number of complex cellular automata rules.<fnref n="1" /> The

<footnote n="1">¹ Escuela Superior de Cómputo, Instituto Politécnico Nacional, Mexico</footnote>

<footnote n="2">² Unconventional Computing Lab, University of the West of England, Bristol, UK</footnote>

<footnote n="1">¹ Complex cellular automata repository. http://www.comunidad.escom.ipn.mx/genaro/Complex_CA_repository.html.</footnote>
number of collisions between particles in complex cellular automata is determined by the their periods (phases) and a number of contact points. A lot of synchronized particles, packages of them or particles with capacity of extensions, are introduced to universes with an infinity of collisions.

A cellular automaton collider is a finite state machine built of rings of one-dimensional cellular automata. We will discuss how a computation can be performed on the collider by exploiting interactions between these particles. In 2002, Tommaso Toffoli introduced the basis of symbol super collider which synthesize the collision-based computing dynamics. In this way, we fuse this framework with the universality of the elementary cellular automaton rule 110 to show how a cellular automata collider works.

## References

1. Adamatzky, A. (ed.): Collision-Based Computing. Springer, Heidelberg (2012). https://doi.org/10.1007/978-1-4471-0129-1

2. Adamatzky, A. (ed.): Advances in Unconventional Computing: Volume 1: Theory, vol. 22. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-319-33924-5

3. Cook, M.: Universality in elementary cellular automata. Complex Syst. 15(1), 1–40 (2004)

4. Hey, A.J.G. (ed.): Feynman and Computation: Exploring the Limits of Computers. Perseus Books Publishing (1999)

5. McIntosh, H.V.: One dimensional Cellular Automata. Luniver Press (2009)

6. Margolus, N., Toffoli, T., Vichniac, G.: Cellular-automata supercomputers for fluid-dynamics modeling. Phys. Rev. Lett. 56(16), 1694 (1986)

7. Martínez, G.J., Adamatzky, A., McIntosh, H.V.: Computing on rings. In: Zenil, H. (ed.) A Computable Universe: Understanding and Exploring Nature as Computation, pp. 257–276 (2013)

8. Martínez, G.J., Adamatzky, A., McIntosh, H.V.: Complete characterization of structure of rule 54. Complex Syst. 23(3), 259–293 (2014)

9. Martínez, G.J., Adamatzky, A., McIntosh, H.V.: Computing with virtual cellular automata collider. In: 2015 Science and Information Conference (SAI), pp. 62–68. IEEE (2015)

10. Martínez G.J., Adamatzky A., McIntosh H.V.: A computation in a cellular automaton collider rule 110. In: Adamatzky, A. (eds.) Advances in Unconventional Computing. Emergence, Complexity and Computation, vol 22, pp. 391–428 (2017). Springer, Cham. https://doi.org/10.1007/978-3-319-33924-5_15

11. Martínez, G.J., Adamatzky, A., Stephens, C.R., Hoeflich, A.F.: Cellular automaton supercolliders. Int. J. Mod. Phys. C, 22(4), 419–439 (2011)

12. Mills, J.W., Parker, M., Himebaugh, B., Shue, C., Kopecky, B., Weilemann, C.: Empty space computes: the evolution of an unconventional supercomputer. In: Proceedings of the 3rd Conference on Computing Frontiers, pp. 115–126. ACM (2006)

13. Moore, C., Mertens, S.: The Nature of Computation. OUP Oxford (2011)

14. Martínez, G.J., McIntosh, H.V., Seck-Tuoh-Mora, J.C., Chapa-Vergara, S.V.: Reproducing the cyclic tag system developed by Matthew Cook with rule 110 using the phases $f_i = 1 - i$. J. Cell. Autom. 6(2–3), 121–161 (2011)

15. Martínez, G.J., Seck-Tuoh-Mora, J.C., Zenil, H.: Computation and universality: class iv versus class iii cellular automata. J. Cell. Autom. 7(5–6), 393–430 (2013)
16. Ninagawa, S., Martínez, G.J.: 1/f Noise in the computation process by rule 110. J. Cell. Autom. **12**(1–2), 47–61 (2016)

17. Regev, A., Shapiro, E.: Cells as computation. Nature, **419**(6905) (2002)

18. Wolfram, S.: Computation theory of cellular automata. Commun. Math. Phys. **96**(1), 15–57 (1984). https://doi.org/10.1007/BF01217347

19. Wolfram, S.: A New Kind of Science. Wolfram Media, Champaign (2002)

20. Wuensche, A.: Exploring Discrete Dynamics. Luniver Press (2011)

21. von Neumann, J.: Theory of self-reproducing automata. University of Illinois Press, Urbana and London (1966). (Completed by A.W. Burks)

22. Toffoli, T.: Non-conventional computers. In: Webster, J. (ed.) Encyclopedia of Electrical and Electronics Engineering, vol. 14, pp. 455–471 (1998)

23. Toffoli T.: Symbol super colliders. In: Adamatzky A. (eds) Collision-Based Computing, pp. 1–23. Springer, London (2002). https://doi.org/10.1007/978-1-4471-0129-1_1
# Some Control and Observation Issues in Cellular Automata

Samira El Yacoubi¹,², Sara Dridi¹,², and Théo Plénet¹,²

¹ IMAGES ESPACE-DEV, University of Perpignan Via Domitia, France

² ESPACE-DEV, University of Montpellier, IRD, Université des Antilles, Université de Guyane, Université de La Réunion, France

{yacoubi,sara.dridi,theo.plenet}@univ-perp.fr

This talk is based on some recent work carried out in collaboration with my PhD students Sara Dridi and Théo Plenet and other colleagues: Franco Bagnoli, Laurent Lefèvre, and Clément Raïevsky. It focuses on studying problems of observability and controllability of cellular automata (CA) considered in the context of control theory, an important feature of which is the adoption of a state space model. This model traditionally uses a set of partial differential equations (PDEs) in the description of system input-output dynamics. While the controllability concerns the ability to steer controlled evolution processes, observability deals with the capability to reconstruct the initial state of the system, taking into account sufficient knowledge of the system dynamics through certain output measurements. These two major concepts have already been studied for continuous systems described by PDEs as reported in the literature [3, 7, 16]. In the case of deterministic linear systems analysis, the so-called Kalman condition [11, 12] is essential and has been widely used to obtain the main characterization results according to the choice of actuator/sensor structures, locations, number, and types (mobile or fixed), see for example [7, 8] and the references therein.

Our work first consists of generalizing the obtained results to systems described by CA considered as the discrete counterpart of PDEs, and exploring other suitable approaches to prove controllability and observability. CA are widely used mathematical models for studying dynamical properties of discrete systems and constitute very promising tools for describing complex natural systems in terms of local interactions [2, 14, 15]. After having introduced the notion of control and observation in CA, in a similar way to the case of discrete-time distributed parameter systems [10], we started to investigate these key concepts of control theory in the case of complex systems modeled by CA.

The case of Boolean CA has been particularly examined to investigate the special case of boundary regional controllability [4]. It consists of considering objectives to be achieved only on a subregion of the whole domain through the application of controls exerted on the boundary of the target region. The problem has been apprehended using several tools: Kalman theorem, Markov Chains, and graph theory [5, 6]. The extension to non-linear CA has also been studied. For the problem of observability, we assume
that the studied system is autonomous and we applied the tools mentioned above to
prove observability. The first results for affine CA can be found in [13]. The non-linear
case as well as the probabilistic case are currently under investigation.

**Keywords:** Controllability • Observability • Cellular Automata • Kalman condition

References

1. Bagnoli, F., El Yacoubi, S., Rechtman, R.: Toward a boundary regional control problem for Boolean cellular automata. Nat. Comput. **17**(3):479–486 (2018). https://doi.org/10.1007/s11047-017-9626-1

2. Chopard, B., Droz, M.: Cellular Automata Modeling of Physical Systems, Cambridge University Press (1998)

3. Curtain, R.F., Zwart, H.: An introduction to Infinite Dimensional Linear Systems Theory. Springer, Heidelberg (1995). https://doi.org/10.1007/978-1-4612-4224-6

4. Dridi, S., El Yacoubi, S., Bagnoli, F.: Boundary regional controllability of linear boolean cellular automata using Markov chain. In: Zerrik, E., Melliani, S., Castillo, O. (eds.) Recent Advances in Modeling, Analysis and Systems Control: Theoretical Aspects and Applications. Studies in Systems, Decision and Control, vol 243, 37–48. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-26149-8_4

5. Dridi, S., Bagnoli, F., EL Yacoubi, S: Markov chains approach for regional controllability of deterministic cellular automata, via boundary actions. J. Cell. Autom. **14**(5/6), 479–498 (2019)

6. Dridi, S., EL Yacoubi, S., Bagnoli, F., Fontaine, A.: A graph theory approach for regional controllability of boolean cellular automata. Int. J. Parallel Emergent Distrib. Syst. 1–15 (2019). https://doi.org/10.1080/17445760.2019.1608442.

7. El Jai, A.: Distributed systems analysis via sensors and actuators. Sen. Actuators A: Phys. **29**(1), 1–11 (1991)

8. El Jai, A., El Yacoubi, S.: On the relations between actuator structures and final constraint minimum-energy problem. Sen. Actuators A: Phys. **33**(3), 175–182 (1992)

9. El Yacoubi, S., El Jai, A., Ammor, N.: Regional controllability with cellular automata models. Lecture Notes on Computer Sciences, **14**(3), 227–253 (2002)

10. El Yacoubi, S: A mathematical method for control problems on cellular automata models. Int. J. Syst. Sci **39**(5), 529–538 (2008)

11. Kalman, R.E.: On the general theory of control systems. In: Proceedings First International Conference on Automatic Control, Moscow, USSR (1960)

12. Kalman, R.E.: Mathematical description of linear dynamical systems. J. Soc. Ind. Appl. Math. Ser. Control **1**(2), 152–192 (1963)

13. Plénet, T., El Yacoubi, S., Raïevsky, C. and Lefévre, L.: Observability of Affine Cellular Automata through Mobile Sensors, accepted for publication in LNCS, ACRI 2020

14. Wolfram, S.: Cellular Automata and Complexity. Science Mathematics Computing. Addison-Wesley (1994)

15. Wuensche, A., Lesser, M.: The global dynamics of cellular automata. In: An Atlas of Basin of Attraction Fields of One-Dimensional Cellular Automata. Addison-Wesley (1992)

16. Zerrik E., Boutoulout A., El Jai A.: Actuators and regional boundary controllability for parabolic systems. Int. J. Syst. Sci. **31**, 73–82 (2000)
# Topological Dynamical Properties in Turing Machines

Rodrigo Torres-Aviles

Universidad de Concepción, Chile

The goal of this talk is to review a non-exhaustive compilation of some of the work in topological properties in Turing machine Dynamical Systems. We follow two interesting lines, born in Kurka's seminal paper: Topological Entropy, where we talk about Jeandel's computability algorithm and undecidability of positivity; and Aperiodicity, where the existence of the property leads to the existence and undecidability of Topological Transitivity, Minimality, and Mixing, among others.
# Isotropic Cellular Automata

Andrew Wuensche

Unconventional Computing Lab, University of the West of England, UK

To respect physics and nature, cellular automata (CA) models of self-organization, emergence, computation, and logical universality should be isotropic, having equiva- lent dynamics in all directions. I will present a novel paradigm, the iso-rule, a concise expression for isotropic CA by the output table for each isotropic neighborhood group, allowing an efficient method of navigating and exploring iso-rule-space. I will describe new functions and tools in DDLab to generate iso-groups and manipulate iso-rule tables, for multi-value as well as binary, in one, two, and three dimensions. These methods include editing, filing, filtering, searching, mutating, analyzing dynamics by input-frequency and entropy, and identifying the critical iso-groups for glider-gun/eater dynamics. I will illustrate these ideas and methods for two dimensional CA on square and hexagonal lattices, focusing on mutant families of logical universal rules found in iso-rule-space, as well as among the narrower iso-subsets of totalistic and survival/birth rules.
# A New Kind of Automata, That May Be Our Universe

Stephen Wolfram

Wolfram Research, USA

A class of models intended to be as minimal and structureless as possible is introduced. Even in cases with simple rules, rich and complex behavior is found to emerge, and striking correspondences to some important core known features of fundamental physics are seen, suggesting the possibility that the models may provide a new approach to finding a fundamental theory of physics.

Quantum mechanics and general relativity—both introduced more than a century ago—have delivered many impressive successes in physics. But so far they have not allowed the formulation of a complete, fundamental theory of our universe, and at this point it seems worthwhile to try exploring other foundations from which space, time, general relativity, quantum mechanics, and all the other known features of physics could emerge.

The purpose here is to introduce a class of models that could be relevant. The models are set up to be as minimal and structureless as possible, but despite the simplicity of their construction, they can nevertheless exhibit great complexity and structure in their behavior. Even independent of their possible relevance to fundamental physics, the models appear to be of significant interest in their own right, not least as sources of examples amenable to rich analysis by modern methods in mathematics and mathematical physics.

But what is potentially significant for physics is that with exceptionally little input, the models already seem able to reproduce some important and sophisticated features of known fundamental physics—and give suggestive indications of being able to reproduce much more.

Our approach here is to carry out a fairly extensive empirical investigation of the models, then to use the results of this to make connections with known mathematical and other features of physics. We do not know a priori whether any model that we would recognize as simple can completely describe the operation of our universe—although the very existence of physical laws does seem to indicate some simplicity. But it is basically inevitable that if a simple model exists, then almost nothing about the universe as we normally perceive it—including notions like space and time—will fit recognizably into the model.

And given this, the approach we take is to consider models that are as minimal and structureless as possible, so that in effect there is the greatest opportunity for the phenomenon of emergence to operate. The models introduced here have their origins in network-based models studied in the 1990s, but the present models are more minimal
and structureless. They can be thought of as abstracted versions of a surprisingly wide range of types of mathematical and computational systems, including combinatorial, functional, categorical, algebraic, and axiomatic ones.
Special Session: Algorithmic Information
Dynamics

Algorithmic Information Dynamics (AID) [1] is an algorithmic probabilistic framework for causal discovery and causal analysis. It enables the solution of inverse problems on the basis of algorithmic probability, using computational tools drawn from algorithmic complexity theory. AID studies dynamical systems in software space where all possible computable models live and is able to explain discrete longitudinal data such as particle orbits in state and phase space, or to approximate continuous systems by discrete computable models. AID provides tools such as algorithmic perturbation analysis to guide the search and use of precomputed models to find relevant generative mechanisms representing causal first principles of a domain of interest, and is an alternative or complement to other approaches and methods of experimental inference, such as statistical machine learning and classical information theory.

AID is related to other areas such as computational mechanics and program synthesis. However, unlike methods such as Bayesian networks, AID does not rely on graphical models or the (often inaccessible) empirical estimation of mass probability distributions. AID encompasses the foundations and methods that make the area of algorithmic information and algorithmic complexity more relevant to scientific discovery and causal analysis. AID also connects with and across other parallel fields of active research such as logical inference, causal reasoning, and neuro-symbolic computation. AID studies how candidate discrete computable equations such as how generating mechanisms are affected by changes in observed phenomena over time as a result of a system evolving (e.g., under the influence of noise) or being externally perturbed (the location in time and space of such perturbations being hypothesized using algorithmic perturbation analysis).

Presenters in this session included Dr. Narsis Kiani, Dr. Felipe S. Abrahão, Dr. Santiago Hernández-Orozco, Dr. Jürgen Riedel, Dr. Victor Iapascurta, Cameron Sajedi, Martin Lind, and Dr. Hector Zenil who presented a number of introductions to the foundations, methods, and applications of AID, ranging from complex networks [2] to machine learning [3], cryptocurrency (Automacoin), and an application to epileptic seizure prediction [4].

In the context of the cryptocurrency project, the conference served as a platform to introduce Automacoin [5]. Automacoin was conceived to be the first cryptocurrency designed to be Turing-universal and also the most eco-friendly of all coins, as its computations are not only the most general-purpose and fundamental, but are stored and never lost or wasted, so they remain available which increases its value.

The Automacoin network behind the cryptocurrency computation is not only meaningful but it may, in a fundamental way, be considered to be the ultimate meaningful task that intelligent beings can perform to use all the energy available to answer all possible questions by mechanistic (computable) means.
References

1. Zenil, H., Kiani, N.A., Abrahão, F.S., Tegnér, J., Algorithmic Information Dynamics. Scholarpedia **15**(7), 53143 (2020)

2. Abrahão, F.S., Wehmuth, K., Ziviani, A.: Algorithmic networks: central time to trigger expected emergent open-endedness. Theor. Comput. Sci. **785**, 83–116 (2019)

3. Hernández-Orozco, S., Zenil, H., Riedel, J., Uccello A., Kiani N.A., Tegnér, J.: Algorithmic Probability-guided Machine Learning On Non-differentiable Spaces, Frontiers in AI (accepted) [cs.LG] (2020)

4. Iapascurta, V.: Detection of Movement toward randomness by applying the block decomposition method to a simple model of the circulatory system. Complex Syst. **28**(1), 59–76 (2019)

5. https://www.automacoin.com/foundations.html. Accessed 6 August 2020
# Contents

<table><tr><td>Exploring Millions of 6-State FSSP Solutions: The Formal Notion of Local CA Simulation</td><td>1</td></tr><tr><td>Tien Thao Nguyen and Luidnel Maignan</td><td></td></tr><tr><td>Non-maximal Sensitivity to Synchronism in Periodic Elementary Cellular Automata: Exact Asymptotic Measures</td><td>14</td></tr><tr><td>Pedro Paulo Balbi, Enrico Formenti, Kévin Perrot, Sara Riva, and Eurico L. P. Ruivo</td><td></td></tr><tr><td>Cycle Based Clustering Using Reversible Cellular Automata</td><td>29</td></tr><tr><td>Sukanya Mukherjee, Kamalika Bhattacharjee, and Sukanta Das</td><td></td></tr><tr><td>Commutative Automata Networks</td><td>43</td></tr><tr><td>Florian Bridoux, Maximilien Gadouleau, and Guillaume Theyssier</td><td></td></tr><tr><td>Cellular String Generators</td><td>59</td></tr><tr><td>Martin Kutrib and Andreas Malcher</td><td></td></tr><tr><td>Everywhere Zero Pointwise Lyapunov Exponents for Sensitive Cellular Automata</td><td>71</td></tr><tr><td>Toni Hotanen</td><td></td></tr><tr><td>Self-stabilizing Distributed Algorithms by Cellular Automata</td><td>86</td></tr><tr><td>Taiga Hongu and Masami Hagiya</td><td></td></tr><tr><td>A Characterization of Amenable Groups by Besicovitch Pseudodistances</td><td>99</td></tr><tr><td>Silvio Capobianco and Pierre Guillon</td><td></td></tr><tr><td>Four Heads are Better than Three</td><td>111</td></tr><tr><td>Ville Salo</td><td></td></tr><tr><td>Complexity of Generic Limit Sets of Cellular Automata</td><td>126</td></tr><tr><td>Ilkka Törmä</td><td></td></tr><tr><td>Latin Hypercubes and Cellular Automata</td><td>139</td></tr><tr><td>Maximilien Gadouleau and Luca Mariot</td><td></td></tr><tr><td>Correction to: A Characterization of Amenable Groups by Besicovitch Pseudodistances</td><td>C1</td></tr><tr><td>Silvio Capobianco and Pierre Guillon</td><td></td></tr><tr><td>Author Index</td><td>153</td></tr></table>