Quasiperiodicity and non-computability in tilings.

November 2, 2015

Andreï Romashchenko (LIRMM, Montpellier)

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. We characterise the classes of Turing degrees that can be represented by quasiperiodic tilings. We also show that every minimal 1-dim subshift can be implemented as a subaction of a 2-dim minimal SFT.