e c a m e c h a n i c s
An automaton is a system designed to follow a pre-determined set of instructions or procedures, such as a ballerina on a music box or the elaborate procession of figurines around a clock tower. Computer-based automata use the computer to process the instructions and generally output the results to a screen or printer. Elementary cellular automota (eca) are one of the simplest computer-based automatons which generate complex behavior.
The study of Elementary Cellular Automaton began in the early 1950s when John von Neuman experimented with creating a fully self-replicating mechanism, one where the host created a replicate of itself and passed on the "intelligence" to create other replicates. John Conway took up the study in the 1970s with the creation of The Game of Life, a computer widget which played with ideas of organic growth and death. Stephen Wolfram pushed further with research into eca in the 1980s and 90s which culminated in his book A New Kind of Science published in 2002.
Cellular “games” fall into two groups. One group generally looks at how the cells interact with each other as the rules are applied. The Game of Life is a simulation that epitomizes these types of games. The other group, such as eca, investigate the output generated by the application of the rules where there is no interaction between the cells.
There are three components to eca. There is a grid of cells; there is the state of the cells at a given time; and there is the rule used to transform. The grid is usually made up of squares; each cell can be in one state a given time; and the rule looks at the state of the current cell and the states of a defined set of it’s neighbors and based on this information assigns a state to the cell at the next time step.
Eca are one dimensional. In pure form, there is an infinite row of cells and at each time step, the state of the cells change like a string of flashing Christmas lights. General practice, however, is to display the changing pattern in a two dimensional time-phase pattern where each time step is a new row. Traditionally these run from top to bottom or left to right.
Eca are unpredictable. While there is a formula (rule) to describe how an automoton runs, there are no formulae to predict the outcome at any specific time step. The only way to see what will happen is to run the automaton. In the end, many of the patterns are regular and predictable, but this can only be determined after the rule has been run. There are many complex patterns which defy formulation.
ECA are completely deterministic. The combination of seed condition and rule (see below) will always generate the same pattern of cell transitions.
In the classic eca the grid is made up of square cells. The cells can be one of two states generally represented by the terms “active” and “passive” or by the digits 1 and 0. Traditionally active / 1 state is black and the passive / 0 state is white. The states of the target cell, it’s left neighbor, and it’s right neighbor are used by the rule to determine the state of the target cell at the next time step. This three cell neighborhood is generally referred to as a wiring diagram and a specific group of cells is called a block.
In the example below, the target cell “T” is the one with the question mark with its current condition marked with a "C" and the neighbors with "L" and "R" -- note that this is a time-phase diagram.
| L | C | R | ||
| T | ||||
In this illustration, the state of the target cell will be determined by a rule where Left is Passive, Current is Passive, and Right is Active. The shorthand notation for this is Block 001. In a two-state, three-cell block automoton, there are eight possible combinations of the blocks ranging from 000 to 111. And to make things a little easier, blocks labeled using the decimal equivalent of the string of binary digits:
| 1 | 1 | 1 | Block 7: | ||||
| 1 | 1 | 0 | Block 6: | ||||
| 1 | 0 | 1 | Block 5: | ||||
| 1 | 0 | 0 | Block 4: | ||||
| 0 | 1 | 1 | Block 3: | ||||
| 0 | 1 | 0 | Block 2: | ||||
| 0 | 0 | 1 | Block 1: | ||||
| 0 | 0 | 0 | Block 0: |
What we don't know from this example is what will happen to the target cell at the next time step. Does Block 001 invoke an active cell or a passive cell? That is what is meant by constructing the rules -- determining whether a block, such as the Block 1, will turn the target cell active or passive. Rules, also called transition functions, are constructed by designating what the new cell state will be for each of the eight blocks such as this:
| 1 | 1 | 1 | Block 7: | 0 | |||
| 1 | 1 | 0 | Block 6: | 0 | |||
| 1 | 0 | 1 | Block 5: | 0 | |||
| 1 | 0 | 0 | Block 4: | 1 | |||
| 0 | 1 | 1 | Block 3: | 1 | |||
| 0 | 1 | 0 | Block 2: | 1 | |||
| 0 | 0 | 1 | Block 1: | 1 | |||
| 0 | 0 | 0 | Block 0: | 0 |
Labels for rules follow the same pattern. The transition state of each block forms an eight digit binary number ranging from 00000000 = 0 to 11111111 = 255, for a total of 256 possible rules. Convention is to use three digit labels for rules, so 0 becomes 000. The example above is the definition for Rule 030 (00011110). In this case, if the current cell is active and its two neighbors are also active, its new state will be determined by Block 7 and it’s new state will be passive.
Rules Definitions: a chart of all the rule defintions.
Running: First a seed row with active and passive cells is created. The simplest is a single active cell neighbored by passive cells, referred to as a single seed or 1-seed. Select a rule where all the transition state of all the blocks has been decided, then run the automaton.
ECA are usually displayed in a time-phase diagram. While ECA are one dimensional and erase the past state when the new state is determined at the next time step, the practice is to display the new state as a new row below the predecessor or as a new column to the right of the predecessor. This way the history is preserved and the pattern over time can be examined. Below is the time-phase diagram for the first 31 time steps of Rule 030.
Time-phase pattern of 31 time steps for Rule 030
And here is an image chart of all the rules run for fifteen time steps.
Extending
There's nothing preventing an increase in the size of the block neighborhood or the number of states in an ECA, however the numbers become daunting.
- If the block neighborhood increases from 3 cells to 5 cells (the current cell plus 2 neighbors on either side), the number of block combinations increases to 32 and the number of rules and patterns increases to 4,294,967,296 (2^32)
- If the number of states increases from 2 to 3 (low, medium, high for instance), then the number of 3-cell block combinations increases to 27 and the number of rules and patterns increases to 7625,597,485,000+ (3^27). Even if the neighborhood is reduced to only 2 cells (only the 2 neighbor cells), there are 9 block combinations and 19,683 rules (3^9)
And finally, there is nothing saying that the "wiring diagram" defining a neighborhood must be limited to the current cell and its neighbors. Wiring diagrams can include cells from previous time steps, don't have to include the current cell, and can be based on probabilities rather than determined outcomes.
References