One Dimensional Cellular Automata (CA)

Input

An initial configuration of a one dimensional cellular automata, a time bound $T$ expressed in unary, a state $q$, and a designated cell $c$ of the bi-infinite lattice.

Problem

Is cell $c$ in state $q$ at time $T$?

Definitions

Each square of the one dimensional bi-infinite lattice is called a site. Each site may take on a finite set of values from an alphabet $\Sigma$, where $|\Sigma| = k$. The range $r$ of each site denotes the number of neighbors to each side of the site that can directly influence it. The variables at each site, denoted $\sigma_i$, take on values based on a local transition rule $\phi : \Sigma^{2r+1} \to \Sigma$, where $\sigma_i(t+1) = \phi(\sigma_{i-r}(t), \sigma_{i-r+1}(t), \ldots, \sigma_{i+r}(t))$. Thus, for a value of $r = 1$, the value of $\sigma_i$ at time $t + 1$ is determined by $\phi(\sigma_{i-1}(t), \sigma_i(t), \sigma_{i+1}(t))$, that is, the values of its two neighbors and itself at time $t$.

Status

$\P$-complete (Lindgren and Nordahl [1], Smith [2], Albert and Culik [3], Greenlaw, Hoover, and Ruzzo [5]).

Remarks

It is well known that one dimensional cellular automata are capable of universal computation, and [5] translates this result into a $\P$-complete decision problem. The reduction to show hardness is from GMSP.

Lindgren and Nordahl [1] construct a universal one dimensional cellular automata from the four tape symbol and seven state universal Turing machine of Minsky [4]. For $r = 1$ ($r = 2$) implying a three (respectively, five) neighbor rule, their construction requires seven (respectively, four) states. Both of these results require periodic background. Using a uniform background, their constructions require nine (five) states for the three (respectively, five) neighbor rule.