Tilings: recursivity and regularity

✍ Scribed by Julien Cervelle; Bruno Durand

• Publisher: Elsevier Science
• Year: 2004
• Tongue: English
• Weight: 279 KB
• Volume: 310
• Category: Article
• ISSN: 0304-3975
• DOI: 10.1016/s0304-3975(03)00242-1

✦ Synopsis

We establish a ÿrst step towards a "Rice theorem" for tilings: for non-trivial sets, it is undecidable to know whether two di erent tile sets produce the same tilings of the plane. Then, we study quasiperiodicity functions associated with tilings. This function is a way to measure the regularity of tilings. We prove that, not only almost all recursive functions can be obtained as quasiperiodicity functions, but also, a function which overgrows any recursive function.