No CrossRef data available.
Article contents
Tilings: simulation and universality
Published online by Cambridge University Press: 27 October 2010
Abstract
Wang tiles are unit-size squares with coloured edges. In this paper, we approach one aspect of the study of tiling computability: the quest for a universal tile set. Using a complex construction, based on Robinson's classical construction and its different modifications, we build a tile set (pronounced ayin) that almost always simulates any tile set. By way of Banach–Mazur games on tilings topological spaces, we prove that the set of -tilings that do not satisfy the universality condition is meagre in the set of -tilings.
- Type
- Paper
- Information
- Mathematical Structures in Computer Science , Volume 20 , Special Issue 5: Theory and Applications of Models of Computation (TAMC 2008–2009) , October 2010 , pp. 813 - 850
- Copyright
- Copyright © Cambridge University Press 2010