\documentstyle[12pt]{article} % Specifies the document style. \textwidth=6.5in \textheight=8.75in \oddsidemargin=0in \evensidemargin=0in \topmargin=-0.50in \flushbottom \newcommand{\Cx}{\mbox{C$\!\!\!$\rule[0.03ex]{0.13em}{1.35ex}$\;$}} \newcommand{\Rl}{\mbox{R$\!\!\!\!$\rule[-0.05ex]{0.20em}{1.5ex}$\:\:$}} \newcommand{\It}{\mbox{Z$\!\!\!\!\!$Z$\:$}} \newcommand{\Na}{\mbox{N$\!\!\!\!$\rule[-0.05ex]{0.17em}{1.5ex}~}} \def\C{{\rm\kern.24em \vrule width.02em height1.4ex depth-.05ex \kern-.26em C}} \def\R{{\rm I\kern-.20em R}} \def\F{{\rm I\kern-.20em F}} \def\Z{{\rm\kern.26em \vrule width.02em height0.5ex depth0ex \kern.04em \vrule width.02em height1.47ex depth-1ex \kern-.34em Z}} \def\N{{\rm I\kern-.20em N}} \def\Q{{\rm\kern.24em \vrule width.02em height1.4ex depth-.05ex \kern-.26em Q}} \newcommand{\NN}{{\bf N}} \newcommand{\ZZ}{{\bf Z}} \newcommand{\RR}{{\bf R}} \newcommand{\CC}{{\bf C}} \newcommand{\QQ}{{\bf Q}} \newcommand{\half}{\mbox{$\frac{1}{2}$}} \newcommand{\beq}{\begin{equation}} \newcommand{\eeq}{\end{equation}} \begin{document} \baselineskip=20pt \pagestyle{plain} \title{ Stable, Multi-State, Time-Reversible \\ Cellular Automata with Rich \\ Particle Content } \author{ Mark J. Ablowitz \hspace{0.5cm} James M. Keiser \hspace{0.5cm} Leon A. Takhtajan\thanks{ On leave of absence from Leningrad Department of V.A. Steklov Mathematical Institute, 191011 Leningrad, USSR.} \\ Program in Applied Mathematics\\ University of Colorado\\ Boulder, CO 80309 } \date{ } \maketitle \begin{center}{\bf Abstract} \end{center} \begin{quote} We discuss a new class of stable multi-state Cellular Automata (CA). The CA significantly extends the two-state, time-irreversible CA proposed by Park, Steiglitz, and Thurston by providing for arbitrary numbers of states as well as time-reversibility. These new CA are dynamical systems possessing an enormous array of coherent particle-like structures. The particle interaction picture is surprisingly rich and includes particle production as well. \end{quote} \section{Introduction} In the last 20 years, there has been a significant increase in the number of researchers who have studied the properties of Cellular Automata (CA) and their applications to the physical sciences (see \cite{nav1} through \cite{wolf1} for models and \cite{wolf2} and \cite{alamos1} for collections of CA papers). Cellular automata have their origins in the work of John von Neumann and his studies of atmospheric models and are discussed in his seminal work on self-reproducing automata \cite{jvn1}. From a general point of view, CA's can be viewed as totally discrete dynamical systems--space, time and field variables are all measured in integral units. In this paper, we recall the notion of a Filter Automata (FA), and examine a particular FA called the Parity Rule Filter Automata (PRFA) presented by Park, et. al. in \cite{prfa1} and \cite{prfa2}. This automata is particularly interesting because given localized initial data, subsequent evolution of the automata yields a remarkable number of coherent structures or `particles'. The PRFA is a two-state, time-irreversible automata: each spatial position can take on two values (e.g. 0 or 1) and the time evolution of the model is in a sense diffusive (i.e. information is lost). These restrictions on the model led us to a reformulation of the original PRFA in terms of which allows extension to an arbitrary number of states. The time evolution of the DE is then analyzed, and we observe that the time-irreversibility is due to a certain coefficient in the reformulated difference equation. Remarkably, by simply removing this coefficient we solve the problem of reversibility, yielding a time-reversible, multi-state automata which preserves all the particles of the original PRFA while introducing numerous others. \section{Cellular Automata} A Cellular Automata (CA) is a totally discrete evolution rule of the form \begin{equation} \label{ca1} X^{t+1} = {\cal F}(X^t) \end{equation} \noindent where \begin{description} \item $X^t \equiv \{ x_i^t \}$ is the entire state at time $t$, \item[ ] $x_i^t \in \{0, 1, 2, \ldots, k - 1\}$ is the quantity, or field value, at position $i$, \item[ ] $i \in \It^n$ is the spatial position, \item[ ] $n \in \It$ is the spatial dimension of the system, \item[ ] $k \in \It$ is the number of states each spatial position can take on. \end{description} The equations of motion are given symbolically by ${\cal F}( \cdot )$, which is in general a set of rules or equations taking the `state' at time $t$ into the new state at time $t+1$. Symbolically, in one dimension, $n = 1$, we have \vspace{0.1in} \begin{flushleft} \hspace{1.0in}$t: \hspace{1.128in} x_{-\infty} \hspace{0.75in} \underbrace{\ldots x_{i-1}\hspace{0.05in} x_i \hspace{0.05in} x_{i+1} \ldots} \hspace{0.75in} x_{\infty}$ $\hspace{4.04in} \downarrow {\cal F}(\cdot) $ \hspace{1.0in}$t+1: \hspace{2.55in} x_i$ \end{flushleft} \vspace{0.25in} The parameters $n$ and $k$ are fixed for a single evolution and are typically given by $n$ = 1, 2, or 3 and $k \ge 2$. We note, for future reference, that the general CA rule (\ref{ca1}) is a {\it temporally explicit} rule: $X^{t+1}$ is a function of only $X^t$. A popular example of a CA is given by John Conway's {\it Game of Life} \cite{life1}. This is a two dimensional, two state cellular automata, i.e. $n = k = 2$ so that for all $t$, \[ x_{i,j}^t = \left\{ \begin{array}{ll} 0 & \mbox{ `dead' } \\ 1 & \mbox{ `alive' } \end{array} \right. \] \noindent The rule ${\cal F}( \cdot )$ is a function of the 8 element (von Neumann) neighborhood ${\cal N}$ given by the nearest and next-nearest neighbors: \begin{center} \begin{tabular}{|c|c|c|} \hline \hspace{0.25in} & \hspace{0.25in} & \hspace{0.25in} \\ \hline & $x_{i,j}^t$ & \\ \hline & & \\ \hline \end{tabular} \end{center} The Rule is: \begin{description} \item [1.] $x_{i,j}^{t+1} = 1$ if \begin{description} \item[ a.] $x_{i,j}^t = 0$ and there are exactly 3 living cells in ${\cal N}$ \item[ ] or \item[ b.] $x_{i,j}^t = 1$ and there are 2 or 3 living cells in ${\cal N}$ \end{description} \item [2.] $x_{i,j}^{t+1} = 0$ if \begin{description} \item[ a.] $x_{i,j}^t = 0 \mbox{ or } 1$ and there are less than 2 or more than 3 living cells in ${\cal N}$ \end{description} \end{description} The interest in this model rests in the fact that there are a number of stable structures which are either stationary or propagate in some periodic fashion. A number of these structures are shown in Figure 1. The `Block' and `Loaf' are stationary, stable structures which have period 1 and displacement zero: at each time step, the particle repeats itself, identically, and does not move in the $i$ or $j$ direction. The `Blinker' has a period of 2 and a displacement of 0. The simplest nontrivial example of particle-like motion is the `Glider'. After 4 time steps, this `particle' moves 1 position in both the $i$ and $j$ directions: $p = 4$ and $d_i = d_j = 1$. In \cite{life2}, a statistical mechanics analysis of the game of Life was presented. \begin{center} {\bf Block} \begin{tabular}{|c|c|}\hline 1 & 1 \\ \hline 1 & 1 \\ \hline \end{tabular} \hspace{1.0in} {\bf Loaf} \begin{tabular}{|c|c|c|c|}\hline & 1 & 1 & \\ \hline 1 & & & 1 \\ \hline & 1 & 1 & \\ \hline \end{tabular} \end{center} \vspace{0.2in} \begin{center} {\bf Blinker} \begin{tabular}{|c|c|c|}\hline & & \\ \hline 1 & 1 & 1 \\ \hline & & \\ \hline \end{tabular} \hspace{0.5in} \begin{tabular}{|c|c|c|}\hline \hspace{0.125in} & 1 & \hspace{0.125in} \\ \hline & 1 & \\ \hline & 1 & \\ \hline \end{tabular} \end{center} \vspace{0.2in} \begin{center} {\bf Glider} \hspace{0.1in} $p = 4$ \hspace{0.1in} $d_x = d_y = 1$ \end{center} \begin{center} \begin{tabular}{|c|c|c|c|}\hline & 1 & & \hspace{0.125in} \\ \hline & & 1 & \\ \hline 1 & 1 & 1 & \\ \hline & & & \\ \hline \end{tabular} \hspace{0.1in} \begin{tabular}{|c|c|c|c|}\hline & & & \hspace{0.125in} \\ \hline 1 & & 1 & \\ \hline & 1 & 1 & \\ \hline & 1 & & \\ \hline \end{tabular} \hspace{0.1in} \begin{tabular}{|c|c|c|c|}\hline & & & \hspace{0.125in} \\ \hline & & 1 & \\ \hline 1 & & 1 & \\ \hline & 1 & 1 & \\ \hline \end{tabular} \hspace{0.1in} \begin{tabular}{|c|c|c|c|}\hline \hspace{0.125in} & & & \\ \hline & 1 & & \\ \hline & & 1 & 1 \\ \hline & 1 & 1 & \\ \hline \end{tabular} \hspace{0.1in} \begin{tabular}{|c|c|c|c|}\hline \hspace{0.125in} & & & \\ \hline & & 1 & \\ \hline & & & 1 \\ \hline & 1 & 1 & 1 \\ \hline \end{tabular} \end{center} \begin{center} {\bf Figure 1.} Particles in Life. \end{center} There are examples of CA's which model fluid-type flows, including models of the Navier-Stokes equations (see \cite{nav1} through \cite{nav4}). We note that Boghosian and Levermore introduced a CA model of Burgers equation \cite{brg1}, which was further analyzed in the work of Lebowitz, et. al. in \cite{brg2}. Other types of models include applications to diffusive equations (e.g. \cite{green}), biological and chemical reactive systems. An example of the later is given in \cite{bz1}, where a CA which qualitatively models the Belousov-Zhabotinskii reaction is described. Additionally, there are {\it solitonic} models, of which the present work is an example; see also \cite{prfa1} through \cite{sol2}. For a review of solitons and their applications, see \cite{abl} and \cite{fadtak}. \section{Filter Automata} Let us recall that CA's are temporally explicit, evolution rules of the form \[X^{t+1} = {\cal F}(X^t). \] \noindent To add one level of generalization, we now introduce the temporally implicit evolution rule \begin{equation} \label{fa1} X^{t+1} = {\cal G}(X^t,X^{t+1}). \end{equation} We call rules of this form Filter Automata (FA), in order to distinguish from the more traditional definition of a CA. ${\cal G}( \cdot )$ in equation (\ref{fa1}) is a set of rules or equations which operates on the old state and {\it recently} computed elements of the new state. In order to calculate a new state a canonical direction (i.e. a direction of sweep) and the notion of boundary conditions are imposed on the FA. \section{Parity Rule Filter Automata} As a particular form of an FA, let us consider the so-called Parity Rule Filter Automata (PRFA), introduced by Park, Steiglitz, and Thurston, \cite{prfa1} and \cite{prfa2}. The PRFA is one-dimensional and two-state ($n = 1, k = 2$) given by the following rule (i.e. ${\cal G(\cdot)}$ is given by) \begin{equation} \label{prfa11} x_i^{t+1} = \left\{ \begin{array}{ll} 1 & \mbox{ if } S_{i,2}^t \mbox{ is even and nonzero} \\ 0 & \mbox{ if } S_{i,2}^t \mbox{ is odd or zero} \end{array} \right. \end{equation} \noindent where \begin{equation} \label{prfa12} S_{i,2}^t = \sum_{j = 1}^{r} x_{i - j}^{t + 1} + \sum_{j = 0}^{r} x_{i + j}^{t} \end{equation} \noindent and $r \ge 1$ is an integer parameter called the {\it radius}, which is assumed fixed for each evolution. The properties of the PRFA in this form has been extensively studied by Goldberg in \cite{gold1}. As previously mentioned, a canonical direction must be introduced so as to provide the implicit rule with newly computed elements of the state $X^{t+1}$. This is given by the following neighborhood of interaction: \vspace{0.25in} \begin{center} \begin{tabular}{ccrl} $t$ & \hspace{0.1in} & & \fbox{$x_i^t$ \hspace{0.1in} $x_{i+1}^t$ $\ldots$ $x_{i+r}^t$} \\ $t+1$ & \hspace{0.1in} & \fbox{$x_{i-r}^{t+1}$ $\ldots$ $x_{i-1}^{t+1}$} & $x_i^{t+1}$ \\ \end{tabular} \vspace{0.25in} {\bf Direction of Sweep $\longrightarrow$} \end{center} Additionally, boundary conditions are specified; we impose zeros sufficiently far to the left, i.e. for all $t$: \[ x_i = 0 \hspace{1.5in} -\infty < i < M \] \noindent for some $M$. This way the lower left branch in the above neighborhood (i.e. time $t+1$) does not contribute to the sum in equation (\ref{prfa12})--the first contributions to this sum come from the first non-zero element that enters the top right branch of the neighborhood (i.e. time $t$). An important observation is that given random initial conditions, a significant amount of diffusion, or filtering, takes place, resulting in the production of a number of stable, periodic structures, or particles. This is indicated in Figure 2. Isolated examples of these particles are given in Figures 3a,b. As indicated in this figure, we can associate with each particle a velocity, given by \[ Velocity = \frac{Displacement}{Period}. \] \vspace{0.25in} \baselineskip=10pt \begin{center} \begin{scriptsize} \begin{verbatim} 11 1 1 1 11 11 1 1111 1 11111 111 11 111 11 111 1 1111 11 111 1 11 1 1 1 1 1 1 1 111 1111 1 11 11 1 11111 1 1 1 1 11 11111111 1 11 1 1 1 1111 1 1 1 1 11 11 1 11111 11 11 1 1 111 1111 111 1 1 1 11 1 11 11 11 11 1 1 11 111 1 1 11 11 1 1 1 11 1 11 111 111 11111 1 111 11 1 1 1 1 1 111 11 1 1 11111111111111 1 11 11 1 1 1 1 1 1 11 111 11 111 111 111 1 1111 1 1 11 1 11 11 1 1 1 11 1 1 1 11 11 11 11 1 11 1111 1 111 1 1 1 11 11 1 1 1 111 111 11111 11 1 1 1 111 1 1 11 11 11 11 11 1 111 1 11 1 1 11 1 11 111 111 11111 1 1 11 11 1 111 1 1 1 11 1 1 1 1 1 1 11111 1 1 1 1 1 11 11 1 1 1 111 1 1 1 111 111 11 111 1 11 1 1 11 1 1 1 11111 1 1 11 1 111 1 1 1 11 1 1111 1 1 11 1 1 1 11 11 1 1 1 111 11 1 11 1 111 1 1 111 1 11 1 1 11 1 1 1111 11 1 1 11 1 111 1 1 1 11 11 1 111 1 1 1 1 11 11 1 1 1 111 1 11 11 1 1 1 1 111 1 11 1 1 11 1 11111 11 11 1 1 \end{verbatim} \end{scriptsize} \begin{center} {\bf Figure 2.} $r = 3$ Random initial conditions. \end{center} \end{center} \baselineskip=20pt The mechanism which causes the diffusion can be traced to the existence of special states in the evolution, namely an $r+1$ contiguous sequence of cells--which we call a {\it prenull}. In one time step this isolated string evolves to the trivial state. This is indicated by the somewhat non-trivial example shown in Figure 4. \baselineskip=10pt \newpage \begin{center} \begin{verbatim} 1111 11 1 111 1 11 111111 11 1 1111 1 1 1 1 1 1 11 111111 11 1 1111 11 1 11 1 1 11 111111 11 1 1111 1 1 111 1 1 1 11 111111 11 1 1111 11 11 1 1 1 11 111111 11 1 1111 1 1 1 11 11 1 11 111111 11 1 1111 11 1 111 1 11 111111 11 1 1111 1 1 1 1 1 1 11 111111 11 1 1111 11 1 11 1 1 11 111111 11 1 1111 1 1 111 1 1 1 11 111111 11 1 \end{verbatim} \vspace{0.1in} \begin{flushleft} $ v = \frac{2}{1} = 2 \hspace{1.0in} v = \frac{2}{2} = 1 \hspace{0.6in} v = \frac{6}{6} = 1 \hspace{1.4in} v = \frac{0}{1} = 0 $ \end{flushleft} \vspace{0.1in} \begin{center} {\bf Figure 3a.} $r = 3, k = 2$ typical particles. \end{center} \vspace{0.25in} \begin{verbatim} 111111 11 1 11 111111 1 11 11 1 111111 1 11 11 111111 11 1 1 111111 1 1 1 1 1 111111 1 11 1 11 111111 11 11 11 1 111111 1 11 1 1 1 111111 11 1 11 111111 1 11 11 1 111111 1 11 11 \end{verbatim} \vspace{0.1in} \begin{flushleft} $ v = \frac{4}{1} = 4 \hspace{1.6in} v = \frac{22}{8} = 2.75 \hspace{1.4in} $ \end{flushleft} \vspace{0.1in} \begin{center} {\bf Figure 3b.} $r = 5$ typical particles. \end{center} \end{center} \baselineskip=20pt \begin{center} \baselineskip=10pt t = 0 000000001100100000000 t = 1 000000100000000000000 t = 2 000000000000000000000 \baselineskip=20pt \begin{center} {\bf Figure 4.} Evolution of an $r = 3$ prenull--diffusion in action. \end{center} \end{center} Reversibility means that each state has a unique predecessor and can be recovered. Here we find that sweeping from the right should recover our previous state. However, it is clear that from the trivial state, $t = 2$ in Figure 4, we cannot reproduce the prenull state shown at $t = 1$. It is this behavior of prenulls that forces the PRFA to become time-irreversible. In the PRFA, there are numerous particles with different velocities, hence interactions can occur. Two interactions are shown in Figures 5a,b. Figure 5a, depicts the interaction of two initially well-separated particles. The left and right non-trivial strings would evolve in isolation as independent particles: \begin{center} Left: p = 6 d = 6 v = 1 \hspace{1.0in} Right: p = 3 d = 5 v = 1.666 \end{center} \noindent The interaction is non-solitonic since the state which evolves after the interaction is considered a single periodic particle with $p = 6, d = 6, v = 1$. Figure 5b is an example of a solitonic interaction. A solitonic interaction is one in which two particles interact, and emerge unchanged with the faster particle to the left of the slower particle. Observe that the slower particle has been retarded and the faster particle advanced relative to the positions each would have had if it evolved in isolation. These so-called `phase shifts' are an additional characteristic of solitonic interactions. \newpage \baselineskip=10pt \begin{center} \begin{verbatim} 1 111 1 11 1 1 1 111 1 11 1 11 1 111 1 1 1 11 11 1 1 111 1 11 11 11 1 1 111 1 11 1 1 1 111 1 11 1 11 1 111 1 1 1 1 1 11 1 11 1 1 1 11 1 1 1 1 1 1 1 1 111 1 1 1 11 11 1 1 1 1 1 11 1 1 1 1 111 1 1 1 11 1 1 1 1 1 1 1 1 111 1 1 1 11 11 1 1 1 \end{verbatim} \begin{center} {\bf Figure 5a.} $r = 3$ Non-solitonic interaction. \end{center} \vspace{1.0in} \begin{verbatim} 1 1 1111 1 1 1111 1 1 1111 1 1 1111 1 1 1111 1 1 1111 1 1 1111 1 1 1 11 1 1 11 1 1 1 1111 1 1 1111 1 1 1111 1 1 1111 1 1 1111 1 1 1111 1 1 1111 1 1 1111 1 1 1111 1 1 1111 1 1 1111 1 1 1111 1 1 \end{verbatim} \begin{center} {\bf Figure 5b.} $r = 3$ Solitonic interaction. \end{center} \end{center} \baselineskip=20pt \newpage \section{Fast Rule Theorem} Given the form of the PRFA as given by equations (\ref{prfa11}) and (\ref{prfa12}), the analytical properties of such an interesting model can be difficult to determine. An alternative rule, the so-called Fast Rule Theorem (FRT), \cite{frt1} allows considerable analytical progress. The FRT is entirely equivalent to the PRFA, it is a geometrical rule (emphasizing the relationships between, as opposed to the values of, cells), and provides for a temporally explicit reformulation of the implicit PRFA. The FRT is given by \begin{equation} \label{frt1} x_{i-r}^{t+1} = \left\{ \begin{array}{ll} x_i^t & \mbox{ if } i \not\in B(t) \\ (x_i^t - 1) \mbox{ mod } 2 & \mbox{ if } i \in B(t). \end{array} \right. \end{equation} \noindent where $B(t)$ is a special set of cells defined at each time step by the following \begin{description} \item[(i)] Sweeping from the left, place the index (spatial coordinate) of the first non-zero site among $x^t$ in $B(t)$ ; \item [(ii)] In increments of $r+1$, place $i + r + 1$ in $B(t)$, if there is at least one non-zero $x_i^t$ in the $r$ sites to the right of the current index in $B(t)$; \item [(iii)] If there are $r$ zero consecutive values of $x_i^t$ to the right of the current index in $B(t)$, go on to the next non-zero $x_i^t$, place the corresponding index in $B(t)$, and repeat steps {\bf (ii)-(iii)}. \end{description} The FRT provides a simple, geometric formula which can be used to prove such results as \begin{description} \item[1. ] Stability \cite{frt1}, \item[2. ] Solitonic interactions of simple particles (period 1 and basic strings) \cite{frt2}, and \item[3. ] Systematic construction of periodic particles, \cite{frt3} and \cite{frt4}. \end{description} As an example of the application of the FRT to the evolution of the PRFA, we perform steps {\bf (i)-(iii)} for a particular initial condition, shown in Figure 6. In Figure 7 we evolve a prenull one time step. With the FRT, it becomes quite obvious how the prenull evolves; a 1 in a boxsite, followed by $r$ zeros becomes the trivial state. \vspace{0.75in} \begin{center} \baselineskip=10pt \begin{tabular}{cccccccccccccccc} 0&0&0&0&0&0&$\fbox{1}$&0&0&1&$\fbox{1}$&1&0&0&$\fbox{0}$&0 \\ 0&0&0&0&0&0&$\fbox{1}$&0&1&0&$\fbox{0}$&1&0&0&$\fbox{0}$&0 \\ 0&0&0&0&0&$\fbox{1}$&0&1&1&$\fbox{0}$&0&1&0&$\fbox{0}$&0&0 \\ 0&0&0&0&$\fbox{1}$&1&1&0&$\fbox{1}$&0&1&0&$\fbox{0}$&0&0&0 \\ 0&0&$\fbox{1}$&1&0&0&$\fbox{0}$&1&0&1&$\fbox{0}$&0&0&0&0&0 \\ $\fbox{1}$&0&0&1&$\fbox{1}$&0&1&1&$\fbox{0}$&0&0&0&0&0&0&0 \\ $\fbox{1}$&0&0&1&$\fbox{1}$&1&0&0&$\fbox{0}$&0&0&0&0&0&0&0 \end{tabular} \baselineskip=20pt \end{center} \begin{center} {\bf Figure 6.} $r = 3$ Evolution of a periodic particle. Boxsites are indicated. \end{center} We will now define a prenull using the idea of boxsites: A {\it {\bf prenull}} is a basic string ($r+1$ cells) which consists of a 1 in a boxsite followed by $r$ zeros. \begin{center} \baselineskip=10pt \begin{tabular}{ccccccccc} & & & &$\fbox{1}$&0&0&0&0 \\ 0&0&0&0&0&0&0&0&0 \end{tabular} \baselineskip=20pt \end{center} \begin{center} {\bf Figure 7.} $r = 3$ Evolution of a prenull. \end{center} \section{Multi-State, Time-Irreversible Rules} An extension of the PRFA to $k-$states is possible. Let us define a $k$-delta function: \begin{equation} \label{del1} \delta_k(x) = \left\{ \begin{array}{ll} 1 & \mbox{ if $x = 0$ mod $k$ } \\ 0 & \mbox{ otherwise. } \end{array} \right. \end{equation} \noindent We can write a difference equation that is equivalent to the FRT and therefore the PRFA (cf. \cite{milt1} \cite{frt5}): \begin{equation} \label{de1} \sum_{j = 0}^{r} x_{i-j}^{t+1} \equiv \sum_{j = 0}^{r} x_{i+j}^{t} + \delta_2(x_i^t) \prod_{j=1}^{r} \delta_2(x_{i-j}^{t+1}) \delta_2(x_{i+j}^{t}) - 1, \end{equation} \noindent where the equivalence is understood {\it mod} 2 (i.e. we mod 2 each side of the equation). Observe that we can re-write this as a linear combination of the sum in the original PRFA, equation (\ref{prfa12}), and an extremely non-linear perturbation \[ x_i^{t+1} \equiv \underbrace{ S_{i,2}^t }_{Linear Part} + \underbrace{ \delta_2(x_i^t) \prod_{j=1}^{r} \delta_2(x_{i-j}^{t+1}) \delta_2(x_{i+j}^{t}) - 1}_{Nonlinear Perturbation} \] \noindent We should point out that evolving any initial condition using only the {\it linear} part simply translates by $r$ cells at each time step--every initial condition is a traveling wave of speed $r$. The introduction of the $k$-delta function allows extension of the $k = 2$ PRFA to arbitrary $k$ as follows: change all the 2's in equation (\ref{de1}) to $k$'s and change the `equivalence mod 2' to `equivalence mod $k$'. This yields \begin{equation} \label{de2} \sum_{j = 0}^{r} x_{i-j}^{t+1} \equiv \sum_{j = 0}^{r} x_{i+j}^{t} + \delta_k(x_i^t) \prod_{j=1}^{r} \delta_k(x_{i-j}^{t+1}) \delta_k(x_{i+j}^{t}) - 1. \end{equation} With this in mind, we formulate the $k$-state FRT which is equivalent to solving for $x_i^t$ via equation (\ref{de2}) as follows: \begin{equation} \label{frt2} x_{i-r}^{t+1} = \left\{ \begin{array}{ll} x_i^t & \mbox{ if } i \not\in B(t) \\ (x_i^t - 1) \mbox{ mod } k & \mbox{ if } i \in B(t). \end{array} \right. \end{equation} \noindent where, the set of boxsites is described below \begin{description} \item[(i)] Sweeping from the left, place the index (spatial coordinate) of the first non-zero site among $x^t$ in $B(t)$ ; \item [(ii)] In increments of $r+1$, place $i + r + 1$ in $B(t)$, if there is at least one non-zero $x_i^t$ in the $r$ sites to the right of the current index in $B(t)$; \item [(iii)] If there are $r$ zero consecutive values of $x_i^t$ to the right of the current index in $B(t)$, go on to the next non-zero $x_i^t$, place the corresponding index in $B(t)$, and repeat steps {\bf (ii)-(iii)}. \end{description} Observe that in the formulation of the $k$-state FRT, equation (\ref{frt2}), we have only changed the `2' in the 2-state FRT, equation (\ref{frt1}). This generalization has non-trivial periodic particles, solitonic interactions, and a time-irreversible prenull. Figures 8a,b illustrate all of these properties. Note that the prenull in the $k-$state rule remains a 1 in a boxsite followed by $r+1$ zeros, however, all possible values of the automata appear in the evolution as well. \newpage \baselineskip=10pt \begin{center} \begin{verbatim} 1 1111212222323333 3 111222333 1 1111212222323333 3 111222333 1 1111212222323333 3 111222333 1 1111212222323333 3 111222333 1 1111212222323333 3 111222333 1 1111212222323333 3 111222333 1 1111212222323333 3 111222333 1 1111212222323333 3 111222333 1 1111212222323333 3 111222333 1 1111212222323333 3 111222333 1 1111212222323333 3 111222333 1 1111212222323333 3 111222333 1 1111212222323333 3 111222333 1 1111212222323333 3 1 1212323 3 1 1111212222323333 111222333 3 1 111121222232333 1112223333 3 1 1111212222323 3 1 1212323333 3 1 1111212222333 111222323333 3 1 111121222333 1112222323333 3 1 1111212323 3 1 1212222323333 3 1 1111222333 111212222323333 3 1 111222333 1111212222323333 3 1 1212323 3 1 1111212222323333 3 111222333 1 1111212222323333 3 111222333 1 1111212222323333 3 111222333 1 1111212222323333 3 111222333 1 1111212222323333 3 111222333 1 1111212222323333 3 111222333 1 1111212222323333 3 111222333 1 1111212222323333 3 111222333 1 1111212222323333 3 111222333 1 1111212222323333 3 111222333 1 1111212222323333 3 111222333 1 1111212222323333 3 111222333 1 1111212222323333 3 111222333 1 1111212222323333 3 \end{verbatim} \begin{center} {\bf Figure 8a.} Solitonic interaction of 2 periodic particles--$r = 2, k = 4$. \end{center} \vspace{0.75in} \begin{verbatim} 000009 000008 000007 000006 000005 000004 000003 000002 1 000000000000 \end{verbatim} \begin{center} {\bf Figure 8b.} Evolution of an irreversible prenull--$r = 5, k = 10$. \end{center} \end{center} \baselineskip=20pt \section{Multi-State, Time-Reversible Rules} Consider the time-irreversible $k = 2$ difference equation (\ref{de2}) \[ \sum_{j = 0}^{r} x_{i-j}^{t+1} \equiv \sum_{j = 0}^{r} x_{i+j}^{t} + \delta_2(x_i^t) \prod_{j=1}^{r} \delta_2(x_{i-j}^{t+1}) \delta_2(x_{i+j}^{t}) - 1. \] \noindent In order that the evolution of the difference equation be time reversible, we need the symmetry $x_{i+j}^t \leftrightarrow x_{i-j}^{t+1}$. However, the coefficient $\delta_2(x_i^t)$ violates this symmetry. Therefore, let us simply disregard this coefficient and consider \begin{equation} \label{de3} \sum_{j = 0}^{r} x_{i-j}^{t+1} \equiv \sum_{j = 0}^{r} x_{i+j}^{t} + \prod_{j=1}^{r} \delta_2(x_{i-j}^{t+1}) \delta_2(x_{i+j}^{t}) - 1. \end{equation} \noindent The remarkable feature of such a simple modification is that it works. The prenull, which is the source of the time-irreversibility in the previous rules, now evolves as a single 1. Before we illustrate the reversible rule, let us make the $k > 2$ generalization and the associated FRT. Considering the difference equation, as before, we simply replace all 2's with $k$'s, and interpret the equivalence `mod $k$'. However, an additional time-reversible coefficient must be added to the product term, a requirement of Fermat's `Little' Theorem. Namely, it states (for $k$ prime) that $x^{k-1} = 1 ( \bmod k)$ for $x \neq 0 \bmod k$. Therefore $\delta_k(x) \equiv 1 - x^{k-1}$. Now replacing $\delta_k(x_i^t)$ by \begin{eqnarray*} \frac{x^{k-1} - 1}{x - 1} & \equiv & x^{k-2} + \ldots + 1 \\ & \equiv & \delta_k(x_i^t) - \delta_k(x_i^t - 1) \end{eqnarray*} \noindent yields \begin{equation} \label{de4} \sum_{j = 0}^{r} x_{i-j}^{t+1} \equiv \sum_{j = 0}^{r} x_{i+j}^{t} + \left[ \delta_k(x_i^t) - \delta_k(x_i^t - 1) \right] \prod_{j=1}^{r} \delta_k(x_{i-j}^{t+1}) \delta_k(x_{i+j}^{t}) - 1. \end{equation} \noindent This equation is valid {\it for all $k$}--we have only used Fermat's Theorem to deduce the general form of the modification. Observe that applying Fermat's Theorem to the $k = 2$ equation, above, results in replacing the $\delta$ coefficient by 1, i.e. \[ \frac{x^{k - 1} - 1}{x - 1} = \frac{x - 1}{x - 1} \] \noindent which precisely yields equation (\ref{de3}). The associated time-reversible $k$-state FRT is also modified by replacing the 2 by a $k$, as before. But now we must modify the formation of the set of boxsites, maintaining consistency with the effect the new coefficient has on the product in equation (\ref{de4}). We therefore have the equation of motion defined by \begin{equation} \label{frt3} x_{i-r}^{t+1} = \left\{ \begin{array}{ll} x_i^t & \mbox{ if } i \not\in \tilde B(t) \\ (x_i^t - 1) \mbox{ mod } k & \mbox{ if } i \in \tilde B(t). \end{array} \right. \end{equation} \noindent where $\tilde B(t)$ is constructed as follows: \begin{description} \item[(i)] Sweeping from the left, place the index (spatial coordinate) of the first non-zero site among $x^t$ in $\tilde B(t)$ ; \item [(ii)] In increments of $r+1$, place $i + r + 1$ in $\tilde B(t)$, if there is at least one non-zero $x_i^t$ in the $r$ sites to the right of the current index in $\tilde B(t)$; \item [(iii)$^\prime$] If $i \in \tilde B(t)$ and $x_{i+j}^t = 0, j = 1, \ldots, r$ then either $i + r \in \tilde B(t)$ if $x_i^t = 1$, or if $x_i^t = 0$, the index of the next non-zero $x_i^t$ belongs to $\tilde B(t)$. Repeat steps {\bf (ii)-(iii)$^\prime$}. \end{description} Observe that the only modification to the original recipe for building $B(t)$ is in step {\bf (iii)}, which we now call {\bf (iii)$^\prime$}. Basically, step {\bf (iii)$^\prime$} shifts the position of a boxsite which follows a prenull. Suppose $x_i = 1$ is a boxsite and $x_{i+j} = 0, j = 1, \ldots, r$. The old rule says that there is no boxsite allocated to position $x_{i+r+1}$, so that $x_i = 1$ evolves to a zero, leading to the diffusion characteristic in the irreversible rule. The modification specified in step {\bf (iii)$^\prime$}, now says that $x_{i+r}$ is made into a boxsite. The evolution of a reversible prenull is shown in Figure 9a. A non-trivial example of a reversible prenull is given in Figure 9b. \baselineskip=10pt \begin{center} \[ 00000\fbox{1}0000\fbox{0}00000 \] \vspace{0.05in} \[ 00000\fbox{1}0000\fbox{0}00000 \] \vspace{0.05in} \[ 00000\fbox{1}0000\fbox{0}00000 \] \end{center} \begin{center} {\bf Figure 9a.} Evolution of a reversible prenull--$r = 5, k = 2$. \end{center} \vspace{0.1in} \begin{center} \begin{tabular}{cccccccccccccccccccccc} & & & & & & & & & & & & & & & & $\fbox{3}$ & 0 & 0 & 0 & 0 & 0 \\ & & & & & & & & & & & & $\fbox{2}$ & 0 & 0 & 0 & 0 & 0 &&&& \\ & & & & & & & & $\fbox{1}$ & 0 & 0 & 0 & $\fbox{0}$ & 0 &&&&&&&& \\ \vspace{0.1in} \\ & & & &0&0&0&0& $\fbox{3}$ & 0 & 0 & 0 & 0 & 0 &&&&&&&& \\ & & & & $\fbox{2}$ & 0 & 0 & 0 & 0 & 0 &&&&&&&&&&&& \\ $\fbox{1}$ & 0 & 0 & 0 & $\fbox{0}$ & 0 &&&&&&&&&&&&&& \end{tabular} \end{center} \begin{center} {\bf Figure 9b.} Evolution of a reversible prenull--$r = 4, k = 4$. \end{center} \baselineskip=20pt To illustrate one of the properties of the new reversible rule, we consider the initial conditions shown in Figure 2a, which under the irreversible rule, yielded what we call a bound (or `glued') state. By running identical initial conditions under the reversible rule we produce Figure 10. This corresponds to particle production, and the similarity with particle physics is quite startling: two particles interact and produce a larger particle plus 2 totally elementary particles which we call `prebasic' particles. It is important to keep in mind that the picture is entirely reversible, i.e. a single particle is bombarded with two `photons' and evolves into 2 particles. As a final example of the diversity of interactions produced by the reversible rule, we consider the initial condition consisting of two well-separated particles: \[ 101101101000000000000001111010111 \] \noindent Under the time-irreversible rule, these particles undergo a solitonic interaction. However, during the interaction, a prenull is produced, so that the {\it solitonic interaction is not reversible}. Running the time-reversible automata with $r = 4, k = 2$ for {\it 23000} time steps we produce the particles listed in the following table. \begin{center} \begin{tabular}{|l|c|c|c|} \hline Particle & Period & Displacement. & Velocity \\ \hline 11001 & 3 & 7 & 2.3 \\ 1110011010 & 31 & 64 & 2.0645 \\ 10000100001010 & 28 & 42 & 1.5 \\ 10100 & 2 & 3 & 1.5 \\ 10100100011000 & 6 & 6 & 1 \\ 10010100101000 & 6 & 6 & 1 \\ 10000001000110 & 6 & 6 & 1 \\ 100011000 & 4 & 3 & 0.75 \\ 1000 & 1 & 0 & 0 \\ \hline \end{tabular} \end{center} \baselineskip=10pt \begin{center} \begin{verbatim} 1 111 1 11 1 1 1 111 1 11 1 11 1 111 1 1 1 11 11 1 1 111 1 11 11 11 1 1 111 1 11 1 1 1 111 1 11 1 11 1 111 1 1 1 1 1 11 1 11 1 1 1 11 1 1 1 1 1 1 1 1 1 1 1 111 11 1 1 11 1 1 11 1 1 11 111 1 1 1 11 1 1 11 111 11 1 1 1 1 1 1 1 1 11 1 1 1 111 1 1 11 1 1 1 1 11 1 1 1 1 11 1 1 111 1 1 1 11 1 1 1 1 1 1 1 1 1 111 11 1 1 11 1 1 1 1 1 11 1 1 1 1 1 1 1 11 11 1 1 1 1 1 1 1 11 1 1 1 1 1 11 1 1 11 111 1 1 1 1 1 1 1 1 1 11 1 1 \end{verbatim} \end{center} \begin{center} {\bf Figure 10.} Time-reversible evolution, corresponding to {\bf Particle Production}. \end{center} \baselineskip=20pt \section{Conclusion} In this paper we have introduced some of the ideas of Cellular and Filter Automata. We have considered in detail a special solitonic filter automata first introduced by Park, et. al. called the Parity Rule Filter Automata. The PRFA has only 2 states available (as `field variables'), and the model is diffusive. Information is lost, and the PRFA is time-irreversible. We discussed an equivalent, analytically useful rule--the Fast Rule Theorem. By reformulating both the PRFA and the FRT allows us to trivially extend the number of states, as well as identify the underlying analytical mechanism that drives the irreversibility. We then formulated the $k$-state irreversible and reversible rules, giving numerous examples of their evolutions (a striking example being shown in Figure 10). {\em Acknowledgements} This work (MJA) is partially supported by the NSF, Grant No. DMS-8916182 and the Air Force Office of Scientific Research, Grant No. AFOSR-90-0039. \begin{thebibliography}{999} \bibitem{nav1} J. Hardy and Y. Pomeau. J. Math. Phys. {\bf 13} p1042 (1972). \bibitem{nav2} J. Hardy, O. de Pazzis, Y. Pomeau. J. Math. Phys. {\bf 14} p1746 (1973). \bibitem{nav3} U. Frisch, B. Hasslacher, and Y. Pomeau. Phys. Rev. Lett. {\bf 56} p1505 (1986). \bibitem{nav4} H.A. Lim. Complex Systems {\bf 2} p45 (1988). \bibitem{brg1} B. Boghosian and C. Levermore. Complex Systems {\bf 1} p17 (1987). \bibitem{brg2} J. Lebowitz, E. Orlandi, E. Presutti. Physica D {\bf 33} p165 (1988). \bibitem{bz1} B. Madore and W. Freedman. Science {\bf 222} p615 (1983). \bibitem{wolf1} S. Wolfram. J. Stat. Phys. {\bf 45} p471 (1986). \bibitem{wolf2} S. Wolfram. Theory and Application of Cellular Automata. World Scientific, Singapore (1986). \bibitem{alamos1} Cellular Automata: Theory and Experiment. Proceedings of a Workshop Sponsored by the Center for Nonlinear Studies, Los Alamos National Laboratory. Physica D {\bf 45}, September 1990. \bibitem{jvn1} J. von Neumann. Theory of Self-Reproducing Automata, edited and completed by A. Burks (University of Illinois Press, Champaign, IL, 1966). \bibitem{life1} J. H. Conway. 1970, unpublished; c.f. M. Gardner. ``Mathematical Games''. Sci. Amer. {\bf 224}, February, p112; March, p106; April, p114, (1971). \bibitem{life2} L.S. Schulman and P.E. Seiden. J. Stat. Phys. {\bf 19} p293 (1978). \bibitem{green} J. Greenberg and S. Hastings. Spatial Patterns for Discrete Models of Diffusion in Excitable Media. SIAM J. Appl. Math. {\bf 34}, p515 (1978). \bibitem{prfa1} J. Park, K. Steiglitz, and W. Thurston. Physica {\bf 19D}, p423 (1986). \bibitem{prfa2} K. Steiglitz, I. Kamal, and A. Watson. IEEE Trans. Comp. {\bf 37}, (1988). \bibitem{gold1} C. H. Goldberg. Complex Systems {\bf 2}, p91 (1988). \bibitem{frt1} T. S. Papatheodorou, M. J. Ablowitz, and Y. G. Saridakis. Stud. Appl. Math., {\bf 79}, p173 (1988). \bibitem{frt2} A. S. Fokas, E. Papadopoulou, Y. G. Saridakis, M. J. Ablowitz. Stud. Appl. Math., {\bf 81}, p153 (1989). \bibitem{frt3} J. M. Keiser. On the Computation of Periodic Particles for Cellular Automata. Masters Thesis, Clarkson University (1989). \bibitem{frt4} M.J. Ablowitz and J.M. Keiser. On Particles and Interaction Properties of the Parity Rule Filter Automata. PAM report 68 (1990). \bibitem{sol1} D. Takahashi and J. Satsuma. J. Phys. Soc. Japan. {\bf 59}, 3514 (1990). \bibitem{sol2} M.J. Ablowitz, J.M. Keiser and L.A. Takhtajan. A Class of Multi-State Time-Reversible Cellular Automata with Rich Particle Content. To appear, Phys. Lett. A (1991). \bibitem{abl} M.J. Ablowitz and H. Segur. Solitons and the Inverse Scattering Transform. SIAM, Philadelphia, 1981. \bibitem{fadtak} L. Faddeev and L.A. Takhtajan. Hamiltonian Methods in the Theory of Solitons. Springer-Verlag (1987). \bibitem{milt1} M.F. Maritz. Soliton Behavior in Cellular Automata and Difference Equations Related to Cellular Automata. Technical Report 2/88, Department of Applied Mathematics, University of the Orange Free State (1988). \bibitem{frt5} M.J. Ablowitz, B.M. Herbst, and J.M. Keiser. Solitons, Numerical Chaos and Cellular Automata, in Integrable and Super-Integrable Systems. Ed. B.A. Kuperschmidt, World Scientific (1990). \end{thebibliography} \end{document}