Universality and complexity in cellular automata
Physica D Nonlinear PhenomenaPublished 1 January 1984
Stephen Wolfram
Citations1,915
SJR quartileQ1
SJR score0.94
SNIP1.39
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
Evidence is presented that all one-dimensional cellular automata fall into four distinct universality classes, and one class is probably capable of universal computation, so that properties of its infinite time behaviour are undecidable.
Abstract
Cellular automata are discrete dynamical systems with simple construction but complex self-organizing behaviour. Evidence is presented that all one-dimensional cellular automata fall into four distinct universality classes. Characterizations of the structures generated in these classes are discussed. Three classes exhibit behaviour analogous to limit points, limit cycles and chaotic attractors. The fourth class is probably capable of universal computation, so that properties of its infinite time behaviour are undecidable.
Keywords
Computer ScienceMathematics
American Journal of Physics<i>The Fractal Geometry of Nature</i>
21,750 Citations1983Benoît B. Mandelbrot, John Wheeler
Mathematics and Computers in SimulationIntroduction to automata theory, languages and computation
10,827 Citations1981
Journal of the Royal Statistical Society Series A (General)Information Theory and Reliable Communication.
5,596 Citations1970P. M. Lee, Robert T. Gallager
This chapter discusses Coding for Discrete Sources, Techniques for Coding and Decoding, and Source Coding with a Fidelity Criterion.
Reviews of Modern PhysicsStatistical mechanics of cellular automata
3,075 Citations1983Stephen Wolfram
Analysis is given of ''elementary'' cellular automata consisting of a sequence of sites with values 0 or 1 on a line, with each site evolving deterministically in discrete time steps according to p definite rules involving the values of its nearest neighbors.
American Mathematical MonthlyComputation: Finite and Infinite Machines.
2,606 Citations1968D. A. Clarke, Marvin Minsky
The abstract theoryas described in this book tells us in no uncertain terms that the machines' potential range is enormous, and that its theoretical limitations are of the subtlest and most elusive sort.
IBM Journal of Research and DevelopmentAlgorithmic Information Theory
1,001 Citations1977Gregory J. Chaitin
In algorithmic information theory the primary concept is that of the information content of an individual object, which is a measure of how difficult it is to specify or describe how to construct or calculate that object.
Mathematical Theory of Computation
685 Citations1972Zohar Manna
This book is a classic text on sequential program verification; it has been widely translated from the original Hebrew and is much in demand among graduate students in the field of computer science.
Mathematical Theory of Computation
641 Citations1991John McCarthy
The goals of this project were the development of logical formalisms for reasoning about programs that use abstractions and reflection, and the application of these theoretical results to selected software problems.
Communications in Mathematical PhysicsAlgebraic properties of cellular automata
418 Citations1984Olivier Martin, Andrew Odlyzko +1 more
Algebraic techniques are used to give an extensive analysis of the global properties of a class of finite cellular automata, and the complete structure of state transition diagrams is derived in terms of algebraic and number theoretical quantities.
Zeitschrift für Naturforschung AInformation Dimension and the Probabilistic Structure of Chaos
246 Citations1982J. Doyne Farmer
The concepts of entropy and dimension as applied to dynamical systems are reviewed from a physical point of view and an algorithm is presented that allows the experimental determination of the information dimension and metric entropy.
Physica D Nonlinear PhenomenaApplications of ergodic theory and sofic systems to cellular automata
136 Citations1984Douglas Lind
It is shown that cellular automata obeying an additive rule are shown to be the same as endomorphisms of a compact abelian group, and therefore their statistical and dynamical behavior can be told exactly by using Fourier analysis and ergodic theory.
Physical review. A, General physicsNew mechanism for deterministic diffusion
76 Citations1983Peter Grassberger
Physica D Nonlinear PhenomenaExploiting regularities in large cellular spaces
49 Citations1984R.Wm. Gosper
A computer algorithm for simulating deterministic cellular automata that grows “smarter” by selectively recording intermediate computations while operating on a compressed representation of the cellular space-time.
Life is universal!
26 Citations1974Robert T. Wainwright
This paper shows how to return the compliment of being programmed to play the game of Life by making Life forms that can imitate computers, and sees that many remarkable consequences follow from the existence of such constructions.