User menu

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

On a conjecture of Kurka. A Turing machine with no periodic configurations

Primary tabs

Blondel, Vincent [UCL] Cassaigne, J. Nichitiu, C.

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.

Document type Communication à un colloque (Conference Paper) – Présentation orale avec comité de sélection
Publication date 2001
Conference "3rd International Conference on Machines, Computations and Universality", Chisinau, Moldova (23-27 May 2001)
Peer reviewed yes
Host document Margenstern, M.; Rogozhin, Y.; ; "Machines, Computations, and Universality. Third InternationalConference, MCU 2001. Proceedings (Lecture Notes in Computer ScienceVol.2055)"- p. 165-176 (ISBN : 3-540-42121-1)
Publisher Springer-verlag
Affiliation UCL - FSA/INMA - Département d'ingénierie mathématique
Links
Bibliographic reference Blondel, Vincent ; Cassaigne, J. ; Nichitiu, C.. On a conjecture of Kurka. A Turing machine with no periodic configurations.3rd International Conference on Machines, Computations and Universality (Chisinau, Moldova, 23-27 May 2001). In: Margenstern, M.; Rogozhin, Y.;, Machines, Computations, and Universality. Third InternationalConference, MCU 2001. Proceedings (Lecture Notes in Computer ScienceVol.2055), Springer-verlag2001, p. 165-176
Permanent URL http://hdl.handle.net/2078.1/68162