Hostname: page-component-78c5997874-ndw9j Total loading time: 0 Render date: 2024-11-05T09:24:49.768Z Has data issue: false hasContentIssue false
  • English
  • Français

The topological entropy of cellular automata is uncomputable

Published online by Cambridge University Press:  19 September 2008

Lyman P. Hurd ,
Jarkko Kari  and
Karel Culik
Lyman P. Hurd
Affiliation:
Laboratory for Plasma Research, University of Maryland, College Park, MD 20742, USA
Jarkko Kari
Affiliation:
Department of Mathematics, University of Turku, 20500 Turku, Finland
Karel Culik
Affiliation:
Department of Computer Science, University of South Carolina, Columbia, SC 29208, USA
Get access Rights & Permissions [Opens in a new window]

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.

Type
Research Article
Information
Ergodic Theory and Dynamical Systems , Volume 12 , Issue 2 , June 1992 , pp. 255 - 265
Copyright
Copyright © Cambridge University Press 1992

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

[1]Berger, R.. The undecidability of the domino problem. Mem. Amer. Math. Soc. 66 (1966).Google Scholar
[2]Coven, E.. Topological entropy of block maps. Proc. Amer. Math. Soc. 78 (1980), 590–594.CrossRefGoogle Scholar
[3]Culik, K. II. On invertible cellular automata. Complex Systems 1 (1987), 1035.Google Scholar
[4]Grünbaum, B. & Shepard, G. C.. Tilings and Patterns (W. H. Freeman and Company: New York, 1987).Google Scholar
[5]Hedlund, G. A.. Transformations commuting with the shift. In: Topological Dynamics, eds, Auslander, J. and Gottschalk, W. G.. (Benjamin: New York, 1968). pp 259–289; Endomorphisms and automorphisms of the shift dynamical system. Math. Syst. Theor. 3 (1969), 320–375.Google Scholar
[6]Hurd, L. P.. Formal language characterizations of cellular automaton limit sets. Complex Systems 1 (1987), 69–80.Google Scholar
[7]Hurd, L. P.. The non-wandering set of a CA map. Complex Systems 2 (1988), 549.Google Scholar
[8]Kaminger, F. P.. The noncomputability of the channel capacity of context-sensitive languages. Inf. Control 17 (1970), 175–182.CrossRefGoogle Scholar
[9]Kari, J.. The nilpotency problem of one-dimensional cellular automata. SIAM J. Comp. submitted.Google Scholar
[10]Lind, D.. Entropies of automorphisms of a topological Markov shift. Proc. Amer. Math. Soc. 99 (1987), 589–595.CrossRefGoogle Scholar
[11]Minsky, M.. Computation: Finte and Infinite Machines (Prentice-Hall: New York, 1967).Google Scholar
[12]Robinson, R. M.. Undecidability and nonperiodicity of tilings of the plane. Invent. Math. 12 (1971), 177–209.CrossRefGoogle Scholar
[13]Walters, P.. An Introduction to Ergodic Theory (Springer: Berlin, 1982).CrossRefGoogle Scholar
[14]Wang, H.. Proving theorems by pattern recognition II Bell System Tech. J. 40 (1961), 1–41.CrossRefGoogle Scholar