Computability in Europe 2006
Logical Approaches to Computational Barriers


Regular Talk:
Simulations Between Tilings


Author(s): Michael Weiss and Gregory Lafitte
Slot: Array, 11:50-12:10, col. 5

Abstract

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