Tilings: recursivity and regularity

We establish a first step towards a “Rice theorem” for tilings: for non-trivial sets, it is undecidable to know whether two different 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. [Copyright &y& Elsevier]