One-dimensional CA

Since each site can take one any of fc values, p is completely defined by specifying the value assigned to each of the possible (2r -f l)-tuple configurations 

After choosing some specific initial global state 

Rules may be combined by composition i.e., two rules, (f i and / 2, may be combined to form the rule (f) = 4 i(t 2- The set of rules obtained in this way is closed under composition, although the number of sites in the neighborhood will typically have to be increased. If a rule is composed with itself, then / = (fxp) generates patterns consisting of alternate time steps of the patterns of / . In general, composition is noncommutative (f i(p2  

Equation 2.35 defines an arbitrary range-r rule that is P -order in time. n -Order rules, for which a particular site value at time t depends on the r-neighborhood site values for the previous n iteration steps, may, of course, also be constructed  

By defining effective site values a = allowing for a larger 

---

For a one-dimensional CA, the valne of the cell at time t - denoted by Ci t) evolves in time according to a rnle F that is a fnnetion of Cj(t) and other cells that are within a range r (on the left and right) of Ci t) ... 

Fig. 1.2 Evolution of a one-dimensional CA starting from a random initial state.

It is easy to see that an elementary size-n one-dimensional CA rule (f) is equivalent to a size-n feedback shift register with a G (0,1, taps at positions n — 2, n — 1 and n, and f 4>. The only difference is that it takes n shift-register time-steps to reproduce a single CA time step. 

We conclude our brief tour of one-dimensional CA by mentioning a few special properties of some selected one-dimensional rules. We will have occasion to refer back, more than once, to some of the behaviors discussed here, after the appropriate set of formal tools has been presented in later chapters. 

The idea now is to use A to systematically sample, and study the behavior of, rules in the rule space starting with one-dimensional CA. The sections below... 

Consider the behavioral changes induced in a randomly chosen one-dimensional CA rule such that A is successively and minimally incremented from 0 to 1. As an example, let us take fc = 4 and r = 2 (i.e. neighborhood size M = 2r + 1), and use a lattice of = 128 sites with periodic boundary conditions. We summarize a typical sequence of induced behavioral cdianges ... 

Fig. 4.15 Schematic view of a small space-time region of a one-dimensional CA. The site-values in the. dotted region are completely determined by values in the surrounding lined area. See text for discussion.

In particular, the last relation implies that if B,T —> oo with T/B fixed, then the information per site in a B x T space-time region, Iq = 5meas(B, T)/B —> 0. In other words, completely random space-time patterns for one-dimensional CA can never really be generated. 

Given any arbitrary local range-r one-dimensional CA rule, (/> 0,1,... fe —... 

Consider once again a size-7V, radins-r one-dimensional CA with periodic boundary conditions ... 

We begin by considering a one-dimensional CA consisting of N sites, and assume periodic boundary conditions. Letting, as always, ao t),... denote the... 

EXAMPLE Consider a simple but non-trivial STG consisting of two nodes and three arcs (the reader can check that this regular language actually characterizes the attractors of many one dimensional CA - rules R12, R56 and 162, among others) ... 

ERCA are, in the usual way, obtained from r = 1 one-dimensional CA by the Fredkin construction (see section 3.1.4.5). Introducing, for convenience, an additional variable di t) = the evolution of a size N system is determined... 

The idea that localized partic le-like propagating structures can be defined on a lattice Wcus nothing new. For example, Minsky was well aware of the existence of gliders in Conway s Life rule. Minsky s own pedagogical example was effectively a four-state one-dimensional CA with states a e 0,1,a,/ and rules 4> (cri i,CTi,cri+i) —cr given by ... 

Langton was able to provide a tentative answer to his question - at least within the somewhat more limited realm of the complex dynamics of CA - by examining the behavior of the entire rule space of elementary one-dimensional CA rules as parameterized by a single parameter A (see section 3.2.1). Given a rule 4>, A is defined to be the fraction of entries in the rule table for [Pg.683]

Suppose that several cells are placed in a line to form a one-dimensional CA. Every unit has an initial state of 0, apart from the central cell, which has a state of 1. 

Similarly, 3 = 7 - 2k. The ratio (Ci/Cq) can be determined by comparing Eq. (5.49) with the corrugation amplitudes of the charge-density contours obtained from first-principles calculations. For example, from Fig. 5.7, averaged from five contours ranging from three contours of thinnest densities, we find (C /Co) 5.7 1.0. Following the procedure for the one-dimensional ca,se, the STM image for the p- tip state is... 

Many alternative schemes for simulating Turing machines in cellular automata have been formulated over the years. For example, Lindgren and Nordahl (1990) constructed an r = 1, A = 7 one-dimensional CA in which tape symbols were represented by stationary cell states (as in Smith s construction) but in which the tape head (with internal state) was represented as a left- or right-moving particle —a propagating set of CA states. 

---