display | more...

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 .

There is a better reason why one-dimensional automata are interesting than the Sierpinski triangle and the Rule-90 (90 is the decimal representation of 01011010) responsible for its creation. This reason is the Rule-110 (01101110). In the 1990's Matthew Cook, a research assistant of Stephen Wolfram proved that Rule-110 is (drumroll, please!) Turing-complete. That's right, folks, these eight extremely simple rules, combined with an infinite one-dimensional strip, form a universal Turing machine, capable of answering any answerable question and simulating the whole Universe, including every one of us with arbitrary precision, given the right input.

Before Rule-110 was found, the simpliest universal Turing machine required not 8, but 28 rules. It is possible, though, that an even simplier machine with 6 rules is possible.

Now behold the beauty, greatness and simplicity of the Rule-110.

Values at t:      111 110 101 100 011 010 001 000
                  --- --- --- --- --- --- --- ---
Value at t + 1:    0   1   1   0   1   1   1   0 

t = 1:                                         *
                                              **
                                             ***
                                            ** *
                                           *****
                                          **   *
                                         ***  **
                                        ** * ***
                                       ******* *
t = 10:                               **     ***
                                     ***    ** *
                                    ** *   *****
                                   *****  **   *
                                  **   * ***  **
                                 ***  **** * ***
                                ** * **  ***** *
                               ******** **   ***
                              **      ****  ** *
                             ***     **  * *****
t = 20:                     ** *    *** ****   *
                           *****   ** ***  *  **
                          **   *  ***** * ** ***
                         ***  ** **   ******** *
                        ** * ******  **      ***
                       *******    * ***     ** *
                      **     *   **** *    *****
                     ***    **  **  ***   **   *
                    ** *   *** *** ** *  ***  **
                   *****  ** *** ****** ** * ***
t = 30:           **   * ***** ***    ******** *
                 ***  ****   *** *   **      ***
                ** * **  *  ** ***  ***     ** *
               ******** ** ***** * ** *    *****
              **      ******   ********   **   *
             ***     **    *  **      *  ***  **
            ** *    ***   ** ***     ** ** * ***
           *****   ** *  ***** *    ********** *
          **   *  ***** **   ***   **        ***
         ***  ** **   ****  ** *  ***       ** *
t = 40: ** * ******  **  * ***** ** *      *****

I can go on an on, but if you really want to see a lot of generations, like a few billions, get Mathematica and try it yourself with different inputs.

Further watching: a MIT lecture by Stephen Wolfram, available for download at http://mitworld.mit.edu/video/149/ (fast forward to 46th minute for the discussion of Rule-110)

Log in or register to write something here or to contact authors.