Quasi-periodic configurations and undecidable dynamics for tilings, infinite words and Turing machines
(2004) Theoretical Computer Science — Vol. 319, n° 1-3, p. 127-143 (2004)
Files
pdfdocument.pdf
Restricted Access - Adobe PDF
- 312.22 KB
Details
- Authors
- Abstract
- 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.
- Affiliations
Citations
Delvenne, J.-C., & Blondel, V. (2004). Quasi-periodic configurations and undecidable dynamics for tilings, infinite words and Turing machines. Theoretical Computer Science, 319(1-3), 127-143. https://doi.org/10.1016/j.tcs.2004.02.018 (Original work published 2004)