Extras‎ > ‎

Rule 110


This Haskell file implements Rule 100.  Rule 110 is a cellular automaton rule
for a 1D cellular automaton.  

The state of the cellular automaton is a string that is infinite in both
directions and contains 0s and 1s.  Updating the state of the string consists
of replacing each value with a new value based on its context.  Patterns
"111", "100", and "000" result in the value "0" at the center, and all other
patterns result in the value "1" at their center.

We can't update an arbitrary infinite string in finite time, but the kinds of
strings we work with are zero except for a finite substring in the middle.

Let's start with a replacement rule that isn't quite right but gets most
of the job done.

> repl110 :: String -> String
> repl110 s | (length s < 3) = s
> repl110 s | take 3 s `elem` ["111","100","000"] = '0' : repl110 (tail s)
> repl110 s = '1' : repl110 (tail s)

That rule isn't quite right because it doesn't do the right thing at the ends
of the string.  We could write special case code for that, but that's a lot of work.
It's easier just to stick some zeros on both ends, perform the substitutions, and
then delete whatever is left.

> rule110 :: String -> String
> rule110 s = trim0s (repl110 ("000" ++ s ++ "000"))

To make this work, we need to write a function that trims the 0s off both ends
of the string.  First, let's write a function that trims 0s off the left end.

> drop0s :: String -> String
> drop0s ('0':s) = drop0s s
> drop0s s = s

To trim 0s off both ends, we just trim, reverse, trim again, and reverse again.
This is a common trick (albeit a bit inefficient).

> trim0s :: String -> String
> trim0s s = reverse (drop0s (reverse (drop0s s)))

There is a function called "iterate f start" in Haskell that generates an infinite list
obtained by applying the same function f again and again, first to the start value, then
to the result of that, etc.  With that, we can now easily look at what happens after many
applications of Rule 110:

> main = print ((iterate rule110 "1") !! 1000)