Wang Tiles
Type of content
Publisher's DOI/URI
Thesis discipline
Degree name
Publisher
Journal Title
Journal ISSN
Volume Title
Language
Date
Authors
Abstract
Wang tiles are a type of theoretical domino, proposed by Hao Wang in 1961. Two related problems were associated with them when they were first proposed. Firstly, deciding whether an arbitrary set could tile the plane (the Domino Problem), and secondly whether any sets existed which could tile the plane only aperiodically. These were solved in 1966 by Robert Berger, who showed that the Domino Problem was undecidable, and produced the first set of aperiodic tiles. This proof involved devising a method by which Wang tiles could simulate Turing machines, hence also demonstrating thatWang tiles are capable of computation. We show some examples of computations done with Wang tiles, then consider hexagonal Wang tiles, and how they can be used to carry out such computations.