Cellular Automata

1. Front Matter

   Pages i-xxv

   PDF

2. Cellular Automata in Triangular, Pentagonal, and Hexagonal Tessellations

   • Carter Bays

   Pages 1-10

3. Cellular Automata in Hyperbolic Spaces

   • Maurice Margenstern

   Pages 11-27

4. Structurally Dynamic Cellular Automata

   • Andrew Ilachinski

   Pages 29-71

5. Asynchronous Cellular Automata

   • Nazim Fatès

   Pages 73-92

6. Quantum Cellular Automata

   • Karoline Wiesner

   Pages 93-104

7. Reversible Cellular Automata

   • Kenichi Morita

   Pages 105-128

8. Additive Cellular Automata

   • Burton Voorhees

   Pages 129-151

9. Cellular Automata with Memory

   • Ramón Alonso-Sanz

   Pages 153-183

10. Classification of Cellular Automata

    • Klaus Sutner

    Pages 185-200

11. Tiling Problem and Undecidability in Cellular Automata

    • Jarkko Kari

    Pages 201-219

12. Cellular Automata and Groups

    • Tullio Ceccherini-Silberstein, Michel Coornaert

    Pages 221-238

13. Self-Replication and Cellular Automata

    • Gianluca Tempesti, Daniel Mange, André Stauffer

    Pages 239-259

14. Gliders in Cellular Automata

    • Carter Bays

    Pages 261-273

15. Basins of Attraction of Cellular Automata and Discrete Dynamical Networks

    • Andrew Wuensche

    Pages 275-289

16. Growth Phenomena in Cellular Automata

    • Janko Gravner

    Pages 291-308

17. Emergent Phenomena in Cellular Automata

    • James E. Hanson

    Pages 309-321

18. Dynamics of Cellular Automata in Noncompact Spaces

    • Enrico Formenti, Petr Kůrka

    Pages 323-335

19. Orbits of Bernoulli Measures in Cellular Automata

    • Henryk Fukś

    Pages 337-355

20. Chaotic Behavior of Cellular Automata

    • Julien Cervelle, Alberto Dennunzio, Enrico Formenti

    Pages 357-371

This volume of the Encyclopedia of Complexity and Systems Science, Second Edition, provides an authoritative introduction and overview of the latest research in cellular automata (CA) models of physical systems, emergent phenomena, computational universality, chaos, growth phenomena, phase transitions, self-organised criticality, reaction-diffusion systems, self-replications, parallel computation, and more. Fundamental topics of algorithmic complexity, algebraic groups, language theory, evolving CA, ergodic theory, synchronisation, tiling problems and undecidability and topological dynamics of CA are addressed. Cellular automata are regular uniform networks of locally-connected finite-state machines, and represent discrete systems with non-trivial behavior, including waves, patterns and travelling localisations. CA are ubiquitous: they are mathematical models of computation and computer models of natural systems. Classes of CA presented in this book include additive CA, automatain hyperbolic spaces and non-compact spaces, CA in triangular, pentagonal and hexagonal tessellations, automata with memory, quantum and reversible automata, structurally-dynamic CA, and asynchronous automata. Topics added to the second edition include: asynchronous cellular automata, stochastic cellular automata as models of reaction-diffusion processes, cellular automata hardware implementation, cellular automata basins of attraction, orbits of Bernoulli measures in cellular automata, and graphs related to reversibility and complexity in cellular. This state-of-the-art reference is unique in bringing together unequalled expertise of interdisciplinary studies at the edge of mathematics, computer science, and physics.

• mathematical machines
• parallel computing
• complex systems
• modeling physical systems
• Firing Squad Synchronization Problem
• Self-Organized Criticality
• dynamics of evolution
• phase transitions

“The volume is an important collection of high-quality works and an excellent reference for researchers in fields related to cellular automata as well as for newcomers to the subject. It is an important addition to the scientific library of any academic institution.” (Silvio Capobianco, zbMATH 1484.68001, 2022)

• Unconventional Computing Centre, University of the West of England, Bristol, UK

  Andrew Adamatzky

Andrew Adamatzky is a Professor in the department of Computer Science and Creative Technologies and Director of the Unconventional Computing Centre, University of the West of England. He has published extensively in theory of computation, cellular automata and mathematical machines, parallel computing, living technologies, organic electronics, and bio-inspired computing. He has authored several books, including Identification of Cellular Automata, Computing in Nonlinear Media, Reaction Diffusion Computers, Dynamics of Crowded Minds, Physarum Machines and edited over 25 collections of chapters. He is founding editor-in-chief of the Journal of Cellular Automata and Journal of Unconventional Computing and editor-in-chief of the International Journal of Parallel, Emergent and Distributed Systems, and Parallel Processing Letters.

Policies and ethics