For quite some time, I’ve wanted to write some Python code to implement and elementary cellular automaton. In particular, I wanted to “investigate” (play around with) the famous Rule 110, which is known to be Turing complete.

Despite the name, this has nothing to do with cellphones. It’s a 1D variation on the well-known 2D Game of Life designed by British mathematician John Conway. [See the John Conway’s Life and Life With Class posts for Python versions]

Note: The code here turned out to be not quite right. Please see the follow-up post, Cellular Automaton Redux, for an improved version.

The end goal is generating images like this:

Which is the result of running Rule 110 for 500 iterations starting with the usual initial single row with one non-blank cell (the top row in the image above, a single pixel). Each iteration produces a new row below it.

A row is a list of bits, zeros (or blanks) and ones (non-blanks). The default starting row has a single non-blank cell with all others presumed blank. In the Python code, we’ll use a list populated with zeros and ones for easy handling.

Rule 110 is so named because 110 in binary is 01101110, and that string of eight bits specifies the rule. Each bit position has an index number, from 0 (right-most or least-significant bit) to 7 (left-most or most-significant bit). These index numbers, expressed in binary, range from 000 to 111.

Note that this eight-bit protocol means rules range from 0 to a max of 255.

Here’s a simple bit of code illustrating how a rule number converts to a set of eight index codes and resulting output:

We use an f-string to convert the rule number into binary (line #4) [see Simple Python Tricks #8 and Simple Python Tricks #15 for an exploration into formatted strings].

The for loop (lines #6 to #8) prints each rule bit on a separate line starting with the bit index number in decimal and binary followed by the output bit.

When run (with the Rule 110 default), this prints:

0 [000]: 0
1 [001]: 1
2 [010]: 1
3 [011]: 1
4 [100]: 0
5 [101]: 1
6 [110]: 1
7 [111]: 0

To see how this works, let’s go step-by-step over how the automaton generates a new row given the default starting row consisting of just one non-blank cell (images run left-to-right, top-to-bottom):

For simplicity, we pad the ends of the row with three blank cells. This makes it easier for the algorithm to scan the row. If the row had only one cell (or only two), it would need handle partial triplets. Padding allows it to always see triplets.

The algorithm starts (upper left) with the left-most three cells, which are 0-0-0. Rule 110 specifies a 0 output in this case, and this is plugged into the center cell (relative to the triplet) in the new row below. The next triplet (upper center) holds a 0-0-1 pattern, and the output of that is a 1. Then we have a 0-1-0 pattern (upper right) for which the output is another 1.

Next is a 1-0-0 pattern — output 0 — and finally the trailing 0-0-0 pattern, which outputs a final 0. We fill in the leading and trailing cells with a 0. (Or just initialize new rows to all zeros.)

To pad rows, we use this simple expand_row function:

Two while loops (lines #5 to #7 and #9 to #11) ensure three leading and trailing blanks. The function alters the passed list and for convenience also returns it.

Lines #17 to #30 test the function. When run, this prints:

[0, 0, 0, 1, 0, 0, 0]
[0, 0, 0, 1, 0, 0, 0]
[0, 0, 0, 1, 0, 0, 0]
[0, 0, 0, 1, 0, 0, 0]
[0, 0, 0, 0, 1, 0, 0, 0]
[0, 0, 0, 1, 0, 0, 0]
[0, 0, 0, 1, 0, 0, 0]
[0, 0, 0, 1, 0, 0, 0]
[0, 0, 0, 1, 0, 0, 0, 0]
[0, 0, 0, 1, 0, 0, 0]
[0, 0, 0, 1, 0, 0, 0]
[0, 0, 0, 1, 0, 0, 0]
[0, 0, 0, 0, 1, 0, 0, 0, 0]

Which is the expected output.

While it would be possible to hard-code all 256 rules, the protocol for converting an integer (from 0 to 255) into a rule allows us to generate rules on the fly with a generate_rule function:

Line #5 ensures a valid integer. Line #8 converts the number into an eight-bit string. Line #11 converts the string into a list of 0s and 1s.

Lastly, line #14 builds and returns a dictionary with bit indexes for keys and the corresponding output as the value (the return expression here is a dict comprehension).

Lines #16 to #22 exercise the function. The output is identical to that shown for the first code fragment above.

With these two helper functions, we’re ready to implement the automaton:

The function is long but not complicated. Line #12 ensures the starting row has leading and trailing padding. Line #17 creates an output buffer for generated rows and initializes it with the starting row. The function eventually returns this list of lists after generating size new rows.

Line #20 generates the rule dictionary from the passed rule number.

The row-generation outer for loop (lines #22 to #45) starts by creating a new row of zeros (line #26). The inner for loop (lines #28 to #38) iterates over the current row (minus two because the last index we need is row[-2] — see the bottom center in the illustration above; the last index is 5 for a row length of 7).

Line #32 extracts the triplet from the row, converts the zeros and ones to string versions, and joins them to form the dictionary key (i.e. “000” to “111”). Line #35 uses the key to get the output value from the rule dictionary. Line #38 plugs the output value into the triplet center position in the new row.

Once the inner loop finishes, we pad the new row and make it the current row (line #42). Lastly, we append this new row to the list of rows (line #45).

Lines #47 to #56 determine if we’re writing rows to the screen or a text file. These lines also allow insertion of the rule number into the filename (lines #51 to #53).

Line #59 iterates through the rows to convert them to string versions. Lines #61 to #73 write the output. The last line of the function (line #76) returns the list of row lists.

Lines #78 to #84 test the run_automata function. Because fname defaults to a filename, the test writes the output to C:\demo\hcc\python\automata.out. The for loop (lines #82 to #84) displays the rows.

When run (with the defaults), this prints:

Run automata with rule 110 (20 rows)

Initial row: 0001000

wrote: C:\demo\hcc\python\automata.out

[0,0,0,1,0,0,0]
[0,0,0,1,1,0,0,0]
[0,0,0,1,1,1,0,0,0]
[0,0,0,1,1,0,1,0,0,0]
[0,0,0,1,1,1,1,1,0,0,0]
[0,0,0,1,1,0,0,0,1,0,0,0]
[0,0,0,1,1,1,0,0,1,1,0,0,0]
[0,0,0,1,1,0,1,0,1,1,1,0,0,0]
[0,0,0,1,1,1,1,1,1,1,0,1,0,0,0]
[0,0,0,1,1,0,0,0,0,0,1,1,1,0,0,0]
[0,0,0,1,1,1,0,0,0,0,1,1,0,1,0,0,0]
[0,0,0,1,1,0,1,0,0,0,1,1,1,1,1,0,0,0]
[0,0,0,1,1,1,1,1,0,0,1,1,0,0,0,1,0,0,0]
[0,0,0,1,1,0,0,0,1,0,1,1,1,0,0,1,1,0,0,0]
[0,0,0,1,1,1,0,0,1,1,1,1,0,1,0,1,1,1,0,0,0]
[0,0,0,1,1,0,1,0,1,1,0,0,1,1,1,1,1,0,1,0,0,0]
[0,0,0,1,1,1,1,1,1,1,1,0,1,1,0,0,0,1,1,1,0,0,0]
[0,0,0,1,1,0,0,0,0,0,0,1,1,1,1,0,0,1,1,0,1,0,0,0]
[0,0,0,1,1,1,0,0,0,0,0,1,1,0,0,1,0,1,1,1,1,1,0,0,0]
[0,0,0,1,1,0,1,0,0,0,0,1,1,1,0,1,1,1,1,0,0,0,1,0,0,0]
[0,0,0,1,1,1,1,1,0,0,0,1,1,0,1,1,1,0,0,1,0,0,1,1,0,0,0]

(Spaces in the output removed to reduce width)

The output file looks like this:

   #   
   ##   
   ###   
   ## #   
   #####   
   ##   #   
   ###  ##   
   ## # ###   
   ####### #   
   ##     ###   
   ###    ## #   
   ## #   #####   
   #####  ##   #   
   ##   # ###  ##   
   ###  #### # ###   
   ## # ##  ##### #   
   ######## ##   ###   
   ##      ####  ## #   
   ###     ##  # #####   
   ## #    ### ####   #   
   #####   ## ###  #  ##   

Neither the displayed output nor the text file give us the kind of display we’d like to see. We need an image file like the one at the beginning of this post.

To do this, we’ll use the Pillow library — formerly the Python Imaging Library (PIL). [To install the library, see Basic Installation from the Pillow docs.]

Here’s our image generation function:

We start (lines #8 to #10) by defining some constants: the background color, the foreground color (the color of non-blank cells), and the image margins. Lines #12 to #15 calculate the image size based on the row data plus the margins.

Next, we create the new image (line #18) and use it to get a drawing object (line #20).

A nested pair of for loops (lines #22 to #31) iterate over the row data. If a cell is non-blank, it calculates the pixel coordinates (lines #29 and #30) and draws a pixel.

Lines #33 to #38 are similar to what we used in the run_automata function to generate a filename for the image file. Line #41 saves the new image.

Lines #45 to #53 test image generation. First, we call run_automata to generate row data. Then we call make_automata_bitmap to create the image.

Now we can generate an image for any rule, but a few more simple functions will make this a better app.

First, a function to run any given rule:

Second, a function to run all 256 rules:

Both functions take a dictionary of parameters and use the KWARG function to extract the ones of interest (see examples.py in the ZIP file linked below). They also print these parameters The code that invokes run_automata and make_automata_bitmap are similar to what we’ve seen above. As usual, both fragments include a way to test the function.

Lastly, some code to stitch it all together and make it run:

The dispatch function expects a command (cmd) and a dictionary of arguments. The command determines which of the two launch functions from above are called.

The dispatch function can be imported to another app and called directly, but the code from line #15 to #30 makes this a useable app by processing command line parameters into dictionary form — treating the first one as the command — and calling dispatch.

A command line might look something like this:

one rule=100 size=300 dpath=C:\py\automata\dat ipath=C:\py\automata\img

Note that, after the initial command, the arguments can appear in any order and are only required to override the defaults. You’ll find a complete app (automata.py) in the ZIP file.

Enjoy!

Link: Zip file containing all code fragments used in this post.

∅