Relationship Between CA and Formal Languages

We begin this section by showing that the finite-time limit set of an arbitrary CA rule (( , Clf = (equation 6.2), is a regular language for all t To this 

We first show how to construct a STG for this rule. In the course of the construction it will become obvious how to generalize to other rules. 

---

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. 

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. 

---