Simple rules can generate complex behaviour. I’m reading A New Kind of Science by Stephen Wolfram. A key idea of the book is that a simple rule, applied iteratively, can generate complex behaviour. The difference between Rules 222, 90, and 30 are trivial, yet they generate vastly different results.

In this post we explore the principles and implement the Elementary Cellular Automata system in F#.

Here’s a 7 x 4 grid. The dots represent Empty cells, the X represent Full cells. All of our grids start with a single Full cell in the middle of the top row.

...X...
.......
.......
.......

We then define a rule. A rule is a function which decides whether a single cell is Empty or Full. This rule function takes values of the 3 cells from the row directly above, corresponding to the cells above and to the left (1), directly above (2), and above and to the right (3). We visualise this below. The cell we are trying to calculate is ?.

123....        .123...        ..123..        ...123.        ....123
.?.....        ..?....        ...?...        ....?..        .....?.
.......        .......        .......        .......        .......
.......        .......        .......        .......        .......

The same rule is applied row after row. The rule is not applied to cells in the far left column and far right columns. These cells will always remain Empty. We’ll look at the naming convention of rules later on, but for now here’s one example.

Below is Rule 222. The first pattern is saying that if cells 1, 2, and 3 are Full, then the cell ? will be Full. And so on, for every possible combination of those 3 cells.

XXX    XX.    X.X    X..    .XX    .X.    ..X    ...
 X      X      .      X      X      X      X      .

This system of rules is as simple as we can get. Each cell can only have two possible states, and the value of the next cell only depends on it’s neighbours.

We just described the Celluar Automata domain. Let’s implement it in code.

• A Cell can be either Empty or Full.
• The Rule type is a function which takes 3 Cells and returns the value of a single Cell.

// A Cell is either Empty or Full
type Cell = Empty | Full

// Rules are functions which take in the values of 3 Cells, and return a single Cell value
type Rule = (Cell * Cell * Cell) -> Cell

// Rule 222 implemented in code
let rule222: Rule = function 
    | (Full, Full, Full) -> Full
    | (Full, Full, Empty) -> Full
    | (Full, Empty, Full) -> Empty
    | (Full, Empty, Empty) -> Full
    | (Empty, Full, Full) -> Full
    | (Empty, Full, Empty) -> Full
    | (Empty, Empty, Full) -> Full
    | (Empty, Empty, Empty) -> Empty

We’ve just described the Cellular Automata system in its entirety. Patterns and complexity emerge from just those rules. The rules by themselves are abstract and we need to apply them somehow. Here we apply the rule on a simple grid. But the same rule could be applied to any other surface - a 3D surface, mobius strip, or grid where the values wrap around.

Onto the implementing the system on a grid. Let’s start off by generating the first row.

let generateStandardFirstRow (width: int) =
    
    if width % 2 = 0 then invalidArg "width" (sprintf "Value must be an odd number. Value passed was %d." width)
    
    Seq.init width (function
        | n when n = (width / 2) -> Full
        | _ -> Empty
    )

So

generateStandardFirstRow 7

Gives us

Empty Empty Empty Full Empty Empty Empty

In order to generate the next row we only need to know the row before it. We take the previous row and apply Seq.windowed. This splits the row of Cells into groups of 3 Cells, which we need in order to calculate the next value.

Recall that our rule requires 3 cells in order to calculate the next value. This is the cell above and to the left, the cell directly above, and the cell above and to the right. This is a problem for the far left and far right columns of the grid. They only have 2 of the 3 cells required. To get around this we enforce a rule that the left column and right column will always remain Empty.

let generateNextRow (rule: Rule) (row: Cell seq) =
    let generatedCells =
        row
        |> Seq.windowed 3
        |> Seq.map (fun v ->
            rule (v.[0], v.[1], v.[2])
        )
        
    // the first and last Cells of each row are Empty since we didn't generate a value for them above
    seq {
        yield Empty
        yield! generatedCells
        yield Empty
    }

Now let’s write a function which generates row after row. Sequences in F# are lazily evaluated. They’re the C# IEnumerable type under the hood. By treating everything as a sequence we’re essentially defining the rules as to how the grid will be generated.

Seq.unfold iteratively applies the Rule to whatever the previous row was, collecting results. Notice we don’t specify how many rows to generate, that’s up to the caller of this function.

let generatePattern (rule: Rule) (firstRow: Cell seq) = 
    firstRow
    |> Seq.unfold (fun row ->
        Some(row, (generateNextRow rule row))
        )

Now we can generate the grid!

let firstRow = generateStandardFirstRow 101
let rows = generatePattern rule222 firstRow |> Seq.take 10

But we want to visualise it. Here’s a basic ASCII renderer.

let drawCell = function
| Full -> "X"
| Empty -> "."

/// Render the grid to an ASCII string
let drawGrid (grid: Cell seq seq) =
    grid
    |> Seq.map (fun row ->
        row
        |> Seq.map drawCell
        |> String.concat ""
    )
    |> String.concat "\n"
    
drawGrid rows

..................................................X..................................................
.................................................XXX.................................................
................................................XXXXX................................................
...............................................XXXXXXX...............................................
..............................................XXXXXXXXX..............................................
.............................................XXXXXXXXXXX.............................................
............................................XXXXXXXXXXXXX............................................
...........................................XXXXXXXXXXXXXXX...........................................
..........................................XXXXXXXXXXXXXXXXX..........................................
.........................................XXXXXXXXXXXXXXXXXXX.........................................

Our algorithm works! Let’s experiment with other rules.

let rule90: Rule = function
    | (Full, Full, Full) -> Empty
    | (Full, Full, Empty) -> Full
    | (Full, Empty, Full) -> Empty
    | (Full, Empty, Empty) -> Full
    | (Empty, Full, Full) -> Full
    | (Empty, Full, Empty) -> Empty
    | (Empty, Empty, Full) -> Full
    | (Empty, Empty, Empty) -> Empty
    
let firstRow = generateStandardFirstRow 101
let rows = generatePattern rule90 firstRow |> Seq.take 50
let arrayOfRows = rows |> Seq.toArray
    
drawGrid rows

..................................................X..................................................
.................................................X.X.................................................
................................................X...X................................................
...............................................X.X.X.X...............................................
..............................................X.......X..............................................
.............................................X.X.....X.X.............................................
............................................X...X...X...X............................................
...........................................X.X.X.X.X.X.X.X...........................................
..........................................X...............X..........................................
.........................................X.X.............X.X.........................................
........................................X...X...........X...X........................................
.......................................X.X.X.X.........X.X.X.X.......................................
......................................X.......X.......X.......X......................................
.....................................X.X.....X.X.....X.X.....X.X.....................................
....................................X...X...X...X...X...X...X...X....................................
...................................X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X...................................
..................................X...............................X..................................
.................................X.X.............................X.X.................................
................................X...X...........................X...X................................
...............................X.X.X.X.........................X.X.X.X...............................
..............................X.......X.......................X.......X..............................
.............................X.X.....X.X.....................X.X.....X.X.............................
............................X...X...X...X...................X...X...X...X............................
...........................X.X.X.X.X.X.X.X.................X.X.X.X.X.X.X.X...........................
..........................X...............X...............X...............X..........................
.........................X.X.............X.X.............X.X.............X.X.........................
........................X...X...........X...X...........X...X...........X...X........................
.......................X.X.X.X.........X.X.X.X.........X.X.X.X.........X.X.X.X.......................
......................X.......X.......X.......X.......X.......X.......X.......X......................
.....................X.X.....X.X.....X.X.....X.X.....X.X.....X.X.....X.X.....X.X.....................
....................X...X...X...X...X...X...X...X...X...X...X...X...X...X...X...X....................
...................X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X...................
..................X...............................................................X..................
.................X.X.............................................................X.X.................
................X...X...........................................................X...X................
...............X.X.X.X.........................................................X.X.X.X...............
..............X.......X.......................................................X.......X..............
.............X.X.....X.X.....................................................X.X.....X.X.............
............X...X...X...X...................................................X...X...X...X............
...........X.X.X.X.X.X.X.X.................................................X.X.X.X.X.X.X.X...........
..........X...............X...............................................X...............X..........
.........X.X.............X.X.............................................X.X.............X.X.........
........X...X...........X...X...........................................X...X...........X...X........
.......X.X.X.X.........X.X.X.X.........................................X.X.X.X.........X.X.X.X.......
......X.......X.......X.......X.......................................X.......X.......X.......X......
.....X.X.....X.X.....X.X.....X.X.....................................X.X.....X.X.....X.X.....X.X.....
....X...X...X...X...X...X...X...X...................................X...X...X...X...X...X...X...X....
...X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.................................X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X...
..X...............................X...............................X...............................X..
.X.X.............................X.X.............................X.X.............................X.X.

Here’s a graphical renderer for the same grid implementation.

#r "nuget:SixLabors.ImageSharp"
open SixLabors.ImageSharp;
open SixLabors.ImageSharp.PixelFormats;

let cols = 501;
let rows = 250;

let image = new Image<Rgba32>(cols, rows);
let white = new Rgba32(255F, 255F, 100F, 1F);
let black = new Rgba32(0f, 0f, 0f, 1F);

let grid =
    generateStandardFirstRow cols
    |> generatePattern rule90
    |> Seq.take rows

let withIndexes x = x |> Seq.mapi (fun index item -> (index, item))

for (rowIndex, row) in withIndexes grid do

    for (cellIndex, cell) in withIndexes row do

        let colour =
            match cell with
            | Full -> black
            | Empty -> white

        image.[cellIndex, rowIndex] <- colour

image.Save("rule90.png")
image

So far we’ve looked at a few specific rules. But how many rules are there and can we generate them dynamically? We’ve hardcoded rules as functions

let rule222: Rule = function 
    | (Full, Full, Full) -> Full
    | (Full, Full, Empty) -> Full
    | (Full, Empty, Full) -> Empty
    | (Full, Empty, Empty) -> Full
    | (Empty, Full, Full) -> Full
    | (Empty, Full, Empty) -> Full
    | (Empty, Empty, Full) -> Full
    | (Empty, Empty, Empty) -> Empty

All rules must return a value for each pattern. Because the patterns are static we could think of identifying rules by what they return for each case, what is on the right hand side of the ->. We could think of the above rule as:

(Full, Full, Empty, Full, Full, Full, Full, Empty)

So a rule is a identified as a list of 8 boolean values. If we use binary to represent this we need a byte (8 bits) of information. This means there are 2^8 rules, giving us 256 possible rules in the Wolfram automata system.

So there are only 256 rules in this Wolfram automata system, and the rule’s name determines what it returns. This is illustrated below. The binary pattern maps 1 to Full and 0 to Empty.

let generateRule(ruleNumber: byte) = 
    let ruleBitString = Convert.ToString(ruleNumber, 2).PadLeft(8, '0');

    let patternToBitStringIndex = function 
        | (Full, Full, Full) -> 0
        | (Full, Full, Empty) -> 1
        | (Full, Empty, Full) -> 2
        | (Full, Empty, Empty) -> 3
        | (Empty, Full, Full) -> 4
        | (Empty, Full, Empty) -> 5
        | (Empty, Empty, Full) -> 6
        | (Empty, Empty, Empty) -> 7

    let ruleFn (cells: Cell * Cell * Cell) = 
        let bitIndex = patternToBitStringIndex cells

        match ruleBitString.[bitIndex] with
        | '0' -> Empty
        | '1' -> Full
        | _ -> raise (Exception("Unexpected input"))
        
    ruleFn
    
let rule254 = generateRule(254uy)
rule254 (Empty, Empty, Empty)

And there we have it, our rule function generator. Here are some interesting rules.

F# is a perfect language to implement Cellular Automata. The type system allows us to exactly model the domain, and sequences make the implementation elegant. There’s no confusing cruft in our code. From this basic implementation you can easily make modifications to the Cellular Automata system. Here’s a few fun things to try out. What if …

• The first row was randomly generated
• Cells could have a value other than Full or Empty?
• Rules incorporated some degree of randomness when deciding the value of the next cell?
• The grid was hexagonal rather than square based?

The Jupyter Notebook and an F# project containing the code for this post is available here.

This is part of F# Advent Calendar 2020. Check out other posts here.

• Cellular Automata Los Alamos Science (1983) - Stephen Wolfram
• Oh My Gosh, It’s Covered in Rule 30s! - Stephen Wolfram
• Stephen Wolfram on the Lex Fridman podcast
  • Abridged clip where they discuss Cellular Automata and Rule 30