Quasi-periodic configurations and undecidable dynamics for tilings, infinite words and Turing machines

Delvenne, Jean-Charles [UCL] Blondel, Vincent [UCL]

We describe Turing machines, tilings and infinite words as dynamical systems and analyze some of their dynamical properties. It is known that some of these systems do not always have periodic configurations; we prove that they always have quasi-periodic configurations and we quantify quasi-periodicity. We then study the decidability of dynamical properties for these systems. In analogy to Rice's theorem for computable functions, we derive a theorem that characterizes dynamical system properties that are undecidable. As an illustration of this result, we prove that topological entropy is undecidable for Turing machines and for tilings. (C) 2004 Elsevier B.V. All rights reserved.