zbMATH — the first resource for mathematics

On topological dynamics of Turing machines. (English) Zbl 0902.68064
Summary: We associate to a Turing machine two dynamical systems which we call Turing machine with moving tape (TMT) and Turing machine with moving head (TMH). TMT are equivalent to generalized shifts of Moore (1990) and they include two-sided full shifts. TMH are shift-commuting maps of two-sided sofic systems. In both classes we characterize systems with the shadowing property, show that a bijective expansive TMT is conjugate to a subshift of finite type and that topological entropy of every TMH is zero. We conjecture that every TMT has a periodic point.

68Q05 Models of computation (Turing machines, etc.) (MSC2010)
Full Text: DOI
[1] Akin, E., The general topology of dynamical systems, (1993), American Mathematical Soc Providence · Zbl 0781.54025
[2] Hanson, J.E.; Crutchfield, J.P., The attractor-basin portrait of a cellular automaton, () · Zbl 0892.58051
[3] Hocking, J.G.; Young, G.S., Topology, (1961), Addison-Wesley Reading, MA · Zbl 0135.22701
[4] Kůrka, P., Regular unimodal systems and factors of finite automata, Theoret. comput. sci., 133, 49-64, (1994) · Zbl 0811.58037
[5] Kůrka, P., A comparison of finite and cellular automata, (), 483-493
[6] Kůrka, P., Simplicity criteria for dynamical systems, (), 189-225
[7] Kůrka, P., Languages, equicontinuity and attractors in cellular automata, Ergod. theory & dyn. system, (1995), to appear · Zbl 0876.68075
[8] Goles, E.; Maass, A.; Martinez, S., On the limit set of some universal cellular automata, Theoret. comput. sci., 110, 53-78, (1993) · Zbl 0774.68085
[9] Moore, Ch., Unpredictability and undecidability in dynamical systems, Phys. rev. lett., 64, 2354-2357, (1990) · Zbl 1050.37510
[10] Smith, A.R., Simple computation-universal cellular spaces, J. ACM, 18, 339-353, (1971) · Zbl 0221.94071
[11] Walters, P., On the pseudo-orbit tracing property and its relationship to stability, (), 231-244
[12] Weiss, B., Subshifts of finite type and sofic systems, Monatsh. math., 77, 462-474, (1973) · Zbl 0285.28021
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.