Code 686 Builds the Chair Tiling

Initializing live version
Download to Desktop

Requires a Wolfram Notebook System

Interact on desktop, mobile and cloud with the free Wolfram Player or other Wolfram Language products.

In A New Kind of Science, rule 90 exemplifies the possibility of nested structures in one-dimensional cellular automata [1]. The comprehensive tome [1] goes on to discuss two-dimensional cellular automata and substitution tiling in Chapter 5, even mentioning Ulam systems and the chair tiling on pages 928–932. Unfortunately, [1] does not explicitly mention the deep cohesion between these ideas, nor do other references mention the interplay between cellular automata and substitution tiling (cf. [2–5]). This Demonstration gives a colorful construction of the trilobite and two crab tiling, which shows how blue crabs grow from the origin according to two-dimensional cellular automaton code 686 (see details).

Contributed by: Brad Klee (February 2019)
Open content licensed under CC BY-NC-SA


One would like to prove that, indeed, the trilobite and two crab tiling places blue crabs according to code 686. A plausible strategy is to show that either the growth rule or the substitution rule will generate the same ternary tree .

To define , we refer back to the more fundamental one-dimensional (1D) rule 90. If the initial condition is one ON node, then the complete spacetime graph will yield a parity pattern with fractal structure. The ON cells have point-like adjacencies, and all ON points alternate between branching and nonbranching adjacencies. As time goes to infinity, the adjacency graph grows to cover larger and larger patches of spacetime. By the eight simple rules, define as the ON-adjacency graph up to time , given the initial condition that is a single ON node.

The limit set, , is not a plane-filling tree because it leaves arbitrarily large regions of OFF cells in spacetime. At time the growing front of reaches only two ON cells spaced apart by OFF cells. The fractal construction of concatenates two copies to the front of a third thus obtaining . The ON counting function is relatively simple over , , and more complicated over (cf. [4, 5]).

The cavities of over spacetime take the shape of isosceles right triangles where the OFF cells fall along the hypotenuse. Dissecting any of these empty triangular cavities with a perpendicular bisector along the hypotenuse produces two similar right triangles. The two smaller triangles allow growth from the hypotenuse, especially if we assume all OFF cells along either of the shorter sides. Ternary may be obtained from binary by recursive branch reflection, without violating the assumption. Starting with the smallest branches, reflect every child branch across the axis of its immediate parent branch and ultimately obtain and its limit set .

The tree does not fit naturally in spacetime as a result of retrogressive growth but could possibly be a two-dimensional (2D) space pattern that evolves through time along a hidden third dimension. It is relatively easy to prove that rule 90 gives a subset of code 686, rotated and scaled by a factor of (cf. [5, 6]). Under code 686, cells along the long hypotenuse must also be OFF, while the other two sides of the triangle will support retrogressive growth. By symmetry, the perpendicular bisector must also be entirely OFF. Finally, the growth rule of code 686 is exactly equivalent to recursive reflections across immediate parent branches. The tree covers the parity pattern of code 686, up to horizontal and vertical reflections around the root node. Additionally, is a space-filling tree because it is impossible to draw arbitrarily large disks over .

Alternatively, the tiling model starts with a plane covering by rotated and translated copies of the L-triomino, also called a chair tile. We require that each chair tile intersects in eight vertices, including midpoints along the two longer edges. A set of 12 decorated chairs dissects the well-known trilobite and crab tiles, so the entire chair tiling can be constructed as a consequence of the local matching rules [2, 3]. The tiling is self similar. In particular, the set of vertices covered by yellow and mulberry channels is equal to the set of crab centroids, after scaling by a linear factor of four.

To construct from the set of crab centroids, start by making a L-triomino from two yellow crabs () and one mulberry crab (). By translations only, L-triominoes can recreate the hierarchical structure of . In this case, the finite approximants partially map the location of crab tiles within the supertile of a mulberry crab, . As in previous constructions, triangular cavities remain. The longer OFF hypotenuse must be tiled by trilobites ( a "trilobite extinction"), and the perpendicular bisector also supports a row of OFF trilobites. In this case the two similar triangles per larger cavity have trilobites on the short edges and crabs on the hypotenuse. Again, well-bounded regions allow us to use reflection to complete the tiling, and follows from . Reflection must be allowable according to the long-edge join rules of the blue chair tiles.

An interesting property of is that , in the sense that centers of the trilobites also form a copy of . This is an important fact for matching rule tilings, as the tree is integral to the "full explanation," which gives a construction of using trilobite T-tetrominoes [3]. In fact, the assertion that code 686 builds the chair tiling is only true if we leave off matching rules. Since the trilobite and crab tiling involves eight translation classes, an entirely sufficient cellular automaton (which seems likely to exist) would require at least four ON symbols, four OFF symbols and one NULL symbol. However, it may be more reasonable to start with two crabs and eight different ON symbols. This is an exciting creative project, which we leave for future research.


[1] S. Wolfram, A New Kind of Science, Champaign, IL: Wolfram Media, Inc., 2002.

[2] C. Goodman-Strauss, "A Small Aperiodic Set of Planar Tiles," European Journal of Combinatorics, 20(5), 1999 pp. 375–384. doi:10.1006/eujc.1998.0281.

[3] C. Goodman-Strauss, "The Trilobite and Crab: A Full Explanation."

[4] J. Shallit. "The On-Line Encyclopedia of Integer Sequences." (Feb 22, 2019)

[5] N. J. A. Sloane. "The On-Line Encyclopedia of Integer Sequences." (Feb 22, 2019)

[6] B. Klee. "The On-Line Encyclopedia of Integer Sequences." (Feb 22, 2019)


Feedback (field required)
Email (field required) Name
Occupation Organization
Note: Your message & contact information may be shared with the author of any specific Demonstration for which you give feedback.