Rule 110 in Haskell

Because WordPress.com does not always render MarkDown properly, you may need to read a copy of this post here.


One of the things I learned by reading AIM 239 is the Game of Life and Cellular Automata. One particular kind of one dimensional cellular automata, Rule 110 popped by my twitter stream the other day, so I thought I could try and code it with the minimal Haskell subset that I can handle.

Rule 110 is special because it is proven to be able to simulate a Turing machine. Head over to its Wikipedia page if you want to learn more about the proof and the interesting story around it.

Rule 110 starts with a string of zeros and ones and a transition table that decides the next state of the automaton. If you put each line of the strings after the other, interesting patterns can emerge. Let’s see the transition state:

Current pattern 111 110 101 100 011 010 001 000
New state for center cell 0 1 1 0 1 1 1 0

If you look closely, you can use a list of eight digits and its index in order to encode the above state transitions:

rule110 = [
  0, -- ((0,0,0), 0)
  1, -- ((0,0,1), 1)
  1, -- ((0,1,0), 1)
  1, -- ((0,1,1), 1)
  0, -- ((1,0,0), 0)
  1, -- ((1,0,1), 1)
  1, -- ((1,1,0), 1)
  0  -- ((1,1,1), 0)
  ] :: [Int]

But what about the transitions of the leftmost and rightmost digit you might think. Let’s assume that their missing neighbor is zero. Therefore, given an initial state and a rule that governs the transitions, we may calculate the next state with:

nextState :: [Int] -> [Int] -> [Int]
nextState state rule =
  [ rule !! x |
    let t = [0] ++ state ++ [0],
    i <- [1..(length(t)-2)],
    let x = (t !! (i-1)) * 4 + (t !! i) * 2 + (t !! (i+1))
  ]

-- construct an infinite sequence of next states
sequenceState :: [Int] -> [Int] -> [[Int]]
sequenceState state rule =
  [state] ++ sequenceState (nextState state rule) rule

Example:

*Main> state = [0,1,1,0]
*Main> nextState state rule110
[1,1,1,0]

One of the most interesting patterns occurs when we begin with the right most digit being 1 and all the rest being zeros:

*Main> state = [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1] :: [Int]
*Main> x = take 30 $ sequenceState state rule110
*Main> showState x
                             *
                            **
                           ***
                          ** *
                         *****
                        **   *
                       ***  **
                      ** * ***
                     ******* *
                    **     ***
                   ***    ** *
                  ** *   *****
                 *****  **   *
                **   * ***  **
               ***  **** * ***
              ** * **  ***** *
             ******** **   ***
            **      ****  ** *
           ***     **  * *****
          ** *    *** ****   *
         *****   ** ***  *  **
        **   *  ***** * ** ***
       ***  ** **   ******** *
      ** * ******  **      ***
     *******    * ***     ** *
    **     *   **** *    *****
   ***    **  **  ***   **   *
  ** *   *** *** ** *  ***  **
 *****  ** *** ****** ** * ***
**   * ***** ***    ******** *
*Main>

The output was somehow pretty printed:

showState [] = return ()
showState state = do
  -- putStrLn $ show (state !! 0)
  putStrLn $ [ c | d <- (state !! 0), let c = if d == 0 then ' ' else '*' ]
  showState $ tail state

I wish I can find time and play more with cellular automata. I kind of find a day every five years or so.

Update: Here is a pattern using Rule 90:

                             *
                            *
                           * *
                          *
                         * *
                        *   *
                       * * * *
                      *
                     * *
                    *   *
                   * * * *
                  *       *
                 * *     * *
                *   *   *   *
               * * * * * * * *
              *
             * *
            *   *
           * * * *
          *       *
         * *     * *
        *   *   *   *
       * * * * * * * *
      *               *
     * *             * *
    *   *           *   *
   * * * *         * * * *
  *       *       *       *
 * *     * *     * *     * *
*   *   *   *   *   *   *   *
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s