2-State 2-Symbol Turing Machines with Periodic Support Produce Regular Sets

Abstract : We say that a Turing machine has periodic support if there is an infinitely repeated word to the left of the input and another infinitely repeated word to the right. In the search for the smallest universal Turing machines, machines that use periodic support have been significantly smaller than those for the standard model (i.e. machines with the usual blank tape on either side of the input). While generalising the model allows us to construct smaller universal machines it makes proving decidability results for the various state-symbol products that restrict program size more difficult. Here we show that given an arbitrary 2-state 2-symbol Turing machine and a configuration with periodic support the set of reachable configurations is regular. Unlike previous decidability results for 2-state 2-symbol machines, here we include in our consideration machines that do not reserve a transition rule for halting, which further adds to the difficulty of giving decidability results.
Type de document :
Communication dans un congrès
Giovanni Pighizzini; Cezar Câmpeanu. 19th International Conference on Descriptional Complexity of Formal Systems (DCFS), Jul 2017, Milano, Italy. Springer International Publishing, Lecture Notes in Computer Science, LNCS-10316, pp.274-286, 2017, Descriptional Complexity of Formal Systems. 〈10.1007/978-3-319-60252-3_22〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01657010
Contributeur : Hal Ifip <>
Soumis le : mercredi 6 décembre 2017 - 11:44:22
Dernière modification le : mercredi 6 décembre 2017 - 13:46:18

Fichier

 Accès restreint
Fichier visible le : 2020-01-01

Connectez-vous pour demander l'accès au fichier

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

Citation

Turlough Neary. 2-State 2-Symbol Turing Machines with Periodic Support Produce Regular Sets. Giovanni Pighizzini; Cezar Câmpeanu. 19th International Conference on Descriptional Complexity of Formal Systems (DCFS), Jul 2017, Milano, Italy. Springer International Publishing, Lecture Notes in Computer Science, LNCS-10316, pp.274-286, 2017, Descriptional Complexity of Formal Systems. 〈10.1007/978-3-319-60252-3_22〉. 〈hal-01657010〉

Partager

Métriques

Consultations de la notice

24