CA and formal languages

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. 

Below we present evidence that (1) the infinite-time limit sets of class cl and c2 CA form regular languages, (2) the infinite-time limit set of class c3 CA (appear to) form context-sensitive languages and (3) the infinite-time limit set of class c4 CA (appear to) to form unrestricted languages. While the evidence is very strong that the assertions about the infinite time limit sets of class c3 and c4 CA are in fact correct, a formal proof has yet to be provided. 

Those negative results did not disprove the hypothesis that computational capability can be correlated with phase transitions in CA rule space they showed only that Packard s results did not provide support for that hypothesis. Relationships between computational capability and phase transitions have been found in other types of dynamical systems. For example, Crutchfield and Young (1989, 1990) looked at the relationship between the dynamics and computational structure of discrete time-series generated by the logistic map at different parameter settings. They found that at the onset of chaos there is an abrupt jump in computational class of the time series, as measured by the formal-language class required to describe the time series. This result demonstrated that a dynamical system s computational capability—in terms of the richness of behavior it produces—is qualitatively increased at a phase transition from ordered to chaotic behavior. 

We shall extensively employ the notation of graph theory it provides a powerful and elegant formalism for the description of both the structure of the discrete lattices on which the CA live, and the complete dynamics (he. the global state transitions) induced by those structures. Graph theory also allows the correspondence between CA configurations and the words of a regular language to be made in a very natural fashion. 

---