Rice's theorem for the limit sets of cellular automata
From MaRDI portal
Publication:1342233
DOI10.1016/0304-3975(94)90041-8zbMath0824.68078OpenAlexW2008835979WikidataQ62045984 ScholiaQ62045984MaRDI QIDQ1342233
Publication date: 11 January 1995
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0304-3975(94)90041-8
Related Items
Number-conserving cellular automata I: Decidability., Solution of some conjectures about topological properties of linear cellular automata, On ergodic linear cellular automata over Zm, Infinite traces and symbolic dynamics, Growing patterns in 1D cellular automata, On dynamical complexity of surjective ultimately right-expansive cellular automata, The relationships of three elementary cellular automata, Quasi-periodic configurations and undecidable dynamics for tilings, infinite words and Turing machines, A complete and efficiently computable topological classification of D-dimensional linear cellular automata over Z m, Statistical mechanics of surjective cellular automata, Decidable characterizations of dynamical properties for additive cellular automata over a finite abelian group with applications to data encryption, Number conserving cellular automata. II: Dynamics., Characterisation of limit measures of higher-dimensional cellular automata, Arithmetical complexity of the language of generic limit sets of cellular automata, A complete and efficiently computable topological classification of D-dimensional linear cellular automata over \(Z_{m}\), Realization problems for nonuniform cellular automata, An efficiently computable characterization of stability and instability for linear cellular automata, \(\mu\)-limit sets of cellular automata from a computational complexity perspective, Nondeterministic cellular automata, Rice’s Theorem for μ-Limit Sets of Cellular Automata, Dynamical behavior of additive cellular automata over finite abelian groups, A search algorithm for subshift attractors of cellular automata, Kolmogorov complexity and cellular automata classification, On the undecidability of the limit behavior of cellular automata, Sensitive dependence on initial conditions for cellular automata, Theory of cellular automata: a survey, The work of Mike Hochman on multidimensional symbolic dynamics and Borel dynamics, Topological and measure-theoretic properties of one-dimensional cellular automata, Nilpotency and periodic points in non-uniform cellular automata, On the dynamics and recursive properties of multidimensional symbolic systems, Additive one-dimensional cellular automata are chaotic according to Devaney's definition of chaos, Additive Cellular Automata Over Finite Abelian Groups: Topological and Measure Theoretic Properties, On the directional dynamics of additive cellular automata, A second step towards complexity-theoretic analogs of Rice's Theorem, Ergodicity, transitivity, and regularity for linear cellular automata over \(\mathbb{Z}_m\), Classification of sofic projective subdynamics of multidimensional shifts of finite type, The mirage of universality in cellular automata, A new dimension sensitive property for cellular automata, Attractors of linear cellular automata, Freezing, Bounded-Change and Convergent Cellular Automata, Decidability and undecidability in cellular automata, Computation theoretic aspects of cellular automata, Formal languages and global cellular automaton behavior
Cites Work
