2001 • Conference Paper
On a conjecture of Kurka. A Turing machine with no periodic configurations
Authors:
Blondel, Vincent ,
Cassaigne, Julien,
Nichitiu, C.
Published in:
3rd International Conference on Machines, Computations and Universality
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.