The topological entropy of cellular automata is uncomputable

DOI10.1017/S0143385700006738zbMath0770.58017WikidataQ62045996 ScholiaQ62045996MaRDI QIDQ4024954

Karel II Culik, L. P. Hurd, Jarkko Kari

Publication date: 18 February 1993

Published in: Ergodic Theory and Dynamical Systems (Search for Journal in Brave)

zbMATH Keywords

cellular automatatopological entropycomputability

Mathematics Subject Classification ID

Topological dynamics (37B99) Entropy in general topology (54C70)

Related Items (28)

Observation of nonlinear systems via finite capacity channels: constructive data rate limits ⋮ A Characterization of Cellular Automata Generated by Idempotents on the Full Shift ⋮ Directional Metric Entropy and Lyapunov Exponents for Dynamical Systems Generated by Cellular Automata ⋮ Quasi-periodic configurations and undecidable dynamics for tilings, infinite words and Turing machines ⋮ Computability of topological entropy: from general systems to transformations on Cantor sets and the interval ⋮ Multidimensional cellular automata: closing property, quasi-expansivity, and (un)decidability issues ⋮ A complete proof that square ice entropy is ⋮ On computing the Lyapunov exponents of reversible cellular automata ⋮ On computing the entropy of cellular automata. ⋮ Undecidability of the topological entropy of reversible cellular automata and related problems ⋮ Computability of entropy and information in classical Hamiltonian systems ⋮ Dynamics and topological entropy of 1D Greenberg–Hastings cellular automata ⋮ Effect of quantified irreducibility on the computability of subshift entropy ⋮ On the entropy of \(\mathbb{Z}^d\) subshifts of finite type ⋮ Computing topological entropy in a space of quartic polynomials ⋮ A characterization of the entropies of multidimensional shifts of finite type ⋮ Sensitive dependence on initial conditions for cellular automata ⋮ Theory of cellular automata: a survey ⋮ Embeddings of dynamical systems into cellular automata ⋮ Topological and measure-theoretic properties of one-dimensional cellular automata ⋮ Complexity of Compact Proofreading for Self-assembled Patterns ⋮ On the topological directional entropy ⋮ On the dynamics and recursive properties of multidimensional symbolic systems ⋮ Chaotic properties of elementary cellular automata with majority memory ⋮ Theory of computation of multidimensional entropy with an application to the monomer-dimer problem ⋮ C0-stability of topological entropy for contactomorphisms ⋮ Attractors of linear cellular automata ⋮ Decidability and undecidability in cellular automata

Cites Work

• Unnamed Item
• Unnamed Item
• Undecidability and nonperiodicity for tilings of the plane
• Entropies of Automorphisms of a Topological Markov Shift
• Topological Entropy of Block Maps
• The noncomputability of the channel capacity of context-sensitive languages

This page was built for publication: The topological entropy of cellular automata is uncomputable