Abstract
We delineate the boundary between decidability and undecidability in the context of one-dimensional cellular automata. The key tool for decidability results are automata-theoretic methods, and in particular decision algorithms for automatic structures, that are inherently limited to dealing with a bounded number of steps in the evolution of a configuration. Undecidability and hardness, on the other hand, are closely related to the full orbit problem: does a given configuration appear in the orbit of another?
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Adamatzky, A.: Identification of Cellular Automata. Taylor & Francis, London (1994)
Amoroso, S., Patt, Y.N.: Decision procedures for surjectivity and injectivity of parallel maps for tesselation structures. Journal of Computer and Systems Sciences 6, 448–464 (1972)
Avigad, J., Harrison, J.: Formally verified mathematics. Comm. ACM 57(4), 66–75 (2014)
Bartholdi, L., Silva, P.V.: Groups defined by automata. CoRR, abs/1012.1531 (2010)
Blumensath, A., Grädel, E.: Automatic structures. In: Proc. 15th IEEE Symp. on Logic in Computer Science, pp. 51–62. IEEE Computer Society Press (1999)
Bryant, R.E.: Graph-based algorithms for boolean function manipulation. IEEE Trans. Computers C-35(8), 677–691 (1986)
Burch, J.R., Clarke, E.M., McMillan, K.L., Dill, D.L., Hwang, J.: Symbolic model checking: 1020 states and beyond. Information and Computation 98(2), 142–170 (1992)
Chang, C.C., Keisler, H.J.: Model Theory. In: Studies in Logic and the Foundations of Mathematics, Elsevier (1990)
Clarke, E., Grumberg, O., Peled, D.: Model Checking. MIT Press (2000)
Cook, M.: Universality in elementary cellular automata. Complex Systems 15(1), 1–40 (2004)
Culik, K., Yu, S.: Undecidability of CA classification schemes. Complex Systems 2(2), 177–190 (1988)
Epstein, D.B.A., Cannon, J.W., Holt, D.F., Levy, S.V.F., Patterson, M.S., Thurston, W.P.: Word Processing in Groups. Jones and Bartlett, Burlington (1992)
Finkel, O.: On decidability properties of one-dimensional cellular automata. Computing Research Repository, abs/0903.4615 (2009)
Garey, M.R., Johnson, D.S.: Computers and Intractability. Freeman (1979)
Grigorchuk, R., Šunić, Z.: Self-Similarity and Branching in Group Theory. In: Groups St. Andrews 2005. London Math. Soc. Lec. Notes, vol. 339. Cambridge University Press (2007)
Grigorchuk, R.R., Nekrashevich, V.V., Sushchanski, V.I.: Automata, dynamical systems and groups. Proc. Steklov Institute of Math. 231, 128–203 (2000)
Harrington, L., Shelah, S.: The undecidability of the recursively enumerable degrees. Bull. Amer. Math. Soc. 6, 79–80 (1982)
Hedlund, G.A.: Endomorphisms and automorphisms of the shift dynamical system. Math. Systems Theory 3, 320–375 (1969)
Huth, M., Ryan, M.: Logic in Computer Science: Modelling and Reasoning about Systems, Cambridge, UP (2000)
Kari, J.: Reversibility of 2D cellular automata is undecidable. Physica D 45, 379–385 (1990)
Kari, J.: The nilpotency problem of one-dimensional cellular automata. SIAM J. Comput. 21(3), 571–586 (1992)
Khoussainov, B., Nerode, A.: Automatic presentations of structures. In: Leivant, D. (ed.) LCC 1994. LNCS, vol. 960, pp. 367–392. Springer, Heidelberg (1995)
Khoussainov, B., Rubin, S.: Automatic structures: overview and future directions. J. Autom. Lang. Comb. 8(2), 287–301 (2003)
Kupferman, O.: Avoiding determinization. In: Proc. 21st IEEE Symp. on Logic in Computer Science (2006)
Kurka, P.: Languages, equicontinuity and attractors in cellular automata. Ergodic Th. Dynamical Systems 17, 417–433 (1997)
Kurka, P.: Topological and Symbolic Dynamics. Number 11 in Cours Spécialisés. Societe Mathematique de France, Paris (2003)
Li, W., Packard, N.: The structure of the elementary cellular automata rule space. Complex Systems 4(3), 281–297 (1990)
Li, W., Packard, N., Langton, C.G.: Transition phenomena in CA rule space. Physica D 45(1-3), 77–94 (1990)
Lind, D.: Multi-dimensional symbolic dynamics. In: Symbolic Dynamics and its Applications. Proc. Sympos. Appl. Math., vol. 60, pp. 61–79. AMS (2004)
Margenstern, M.: Frontier between decidability and undecidability: a survey. TCS 231, 217–251 (2000)
Meyers, R.A. (ed.): Encyclopedia of Complexity and System Science. Springer, Berlin (2009)
Neary, R., Woods, D.: On the time complexity of 2-tag systems and small universal turing machines. In: FOCS, pp. 439–448. IEEE Computer Society, Washington (2006)
Neary, T., Woods, D.: P-completeness of cellular automaton rule 110. In: Bugliesi, M., Preneel, B., Sassone, V., Wegener, I. (eds.) ICALP 2006. LNCS, vol. 4051, pp. 132–143. Springer, Heidelberg (2006)
Nekrashevych, V.: Self-Similar Groups. In: Math. Surveys and Monographs, vol. 117. AMS (2005)
Perrin, D., Pin, J.-E.: Infinite Words. In: Pure and Applied Math., vol. 141, Elsevier, Amsterdam (2004)
Rabin, M.O., Scott, D.S.: Finite automata and their decision problems. IBM Jour. Research 3(2), 114–125 (1959)
Rogers, H.: Theory of Recursive Functions and Effective Computability. McGraw-Hill, New York (1967)
Sacks, G.E.: The recursively enumerable degrees are dense. Ann. Math. 80, 300–312 (1964)
Safra, S.: On the complexity of ω-automata. In: Proc. 29th FOCS, pp. 319–327. IEEE Computer Soc. Press, Washington (1988)
Sakarovitch, J.: Elements of Automata Theory. Cambridge University Press (2009)
Soare, R.I.: Recursively Enumerable Sets and Degrees. In: Perspectives in Mathematical Logic. Springer, Berlin (1987)
Sutner, K.: A note on Culik-Yu classes. Complex Systems 3(1), 107–115 (1989)
Sutner, K.: Classifying circular cellular automata. Phys. D 45(1-3), 386–395 (1990)
Sutner, K.: De Bruijn graphs and linear cellular automata. Complex Systems 5(1), 19–30 (1991)
Sutner, K.: Cellular automata and intermediate degrees. Theoretical Computer Science 296, 365–375 (2003)
Sutner, K.: Universality and cellular automata. In: Margenstern, M. (ed.) MCU 2004. LNCS, vol. 3354, pp. 50–59. Springer, Heidelberg (2005)
Sutner, K.: Encyclopedia of Complexity and System Science, chapter Classification of Cellular Automata. In: Meyers [31] (2009)
Sutner, K.: Model checking one-dimensional cellular automata. J. Cellular Automata 4(3), 213–224 (2009)
Sutner, K.: Cellular automata, decidability and phasespace. Fundamenta Informaticae 140, 1–20 (2010)
Sutner, K., Lewi, K.: Iterating invertible binary transducers. In: Kutrib, M., Moreira, N., Reis, R. (eds.) DCFS 2012. LNCS, vol. 7386, pp. 294–306. Springer, Heidelberg (2012)
Vorhees, B.: Computational Analysis of One-Dimensional Cellular Automata. World Scientific, Singapore (1996)
Wolfram, S.: Computation theory of cellular automata. Comm. Math. Physics 96(1), 15–57 (1984)
Wolfram, S.: Twenty problems in the theory of cellular automata. Physica Scripta T9, 170–183 (1985)
Wolfram, S.: A New Kind of Science. Wolfram Media, Champaign (2002)
Wuensche, A.: Classifying cellular automata automatically. Complexity 4(3), 47–66 (1999)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this chapter
Cite this chapter
Sutner, K. (2015). Linear Cellular Automata and Decidability. In: Adamatzky, A. (eds) Automata, Universality, Computation. Emergence, Complexity and Computation, vol 12. Springer, Cham. https://doi.org/10.1007/978-3-319-09039-9_12
Download citation
DOI: https://doi.org/10.1007/978-3-319-09039-9_12
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-09038-2
Online ISBN: 978-3-319-09039-9
eBook Packages: EngineeringEngineering (R0)