Undecidability of the topological entropy of reversible cellular automata and related problems

DOI10.1007/978-3-031-34034-5_8MaRDI QIDQ6149121

Toni Hotanen

Publication date: 12 January 2024

Published in: Unconventional Computation and Natural Computation (Search for Journal in Brave)

zbMATH Keywords

entropyTuring machinescellular automataLyapunov exponentsdecision problemcomputableundecidable

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Quantum algorithms and complexity in the theory of computing (68Q12) Other nonclassical models of computation (68Q09) Biologically inspired models of computation (DNA computing, membrane computing, etc.) (68Q07)

Cites Work

• Unnamed Item
• Unnamed Item
• On topological dynamics of Turing machines
• Distortion in one-head machines and cellular automata
• The Transitivity Problem of Turing Machines
• Computability of the entropy of one-tape Turing Machines
• Periodicity and Immortality in Reversible Computing
• The topological entropy of cellular automata is uncomputable
• Dynamics of Cellular Automata on Beta-Shifts and Direct Topological Factorizations

This page was built for publication: Undecidability of the topological entropy of reversible cellular automata and related problems