What a Cellular Automaton Is
Over and over again we will see the same kind of thing: that even though the underlying rules for a system are simple, and even though the system is started from simple initial conditions, the behavior that the system shows can nevertheless be highly complex. And I will argue that it is this basic phenomenon that is ultimately responsible for most of the complexity that we see in nature.
A New Kind of Science, p. 28
A Cellular Automaton is a rule-based growth "game". The game board is a grid that, ideally, is made up of an infinite number of cells. At the beginning of the game, rules are established which determine how the cells will behave. Once the rules have be set, one or more cells in the grid (the seed cells) are made active and from there, the rules are applied simulatneously to the cells, and then again and again. (See this Wikipedia page for more.)
Cellular games fall into two groups. One group generally looks at how the cells interact with each other as the rules are applied. The second group focuses more on the patterns generated by the application of rules. The Game of Life, developed in 1970 by mathmetician John Conway, is a simulation that epitomizes the games focused on the interaction between cells. There are many YouTube videos about the Game of Life. This one, from a Stephen Hawkings BBC special, is an excellent visualization of the rules. This one, Life in Life, is a Game of Life simulation running its course.
The other type of game, the one focused more on patterns, is what Wolfram wrote about and what I have studied. These are called Elementary Cellular Automata. In the classic elementary game, the rules which determine whether any particular cell is active (black) or passive (white) are based on the state of that cell's predecessor and the predecessor's neighbors to the left and right. In the example below, the target cell is the one with the question mark with its predecessor marked with a "P" and the neighbors with "L" and "R".
| L | P | R | |||||||
| ?? | |||||||||
The state of the target cell in the example above will be determined by the rule of Left is Passive, Predecessor is Passive, and Right is Active. The shorthand notation for this rule is 001. What we don't know from the example above is what will happen to the target cell? Does 001 rule invoke an active cell or a passive one? That is what is meant by setting the rules -- determining whether a rule, such as the 001 rule, will turn the target cell active or passive.
All in all, there are eight rules in the classic elementary game which cover every combination of the Left, Predecessor, and Right being either active or passive. Here's a chart showing the eight rules:
| Rule 7: | 1 | 1 | 1 | |||||
| Rule 6: | 1 | 1 | 0 | |||||
| Rule 5: | 1 | 0 | 1 | |||||
| Rule 4: | 1 | 0 | 0 | |||||
| Rule 3: | 0 | 1 | 1 | |||||
| Rule 2: | 0 | 1 | 0 | |||||
| Rule 1: | 0 | 0 | 1 | |||||
| Rule 0: | 0 | 0 | 0 |
A quick side note before diving in futher. Most everything in elementary cellular automata is labeled using the decimal equivalent of the binary number formed the 0s and 1s used to describe the active and passive states of cells. In the chart above, the topmost rule is 111 and 111 in binary converts to 7 in decimal numbers. Also note the numbering throughout will start with 0, and not 1. This can be a little discombobulating when there are eight rules, but the topmost one is Rule 7.
We've established that there are eight possible rules to the cellular automaton game. And, in our example above, we have identified that the target cell is being affected by Rule 1 (the 001 rule), but we have no idea whether it will become active or passive. The next step is to specify how a particular rule will impact the target cell. Actually, the next step is to specify how all eight rules will respond, because there is a chance that each rule will be called upon in the running of a particular game.
Going back to the rules chart, we can start specifying which rules will turn target cells active and which will turn them passive. In the example below, the column to the right is used to indicate that Rules 7, 4, 3, and 1 will turn the target into an active cell and Rules 6, 5, 2, and 0 will turn it into a passive one:
| Rule 7: | 1 | 1 | 1 | 1 | ||||
| Rule 6: | 1 | 1 | 0 | 0 | ||||
| Rule 5: | 1 | 0 | 1 | 0 | ||||
| Rule 4: | 1 | 0 | 0 | 1 | ||||
| Rule 3: | 0 | 1 | 1 | 1 | ||||
| Rule 2: | 0 | 1 | 0 | 0 | ||||
| Rule 1: | 0 | 0 | 1 | 1 | ||||
| Rule 0: | 0 | 0 | 0 | 0 |
In total, there are 256 possible combinations, or sets of rules, of the eight rules turning the target into an active or passive cell. As with the rules, these rulesets are labeled by converting the chain of 1s and 0s into its decimal equivalent. In the above example, the chain is 10011010 which, as a binary number, converts to 154 decimal. Therefore, the ruleset specified above is known as Ruleset 154.
The last step in setting up an elementary game is to identify the starting, or seed, cell or cells. In the classic game, there is only a single seed cell. Once the seed cell has been turned "on" and a ruleset specified, the rules of the game are applied automatically (hence "automaton"), row by row, to determine if the cells in each subsequent row of the grid should be passive (white) or active (black).
That's pretty much it. Simple rules, running automatically, determining whether cells in a grid are active or passive. And while many, if not most, of the patterns are pretty boring or even non-existent, there are certain rulesets which generate highly complicated patterns. The question is how do they do it, and what does it mean that a rudimentary technique can generate a sophisticated solution?
To see snapshots of all 256 patterns, click here or on the All the Rules link in the list of illlustrations.
Home
Beginnings & the Use of Color
