As with any cellular automaton, this variation is composed of a "universe" which contains the current information at any time t and the rules which specify how that information will be transformed at t + 1. Von Neumann and Conway both studied two-dimensional cellular automata, which have a universe composed of a two-dimensional field of bits (or integers, etc.). These are remarkable for the patterns they may generate in each frame, easily viewable as separate entities. Viewing the evolution of one over its entire history is problematic, however, as you can only look at the frames one or two at a time. One-dimensional cellular automata do not have this problem because their universe is a line of values, called sites. Hence, to display the evolution of this kind of automaton, you need only to look at a stack of these lines over time.
Rules may be examined in terms of k and r, where k is the number of possible states a site may take, and r is the distance in sites that are taken into consideration. Thus, a binary automaton that looks at itself and its two neighbors to decide its next state has k = 2 and r = 1.
The number of possible rules to use for computation with a given k and r are kk2r+1, a number that becomes huge for even small values of either. For the elementary k = 2 and r = 1 automatons, there are 256 possible rules by which the automaton can evolve. For example, one rule might be to take the XOR of the surrounding two values at t to decide a site's value at t + 1. This rule, viewed as a table, would look like:
Values at t: 111 110 101 100 011 010 001 000
--- --- --- --- --- --- --- ---
Value at t + 1: 0 1 0 1 1 0 1 0
This brute-force way of expressing the rules is powerful because it can create rules that are not based on any mathematical formula (like XOR). In other words, a completely arbitrary rule can be expressed as a table in the above form, regardless of its derivation. This expression of rules is also great because it lends itself to enumerating the whole set of rules, so they can each be easily and uniquely identified. To get the "rule number" of any k = 2 and r = 1 one-dimensional cellular automaton, just convert the Value at t + 1: fields into a single integer, like 01011010 from above. Then, convert the integer to base 10, so the above is rule number 90 (010110102 = 9010).
As an example of why one-dimensional automata are interesting, here's a nice fractal that is generated from a seed value of a single site at t = 1, using rule 90 from above. It is the Sierpinski triangle, also known as the odd values of Pascal's triangle.
t = 1: *
* *
* *
* * * *
* *
* * * *
* * * *
* * * * * * * *
* *
t = 10: * * * *
* * * *
* * * * * * * *
* * * *
* * * * * * * *
* * * * * * * *
* * * * * * * * * * * * * * * *
* *
* * * *
* * * *
t = 20: * * * * * * * *
And so forth, but my hands are getting tired.
I made a script to display rule 110 mentioned below as well as any others you might be curious about; try it at http://www.postreal.org/onedca .
| 
