![]() The main ingredient is a new proof of Hooper's theorem by Kari and Ollinger combined with an encoding into subshifts of an effective set with no recursive points. We prove in particular in Theorem 2 that there exists a Turing machine for which the set of immortal configurations is nonempty and contains no computable configurations. In this article, we go further, and give some news results on the set of im-mortal configurations. Delvenne and Blondel proved that the set of immortal configurations, if nonempty, always contains quasi-periodic configurations. A few results give some structure on the set of immortal configurations: Kurka asked whether there always exists a (temporally) periodic configuration, and was refuted by Blondel et al. In fact, in the con-struction by Hooper, if the Turing machine has an immortal configuration, then it has one where the tape is almost completely empty. However, the result does not say anything about what the immortal configurations look like. The seminal article of Hooper proves that we cannot decide whether a Turing machine has an immortal configuration (is immortal). In this context, we call a configuration immortal if the machine runs forever starting from it. In this context, a Turing machine does not start from a specified initial state and tape, but from any configuration. In this paper we investigate the behaviour of Turing machines seen as dynam-ical systems. The result is obtained by combining a new proof of Hooper's theorem with recent results on effective symbolic dynamics. We investigate the immortality problem for Turing machines and prove that there exists a Turing Machine that is immortal but halts on every recursive configuration.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |