The topological entropy of cellular automata is uncomputable. (English) Zbl 0770.58017

Let \(S\) be a finite set, \(S^ \mathbb{Z}\) the set of all functions \(\mathbb{Z} \to S\) and \(\sigma: S^ \mathbb{Z} \to S^ \mathbb{Z}\) the left shift, i.e. \(\sigma(x)_ i = x_{i+1}\), for all \(i \in \mathbb{Z}\). A cellular automaton is a continuous function \(S^ \mathbb{Z} \to S^ \mathbb{Z}\) which commutes with \(\sigma\). The authors show: (1) There is no algorithm which will take a description of a cellular automaton and determine whether it has zero topological entropy, or for any fixed \(\varepsilon > 0\) compute its topological entropy to a tolerance \(\varepsilon\). (2) An example of a cellular automaton with only one periodic point, having nontrivial non- wandering set and arbitrarily large topological entropy.
Reviewer: J.Ombach (Kraków)


37B99 Topological dynamics
54C70 Entropy in general topology
Full Text: DOI


[1] Grünbaum, Tilings and Patterns (1987)
[2] Culik, Complex Systems 1 pp 1035– (1987)
[3] DOI: 10.2307/2042437 · Zbl 0452.54038
[4] Berger, Mem. Amer. Math. Soc. 66 pp none– (1966)
[5] Wang, Bell System Tech. J. 40 pp 1– (1961)
[6] Walters, An Introduction to Ergodic Theory (1982) · Zbl 0475.28009
[7] Hedlund, Topological Dynamics pp 259– (1968)
[8] Minsky, Computation: Finte and Infinite Machines (1967) · Zbl 0195.02402
[9] Kari, SIAM J. Comp. none pp none– (none)
[10] DOI: 10.2307/2046371 · Zbl 0619.54030
[11] DOI: 10.1016/S0019-9958(70)90533-4 · Zbl 0196.01802
[12] Hurd, Complex Systems 2 pp 549– (1988)
[13] Hurd, Complex Systems 1 pp 69– (1987)
[14] DOI: 10.1007/BF01418780 · Zbl 0197.46801
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.