Hendy Wickham-Pussey

Undecidability of Tilings of the Plane

Abstract

As a whole this paper seeks to answer the Domino Problem, or more precisely, to prove it's undecidability.

The first chapter establishes whether or not periodicity is an appropriate way to decide whether or not a given tile set tiles the plane. In fact this is not the case and the construction of an aperiodic tile set (namely the Robinson tiles) is used to prove this. Given that an aperiodic tile set exists it is not possible to determine whether or not a tile set tiles the plane based purely on whether or not it can do so periodically, as this would imply that aperiodic tile sets cannot tile the plane.

The Robinson tiles are then considered in terms of substitution. First a partial-substitution is shown which follows from the construction of the tilings in the previous chapter. This allows for another proof of their aperiodicity. In fact a proof is given that any substitution with a unique composition leads to a non-periodic tiling. The Robinson tiles are then used to construct a tile set with a formal substitution tiling, but that still replicates the Robinson tiles. This allows (among other things) for the identification of the minimal subspace of the tiles.

The classical decision problems of the Halting Problem and Immortality Problem are then considered and proved to be undecidable. The Halting Problem has a simple enough proof by construction of a Turing machine which contradicts itself. The Halting Problem is also reduced to the Immortality Problem, by way of counter machines, and this proves the undecidability of the latter.

Two proofs of the undecidability of the Domino Problem have been given. The first is by Robinson and requires the combination of his tile set with Turing tiles to show the Domino Problem as a Reduction of the Origin-Constrained Problem. It is therefore necessary to explore the undecidability of this problem too, and it's proof is to show it is a reduction of the Halting Problem. This is followed by the Periodic Problem as the construction of the tile set used for this leads directly on from that which Robinson described, and goes onto prove that this too is an undecidable problem.

The second proof of the undecidability of the Domino Problem is more recent (2008) and is the work of Kari. This converts the tile into a system of affine maps, and thereby a Turing Machine. This effectively reduces the Immortality Problem to the Domino Problem, and so the second proof is complete. It is natural to follow this with a consideration of the Row-Constrained Problem. The method reduction is the same, but because of the extra constraint it is the Halting Problem not the Immortality Problem that is reduced to the Row-Constrained Problem.

The figures throughout this report are of my own construction with the exception of those in Chapter 2, namely Figure 2.2.1, Figure 2.3.1, Figure 2.2.3, which have been taken from Kari's “On the Undecidability of the Tiling Problem”. The figures of Chapter1 have been created from descriptions and diagrams of Robinson's original construction in [10]. And similarly the figures of Chapter 2 have been created from descriptions and diagrams in Gähler's paper [3].

The concepts considered are either my own or have been replicated from others papers and appropriately referenced. Particularly Sections 2.2 and 8.1 being entirely my own work (although chapter 8 draws heavily on the work of Kari in the previous chapter). Similarly the complete proof of the Immortality Problem is my own, although individual theorems involved in it have been used elsewhere.

Hendy Wickham-Pussey's Thesis

Share this page:

Contact details

Department of Mathematics
University of Leicester
University Road
Leicester LE1 7RH
United Kingdom

Tel.: +44 (0)116 229 7407

Campus Based Courses

Undergraduate: mathsug@le.ac.uk
Postgraduate Taught: mathspg@le.ac.uk

Postgraduate Research: pgrmaths@le.ac.uk

Distance Learning Course  

Actuarial Science:

DL Study

Student complaints procedure

AccessAble logo

The University of Leicester is committed to equal access to our facilities. DisabledGo has detailed accessibility guides for College House and the Michael Atiyah Building.