2009 | OriginalPaper | Chapter
An Almost Totally Universal Tile Set
Authors : Grégory Lafitte, Michael Weiss
Published in: Theory and Applications of Models of Computation
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Wang tiles are unit size squares with colored edges. In this paper, we approach one aspect of the study of tilings 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
) which
almost always
simulates any tile set. By way of Banach-Mazur games on tilings topological spaces, we prove that the set of
μ
-tilings which do not satisfy the universality condition is meager in the set of
μ
-tilings.