Computability in Europe 2008
Logic and Theory of Algorithms

Print current page  Print this page

Regular Talk:
Simulations Between Tilings

Edit abstract data

Author(s): Michael Weiss and Gregory Lafitte
Slot: Wed, 11:50-12:10, Room 19 (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

websites: Arnold Beckmann 2008-05-19 Valid HTML 4.01! Valid CSS!