
## 2 Cellular Automata And The Majority Problem 2.1 Cellular Automata

CAs are dynamical systems in which space and time are discrete. A standard CA consists of an array of cells, each of which can be in one of a finite number of possible states, updated synchronously in discrete time steps, **according to**
a local, identical transition rule. Here we will only consider boolean automata for which the cellular state s ∈ {0, 1}. The regular cellular array (grid) is ddimensional, where d = 1, 2, **3 is used in practice. For one-dimensional grids, a**
cell is connected to r local neighbors (cells) on either side where r **is referred**
to as the radius (thus, each cell has 2r **+ 1 neighbors, including itself). The**
transition rule **contained in each cell is specified in the form of a rule table,**
with an entry for every possible neighborhood configuration of states. The state of a cell at the next time step is determined by the current states of a surrounding neighborhood of cells. Thus, for a linear CA of radius r **with**
1 ≤ r ≤ N**, the update rule can be written as:**

$$s_{t+1}^{i}=\phi(s_{t}^{i-r}...,s_{t}^{i},...s_{t}^{i+r}),$$

where s t i denotes the state of site i at time t, φ **represents the local transition**
rule, and r **is the CA radius.**
The term configuration **refers to an assignment of ones and zeros to all the**
cells at a given time step. It can be described by st = (s 0 t
, s1 t
, . . . , sN−1 t**), where**
N **is the lattice size. The CAs used here are linear with periodic boundary**
conditions s N+i t = s i t i.e., they are topologically rings.

A global update rule Φ can be defined which applies in parallel to all the cells:

## St+1 **= Φ(**St).

The global map Φ thus defines the time evolution of the whole CA. To visualize the behavior of a CA one can use a two-dimensional space-time diagram, where the horizontal axis depicts the configuration st **at a certain**
time t **and the vertical axis depicts successive time steps, with time increasing** down the page (for example, see figure 1).

## 2.2 The Majority Problem

The density task is a prototypical distributed computational problem for CAs.

For a finite CA of size N it is defined as follows. Let ρ0 **be the fraction of 1s**
in the initial configuration (IC) s0**. The task is to determine whether** ρ0 is greater than or less than 1/**2. In this version, the problem is also known as**