Theory of cellular automata: A survey

https://doi.org/10.1016/j.tcs.2004.11.021Get rights and content
Under an Elsevier user license
open archive

Abstract

This article surveys some theoretical aspects of cellular automata CA research. In particular, we discuss classical and new results on reversibility, conservation laws, limit sets, decidability questions, universality and topological dynamics of CA. The selection of topics is by no means comprehensive and reflects the research interests of the author. The main goal is to provide a tutorial of CA theory to researchers in other branches of natural computing, to give a compact collection of known results with references to their proofs, and to suggest some open problems.

Keywords

Cellular automata
Reversible computation
Decidability
Discrete dynamical system

Cited by (0)

Research supported by the Academy of Finland Grant 54102.