\documentstyle[titlepage,12pt]{article}
\newcommand{\half}{\mbox{$\frac{1}{2}$}}
\newcommand{\beq}{\begin{equation}}
\newcommand{\eeq}{\end{equation}}

\begin{document}

\title{Soliton Cellular Automata}
\author{Mark J. Ablowitz \hspace{0.5cm} 
B.M. Herbst \hspace{0.5cm} James M. Keiser}

\maketitle
\pagestyle{empty}
\baselineskip=20pt

\begin{center}
\bf{Introduction}
\end{center}
Cellular Automata (CA) have been applied to physical systems
ranging from biology and chemistry, to physics and the engineering
sciences, most notably fluid dynamics.  One of the most 
famous CA is LIFE:
\begin{itemize}
\item Life was invented in 1968 by Cambridge mathematician J.H. Conway.
\item Martin Gardner popularized  the game in {\it Scientific American}
in the early 1970's.
\item Life is played on an infinite 2-dimensional grid (checkerboard).
\item Each cell has eight neighbors (von Neumann neighborhood).
\item Each cell is in 1 of 2 states:
\[ 0 \equiv Dead \hspace{1.0in} 1 \equiv Alive \]
\item At time $t+1$ the state of a cell depends on the number
of living cells in its neighborhood at the previous time $t$.
\item All cells are updated simultaneously according to the following
rules:
\subitem (i) If a dead cell has precisely 3 living neighbors at 
time $t$, then that cell is ``born'' at time $t+1$, otherwise it 
remains dead.
\subitem (ii) If a living cell has 2 or 3 neighbors at time $t$, then
it remains living at time $t+1$.
\subitem (iii) If a living cell has $\leq 1$ or $\geq 4$ living
neighbors at time $t$, then it dies at time $t+1$ from ``loneliness''
or ``overpopulation'', respectively.
\end{itemize}

\newpage
\begin{center}
\bf{CA vs FA}
\end{center}
Automata are partitioned into two broad categories depending on the
type of previous information used to update the current state.

CA's evolve according to a rule using one previous time step to 
determine the state of a given cell, $x_i^t$.  This rule is of the 
form 
\begin{equation} \label{ca1}
x_i^{t+1} = F(r,x_i^t)
\end{equation}
where $F$ is called the Global Update Rule (GUP), and $r$ defines the 
neighborhood influencing the cell $x_i^t$.

We are interested in a class of one dimensional automata called
Filter Automata (FA) which have rules of the form
\begin{equation} \label{fa1}
x_i^{t+1} = F(r,x_i^t,x_i^{t+1})
\end{equation}
Note that both previous, $x_i^t$, and current, $x_i^{t+1}$, 
information is used to determine $x_i^{t+1}$.

The particular GUP associated with (\ref{fa1}) was introduced by 
Steiglita, Kamal, and Watson of Princeton University, and is called
the Parity Rule Filter Automata (PRFA).  The PRFA is given by the 
following
\begin{equation} \label{prfa1}
x_i^{t+1} = \left\{ \begin{array}{ll}
1 & \mbox{ if } S(x_i^{t+1}) \mbox{ is even and nonzero} \\
0 & \mbox{ if } S(x_i^{t+1}) \mbox{ is odd or zero} 
\end{array} \right.
\end{equation}
where
\begin{equation}  \label{prfa2}
S(x_i^{t+1}) = \sum_{j=1}^{r} x_{i-j}^{t+1} + 
		  \sum_{j=0}^{r} x_{i+j}^{t}
\end{equation}

Figure 2 shows a random IC evolved for a number of time steps.
We see that a number of stable patterns, called ``particles'', 
have emerged.  The PRFA supports a number of these particles.  
Figure 3 shows what we call a solitonic interaction, illustrating
the reason for our interest in the PRFA. 

\begin{center}
\bf{FRT}
\end{center}
The PRFA as given by (\ref{prfa1}) and (\ref{prfa2}) is analytically
difficult to manipulate, prompting the development of the
Fast Rule Theorem (FRT) by Papatheodorou, Ablowitz, and Saridakis.

The FRT is given by
\begin{equation} \label{eq:frt1}
x_{i-r}^{t+1} = \left\{ \begin{array}{ll}
           x_i^t & \mbox{ if } i \not\in B(t) \\
\overline{x}_i^t & \mbox{ if } i \in B(t)
\end{array} \right.
\end{equation}
where $\overline{a} = (a + 1) \bmod 2$, and is the complement of $a$.
$B(t)$ is called the set of box sites at time $t$, and contains space
indices constructed as follows:
\begin{enumerate}
\item Place the index of the first 1 in $B(t)$
\item In increments of $r+1$, place the corresponding index in $B(t)$,
      unless there exist at least $r+1$ zeros after a previously 
      included index, in this case go on to the next 1.
\end{enumerate}

A number of general results have been obtained using the FRT, 
proving its usefulness as an analytical tool.  Much research has
been directed at particles called ``basic strings'', which consist
of groups of $r+1$ sites, and at period 1 particles, finite
sequences of 0's and 1's which repeat themselves at every time step.

\begin{center}
\bf{A Difference Equation for the PRFA}
\end{center}
The PRFA has been written in terms of a difference scheme of the 
form 
\beq
a_i^{t+1} = \sum_{k=2}^n (-1)^k \beta_k \sum_{j_1,\ldots,j_k}
a_{j_1}a_{j_2}\ldots a_{j_k} \label{diff}
\eeq
where $n= 2r+1$, $\beta_k = 2^{k-1} - 1$, 
and $\sum_{j_1,\ldots,j_k}$ denotes the sum over all possible 
combinations of the products of $k$ different terms. 

\begin{center}
\bf{Difference Equation for Periodic Particles}
\end{center}

A periodic particle is specified by a number of parameters:
\begin{enumerate}
\item Radius, $r \geq 2$
\item Period, $p \geq 1$
\item $p$ intermediate displacements, 
$d_j$ for $j = 1, 2, \ldots p$, $0 \leq d_j \leq r - 1$.
\end{enumerate}

We introduce the following functions for convenience
\begin{equation} \label{eq:deltaj}
\delta_j = \delta(\frac{i - \rho_j}{r + 1}) \mbox{\hspace{0.5in} $j = 0, 2, \ldots, p-1$}
\end{equation}
where the $\delta$-function is defined by
\begin{equation} 
\delta(k) = \left\{ \begin{array}{ll} \label{eq:delta}
$1$ & \mbox{if $k \in {\cal Z}^+$ or $0$} \\
$0$ & \mbox{otherwise}
\end{array}
\right. 
\end{equation}
and the constants $\rho_j$ are given iteratively by 
\begin{eqnarray} \label{eq:rhoj}
\rho_0 & \equiv & 0 \nonumber \\
\rho_j & = & \rho_{j-1} + (r-d_j) \mbox{\hspace{0.5in} $j = 1, 2, \ldots, p$}
\end{eqnarray}
Evaluating Equation (\ref{eq:rhoj}) at $j = p$, we define
\begin{equation}
\rho = \rho_p = p * r - \sum_{j = 1}^{p} d_j
\end{equation}

It has been shown that the set of difference equations
\begin{eqnarray} \label{eq:per1}
x_i & = & \delta(\frac{i - \rho_0}{r + 1}) \mbox{\hspace{0.5in}$ 0 \leq i < \rho $} \\
x_i & = & x_{i-\rho} + (1 - 2 x_{i-\rho}) \delta(\frac{i - \rho_0}{r + 1})
\mbox{\hspace{0.5in} $ i \geq \rho$} \nonumber
\end{eqnarray}
produces spatially periodic sequences of 0's and 1's of the form
\[ {\bf P O P O P O}\ldots. \]
where {\bf P} is non-trivial and begins and ends with a 1, 
and each {\bf O} contains only 0's.  Each {\bf P} was then shown 
to be a temporally periodic particle of period 1 when evolved 
by the FRT.




Also, it was shown that period 2 particles can be produced by an
analogous set of difference equations
\begin{eqnarray} \label{eq:per2}
x_i & = &\delta(\frac{i - \rho_0}{r + 1}) + \delta(\frac{i - \rho_1}{r + 1})
- 2 \delta(\frac{i - \rho_0}{r + 1}) \delta(\frac{i - \rho_1}{r + 1})
\mbox{\hspace{0.20in} $ 0 \leq i < \rho$} \\
x_i & = & x_{i-\rho} + (1 - 2 x_{i-\rho}) \nonumber \\
& & * (\delta(\frac{i - \rho_0}{r + 1}) + \delta(\frac{i - \rho_1}{r + 1})
- 2 \delta(\frac{i - \rho_0}{r + 1}) \delta(\frac{i - \rho_1}{r + 1}) )
\mbox{\hspace{0.20in} $ i \geq \rho$} \nonumber
\end{eqnarray}



We have proposed that the general period $p$ difference equation 
be written as
\begin{eqnarray} \label{eq:gende}
x_i & = & g_i \mbox{\hspace{0.5in} $0 \leq i < \rho$} \\
x_i & = & x_{i - \rho} f_i + g_i \mbox{\hspace{0.5in} $ i \geq \rho$} \nonumber
\end{eqnarray}
where 
\[f_i = 1 - 2 g_i \]
The first equation again defines the $\rho$ initial conditions necessary
to evaluate the second equation, resulting in spatially periodic sequences
of the above form.  The function $g_i$ is, in words, the sum 
of all combinations of products of individual $\delta$-functions and is 
given by
\[ g_i = a_1 b_1 + a_2 b_2 + \ldots + a_p b_p \]
where
\[ a_j = (-1)^{j-1} j \mbox{\hspace{0.5in}$j = 1, 2, \ldots, p$} \]
and $b_j$ is the sum of all unique products of $j$ delta functions.


\begin{center}
\bf{The Future}
\end{center}
A number of unanswered questions remain concerning the global behavior
of the particles found in the PRFA and the underlying relationship 
between solutions of, as yet undetermined, PDE's with solitonic 
solutions.  Among these are
\begin{itemize}
\item General Evolution Theorem.  Figure 2 shows a random initial
condition evolving to a finite set of particles ordered by velocity.
How can one prove such a general result, that has been observed for
all such initial conditions.
\item Reversibility of states.  The conditions under which a given
state can be recreated from future states has been determined, yet
the role this has regarding the global behavior of arbitrary initial
conditions must be nailed down.
\item PDE's.  Which, if any, PDE is associated with the discrete
structures found in the PRFA?
\item Statistical analysis.  Is there an appropriate statistical
analysis which could be applied to the previous question?  Can a
rate of organization of random IC's be computed--observe how 
``quickly'' Figure 2 becomes ordered.
\end{itemize}

















\end{document}