## Introduction

Since the study of life began, many have asked: is it unique in the universe, or are there other interesting forms of life elsewhere? Before we can answer that question, we should ask others: What makes life special? If we happen across another system with life-like behavior, how would we be able to recognize it? We are speaking, of course, of the mathematical systems of cellular automata, of the fascinating patterns that have been discovered and engineered in Conway’s Game of Life [5, 13], and of the possible existence of other cellular automaton rules with equally complex behavior to that of Life. In an influential early paper [28], Stephen Wolfram proposed an answer to this question of what makes Life special. He categorized cellular automaton rules into four types, according to their behavior when started with random initial conditions.

Wolfram initially intended this classification for one-dimensional cellular automata, but in a later paper [29] he and Packard extended it to the same set of twodimensional automata that we consider here; Adamatzky et al. [1] performed a more detailed classification of some of these automata based on the same principle of studying their behavior on random initial conditions. However, Wolfram’s classification is problematic in more than one way. Although there is some evidence for phase transitions between regions of rule space where one class is more frequent than others [6, 19, 20, 30], the classification depends strongly on the specific behavior of an individual rule, so that one cannot use it to predict which rules are likely to have interesting behavior, but only to describe that behavior after having already observed it. The boundary between classes is less.

### Life-Like Rules

The space of possible cellular automaton rules is infinite and highly varied. One may define cellular automata on grids of high dimensions or neighborhood structures more general than grids. The set of neighbors of a cell may be only those other cells nearest to it in the grid or may fall within a neighborhood larger than the unit radius. The state of a cell may depend only on the states of neighboring cells in the previous time step, or it may depend on the states of neighbors over several previous time steps. The number of states of each cell may be any finite number or even a continuously variable value, and researchers have considered update rules that are asynchronous, randomized, or quantum mechanical.

In a cellular automaton of this type, a single cell may do one of four things within a single time step: If it was dead but becomes alive, we say that it is born. If it was alive and remains alive, we say that it survives. If it was alive and becomes dead, we say that it dies. And if it was dead and remains dead, we say that it is quiescent. We follow a standard convention for naming these cellular automata in which the update rule of the automaton is represented by a rule string, a sequence of characters in the form “Bxxx/Syyy”. The xxx part of the rule string is a subset of the digits from 0 to 8, representing numbers of neighbors such that a dead cell with that many neighbors would become alive in the next time step, causing a birth event: the B stands for birth. The yyy part of the rule string is another subset of digits, representing numbers of neighbors such that a live cell with that many neighbors would remain alive in the next time step, causing a survival event: the S stands for survival. For instance, Conway’s Game of Life itself is represented by the rule string “B3/S23”: a dead cell with three live neighbors leads to a birth event, and a live cell with two or three live neighbors leads to a survival event. All other combinations of cell state and number of neighbors lead to death or quiescence; we do not need to list these combinations separately as they can be inferred from the birth and survival parts of the rule string.

### Natural Evolution or Intelligent Design?

Wolfram’s classification takes the point of view of statistical mechanics, a field that uses probability to study large systems of interacting objects such as the molecules in an ideal gas. Wolfram posits that a typical initial state of the automaton has a 50/50 chance that any given cell is alive or dead, independently of all other cells; he then asks how the automaton behaves when started from this typical state.

### Last word

Often within a random initial state, despite the tiny probability (2−1012 ) that this pattern occurs at any particular location. However, from the practical point of view, the cellular automaton patterns that can be seen to occur randomly and the patterns that can be constructed by human engineering are very different from each other. The patterns arising from random fields in Life, as seen in practice, consist overwhelmingly of small still lifes and small period-two oscillators, with higher-period oscillators such as the period-3 pulsar, period-15 pentadecathlon, and period-8 figure-8 arising much less frequently (once per 20,000, 1.6 million, or 33 million distinct patterns generated in this way, respectively) in experiments performed by Achim Flammenkamp [12]. In contrast, many of the most interesting patterns in Life were formed by human engineering and may combine hundreds of individual patterns that themselves have much higher complexity than the patterns that could ever be seen in random experiments by any human observer. If we seek rules that can support similar patterns, we should use a classification scheme that classifies those rules similarly to Live, regardless of whether they behave similarly on random initial conditions. Consider, for instance, the following Life patterns.