The 4-way deterministic tiling problem is undecidable |
| |
| Authors: | Ville Lukkarila |
| |
| Affiliation: | Department of Mathematics, University of Turku, FI-20014 Turku, Finland; Turku Centre for Computer Science, FI-20520 Turku, Finland |
| |
| 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. |
| |
| Keywords: | Deterministic tiles Domino problem Tiling problem Undecidability Wang tiles |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
