| NSC module > Cellular Automata applet |
A conventional one dimensional cellular automata is represented by a row of cells which can either be 1 or 0 (black or white etc). The automata has a set of rules which determine what value a cell will take on in the next state depending on its current value and the values of the two cells either side of it. These states can then be displayed with each new one below the current one, to see how they evolve over time.
Each possible current state of a cell and its neighbors needs to have a value assigned to it which the cell will take on in the next state. For example, each cell x might follow these transitions, where the 3 bit numbers are the current state of the left neighbor, cell x, and the right neighbor, and the 1 bit number is the next state of cell x:
111 -> 0 110 -> 0 101 -> 0 100 -> 1 011 -> 0 010 -> 0 001 -> 1 000 -> 0
This is referred to as rule 18 because running the next states in order gives the binary representation for 18 - 01001000. Since this is an 8 bit binary number, there are 256 possible rules.
Extensions for one dimensional cellular automata include increasing the number of neighbors each side of the cell that the automaton looks at to decide the next state, or looking at previous states as well as the current state to decide the next state of each cell. For example, for 2 neighbors instead of 1, rules would look like this:
11111 -> 1 11110 -> 0 11101 -> 0 11100 -> 1 11011 -> 0 ...
The binary strings representing the current state of a cell and 2 neighbors either side of it is obviously a 5 bit number instead of the usual 3 bit number. This means there are now 32 values to assign giving a 32 bit string of next values. Since there are now 32 bits in the next values binary string, there are 2^32 = 4294967296(!) possible different rules.
Taking into account 1 previous state as well as the current one (a depth of 2), with the standard 1 neighbor either side, gives transitions looking like this, where the leftmost 3 bits are the values of the left neighbor, the cell in question, and the right neighbor in the current state, and the rightmost 3 bits are those values in the previous state:
111111 -> 0 111110 -> 1 ...
In an automaton like this, there are 2^(2^6) = 2^64 = 1.8x10^19 rules (a lot). You can imagine how many rules there are for automata with a larger depth AND a larger width of neighbors.
One other extension is using a larger base instead of just base 2 (binary). For example, base 10 (decimal) would mean each cell could have any value from 0 to 9. With conventional width and depth, transitions would look like this:
999 -> 4 998 -> 7 997 -> 0 ... 001 -> 8 000 -> 3
An automaton of this scope would have 10^1000 possible rules.
In the applet there is a drop down menu for configuring the automata which is initially set to make a standard one dimensional automata with base 2 (binary) cells, taking into account 1 neighbor either side, and a depth of 1 (only taking into account the current state). With these settings there are 256 possible rules as explained above, so the rule box will go from 0 to 255. Changing the base, neighbors, or depth will increase the number of possible rules and the rule box will therefore allow larger numbers. The grid shows current and previous states of the automaton, the bottom row is the current state with the history of states above it. You can draw on the grid to create your own starting states - values are represented by different shades of green, clicking on a square will increase its value by 1 or set it to 0 if it is already at the maximum value allowed by the chosen base. Alternatively you can simply randomise the grid or clear it with the relevant buttons. Pressing "go" will start the states scrolling up the screen with each new state created in the bottom row, and the speed can be adjusted with the slider (although this may be limited by the speed of your computer). Changing the settings while the automaton is running will require you to stop and start it again for the changes to take effect.