The topological entropy of cellular automata is uncomputable
- 1 June 1992
- journal article
- research article
- Published by Cambridge University Press (CUP) in Ergodic Theory and Dynamical Systems
- Vol. 12 (2) , 255-265
- https://doi.org/10.1017/s0143385700006738
Abstract
There is no algorithm which will take a description of a celluar automaton and determine whether it has zero topological entropy, or for any fixed ε > 0 compute its topological entropy to a tolerance e. Furthermore a set of aperiodic Wang tiles arising from Penrose's kite and dart tiles is used to demonstrate specific examples of cellular automata with a single periodic point but non-trivial non-wandering sets, which furthermore can be constructed to have arbitrarily high topological entropy.Keywords
This publication has 9 references indexed in Scilit:
- Entropies of Automorphisms of a Topological Markov ShiftProceedings of the American Mathematical Society, 1987
- Entropies of automorphisms of a topological Markov shiftProceedings of the American Mathematical Society, 1987
- An Introduction to Ergodic TheoryPublished by Springer Nature ,1982
- Topological entropy of block mapsProceedings of the American Mathematical Society, 1980
- Topological Entropy of Block MapsProceedings of the American Mathematical Society, 1980
- Undecidability and nonperiodicity for tilings of the planeInventiones Mathematicae, 1971
- The noncomputability of the channel capacity of context-sensitive languagesInformation and Control, 1970
- The undecidability of the domino problemMemoirs of the American Mathematical Society, 1966
- Proving Theorems by Pattern Recognition - IIBell System Technical Journal, 1961