Quasiperiodicity and non-computability in tilings - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Conference Papers Year : 2015

Quasiperiodicity and non-computability in tilings

Abstract

We study tilings of the plane that combine strong properties of different nature: combinatorial and algorithmic. We prove 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 effectively closed set can be recursively transformed into a tile set so that the Turing degrees of the resulted tilings consists exactly of the upper cone based on the Turing degrees of the later.

Dates and versions

lirmm-01165314 , version 1 (18-06-2015)

Identifiers

Cite

Bruno Durand, Andrei Romashchenko. Quasiperiodicity and non-computability in tilings. MFCS: Mathematical Foundations of Computer Science, Aug 2015, Milan, Italy. pp.218-230, ⟨10.1007/978-3-662-48057-1_17⟩. ⟨lirmm-01165314⟩
133 View
0 Download

Altmetric

Share

Gmail Facebook X LinkedIn More