A GAME OF LIFE ON PENROSE TILINGS

arXiv:1708.09301v1 [nlin.CG] 29 Aug 2017

DUANE A. BAILEY AND KATHRYN A. LINDSEY

Abstract. We define rules for cellular automata played on quasiperiodic tilings of the plane arising from
the multigrid method in such a way that these cellular automata are isomorphic to Conway’s Game of
Life. Although these tilings are nonperiodic, determining the next state of each tile is a local computation,
requiring only knowledge of the local structure of the tiling and the states of finitely many nearby tiles. As
an example, we show a version of a “glider” moving through a region of a Penrose tiling. This constitutes
a potential theoretical framework for a method of executing computations in non-periodically structured
substrates such as quasicrystals.

1. Introduction
Inspired by Conway’s Game of Life ([3]), various researchers have investigated properties of similarlydefined cellular automata played on Penrose tilings (e.g. [4, 7, 8, 10, 11]). Since Penrose tilings are not
periodic ([6]), the challenge is to define a finite state cellular automaton which is locally computable –
meaning that the next state of a tile depends only on the current states of finitely many “nearby” tiles –
and yet has interesting emergent global properties. In particular, the existence of “gliders” and the ability
to support universal computation is of interest.
In this note, we present a natural method for embedding the original Game of Life in any tiling of the
plane that arises via the multigrid method, a class of tilings that include Penrose rhomb tilings. The resulting
cellular automata, defined on quasiperiodic tilings, are locally computable and precisely mimic the behavior
of the original Game of Life. In particular, they admit gliders, signal delivery, universal computation, and
reproduction.
Quasiperiodic tilings may be thought of as “toy models” of quasicrystals - physical substances which,
like quasiperiodic tilings, exhibit order but not periodicity. Penrose tilings, in particular, are a geometric
model for icosahedral quasicrystals [9]. This investigation is motivated by the promise of new media for
hosting computation – a topic which gives rise to the question of how to “compute” in non-periodically
structured substrates.
2. Statement of Results
Quasiperiodic tilings generated by the “multigrid” method admit ribbons of tiles. A ribbon consists
of a bi-infinite sequence of sequentially adjacent tiles that share an edge that is parallel to some fixed vector.
In a tiling generated by an n-multigrid, every edge of the tiling is parallel to one of n distinct vectors, say
v1 , . . . , vn ∈ R2 . Define a tile to be of type (i, j) if has two edges parallel to vi and two edges parallel to vj .
A regular tiling has n2 types of tiles, each of which is a parallelogram and has a unique type. A tile with
more than four edges, which by definition belongs to a singular tiling, may be of more than one type (a tile
of type (i, j) may have additional edges not parallel to vi or vj .) For any choice of (i, j), i 6= j, in any tiling
arising from a multigrid construction, the set of all ribbons passing through all tiles of type (i, j) forms a
square grid graph (i.e. the pattern formed by the ribbons is topologically the same as the pattern of lines on
a piece of graph paper). The “vertices” of the square grid graph are the type (i, j)-tiles. See Figure 1.
This square grid graph structure determines a natural isomorphism between the set of type (i, j) tiles
in a regular quasiperiodic tiling arising from a multigrid construction and the grid of squares in Conway’s
original Game of Life. This isomorphism preserves the property of adjacency of tiles within the lattice, and
is unique up to choosing which tile represents the origin in the square grid Z2 and which directions of ribbons
Date: August 29, 2017.
2010 Mathematics Subject Classification. primary 37B15, 53C23; secondary 68Q80.
Key words and phrases. cellular automata, quasiperiodic tiling, quasicrystal, Penrose tiling, Game of Life.
Second author supported by an N.S.F. Mathematical Sciences Research Postdoctoral Fellowship.
1

2

D. BAILEY AND K. LINDSEY

correspond to the positive x and y directions in Z2 . Since discerning ribbons only entails evaluating the
parallelism of edges of adjacent tiles, picking out the natural lattice structure of the set of type (i, j) tiles in
any region requires only local knowledge of the tiling.
Our fundamental observation is that the original Game of Life may be “played” on this lattice of type
(i, j) tiles. That is, in a regular tiling, each tile of type (i, j) has precisely eight neighbors – the eight (i, j)
type tiles that are “neighboring” in the lattice structure determined by the square grid graph of ribbons.
Equipped with this observation, several obvious variants of the “game” are possible:
Game Variants:
(i) We pick a pair of grid indices (i, j), play the Game of Life on the lattice consisting of all (i, j) type
tiles, and declare all tiles that are not type (i, j) to be “dead.”
(ii) As in variant (i), we pick a pair of grid indices (i, j) and play the Game of Life on the lattice
consisting of all type (i, j) tiles. However, instead of declaring tiles of other types to be dead,
we associate each tile that is not type (i, j) to a nearby type (i, j) tile. Section §5.1 describes a
canonical way to associate every tile that is not type (i, j) to a nearby type (i, j) tile. We call the
type (i, j) tiles dominant, and we call the set of non-dominant tiles associated to a dominant tile
the supporting tiles. We declare that a supporting tile is alive if and only if its associated dominant
tile is alive. (This is equivalent to specifying that the neighbors of a supporting tile are the eight
dominant tiles that neighbor its associated dominant tile.)
 (See Figure 2.)
(iii) In a regular tiling arising from a n-multigrid, there are n2 types of tiles, and each tile is of a unique
type. We simultaneously play a different copy of the Game of Life on each lattice consisting of all
tiles of a given type. These copies do not interact.
(iv) As in variant (iii), we play a different copy of the Game of Life on each lattice consisting of all tiles
of a given type, but on a singular tiling. In this case, copies of the Game of Life played on different
sets of tiles interact. Tiles that belong to more than one lattice serve as channels of communication
between the copies of the Game of Life played of these lattices. (See Section §5.2.) A different local
rule may be required for these tiles, as they have more than eight neighbors.
3. The original Game of Life
Let X be a tiling of the plane, and let T be the set of tiles in X. A cellular automaton played on X
with a set of states A = {a1 , . . . , an } is a map f : T A → T A such that
(i) each tile t ∈ T has a “neighborhood” N (t) ⊂ T consisting of finitely many “nearby” tiles
(ii) there is a “local rule” map, r, defined on the set of all configurations of all neighborhoods and taking
values in A, so that for all configurations c ∈ T A and all t ∈ T , πt (f (c)) = r(πN (t) (c)), where πi is
the restriction to the ith coordinate.
The space T A is the phase space, or set of all possible configurations for the cellular automaton; a point
c ∈ T A is an assignment of one state in A to each tile t ∈ T . Condition (ii) says that, regardless of the
global configuration c, the next state of each tile t is can be computed from the current states of the tiles in
the neighborhood N (t) using the local rule r.
In Conway’s original Game of Life ([3]), T is the standard tiling of the plane by isometric squares, and
A = {0, 1}. Tiles in state 1 are said to be “alive” or “living,” and tiles in state 0 are said to be “nonliving” or
“dead.” For each tile t, N (t) is the eight tiles which neighbor t (i.e. are vertically, horizontally, or diagonally
adjacent to t). The local rule r is


1
r(t) = 1


0

if t is living and precisely 2 or 3 tiles in N (t) are alive
if t is dead and precisely 3 tiles in N (t) are alive
otherwise

Invented in 1970 by John Conway and popularized by Martin Gardner in an article in Scientific
American ([3]), the Game of Life exhibits many interesting local configurations, including gliders, glider
guns, spaceships, and replicators (cite). It was shown to support universal computation, with the proof
utilizing streams of gliders to transmit signals ([1]). Dave Greene found the first replicator in the Game of
Life in 2013 ([5]).

A GAME OF LIFE ON PENROSE TILINGS

3

Figure 1. Eight ribbons of a “square grid graph” of ribbons in a Penrose tiling are colored
in. The two chosen vectors, vi and vj , are the vectors parallel to the edges of the purple
tiles. The purple (i, j)-type tiles are the intersections of the grid of pink ribbons and the grid
of blue ribbons. Only four ribbons of each ribbon grid are colored, so that the reader may
more clearly see the geometric structure, but one could complete the coloring by making all
of the (i, j)-type tiles purple and extending pink and blue ribbons out from these tiles.
4. The multigrid method
In this section, we review the multigrid method (introduced by de Bruijn in [2]) and use it to justify
our assertion that the set of all ribbons passing through all type (i, j) tiles forms a square grid graph.
4.1. General multigrids. The multigrid method is a method of constructing quasiperiodic tilings. A grid
is an infinite family of equally spaced, parallel lines in the plane. (Note that his use of the word “grid”
differs from that of the “square grid graph” of Section §2 and Figure 1.) An n-multigrid, n ≥ 2, sometimes
called just a multigrid, is the union of n grids in the plane, with no two grids parallel to the same vector. A
multigrid (or the associated tiling) is said to be regular if no point is the intersection of more than 2 lines;
otherwise it is singular.
A multigrid determines a tiling of the plane (see §4.2). The tiling consists of one tile for each intersection of two (or more) lines in the multigrid. If precisely 2 lines of the multigrid intersect at a point v,
the tile corresponding to v is a parallelogram whose edges are perpendicular to the lines intersecting at v.
In the case of a singular multigrid, if k ≥ 2 lines of the multigrid intersect at v, the associated tile has one
edge for each of the 2k half-lines incident to v, and the edges are perpendicular to the associated half-lines
and arranged in the same order.
Consequently, all tiles that correspond to intersections of a given line, say L, with other lines in a
multigrid have opposite edges that are perpendicular to L (and hence parallel). The line L corresponds in
the tiling to a ribbon of tiles that all have a pair of edges that are perpendicular to L. Two grids in the
multigraph correspond in the tiling to a “square grid graph” of ribbons, and the intersection points of these
two grids correspond to the set of tiles that have edges perpendicular to the lines in both of these grids (see
Figure 1).

4

D. BAILEY AND K. LINDSEY

Figure 2. Sixteen generations of a “glider” as it passes over a Penrose tiling, read from
left-to-right, top-to-bottom. Here we are using Game Variant (ii); the living dominant
tiles are black, and the supporting tiles associated to living dominant tiles are gray. The
configurations in each column of the figure represent the glider in the same position (relative
to the grid of dominant tiles). The different configurations that represent the glider in the
same position are due to the local structure of the tiling; a glider will assume identical
configurations at times, but that timing is, itself, nonperiodic.
4.2. Constructing Penrose tilings from pentagrids. For concreteness, we describe how to construct
the tiling associated to a 5-multigrid (called pentagrid) in which the grids are parallel to the vectors
2πi
1, ζ 1 , ζ 2 , ζ 3 , ζ 4 , where ζ = e 5 . This is the case described by de Bruijn and which gives rise to Penrose
tilings. An analogous process defines the tiling associated to a general n-multigrid (see, e.g. [12, 2]).
First, we define the 5-multigrid, which in this case is also called a pentagrid. Fix real numbers
γ0 , . . . , γ4 . For j = 0, ..., 4, define the j th grid to be the set
{z ∈ C | Re(zζ −j ) + γj ∈ Z},
which consists of of equally spaced parallel lines. The pentagrid determined by γ0 , ..., γ4 is the union of grids
0 to 4.
We now define a map K : C → Z5 that describes the coordinate of points in the plane relative to each
of the five grids. Namely, K associates to each point z ∈ C the point K(z) ∈ Z5 whose j th coordinate is
given by
Kj (z) = dRe(zζ −j ) + γj e.

A GAME OF LIFE ON PENROSE TILINGS

5

Define the map φ : Z5 → C by
φ(~k) = ~k · (1, ζ 1 , ζ 2 , ζ 3 , ζ 4 ).
The set of vertices of the associated tiling is the image of the plane C under φ ◦ K. As z travels in a small
circle around a point mentioned by n ≥ 2 lines of the multigrid, the map φ ◦ K(z) picks out a sequence of 2n
points in C; straight line segments connecting these 2n vertices (in cyclic order) are the edges of a tile in the
tiling. Each tile of the tiling comes from such an intersection of grid lines. De Bruijn proved [2] that if the
pentagrid determined by γ0 , . . . , γ4 is regular, then the associated tiling is a Penrose tiling, and conversely,
every Penrose tiling arises from such a pentagrid.
A tile of type (i, j), which comes from an intersection point of a line in the ith grid and a line in the
th
j grid, has edges parallel to ζ i and ζ j . If this intersection point is mentioned by precisely n ≥ 2 lines of
the grid, the tile will have 2n edges, of which two are parallel to ζ i and two are parallel to ζ j . If the tile is a
quadrilateral, whether it is a thick rhomb or a thin rhomb depends on the parity of i − j. A Penrose tiling
exhibits ten different tile orientations (5 rotations of both thin and thick tiles); these correspond to the 52
ways that two of the five grids can intersect. The intersection of a fixed line of grid i with the other lines of
the multigrid corresponds to a ribbon of tiles that all have edges parallel to ζ i .
Example. Figure 3 shows a small section of a pentagrid. Consider the intersection of line 0 of grid 0 and
line −1 of grid 4 in the pentagrid; call this point z. In a small neighborhood of z, K takes on four distinct
values: K(z0 ) = (0, 1, 1, 0, −1), K(z1 ) = (1, 1, 1, 0, −1), K(z2 ) = (1, 1, 1, 0, 0), and K(z3 ) = (0, 1, 1, 0, 0).
Thus, the point z corresponds to the tile (a “thick” rhomb) whose four vertices have coordinates
φ(K(z0 )) = ζ 1 + ζ 2 − ζ 4 ,
φ(K(z1 )) = 1 + ζ 1 + ζ 2 − ζ 4 ,
φ(K(z2 )) = 1 + ζ 1 + ζ 2 , and
φ(K(z3 )) = ζ 1 + ζ 2 .
Since ζ j has unit magnitude, we can see that the edges of the tile all have unit length. Since the coordinates
of the four points differ by a single multiple of 1 and/or ζ 4 , the edges of the tile are parallel to the vectors 1
or ζ 4 in C.
5. Notes on Game Variants
5.1. Variant (ii): dominant and supporting tiles. Section §4 describes a bijection between the set of
tiles (of a tiling arising from a regular multigrid G) and the set of points in the plane that are mentioned
by more than one grid of G. For each pair of grid indices (i, j), the union of grids i and j determines a
decomposition of the plane into parallelograms. To be a true decomposition of the plane (i.e. each point
belongs to precisely one parallelgram), view each parallelogram to be a product of left-closed, right-open (or
right-open, left-closed) intervals. If a point v is in the intersection of two (or more) grids and belongs to
parallelogram P , define the tile corresponding to v to be in the support of the type-(i, j) tile associated to
the top left (or any other consistent choice) corner of the parallelogram P .
5.2. Variant (iv): singular tilings and interacting copies of the Game of Life. Suppose precisely
3 lines of a multigrid intersect at a point z; let i, j, k be the indices of the three grids. The tile associated
to z has six sides, is of types (i, j), (j, k), and (i, k), and belongs to the three corresponding lattices of tiles.
Thus, this one tile may have as many as 24 neighbors – eight neighbors in each of three lattices. We may
wish to impose a different local rule for tiles with more than eight neighbors. The state of this tile impacts
the evolution of each of the three “copies” of the Game of Life.

In general, a tile that represents the intersection of n ≥ 3 lines in a multigrid is of n2 types and
thus belongs to n2 lattices, each of which hosts a copy of the Game of Life. If each of its neighboring tiles
arise from the intersection of precisely two multigrid lines (i.e. is a parallelogram), the tile will have 8 · n2
neighbors. Understanding the qualitative effects of different possible local rules for tiles of more than one
type is beyond the scope of this work.
In the case of Penrose tilings, given any 3 distinct edge directions, there is at most one tile that has
edges in all 3 directions (as well as, possibly, other directions). Thus, communication between the games
played on the three associated lattices of tiles can occur only at this one location. Such a tile results from

D. BAILEY AND K. LINDSEY

i

Gr
-1

-2

-2

2

d2

1

-1

0

0

id
Gr

6

3
1
2

2
1

-2

z0 z1
z3 z2

-1

4
φ(K(z ))
1

1

-2

0

Grid

0

Grid

0

-1
φ(K(z ))

2

τ

-2
φ(K(z ))
3

i

φ(K(z ))
2

-1

0
1
Grid 0

2

1

Figure 3. The intersection, z, of line 0 of grid i = 0 and line -1 of grid j = 4. The nearby
points z0 , z1 , z2 , and z3 are mapped by K to four different points in Z5 . The images of
these points under φ are the vertices of a tile in the associated tiling.
the intersection of lines in 3 distinct grids of the pentagrid. To see that there can be at most one such tile,
we may assume without loss of generality that two of the grids are grid 0 and grid 1, corresponding to the
vectors ζ 0 and ζ 1 . Let M be an affine deformation of the complex plane that maps these two vectors to
1 and i in C. Denote by u the image under M of ζ j , for any fixed j ∈ {2, 3, 4}. Since both the real and
complex coordinates of u are irrational, the three vectors 1, i, and u are rationally independent. Therefore,
at most one point is in the intersection of grids 0, 1, and j; this proves the assertion that a (nonregular)
Penrose tiling has most one tile of type (0, 1, j).
6. Discussion
In some ways, our approach may be seen to have skirted the problem of how to “compute” in nonperiodic substrates. However, the fundamental observation of this work is that nonperiodic tilings may have
periodic features that can be harnessed for computation. The collection of all tiles of type (i, j) naturally
forms a lattice, but tiles that occupy adjacent positions in the lattice may not be adjacent in the tiling as
a whole (they are, however, a bounded distance apart). Game variant (ii) may be interpreted as a way to
address this issue; one may consider the union of a dominant tile together with its supporting tiles as a single
giant tile, eliminating the dead space between dominant tiles. While interaction between copies of the game
of life played on different lattices can occur at tiles with more than four sides, (nonregular) Penrose tilings
have at most one tile that belongs to any three distinct lattices; generalizations of multigrids in which lines
of the grid are not required to be spaced equally could give rise to more tiles that are loci for communcation
between the lattices. It remains to be seen to what extent our approach can inform implementation of
computation in real-world nonperiodic substrates.
References
[1] Elwyn R. Berlekamp, John H. Conway, and Richard K. Guy. Winning ways for your mathematical plays. Vol. 1. A K
Peters, Ltd., Natick, MA, second edition, 2001.

A GAME OF LIFE ON PENROSE TILINGS

7

[2] N. G. de Bruijn. Algebraic theory of Penrose’s nonperiodic tilings of the plane. I, II. Nederl. Akad. Wetensch. Indag. Math.,
43(1):39–52, 53–66, 1981.
[3] Martin Gardner. Mathematical games – the fantastic combinations of John Conway’s new solitaire game of “life”. Scientific
American, 223:120–123, 1970.
[4] Adam P. Goucher. Gliders in cellular automata on Penrose tilings. J. Cell. Autom., 7(5-6):385–392 (2013), 2012.
[5] Dave Greene. Geminoid challenge.
[6] Branko Grünbaum and G. C. Shephard. Tilings and patterns. A Series of Books in the Mathematical Sciences. W. H.
Freeman and Company, New York, 1989. An introduction.
[7] Katsunobu Imai, Takahiro Hatsuda, Victor Poupet, and Kota Sato. A 6-state universal semi-totalistic cellular automaton
on kite and dart Penrose tilings. Fund. Inform., 126(2-3, [On cover: nos. 3-4]):247–261, 2013.
[8] Chuzo Iwamoto Kota Sato, Katsunobu Imai. Universal von neumann neighborhood cellular automata on penrose tilings.
In First International Symposium on Computing and Networking, pages 515–521, 2013.
[9] A. L. Mackay. What has the penrose tiling to do with the icosahedral phases? geometrical aspects of the icosahedral
quasicrystal problem. Journal of Microscopy, 146(3):233–243, 1987.
[10] N. Owens and S. Stepney. The game of life rules on Penrose tilings: Still life and oscillators. Game of Life Cellular
Automata, pages 331–378, 2010.
[11] Nick Owens and Susan Stepney. Investigations of Game of Life cellular automata rules on Penrose tilings: lifetime, ash,
and oscillator statistics. J. Cell. Autom., 5(3):207–225, 2010.
[12] Marjorie Senechal. Quasicrystals and geometry. Cambridge University Press, Cambridge, 1995.
Department of Mathematics, Williams College, Williamstown, MA 01267, U.S.A.
E-mail address: bailey@cs.williams.edu
Department of Mathematics, University of Chicago, Chicago, IL 60637, U.S.A.
E-mail address: klindsey@math.uchicago.edu

