×

zbMATH — the first resource for mathematics

On the dynamics and recursive properties of multidimensional symbolic systems. (English) Zbl 1168.37002
The paper starts with several definitions such as shift of finite type and sofic shift, in the set theoretical setting. Their dynamics is studied in connection with the dynamics of cellular automata. The cellular automaton is viewed as a continuous transformation \(f:\Sigma^{\mathbb{Z}^d}\mapsto\Sigma^{\mathbb{Z}^d}\) of the full shift which commutes with the shift action. The framework thus defined serves to solve such problems as entropy of the cellular automata, topological dynamics aspects, representation of Turing machines within shifts of finite type, real Turing machines a.o.

MSC:
37B50 Multi-dimensional shifts of finite type, tiling dynamics (MSC2010)
37B15 Dynamical aspects of cellular automata
37B40 Topological entropy
68Q80 Cellular automata (computational aspects)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Berger, R.: The undecidability of the domino problem. Mem. Am. Math. Soc. 66, 72 (1966) · Zbl 0199.30802
[2] Blanchard, F., Maass, A.: Dynamical properties of expansive one-sided cellular automata. Isr. J. Math. 99, 149–174 (1997) · Zbl 0892.58042 · doi:10.1007/BF02760680
[3] Boyle, M., Maass, A.: Expansive invertible onesided cellular automata. J. Math. Soc. Japan 52(4), 725–740 (2000) · Zbl 0970.37012 · doi:10.2969/jmsj/05240725
[4] Boyle, M., Schraudner, M.: Z d shifts of finite type without equal entropy full shift factors. J. Differ. Equ. Appl. (to appear) · Zbl 1161.37021
[5] Burton, R., Steif, J.E.: Non-uniqueness of measures of maximal entropy for subshifts of finite type. Ergodic Theory Dyn. Syst. 14(2), 213–235 (1994) · Zbl 0807.58023 · doi:10.1017/S0143385700007859
[6] Culik II, K., Hurd, L.P., Yu, S.: Computation theoretic aspects of cellular automata. Phys. D 45(1–3), 357–378 (1990); Cellular Automata: Theory and Experiment. Los Alamos, NM (1989) · Zbl 0729.68052
[7] Delvenne, J.-C., Kurka, P., Blondel, V.: Decidability and universality in symbolic dynamical systems. Fundam. Inform. 74(4), 463–490 (2006) · Zbl 1114.03032
[8] Friedland, S.: On the entropy of Z d subshifts of finite type. Linear Algebra Appl. 252, 199–220 (1997) · Zbl 0893.54031 · doi:10.1016/0024-3795(95)00676-1
[9] Hedlund, G.A.: Endormorphisms and automorphisms of the shift dynamical system. Math. Syst. Theory 3, 320–375 (1969) · Zbl 0182.56901 · doi:10.1007/BF01691062
[10] Hochman, M., Meyerovitch, T.: A characterization of the entropies of multidimensional shifts of finite type. Ann. Math. (to appear) · Zbl 1192.37022
[11] Hopcroft, J.E., Ullman, J.D.: Introduction to Automata Theory, Languages, and Computation. Addison-Wesley Series in Computer Science. Addison-Wesley Publishing Co., Reading, MA (1979) · Zbl 0426.68001
[12] Hurd, L.P.: Formal language characterizations of cellular automaton limit sets. Complex Syst. 1(1), 69–80 (1987) · Zbl 0655.68105
[13] Hurd, L.P.: Nonrecursive cellular automata invariant sets. Complex Syst. 4(2), 131–138 (1990) · Zbl 0724.68055
[14] Hurd, L.P., Kari, J., Culik, K.: The topological entropy of cellular automata is uncomputable. Ergodic Theory Dyn. Syst. 12(2), 255–265 (1992) · Zbl 0770.58017 · doi:10.1017/S0143385700006738
[15] Johnson, A., Madden, K.: Factoring higher-dimensional shifts of finite type onto the full shift. Ergodic Theory Dyn. Syst. 25(3), 811–822 (2005) · Zbl 1140.37304 · doi:10.1017/S0143385704000823
[16] del Junco, A.: A simple measure-preserving transformation with trivial centralizer. Pac. J. Math. 79(2), 357–362 (1978) · Zbl 0368.28019
[17] Kari, J.: Rice’s theorem for the limit sets of cellular automata. Theor. Comput. Sci. 127(2), 229–254 (1994) · Zbl 0824.68078 · doi:10.1016/0304-3975(94)90041-8
[18] Kari, J.: Theory of cellular automata: a survey. Theor. Comput. Sci. 334(1–3), 3–33 (2005) · Zbl 1080.68070 · doi:10.1016/j.tcs.2004.11.021
[19] Lind, D.A.: The entropies of topological Markov shifts and a related class of algebraic integers. Ergodic Theory Dyn. Syst. 4(2), 283–300 (1984) · Zbl 0546.58035 · doi:10.1017/S0143385700002443
[20] Mozes, S.: Tilings, substitution systems and dynamical systems generated by them. J. Anal. Math. 53, 139–186 (1989) · Zbl 0745.52013 · doi:10.1007/BF02793412
[21] Myers, D.: Nonrecursive tilings of the plane. II. J. Symb. Log. 39, 286–294 (1974) · Zbl 0299.02055 · doi:10.2307/2272641
[22] Nasu, M.: Textile systems and onesided resolving automorphisms and endomorphisms of the shift. Ergodic Theory Dyn. Syst. 28(1), 167–209 (2008) · Zbl 1171.37308 · doi:10.1017/S0143385707000375
[23] von Neumann, J.: Theory of self-reproducing automata. University of Illinois Press, Urbana, London (1966)
[24] Ornstein, D.S., Weiss, B.: How sampling reveals a process. Ann. Probab. 18(3), 905–930 (1990) · Zbl 0709.60036 · doi:10.1214/aop/1176990729
[25] Quas, A., Scedil;ahin, A.A.: Entropy gaps and locally maximal entropy in \(\mathbb{Z}\) d subshifts. Ergodic Theory Dyn. Syst. 23(4), 1227–1245 (2003) · Zbl 1039.37008 · doi:10.1017/S0143385702001761
[26] Robinson, R.M.: Undecidability and nonperiodicity for tilings of the plane. Invent. Math. 12, 177–209 (1971) · Zbl 0207.51305 · doi:10.1007/BF01418780
[27] Simpson, S.G.: Medvedev degrees of 2-dimensional subshifts of finite type. Preprint, www.math.psu.edu/simpson/papers/2dim.pdf (2007)
[28] Sutner, K.: Universality and cellular automata. In: Machines, Computations, and Universality. Lect. Notes Comput. Sci., vol. 3354, pp. 50–59. Springer, Berlin (2005) · Zbl 1119.68121
[29] Walters, P.: An Introduction to Ergodic Theory. Grad. Texts Math., vol. 79. Springer, New York (1982) · Zbl 0475.28009
[30] Wolfram, S.: Universality and complexity in cellular automata. Phys. D 10(1–2), 1–35 (1984); Cellular Automata. Los Alamos, N.M. (1983)
[31] Zheng, X., Weihrauch, K.: The arithmetical hierarchy of real numbers. MLQ Math. Log. Q. 47(1), 51–65 (2001) · Zbl 0968.03075 · doi:10.1002/1521-3870(200101)47:1<51::AID-MALQ51>3.0.CO;2-W
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.