These tiles implement Wolfram's rule 110, a 1D cellular automaton, using boundary constraints to realize transitions.

5

8

1

113

updated May 21, 2024

These tiles can be fit together as jigsaw pieces, and when assembled, will implement the elementary cellular automaton known as Rule 110. They should ideally be printed in two different colors as shown, so that tiles representing a value of 0 (white) are distinct from those representing a value of 1 (black). It is also possible to determine this by looking at the position of the lower jigsaw tab.

The tiles must be assembled at the given orientation, not flipped or rotated, and aligned with a square grid. The shapes would need to be modified slightly to rule out a shift between rows, so I leave this to the user. Here is an example of what kinds of patterns can be constructed.

The initial idea was to construct a tile for each of the 8 possible windows 000, 001, 010, 011, 100, 101, 110, 111 that determine the value in the next row, creating jigsaw joins left and right to represent the overlap, e.g. between 010 and 101, as well as jigsaw joins top and bottom to represent the functional transition to the next cell value.

It can be simplified to a set of 6 tiles by observing that if the middle window value is 0, then the left value (written as x) can be ignored. This results in 6 square tiles for windows: x00, x01, 010, 011, 110, 111.

If can be further reduced to a set of 5 tiles, because 011 and 010 must always be preceded by x01. So we can combine these three square tiles into two 2:1 rectangular tiles for windows: x010 and x011.

This transition diagram illustrates how the tiles can be attached left to right. Another way to think of it is to consider Rule 110 to be the repeated application of a finite-state transducer. Each tile corresponds to a transition, and number of states corresponds to the overlap.

I have used the 5-tile set in my construction because it saves some effort in placement, but I have included models for the the 6 tile set. You need to print the the three non-specific tiles: x00, 110, 111 as well as either x01, 010, 011 for the six tile set or x010, x011 for the five tile set.

Because these transitions are non-deterministic, it is possible to get stuck. You can avoid that by looking ahead to the appropriate window. However, the constraints will prevent you from violating the transition rule.

The author marked this model as their own original creation.