×

One head machines from a symbolic approach. (English) Zbl 1118.68064

Summary: We consider the Turing machine as a dynamical system and we study a particular partition projection of it. In this way, we define a language (a subshift) associated to each machine. The classical definition of Turing machines over a one-dimensional tape is generalized to allow for a tape in the form of a Cayley graph. We study the complexity of the language of a machine in terms of realtime recognition by putting it in relation with the structure of its tape. In this way, we find a large set of realtime subshifts some of which are proved not to be deterministic in realtime. Sofic subshifts of this class correspond to machines that cannot make arbitrarily large tours. We prove that these machines always have an ultimately periodic behavior when starting with a periodic initial configuration, and this result is proved for any Cayley graph.

MSC:

68Q05 Models of computation (Turing machines, etc.) (MSC2010)
37B10 Symbolic dynamics
68Q45 Formal languages and automata
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Béal, M.-P.; Perrin, D., (Rosenberg, G.; Salomaa, A., Symbolic Dynamics and Finite Automata. Symbolic Dynamics and Finite Automata, Handbook of Formal Languages, vol. 2 (1997), Springer), (Chapter 10)
[2] Blondel, V. D.; Cassaigne, J.; Nichitiu, C., On the presence of periodic configurations in Turing machines and in counter machines, Theoret. Comput. Sci., 289, 573-590 (2002) · Zbl 1061.68050
[3] M. Blum, W.J. Sakida, On the capability of finite automata in 2 and 3 dimensional space, in: 17th IEEE FOCS Conference, 1977, pp. 147-161; M. Blum, W.J. Sakida, On the capability of finite automata in 2 and 3 dimensional space, in: 17th IEEE FOCS Conference, 1977, pp. 147-161
[4] Bunimovich, L. A.; Troubetzkoy, S., Topological dynamics of flipping Lorentz lattice gas models, J. Stat. Phys., 72, 297-307 (1993) · Zbl 1099.82509
[5] M. Delorme, J. Mazoyer, Pebble Automata. Figures families recognition and universality, Research Report, No 99-32, 1999; M. Delorme, J. Mazoyer, Pebble Automata. Figures families recognition and universality, Research Report, No 99-32, 1999 · Zbl 1011.68055
[6] A. Gajardo, A symbolic projection of Langton’s Ant, in: Discrete Mathematics and Theoretical Computer Science Proceedings, vol. AB, 2003, pp. 57-68; A. Gajardo, A symbolic projection of Langton’s Ant, in: Discrete Mathematics and Theoretical Computer Science Proceedings, vol. AB, 2003, pp. 57-68 · Zbl 1033.37005
[7] Gajardo, A.; Goles, E., Dynamics of a class of ants on a one-dimensional lattice, Theoret. Comput. Sci., 322, 2, 267-283 (2004) · Zbl 1068.68059
[8] Kitchens, B., Symbolic Dynamics (1998), Springer
[9] Kůrka, P., On topological dynamics of Turing machines, Theoret. Comput. Sci., 174, 1-2, 203-216 (1997) · Zbl 0902.68064
[10] Kůrka, P.; Maass, A., Realtime subshifts, Theoret. Comput. Sci., 237, 307-325 (2000) · Zbl 0947.68534
[11] Kůrka, P., Topological and Symbolic Dynamics (2003), Société Mathématique de France: Société Mathématique de France Paris · Zbl 1038.37011
[12] Lind, D.; Marcus, B., An Introduction to Symbolic Dynamics and Coding (1995), Cambridge University Press · Zbl 1106.37301
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.