Section 5 - Cellular Automata

3A.5.1 1D Cellular Automata

Life is an example of a 2D CA (Two Dimensional Cellular Automaton) because it uses input and output on a 2D grid. However, we can get all the adrenaline-pumping, heart-pounding action of life with a fraction of the complexity by implementing a 1D CA (One Dimensional Cellular Automaton). This suits our lesson plan because we have been covering one dimensional arrays. Not only that, but we can display our 1D arrays a-row-at-a-time, stacking them up, so to speak, so as to build up a 2D pattern.

In one dimension, each generation exists as a linear row of cells, each cell being either on (alive or 1) or off (dead or 0). (Since we are not really going to emulate life necessarily, we will use on or 1 rather than alive, and off or 0 rather than dead.) In a console application, we can also represent the row as a 1D array of chars or a string, with a blank , ' ' for 0 and an asterisk, '*', for 1. So in our pictures and discussion, I will use ' ' and '*' interchangeably with off and on or 0 and 1, respectively.

Here are three random (and unrelated) generations for a possible 1D CA:

 "** * ** *** *** *** ** ** * * * ****** **"

"                          *                            "

" ******  ******  ****** * * * * ** **      ***      *  "

Any of these three generations might be a seed for a 1D CA or they might arise as a result of applying a rule to a previous generation of some 1D CA. As usual, all of the cells update their state depending on the states of their neighbors. The state of a particular cell in the current generation is determined by the states of the cell itself, its left neighbor and its right neighbor, all three values read from the previous generation.

For example, let's say that the cell (named Bob) is on. To Bob's left, Frank is also on, and to Bob's right, Shelly is off. Then we need to know what Bob will be in the next generation. Of course, this depends on the rule we are using.

But let's say that we happen to be using a rule that tells Bob to turn-Off in response to this. We can represent this as follows:

or, in terms of 1s and 0s

and if we are using in blanks or asterisks:

Now, Bob's [on-on-off] environment from the previous generation is just one of eight possible states in which Bob might find himself. In order to have a complete rule-set for our CA, we need to know the outcomes for all eight possibilities. Selecting seven other rules to go along with the one above, we will have a complete rule-set for a CA. This can be shown in a table as follows (we'll use 1s and 0s):

Now we have the complete rule for this particular 1D automaton. For example, what if, in a given generation, Bob's environment is described by off-on-on (" **" or 011). What is Bob in the next generation? Look up and find 011 in the top row of the rule table. It is the fifth triplet from the left, and we see, by looking at the result directly below that triplet, the output for Bob is 1 or "*".

Remember, I have chosen only one rule, somewhat at random, by picking outputs for each of the eight possible combinations of inputs.

Notice that the triplet at the far right of this table tells us how to respond if the inputs are 000. Looking immediately left in that same table, we see the rule's output for the input triplet 001. Left a little more gives the rule's response to an input of 010, and so on, until we get to the far left where we have the rule's output for 111. If we agree that we will always use this arrangement when describing a rule, we don't even need the top rows. All we need are numbers at the bottom. So the above rule can be described more succinctly as follows:

0 0 0 1 1 1 1 0

Here, the 0 at the far right is assumed to be the output of 000. The 1 to its left is assumed to be the output of 001. Continuing, we get to the leftmost 0 which is, by agreement, the output for the inputs 111. This is a pretty simple way to express the rule.

But wait. If you order now, you can get an even more concise notation. We see that every rule-set will always be eight bits (can you tell me why?) and each bit is either 0 or 1. So the above rule, if interpreted as a binary number, can be converted to its decimal equivalent. What is that? 00011110 is ... drum roll please... the number 30. We have just shown that if someone tells us they are using rule-set #30 then we know exactly how our CA will evolve. But what if they tell us they are using, say, rule-set #182? Just convert the number 182 to binary and build the table.

182 = 1 0 1 1 0 1 1 0

So the rule will be:

This means that we can completely describe all possible 1D cellular automata. Every automaton is completely determined by a number between 0 and 255. That number gives the rule-set for propagating each cell to its new value in the next generation. This efficient codification for the 256 possible 1-D cellular automata was initially devised by Melanie Mitchell, one of the most active contributors to the fields of cellular automata and genetic algorithms in recent years.

Qualification: In fact, we have been dealing with a special type of 1D CA. Our CAs are 1D and have the following two additional constraints:

1. Each cell only has two possible states, 1 or 0 (on or off), and
2. Each cell's state is determined only by it and its two closest neighbors.

It is for these kinds of CA only that we can assert that a single number from 0 to 255 completely describes the CA. In general CA theory, there can be more than two states, and a cell can be affected directly by its more distant neighbors, not just the ones to its immediate left and right. But we are not considering these more general entities.

3A.5.2 Rule 30

If we start out with the seed pattern: 0001000 and apply rule #30 to it, we will get 0011100 (check it yourself - don't take my word for it). Apply rule #30 again and you'll get 0110010. Do it again and you get 1101111. If we print out each generation below the previous one, using black and white squares rather than 0s and 1s, we will get this pattern:

Gosh, we have a seed string, " * " and a rule #30. From these two things, we can manually create new strings. Not only that, we can output each string to the screen on its own line. (This should result in our own personal rule #30 image for this seed string). Can we write a program that asks for a rule from 0 - 255 and then produces an image?

Enter Rule (0 - 255): 30
start
*
***
**  *
** ****
**  *   *
** **** ***
**  *    *  *
** ****  ******
**  *   ***     *
** **** **  *   ***
**  *    * **** **  *
** ****  ** *    * ****
**  *   ***  **  ** *   *
** **** **  *** ***  ** ***
**  *    * ***   *  ***  *  *
** ****  ** *  * *****  *******
**  *   ***  **** *    ***      *
** **** **  ***    **  **  *    ***
**  *    * ***  *  ** *** ****  **  *
** ****  ** *  ******  *   *   *** ****
**  *   ***  ****     **** *** **   *   *
** **** **  ***   *   **    *   * * *** ***
**  *    * ***  * *** ** *  *** ** * *   *  *
** ****  ** *  *** *   *  ****   *  * ** ******
**  *   ***  ****   ** *****   * ***** *  *     *
** **** **  ***   * **  *    * ** *     *****   ***
**  *    * ***  * ** * ****  ** *  **   **    * **  *
** ****  ** *  *** *  * *   ***  **** * ** *  ** * ****
**  *   ***  ****   **** ** **  ***    * *  ****  * *   *
** **** **  ***   * **    *  * ***  *  ** ****   *** ** ***
**  *    * ***  * ** * *  ***** *  ******  *   * **   *  *  *
** ****  ** *  *** *  * ****     ****     **** ** * * *********
**  *   ***  ****   **** *   *   **   *   **    *  * * *        *
** **** **  ***   * **    ** *** ** * *** ** *  ***** * **      ***
**  *    * ***  * ** * *  **  *   *  * *   *  ****     * * *    **  *
** ****  ** *  *** *  * **** **** ***** ** *****   *   ** * **  ** ****
**  *   ***  ****   **** *    *    *     *  *    * *** **  * * ***  *   *
** **** **  ***   * **    **  ***  ***   ******  ** *   * *** * *  **** ***
**  *    * ***  * ** * *  ** ***  ***  * **     ***  ** ** *   * ****    *  *
** ****  ** *  *** *  * ****  *  ***  *** * *   **  ***  *  ** ** *   *  ******
*  *   ***  ****   **** *   ******  ***   * ** ** ***  ******  *  ** *****
**** **  ***   * **    ** **     ***  * ** *  *  *  ***     ******  *    *   *
*    * ***  * ** * *  **  * *   **  *** *  **********  *   **     ****  *** **
***  ** *  *** *  * **** *** ** ** ***   ****         **** ** *   **   ***   *
***  ****   **** *    *   *  *  *  * **   *       **    *  ** ** * **  * **
* **  ***   * **    **  *** *********** * * ***     ** *  *****  *  * * *** *
* ***  * ** * *  ** ***   *           * * *  *   **  ****    ****** * *   ***
** *  *** *  * ****  *  * ***         ** * ***** ** ***   *  **      * ** **
**  ****   **** *   ****** *  *       **  * *     *  *  * ***** *    ** *  * *
***   * **    ** **      *****     ** *** **   ******** *     **  **  **** *

end

You have to squint a little to see the various sized upside-down triangles, but this is, indeed, the same result as shown in the prettier images, above. Look at the first three generations, for instance, and compare that with the first graphic in this section.

This output results from a program that allows the user to enter any rule and then applies that rule to a seed consisting of a single asterisk floating in a sea of off cells. A different program might allow the user to choose a seed, but that requires more work from the user.

Let's run the program again, this time applying rule 124 to the same seed:

'
Enter Rule (0 - 255): 124
start
*
**
***
* **
*****
*   **
**  ***
*** * **
* *******
***     **
* **    ***
*****   * **
*   **  *****
**  *** *   **
*** * ****  ***
* *****  ** * **
***   ** ********
* **  ****      **
***** *  **     ***
*   **** ***    * **
**  *  *** **   *****
*** ** * *****  *   **
* ********   ** **  ***
***      **  ****** * **
* **     *** *    *******
*****    * ****   *     **
*   **   ***  **  **    ***
**  ***  * ** *** ***   * **
*** * ** ****** *** **  *****
* ********    *** ***** *   **
***      **   * ***   ****  ***
* **     ***  *** **  *  ** * **
*****    * ** * ***** ** ********
*   **   ********   ******      **
**  ***  *      **  *    **     ***
*** * ** **     *** **   ***    * **
* **********    * *****  * **   *****
***        **   ***   ** *****  *   **
* **       ***  * **  ****   ** **  ***
*****      * ** ***** *  **  ****** * **
*   **     ******   **** *** *    ******
**  ***    *    **  *  *** ****   *
*** * **   **   *** ** * ***  **  **
* *******  ***  * ******** ** *** ***
***     ** * ** ***      ****** *** **
* **    ********* **     *    *** *****
*****   *       *****    **   * ***   **
*   **  **      *   **   ***  *** **  *
**  *** ***     **  ***  * ** * ***** **
*** * *** **    *** * ** ********   ****
* ***** *****   * ********      **  *
***   ***   **  ***      **     *** **
* **  * **  *** * **     ***    * *****
***** ***** * *******    * **   ***   **
*   ***   *****     **   *****  * **  **
**  * **  *   **    ***  *   ** ***** *
*** ***** **  ***   * ** **  ****   ****
* ***   ***** * **  ******** *  **  *  *
*** **  *   ******* *      **** *** ** *
* ***** **  *     ****     *  *** ******
***   ***** **    *  **    ** * ***
* **  *   *****   ** ***   ****** **
***** **  *   **  **** **  *    *****
*   ***** **  *** *  ***** **   *   **
**  *   ***** * **** *   *****  **  ***
*** **  *   *****  ****  *   ** *** * **
* ***** **  *   ** *  ** **  **** ******
***   ***** **  ***** ****** *  ***
* **  *   ***** *   ***    **** * **
***** **  *   ****  * **   *  *******
*   ***** **  *  ** *****  ** *     **
**  *   ***** ** ****   ** *****    ***
*** **  *   ******  **  ****   **   * **
* ***** **  *    ** *** *  **  ***  ****
***   ***** **   **** **** *** * ** *
* **  *   *****  *  ***  *** *********
***** **  *   ** ** * ** * ***       **

end
Press any key to continue . . .

It seems that someone has written a program that works. Let's see how much of a challenge this actually is. While it is relatively easy from a programming standpoint, you may have found that the one tricky part was -- or is -- understanding the meaning of a rule as a single number. Some of you will get this on the first "read" and have it down already, while others will need to reread the above development to really see how we get a complete rule-set from a single 8-bit number. Do that first, before going on to the next sections which proposes an OOP implementation of this 1D CA.

3A.5.3 Some Perspective

What we are going to do next has all the characteristics of CA programming. The brain connections you are about to cultivate will work very well for much more complicated systems because they all use the same basic ideas that we are learning here, i.e., applying a discrete rule set to the elements of an array.

I like to give some perspective every now and then, because sometimes these topics can seem a little abstract. Is there any use for the techniques we are about to apply? Yes. The skills developed in this module and the associated homework assignment are used in areas such as computer animation, image processing, pattern recognition, artificial intelligence, biological systems theory, environmental systems theory, chaos, fractals, genetic algorithms, econometrics, epidemiology modeling (i.e., health/illness epidemics), computer games, multi-robot autonomous control theory, film and television special effects and fluid dynamics.