Name
Title | ||
|---|---|---|
On the presence of periodic configurations in Turing machines and in counter machines |
Abstract | ||
|---|---|---|
A configuration of a Turing machine is given by a tape content together with a particular state of the machine. Petr Kůrka 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. |
Year | DOI | Venue |
|---|---|---|
2002 | 10.1016/S0304-3975(01)00382-6 | Theor. Comput. Sci. |
Keywords | DocType | Volume |
tape content,counter machine,Turing machine,periodic configuration,dynamical system,periodic orbit,explicit counterexample,particular state,Petr K,configuration space | Journal | 289 |
Issue | ISSN | Citations |
1 | Theoretical Computer Science | 14 |
PageRank | References | Authors |
1.34 | 4 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Vincent D. Blondel | 1 | 1880 | 184.86 |
| Julien Cassaigne | 2 | 282 | 40.80 |
| Codrin Nichitiu | 3 | 49 | 5.73 |