Domino problem
From Wikipedia, the free encyclopedia
In geometry, the Domino Problem is the problem of deciding whether a given set of tiles admits a tiling.
In a 1961 paper[1] proposing a method for deciding an important case of David Hilbert's Entscheidungsproblem, the logician Hao Wang discusses tiling the plane with
square plates of the same size with edges colored, each in a different manner
that may not be rotated or reflected, now called Wang tiles, and offhandedly gives a
Fundamental Conjecture: A finite set of plates is solvable [That is, admits a tiling of the plane] ... if and only if there exists a cyclic rectangle of the plates; or in other words, a finite set of plates is solvable if and only if it has at least one periodic solution.
In short, he conjectured that there is no aperiodic set of tiles. Wang continues
If [the conjecture] is true, we can decide effectively whether any given finite set of plates is solvable.
In other words, if every set of Wang tiles either does not admit a tiling, or admits a periodic tiling, then there is an algorithm for deciding which is the case: enumerate all possible coverings of larger and larger rectangles until either there is some size of rectangle that the tiles cannot cover, or until a fundamental domain for a periodic tiling is found. Either way, the algorithm will eventually halt, so long as no aperiodic sets of tiles exist.
This observation holds in a very wide range of other settings, such as tiling by unmarked polygons—we need only be able to enumerate all possible configurations of any given set of tiles and check whether a given configuration is a fundamental domain for some periodic tiling.
The Domino Problem, then, is
Does a given set of tiles admit a tiling?
and the question, in a given setting, is whether this problem is decidable or not, whether there is an effective procedure for settling the problem for any given set of tiles.
In 1966, Robert Berger proved the Domino Problem is in fact undecidable for Wang tiles (and implicitly, for planar tiles in general),[2] incidentally giving an aperiodic set of over 20,000 tiles. (In his unpublished Ph.D. thesis, he gives a smaller set of 104.)
Raphael Robinson reworked Berger's proof in a highly elegant and readable 1971 paper.[3]
[edit] References
- ^ Wang, Hao (1961). "Proving theorems by pattern recognition- II". Bell System Technical Journal 40: 1–42.
- ^ Berger, Robert (1966). "The undecidability of the Domino Problem". Memoirs Am. Math. Soc. 66.
- ^ Robinson, R.M. (1971). "Undecidability and nonperiodicity for tilings of the plane". Inv. Math 12: 177–209. doi:.
