An Almost Totally Universal Tile Set

摘要

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 y (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 y-tilings which do not satisfy the universality condition is meager in the set of y-tilings.