Wang Tiles

Type of content
Reports
Publisher's DOI/URI
Thesis discipline
Degree name
Publisher
Journal Title
Journal ISSN
Volume Title
Language
Date
2022
Authors
Edwards, Kieran
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.

Description
Citation
Keywords
Wang Tiles, Domino Problem, Turing
Ngā upoko tukutuku/Māori subject headings
ANZSRC fields of research
Fields of Research::49 - Mathematical sciences
Rights
All Rights Reserved