Quasiperiodicity and Non-computability in Tilings

摘要

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; 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 Π_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.