Last edited 21mar03 by Bryan Petrus
Find this document at www.ncsa.uiuc.edu/Classes/MATH198/petrus

Bryan Petrus

illiCell

Cellular Automata

Math198 Semester Project

Abstract

A cellular automaton, in its simplest form, is a set of rules. The simplest cellular automata use a grid of spaces in which each space can either be filled or not filled, a one or a zero. In each iteration of the automaton, the state of each cell is dete rmined by the states of the cells around it in the previous iteration. The set of rules for a valid cellular automaton must give an output for every possible set of inputs. Famous cellular automata are generally two-dimensional. For example, the "Game of Life" portrays successive "generations" of a toy model of a population on a two-dimensional grid.¹ In another type of cellular automaton, as described by Stephen Wolfram, the cellular automaton is one-dimensional, but each succeeding iterat ion is displayed on the next line of the grid. In this way, a two-dimensional graph is created, with time supplying the second dimension.². Cellular automata have a variety of uses in real world computations and models. Wolfram uses them to model a variety of situations, for example, snowflakes and mollusk shells. Other uses include modeling genetics,³ where each generation is determined by the state of the previous generation.

Math Elements

The overriding concern in making a program to display cellular automata (CA) is the description and determination of the rules. Wolfram treats each of his rules as a binary number. If each cell in the grid is either off or on, then the automaton can be treated as a series of 1's and 0's. In a Wolfram CA, the next state of any given cell is determined by the state of the cell and the cells surrounding it in the previous iteration. So, for example, (forgive the lack of artwork, but I am a complete novi ce at html):

0 1 0

is one state and

1 0 1

is another. To differentiate easily between different states, each cell is given a number:

0 1 2

And this can be translated to binary as:

1 2 4

Making each state a binary number:

0 1 0 = 2
1 0 1 = 5

From this it follows that there are eight possible states, from 000 to 111, in a one-dimensional CA. Since there are eight possible states, then any rule must take into account each state. And, since there are only two possible outcomes, 1 or 0, the sta te can be written in shorthand as an eight digit binary number. Therefore, the rules range from 000000000 to 111111111, or 0 to 511. In a two-dimensional CA, the prior state for a given cell looks like this:

0 1 0
1 0 1
1 1 1

Following the same idea as in one dimension, then the state can be numbered as:

0 1 2
3 4 5
6 7 8

This time, there are 2⁹=512 possible states making there 2⁵¹² total possible CA's. Each rule can, in the same way as before, be written as a binary number. However, C doesn't like 512 digit integers, so rather than use a number, I use d an array. Finally, I currently just randomly select a rule rather than accepting user input. This can be changed easily enough, but a truly practical system would be difficult to design.

The program that iterates the cellular automata turns the state into a binary number. For example:

0 1 0
1 0 1
1 1 1

is equal to 0*2⁰ + 1*2¹ + 0*2² + 1*2³ + 0*2⁴ + 1*2⁵ + 1*2⁶ + 1*2⁷ + 1*2⁸ = 2 + 8 + 32 + 64 + 128 + 256 = 490. So the program would check element 490 of the rule array and assign its value to the next value of the CA.

This creates the two-dimensional array displayed in three-dimensions. A true three-dimensional CA is more difficult, mainly because the rules would need to be incredibly complex (2²⁷ states, and that many digits in a rule number). An easier w ay to do this is following the rules of the "Game of Life."

Game of Life

John Conway's "Game of Life" bases its rules only on the number of cells surrounding any given cell, not their positions. This means that there are fewer "Game of Life" rules then there are CA's for two dimensions. In three dimensions, this can be a maj or benefit. In two dimensions, the Game of Life takes three rules:

1. A living cell lives if it is surrounded by 2 or 3 living cells.
2. A dead cell grows if it is surrounded by 3 living cells.
3. In any other case, the cell dies.

Although it takes more rules, I found it better to describe it by four rules rather than three in order to make the transition to three dimensions easier. So, the new rules can be summarized as follows.

A given cell is alive in the next iteration if:
1. The cell is alive and:

a) It has more than 1 neighbor
b) It has less than 4 neighbors
2. The cell is dead and:

a) It has more than 2 neighbors
b) It has less than 3 neighbors

With these, yiu can define a two dimensional CA with four rules as opposed to 512. The downside is that the precision of the CA has been severely reduced. In three dimensions, however, this becomes a necessity. Remember that there are nine neighbors in two dimensions, making 2⁹=512 states and that many rules for each cellular automaton. In three dimensions, there are 27 neighbors, making 2²⁷=134,217,728 states and that many rules necessary. Making an array that size, while it may be possible, would be wildly impractical. Meanwhile, the Game of Life in three dimensions can use the same 4 rules, with changes made to deal with the increased space.

Other Information

Here is some other information on my project:

Here is a narrative of my project and my work on it.

References

1. Gambill, Tom. Class Notes for CS 101.

2. Wolfram, Stephen. "A New Kind of Science." Lecture at University of Illinois, Urbana-Champaign on October 14, 2002.

3. EcVA group, SantaFe Institute. "Evolving Cellular Automata With Genetic Algorithms." http://www.santafe.edu/projects/evca/Projects/evca.html

4. Eck, David J. "Cellular Automata and the Edge of Chaos." http://math.hws.edu/xJava/CA/

Thanks for help on the code to Chris Appuhn for helping me with illiSkel. Of course, thanks to the programmers of illiSkel, George Francis, Stuart Levy, Glenn Chappell, and Chris Hartman. Finally thanks again to Professor Francis for all the help he gave me.

Back to the main page.