Advertisement
Published in:
2015 | OriginalPaper | Chapter
Quasiperiodicity and Non-computability in Tilings
Authors : Bruno Durand, Andrei Romashchenko
Published in: Mathematical Foundations of Computer Science 2015
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
Abstract
We study tilings of the plane that combine strong properties of different nature: combinatorial and algorithmic. We prove the existence of a tile set that accepts only quasiperiodic and non-recursive tilings. Our construction is based on the fixed point construction [12]; we improve this general technique and make it enforce the property of local regularity of tilings needed for quasiperiodicity. We prove also a stronger result: any \(\mathrm \Pi _1^0\)-class can be recursively transformed into a tile set so that the Turing degrees of the resulting tilings consists exactly of the upper cone based on the Turing degrees of the latter.