Solvable Cellular Automata: Methods and Applications (Understanding Complex Systems)

✍ Scribed by Henryk Fukś

• Publisher: Springer
• Year: 2023
• Tongue: English
• Leaves: 304
• Category: Library

✦ Synopsis

The main focus of the book is solvability of cellular automata, that is, expressing the state of a given cell after a given number of steps by an explicit formula. The author considers solutions of two types of initial value problems for cellular automata, the deterministic one and the probabilistic one. In the first chapter the basic concepts of cellular automata theory are introduced. Deterministic initial value problem is introduced next and solutions for selected simple rules are also presented. In the following chapters various techniques for solving the deterministic problem are introduced, using elementary CA rules of increasing complexity as examples. The second part of the book introduces the concept of probability measure in the context of cellular automata and the probabilistic initial value problem for both deterministic and probabilistic rules. The book is amply illustrated with examples and applications such as the density classification problem, phase transitions in traffic models or the diffusion of innovations model. In the appendix, solution formulae (both deterministic and probabilistic) for over 60 elementary cellular automata rules are listed. Ruelle-Frobenius-Perron equations for all 88 minimal elementary cellular automata are also provided.

✦ Table of Contents

Preface
Contents
Notation and Symbols
List of Figures
List of Tables
1 Deterministic Cellular Automata
1.1 Basic Definitions
1.2 Elementary Rules and Their Nomenclature
1.3 Blocks and Block Mappings
1.4 Orbits of Cellular Automata
1.5 Minimal Rules
References
2 Deterministic Initial Value Problem
2.1 Single Input Rules
2.2 Polynomial Representation of Local Rules
2.3 Emulation
2.3.1 Emulators of Identity
2.3.2 Emulators of Shift and Its Inverse
2.3.3 Emulators of Other Single Input Rules
References
3 Multiplicative and Additive Rules
3.1 Multiplicative Rules
3.1.1 Rules 32 and 140
3.2 Additive Rules
3.3 Rules 132 and 77
Reference
4 More Complex Rules
4.1 Rule 172
4.1.1 Solving Rule 172
4.2 Rule 168
4.3 Rule 164
4.4 Pattern Decomposition
4.4.1 Rule 78
References
5 Exploiting Rule Identities
5.1 Identities of Fn+1=Gk Fn-k Type
5.2 The Case of G=σ or G=σ-1
5.3 Identities of F=GH Type
6 Rules with Additive Invariants
6.1 Number-Conserving Rules
6.2 Rule 184—Preliminary Remarks
6.3 Finite State Machines
6.3.1 Further Properties of Preimages of 1 for Rule 184
6.3.2 Proof of Proposition 6.1
6.4 Solution of the Initial Value Problem for Rule 184
6.5 Higher Order Invariants
6.6 Elementary CA with Second Order Invariants
6.7 Rules 142 and 43
6.8 Rule 14
References
7 Construction of the Probability Measures
7.1 Cylinder Sets and Their Semi-algebra
7.2 Extension Theorems
7.3 Shift-Invariant Measure and Consistency Conditions
7.4 Block Probabilities
7.5 The Long Block Representation
7.6 The Short Block Representation
References
8 Probabilistic Solutions
8.1 Motivation
8.2 Ruelle-Frobenius-Perron Equation for Cellular Automata
8.3 Orbits of Measures Under the Action of Cellular Automata
8.4 The First Order Probabilistic Initial Value Problem
8.5 Solutions with Dependencies in Products: Rule 172
8.6 Additive Rules
8.7 Higher Order Probabilistic Solutions
8.8 Rule 184
8.9 Rule 14 and Other Rules with Second Order Invariants
8.10 Surjective Rules
8.10.1 The Algorithm for Determining Surjectivity
8.10.2 The Balance Theorem
8.10.3 Solution of the Probabilistic IVP for Surjective Rules
8.11 Further Use of RFP Equations
References
9 Probabilistic Cellular Automata
9.1 Probabilistic CA as a Markov Process
9.2 Maps in the Space of Measures
9.3 Orbits of Probability Measures
9.4 Single Transition α-Asynchronous Rules
9.4.1 Rule 200A
9.5 Cluster Expansion
9.5.1 Special Case: tildea=a
9.5.2 General Case
References
10 Applications
10.1 Asymptotic Emulation
10.2 Jamming Transitions
10.3 Critical Slowing down
10.3.1 First Order Transitions
10.3.2 Second Order Transitions
10.4 Density Classification
10.5 Finite Size Effects
10.6 Equicontinuity
References
11 Approximate Methods
11.1 Bayesian Extension
11.2 The Scramble Operator
11.3 Local Structure Maps
11.4 Quality of the Local Structure Approximation
11.5 Minimal Entropy Approximation
References
12 Beyond Solvable Elementary Rules
12.1 Solvable Versus Non-solvable Rules
12.2 Higher Radius, Number of States and Dimension
References
Appendix A Polynomial Representation of Minimal Rules
Appendix B Deterministic Solution Formulae
Appendix C Probabilistic Solution Formulae
Appendix D Ruelle-Frobenius-Perron Equation of Order 3 for Minimal ECA
Index