Outline of Book

The remainder of the book is divided into eleven largely self-contained chapters. Chapter 2 introduces some basic mathematical formalism that will be used throughout the book, including set theory, information theory, graph theory, groups, rings and field theory, and abstract automata. It concludes with a preliminary mathematical discussion of one and two dimensional CA. 

Chapter 4 covers much of the same ground as chapter 3 but from a more formal dynamical systems theory approach. The discrete CA world is examined in the context of what is known about the behavior of continuous dynamical systems, and a number of important methodological tools developed by dynamical systems theory (i.e. Lyapunov exponents, invariant measures, and various measures of entropy and 

Chapter 5 provides some examples of purely analyti( al tools useful for describing CA. It discusses methods of inferring cycle-state structure from global eigenvalue spectra, the enumeration of limit cycles, the use of shift transformations, local structure theory, and Lyapunov functions. Some preliminary research on linking CA behavior with the topological characteristics of the underlying lattice is also described. 

Chapter 6 is a short primer on CA and language theory, and provides a basic discussion of formal language theory, the relationship between CA and formal language theory, power spectra of regular languages and reversible computation. 

Chapter 7 discusses a variety of topics all of which are related to the class of probabilistic CA (PCA) i.e. CA that involve some elements of probability in their state and/or time-evolution. The chapter begins with a physicist s overview of critical phenomena. Later sections include discussions of the equivalence between PCA and spin models, the critical behavior of PCA, mean-field theory, CA simulation of conventional spin models and a stochastic version of Conway s Life rule. 

---