On the presence of periodic configurations in Turing machines and in counter machines
Volume: 289 • Number: 1 • Pages: 573-590
A configuration of a Turing machine is given by a tape content together with a particular state of the machine. Petr Kurka has conjectured that every Turing machine-when seen as a dynamical system on the space of its configurations-has at least one periodic orbit. In this paper, we provide an explicit counterexample 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 space is undecidable. (C) 2002 Elsevier Science B.V. All rights reserved.