Logical Approaches to Computational Barriers

Simulations Between Tilings

Author(s): |
Michael Weiss and Gregory Lafitte |

Slot: |
Array, 11:50-12:10, col. 5 |

Wang tiles are unit size squares with colored edges. To know if a given finite set of Wang tiles can tile the plane while respecting colors on edges is undecidable. Robinson's tiling is an auto-similar tiling where the computation of a Turing Machine can be carried out. We introduce finer notions of simulation between tilings, giving rise to a finer notion of universality. We show how to use this construction to be able to simulate a tile set by another tile set through Turing machines. We study the computability of some problems related to simulation. Finally, we show how to build a tile set that can simulate all the periodic tile sets.

websites: Arnold Beckmann | 2008-05-19 |