Editorial

Selected reviews and topics in cellular automata

Suppose one has an infinite regular system of lattice points in , each capable of existing in various states . Each lattice point has a well defined system of neighbors, and it is assumed that the state of each point at time is uniquely determined by the states of all its neighbors at time . Assuming that at time only a finite set of points are active, one wants to know how the activation will spread. (Stanislaw Ulam 1960)

Cellular automata are regular uniform networks of locally connected finite-state machines. They are discrete systems with non-trivial behaviour. Cellular automata are ubiquitous: they are mathematical models of computation and computer models of natural systems. Cellular automata are interdisciplinary field, whose general goal might be summarized as the quest for theoretical constructs, computational solutions, and practical implementations of novel and powerful models of discrete world.

Cellular automata form theoretical background and, at the same time simulation tools and implementation substrates, of mathematical machines with unbounded memory, discrete theoretical structures, digital physics, and modelling of spatially extended nonlinear systems; massive-parallel computing, language acceptance, and computability; reversibility of computation, graph–theoretic analysis and logic; chaos and undecidability; and evolution, learning, and cryptography. It is almost impossible to find a field of natural and technical sciences, where cellular automata are not used. Cellular automata are ubiquitous.

This special issue is a unique compendium of short reviews written by superstars. All of them are working and actively publishing in cellular automata for last 20–30 years and their papers are considered as iconic works famed by researchers, academicians, and students.

A problem is undecidable whether there is no algorithm to assign an answer ‘yes’ or ‘no’ to each data input. Jarkko Kari gives a marvellous introduction to decidable and undecidable problems in cellular automata. He illustrates the (un)decidability on the titling problems and also analyses (un-)decidability in relation to injective, surjectivity and periodicity, chaoticity, dynamics of global evolution towards fixed points and cycles, and time symmetry.

The automaton is non-deterministic if it takes several possible states being in a given current state. Martin Kutrib overviews computational power non-deterministic cellular automata and specific properties of space- and time-bounded non-determinism. Kutrib's paper is an indispensable source of rigorous comparative analysis of different types of non-determinism and their properties.

Kenichi Morita studies computing aspects of reversibility for over 30 years. In his present paper, he overviews reversible cellular automata in a context of computation. He shows how to design reversible cellular automata, and how to simulate irreversible cellular automata, reversible Turing machines, cyclic tag systems, and reversible logical circuits in the reversible cellular automata.

Ergodic theory studies dynamical systems in terms of their invariant measures. Markus Pivato introduces invariant measures on cellular automata; outlines principle concepts of the ergodic theory of cellular automata; and illustrates the concepts on measurable dynamics, entropy, and algebraic cellular automata.

When two cellular automatists strike a conversation, they briefly chat about Wolfram but then indulge themselves in a long talk about Sutner's computational classification of cellular automata. In his present paper, Klaus Sutner starts with Wolfram classes and Li–Packard classification; then discusses classifications based on short-term evolution, surjectivity, injectivity, and reversibility; and analyses Culik–Yu classification as a mix of global dynamics and decidability. He ends the paper with welcoming thoughts on an automatic classification of cellular automata.

Burton Voorhees introduces the selfing operation, in which an additive cellular automaton acts back on itself to generate a new additive rule. He characterizes the state transition diagrams of the selfing operations. His novel formalizations could inspire unusual developments in the dynamical system studies of the spatially extended discrete systems.

Hiroshi Umeo is a guru in the famous and half-a-century old problem of the firing squad synchronization. A cellular automaton starts its evolution with a single cell in an active, or firing, state and ends its evolution with all cells firing simultaneously. The problem was formulated by John Myhill and Edward Moore, and dozens of solutions were perfected by generations of cellular automatists. Hiroshi Umeo overviews the advanced algorithms of synchronization of 2D cellular arrays and analyses their efficiency and optimality.

Gianluca Tempesti surveys self-replicating loops, starting from von Neumann's original implementation of the Universal Constructor. The survey then covers more than 50 years of research in the domain, focusing first on Langton's loop and its numerous successors, to finish with some of the latest implementations that target more specifically a potential implementation as electronic devices, sometimes by diverting slightly from the pure cellular automata paradigm.

We believe that this totally unique composition of views will attract readers from all walks of life: mathematicians, computer scientists, electronic engineers, physicists, and anyone interested in mathematical theory of discrete nonlinear systems and mathematical machines.