The Mathematics of Cellular Automata

This textbook offers a rigorous mathematical introduction to cellular automata (CA). Numerous colorful graphics illustrate the many intriguing phenomena, inviting undergraduates to step into the rich field of symbolic dynamics. Beginning with a brief history, the first half of the book establishes the mathematical foundations of cellular automata. After recapping the essentials from advanced calculus, the chapters that follow introduce symbolic spaces, equicontinuity, and attractors. More advanced topics include the Garden of Eden theorem and Conway's Game of Life, and a chapter on stochastic CA showcases a model of virus spread. Exercises and labs end each chapter, covering a range of applications, both mathematical and physical. Designed for undergraduates studying mathematics and related areas, the text provides ample opportunities for end-of-semester projects or further study. Computer use for the labs is largely optional, providing flexibility for different preferences and resources. Knowledge of advanced calculus and linear algebra is essential, while a course in real analysis would be ideal. Cover half title page title page Copyright Contents Preface Basic notation Chapter 1. Introduction to Symbolic Dynamics and Cellular Automata 1.1. Coding and symbolic dynamics 1.2. Cellular automata 1.3. Exercises 1.4. Labs Chapter 2. Properties of Symbol Spaces 2.1. Symbol spaces for cellular automata 2.2. Open and closed sets in metric spaces: The bigger picture 2.3. Convergence and Cauchy sequences in metric spaces 2.4. Dimension 2.5. Zero-dimensional metric spaces 2.6. Exercises 2.7. Labs Chapter 3. Dynamics of CAs: Equicontinuity and attractors 3.1. Continuous functions on R 3.2. Continuous functions on metric spaces 3.3. Equicontinuity and dynamics 3.4. Limit sets, accumulation points, and attractors 3.5. Exercises 3.6. Labs Chapter 4. Dynamics and Classification of Cellular Automata 4.1. A labeling scheme for elementary CAs 4.2. Two classifications of one-dimensional CAs 4.3. Classes E1 and E2: Equicontinuity in CAs 4.4. Classes E3 and E4: Chaotic dynamics in CAs 4.5. Chaotic dynamics of cellular automata 4.6. Exercises 4.7. Labs Chapter 5. Surjectivity and the Garden of Eden Theorem 5.1. Surjective maps 5.2. Surjectivity and dynamics for CAs 5.3. Exercises 5.4. Labs Chapter 6. Two-dimensional CAs and Conway’s Game of Life 6.1. The basic setup for 2D CAs 6.2. Conway’s Game of Life 6.3. The classification scheme for 2D CAs 6.4. Exercises 6.5. Labs Chapter 7. Stochastic Cellular Automata 7.1. An overview of probability distributions among CAs: Making random choices 7.2. The first examples 7.3. Equicontinuity and classification of SCAs 7.4. A detailed definition of a stochastic cellular automaton in one dimension 7.5. An application of SCAs: Modeling viral spread 7.6. Exercises 7.7. Labs Chapter 8. Further directions 8.1. Topological entropy for 1D CAs 8.2. Language 8.3. Dense periodic points and shift maps 8.4. Variations on cellular automata 8.5. Applications to urban development 8.6. Graphics in higher dimensions Bibliography Index Back Cover