intro

Cellular Automata: an Introduction

What Are Cellular Automata (CA)? An Example of a Set of Rules An Example of a Pattern Generated by a Rule More Patterns and a Hint of the Categorizations Stephen Wolfram's CA Categorizations References and Links

What Are Cellular Automata (CA)?
CA have three fundamental characteristics [1]: 1. parallelism -- all states are updated simultaneously 2. locality -- a cell's new state is based on its old state and the state of the neighboring cells 3. homogeneity -- the same rules are applied to the whole automoton Extremely complex behavior can result from very simple rules. "Any system with many identical discrete elements undergoing deterministic local interactions may be modelled as a cellular automaton . . . Physical examples may be found in aggregation phenomena such as snowflake growth . . . The solitaire computer game of 'Life' is an example of a two-dimensional cellular automaton." [2] back to the top

An Example of a Set of Rules [2]
This is an example of a set of rules for a one-dimensional CA (a line): figure 1 This shows each of the 8 (=2^3) possible sets of values for a site (a digit) and its nearest neighbors above the line; below the line appears the value to be taken by the central number in each grouping above the line. For example, in the first "grouping," for lack of a better term, if a 1 has a 1 on the left and a 1 on the right, it will become a 0 at the next step; or consider the second-to-last grouping: if a 0 has a 0 on the left and a 1 on the right, it will become a 1 at the next step. (" . . . the two end sites depend on unspecified values.") Notice that this rule "may be considered to take the value of a site to be the sum modulo two of the values of its two neighbours on the previous time step." For example, in the first grouping: (1+1) mod 2 = 2 mod 2 = 0; in the second-to-last grouping: (0+1) mod 2 = 1 mod 2 = 1; in the last grouping: (0+0) mod 2 = 0 mod 2 = 0. "Rules may be denoted by the decimal equivalents of their binary specifications: [the above] thus gives rule 01011010[binary]=90[decimal] ." Since there are 8 digits in this binary specification, there is a total of 2^(2^3) = 2^8 = 256 possible binary specifications and thus rules. "Only the 32 rules of the form a[1]a[2]a[3]a[4]a[2]a[5]a[4]0 (this only has 5 unique digits that can take on values of 0 or 1, and 2^5 = 32) satisfy reflection symmetry and leave the 'quiescent' [inactive] configuration -000000- unchanged, and are therefore considered 'legal'." back to the top

An Example of a Pattern Generated by a Rule [3]
The figure below shoes two constructions for the pattern generated by rule 90 (see above). The generated pattern is actually Pascal's triangle modulo two. Or think of the pattern this way: stunted binary trees, wherein each nonzero site gives rise to two diagonal branches at the next step, but those branches are inhibited if they would collide. "The final pattern of nonzero sites is obtained as the limit of the recursive geometrical construction shown in fig. 3. This pattern is seen to be ``self-similar'' or ``scale invariant'', in that views with different ``magnifications'' (but the same ``resolution'') are indistinguishable." This pattern is generated from a "seed," a single nonzero site. figure 2 back to the top

More Patterns and a Hint of the Categorizations [4]
Figure 3 below shows several patterns of an initial disordered state. The previous example considered an initial ordered state. (For comparison, figure 4 below shows the 32 patterns generated from a simple seed.) An initial ordered state has a few nonzero sites, whereas in disordered initial states each site is chosen independently to be 1 with a certain probability p0, so the initial density p of nonzero sites is p0. Each of the 32 patterns in the figure below has an initial disordered state with density 1/2. The patterns are a bit difficult to discern in full detail, but notice that the patterns exhibit several types of steady state behavior: some evolve quickly to uniform states (such as rule 250); some evolve quickly to stable patterns, sometimes involving independent sections of short-period cycles (such as rules 94 and 132); some exhibit continually complicated patterns (such as 18 and 90). figure 3 figure 4 back to the top

Stephen Wolfram's CA Categorizations
Wolfram proposed four categories:[1, 5, 6] Class 1: point attractors -- the system enters a fixed state quickly (dies out -- goes to all zeroes) Class 2: limit cycles -- the system develops a periodic pattern Class 3: chaotic -- the system becomes aperiodic, changing unpredictably and indefinitely Class 4: structured -- the system develops highly complex but unstable patterns ". . . cell state should change between 25% and 50% of the time for Class 4. Less than this generally leads to static behaviour (Classes 1 & 2), more to chaotic behaviour (Class 3)." [1] "Mathematicians believe that every cellular automaton - regardless of its dimensions or number of possible states - falls into one of these four categories. As far as Wolfram knows, this has yet to actually be proven." [5] back to the top

References and Links
The above information was taken (sometimes shamelessly verbatim) from the following: 1: http://ai.miningco.com/compute/ai/library/weekly/aa083199.htm 2: http://www.stephenwolfram.com/publications/articles/ca/82-cellular/2/text.html 3: http://www.stephenwolfram.com/publications/articles/ca/82-cellular/3/text.html 4: http://www.stephenwolfram.com/publications/articles/ca/82-cellular/4/text.html 5: http://www.susqu.edu/facstaff/b/brakke/complexity/harris/ca.htm 6: http://life.csu.edu.au/complex/tutorials/tutorial1.html 7: http://www.brunel.ac.uk/depts/AI/alife/al-snowf.htm 8: http://www.stephenwolfram.com/publications/articles/general/88-complex/2/text.html The following are worth exploring: Several of Stephen Wolfram's articles on cellular automata A collection of interactive sites for generating cellular automata Play John Conway's The Game of Life, a class 4 CA

Cellular Automata:

an Introduction