On a conjecture of Kurka. A Turing machine with no periodic configurations
(2001) 3rd International Conference on Machines, Computations and Universality — Location: Chisinau, Moldova (23.May.2001)
Files
No attached file found for this publication.
Details
- Authors
- Abstract
- A configuration of a Turing machine is given by a tape content together with a particular state of the machine. Petr Kurka (see Theoretical Comput. Sci. vol.174, p.203-16, 1997) has conjectured that every Turing machine - when seen as a dynamical system on the space of its configurations - has at least one periodic orbit. We provide an explicit counter-example to this conjecture. We also consider counter machines and prove that, in this case, the problem of determining if a given machine has a periodic orbit in configuration apace is undecidable.
- Affiliations
Citations
Blondel, V., Cassaigne, J., & Nichitiu, C. (2001). On a conjecture of Kurka. A Turing machine with no periodic configurations. In Margenstern, M.; Rogozhin, Y.; (ed.), Machines, Computations, and Universality. Third InternationalConference, MCU 2001. Proceedings (Lecture Notes in Computer ScienceVol.2055) (p. p. 165-176). Springer-verlag. https://hdl.handle.net/2078.5/231012