Affordable Access

Publisher Website

The 4-way deterministic tiling problem is undecidable

Authors
Journal
Theoretical Computer Science
0304-3975
Publisher
Elsevier
Publication Date
Volume
410
Issue
16
Identifiers
DOI: 10.1016/j.tcs.2008.12.006
Keywords
  • Deterministic Tiles
  • Domino Problem
  • Tiling Problem
  • Undecidability
  • Wang Tiles

Abstract

Abstract It is shown that the (infinite) tiling problem by Wang tiles is undecidable even if the given tile set is deterministic by all four corners, i.e. a tile is uniquely determined by the colors of any two adjacent edges. The reduction is done from the Turing machine halting problem and uses the aperiodic tile set of Kari and Papasoglu.

There are no comments yet on this publication. Be the first to share your thoughts.