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

DOI10.1007/978-3-031-34034-5_8MaRDI QIDQ6149121zbMATH OpenFDO

Authors Toni Hotanen

Publication date 12 January 2024

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

Full work available at URL https://doi.org/10.1007/978-3-031-34034-5_8

zbMATH Keywords

cellular automatacomputabledecision problementropyLyapunov exponentsTuring machinesundecidable

Mathematics Subject Classification ID

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

Cites work

• Computability of the entropy of one-tape Turing machines
• Distortion in one-head machines and cellular automata
• Dynamics of cellular automata on beta-shifts and direct topological factorizations
• scientific article; zbMATH DE number 5380239 (Why is no real title available?)
• On topological dynamics of Turing machines
• Periodicity and Immortality in Reversible Computing
• Some undecidable problems about the trace-subshift associated to a Turing machine
• The topological entropy of cellular automata is uncomputable
• The transitivity problem of Turing machines

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6149121)