User menu

Accès à distance ? S'identifier sur le proxy UCLouvain

On the presence of periodic configurations in Turing machines and in counter machines

Primary tabs

Blondel, Vincent [UCL] Cassaigne, Julien Nichitiu, Codrin

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.

Document type Article de périodique (Journal article) – Article de recherche
Access type Accès restreint
Publication date 2002
Language Anglais
Journal information "Theoretical Computer Science" - Vol. 289, no. 1, p. 573-590 (2002)
Peer reviewed yes
Publisher Elsevier Science Bv (Amsterdam)
issn 0304-3975
Publication status Publié
Affiliation UCL - FSA/INMA - Département d'ingénierie mathématique
Links
Bibliographic reference Blondel, Vincent ; Cassaigne, Julien ; Nichitiu, Codrin. On the presence of periodic configurations in Turing machines and in counter machines. In: Theoretical Computer Science, Vol. 289, no. 1, p. 573-590 (2002)
Permanent URL http://hdl.handle.net/2078.1/41554