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:

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:

                             *
                            *
                           * *
                          *
                         * *
                        *   *
                       * * * *
                      *
                     * *
                    *   *
                   * * * *
                  *       *
                 * *     * *
                *   *   *   *
               * * * * * * * *
              *
             * *
            *   *
           * * * *
          *       *
         * *     * *
        *   *   *   *
       * * * * * * * *
      *               *
     * *             * *
    *   *           *   *
   * * * *         * * * *
  *       *       *       *
 * *     * *     * *     * *
*   *   *   *   *   *   *   *