%article---report,book,letter
%12pt---11pt,twoside,twocolumn,titlepage(for article so that abstract,
% title each a separate page),openbib, e.g. [11pt, titlepage]
\documentstyle[12pt]{article}
\textwidth 6in
\textheight 8.5in
\evensidemargin .25in
\oddsidemargin .25in
\topmargin .25in
\headsep 0in
\headheight 0in
\footskip .5in
%If you want single spaced copy, delete the next two lines.
\parskip 1.75\parskip plus 3pt minus 1pt
\renewcommand{\baselinestretch}{1.5}
%plain---default,no head,foot only page number
%other---empty(no head, no foot),headings(foot is empty)
\pagestyle{plain}
%arabic----others:roman, Roman, alph, Aiph
\pagenumbering{arabic}
\begin{document}
\renewcommand{\o}[2]{\frac{#1}{#2}}
\newcommand{\hf}{\o{1}{2}}
\newcommand{\ba}{\begin{eqnarray}}
\newcommand{\eps}{\epsilon}
\newcommand{\ea}{\end{eqnarray}}
\newcommand{\raw}{\rightarrow}
\newtheorem{theorem}{Theorem}
\newtheorem{example}{Example}
\newtheorem{lemma}{Lemma}
\newtheorem{prop}{Proposition}
\newcommand{\DOT}{\hspace{-0.08in}{\bf .}\hspace{0.1in}}
\newcommand{\Der}{{\rm Der}}
\renewcommand{\H}{{\bf H}}
\renewcommand{\L}{{\cal L}}
\newcommand{\K}{{\bf K}}
\newcommand{\grad}{\nabla}
\newcommand{\X}{{\bf X}}
\newcommand{\R}{{I\kern -0.3 em R}}
\newcommand\C{{\rm C\kern -0.5em \stalk\kern 0.5em}}
\newcommand\stalk{\vrule height1.395ex width0.06em depth-0.05ex}
\newcommand{\Z}{{ Z \kern -0.45 em Z}}
\newcommand{\smZ}{{ Z \kern -0.8 em Z}}
\newcommand{\Mo}{{\bf M}_0}
\newcommand{\D}{{\rm D \kern -0.6 em /\kern 0.1 em}}
\newcommand{\G}{{\bf \widetilde G}}
\newcommand{\Po}{{\bf P}_0}
\newcommand{\IM}{{\rm Im}}
\newcommand{\qed}{\hskip 3em \hbox{\BOX} \vskip 2ex}
\newcommand{\colono}{\colon\negthinspace}
\begin{center}
{\bf An Algebraic Approach to Discrete Mechanics \\}
\vspace{0.5cm}
{\em John C.\ Baez and James W.\ Gilliam\\}
\vspace{0.3cm}
{\small Department of Mathematics\\
University of California \\
Riverside, California 92521\\}
\vspace{0.3cm}
{\small December 13, 1993\\}
\vspace{0.3 cm}
{Published in Lett.\ Math.\ Phys.\ {\bf 31} (1994), 205-212.\\}
\vspace{0.5cm}
\end{center}
\newcommand{\tensor}{\otimes}
\renewcommand{\L}{{\cal L}}
\newcommand{\w}{\wedge}
\newcommand{\ata}[2]{A_{#1} \tensor A_{#2}}
\newcommand{\att}{A \tensor \cdots \tensor A}
\newcommand{\atata}[3]{A_{#1} \tensor A_{#2} \tensor A_{#3}}
\newcommand{\Att}{A^{\tensor(T+1)}}
\newcommand{\Om}{\Omega}
\newcommand{\om}{\omega}
\newcommand{\al}{\alpha}
\newcommand{\maps}{\colon}
\newcommand{\be}{\beta}
\renewcommand{\include}{\hookrightarrow}
\renewcommand{\phi}{\varphi}
\newcommand{\oatt}{A \tensor \ldots \tensor \Om^1(A) \tensor \ldots \tensor A}
\newcommand{\del}{\delta}
\newcommand{\Li}{1 \tensor \cdots \tensor \L \tensor \cdots \tensor 1}
\newcommand{\BOX}{\hbox {$\sqcap$ \kern -1em $\sqcup$}}
\newcommand{\poly}{k[q_1,\ldots,q_n]}
\newcommand{\bex}{\bigskip \noindent {\bf Example:} $\;$}
\hfuzz9pt
\begin{abstract}
Using basic ideas from algebraic geometry, we extend the methods of
Lagrangian and symplectic mechanics to treat a large class of
discrete mechanical systems, that is, systems such as cellular automata
in which time proceeds in integer steps and the configuration space is
discrete. In particular, we derive an analog of the Euler-Lagrange
equation from a variational principle, and prove an analog of Noether's
theorem. We also construct a symplectic structure on the analog of the
phase space, and prove that it is preserved by
time evolution. \end{abstract}
\section{Introduction}
One of the first uses of digital computers was to approximately simulate
physical systems by numerically solving differential equations. As
physicists become more familiar with digital computation, there has
naturally been increased interest in {\it exact} simulation of
``discrete mechanical systems,'' in which time evolution proceeds in
integer steps and the state space is a finite set. (We wish to
distinguish such systems from ``discrete dynamical systems'' in which
time is discrete but the state space is a manifold.) Presently, the
most widely studied examples of discrete mechanical systems are cellular
automata on finite lattices. But there is no need to limit discrete
mechanics to the study of cellular automata, which are analogous to
field theories in classical mechanics. Just as it is
useful to treat classical field theories as a special case of classical
mechanical systems, it may be useful to treat cellular automata as a
special case of discrete mechanical systems.
It seems worthwhile to attempt to extend standard techniques in
classical mechanics, such as the Lagrangian and Hamiltonian formalisms, to
discrete mechanics. The lack of a notion of differentiation might
appear an insurmountable obstacle to such a project. We show,
however, that the algebraic definition of differential forms provides a
partial substitute for the usual differential calculus. We begin by
deriving an analog of the Euler-Lagrange equation for discrete mechanics,
starting from a variational principle. As an example of how this analog
works, we prove a version of Noether's theorem applicable to this
context. We also relate our framework to Hamiltonian mechanics, or more
precisely, symplectic geometry.
For somewhat related work on extending notions of classical mechanics to
more general algebraic settings see, for example \cite{Nam,TVW}. For
related work in discrete dynamical systems see \cite{IA,Z} and the
references therein. For applications of symplectic mechanics to
cellular automata see \cite{K}. The authors would like to thank Norm
Margolus, Bruce Smith, Mark Smith and Tomaso Toffoli for many useful
discussions of cellular automata.
\section{The Euler-Lagrange Equation}
In order to apply the methods of differential geometry to discrete
configuration spaces, we will use the strategies of algebraic geometry.
This is in fact quite natural, given the successful
application of algebraic geometry to many problems involving integrable
systems \cite{Mum,Nov}.
The key idea is to replace the real numbers by an arbitrary commutative
ring $k$, with the most interesting examples for the purposes of discrete
mechanics being the integers, the integers modulo $n$, and other finite
rings. Also, rather than working directly with the configuration space,
we work with the algebraic functions on the configuration space, which
form a commutative algebra $A$ over $k$. For example, if $k$ is a field
and the configuration space is an $n$-dimensional vector space over $k$,
we have $A = k[x_1, \ldots, x_n]$, the algebra of polynomial functions
in $n$ variables. Since the theory may seem rather abstract, in what
follows we illustrate each construction with the simplest example, the
particle in a potential in a one-dimensional configuration space, where
$A = k[x]$.
Let $k$ be a commutative ring and $A$ a commutative algebra over $k$.
Just as $A$ plays the role of the functions on configuration space, the
algebra $H = \Att = \att$ is to be thought of as the functions on the
space of ``histories," where time takes values in the discrete set $\{0,
\ldots, T \}$. It will be convenient to sometimes use the notation $H =
A_0 \tensor A_1 \tensor \cdots \tensor A_T$, where the
algebras $A_i$ are simply copies of $A$, with $A_i$ thought of as the
functions on configuration space at time $i$.
Fix an element $\L \in \ata{}{}$, which will play the role of the
Lagrangian for our system.
In the algebra $H$ let
\[ S = \sum\limits_{i=0}^{T-1} \L_i ,\]
where $\L_i = \Li$ with $\L$ occupying the
$i$th and $(i+1)$st slots. The element $S$ corresponds to the action
functional in classical mechanics.
\bex Suppose $2$ is a unit in $k$ and the algebra
$A = k[x]$, so $\ata{}{} \cong k[q_1,q_2]$ and $H \cong
k[q_0, \ldots, q_T]$, the
polynomials in $T+1$ variables over $k$. We then
consider the Lagrangian ${\cal L}_i$ for a particle in a polynomial
potential $V$ as a function of consecutive
positions $q_i$ and $q_{i+1}$ of the particle,
\[\L_i = \L(q_i ,q_{i+1}) = {1\over 2} m\dot q_i^{2} - V(q_i),\]
where we define $\dot q_i = q_{i+1} - q_{i}$ and where $m$ is a ring
element representing the mass of the particle.
\bigskip
In order to formulate a variational principle we need an algebraic
analog of the the differential calculus. For this we borrow from
algebraic geometry the concept of K\"ahler differentials
\cite{Hart,Mat}, or more generally, algebraic differential forms. If
$B$ is a commutative $k$-algebra, the algebraic differential forms
$\Om(B)$ are a graded-commutative differential graded algebra with
$\Om^0(B) = B$, defined by the following universal property: given any
graded-commutative differential graded algebra $\Om$ and given any
algebra homomorphism $f\maps B \to \Om^0$, there exists a unique
differential graded algebra homomorphism $f_{\ast}\maps \Om(B) \to \Om$
such that the following diagram commutes: \bigskip
\begin{tabular}{cccccccccc}
&&&&&&&$\Om(B)$ & $ \buildrel f_{\ast} \over \longrightarrow$ & $\Om$
\cr
&&&&&&&$\Bigg\uparrow$ & & $\Bigg\uparrow$ \cr
&&&&&&&$B$ & $ \buildrel f \over \longrightarrow$ & $\Om^0$ \cr
\end{tabular}
\bigskip
\noindent We write the product in $\Om(B)$ as a wedge product and the
differential as $d$.
Concretely, $\Om(B)$ is the algebra generated by $B$ and
elements $da$, where $a \in B$,
with the relations:
\[ d(\lambda a) = \lambda da,
\quad d(a + b) = da + db,
\quad d(ab) = da \w b + a \w db ,\]
\[ a \w db = db \w a,\quad da \w db = -db \w da,\quad da \w da = 0. \]
(The last is only necessary if 2 is not a unit in $k$.)
Now it can be shown that for any algebra $A$,
\[\Om^p (\ata{}{}) = \bigoplus
\limits_{q=0}^p\; \Om^q(A) \tensor \Om^{p-q}(A).\]
so by induction,
\[\Om^1(H) = \bigoplus\limits_{i=0}^{T} A_0 \tensor \cdots \tensor \Om^1(A_i)
\tensor \cdots \tensor A_T.\]
Let $p_i \maps \Om^1(H) \to \Om^1(H)$
denote projection onto the $i$th summand. We define
$d_i = p_id$ and note
$\displaystyle d = \sum\limits_{i=0}^{T} d_i.$
This
allows us to define a new operator
$\displaystyle\del = \sum\limits_{i=1}^{T-1} d_i ,$
which we think of as a variation keeping the endpoints fixed.
We now determine the variation of the action $S$ with fixed endpoints.
\begin{prop} \DOT
$\del S = \sum\limits_{i=1}^{T-1} d_i\L_i + d_i \L_{i-1}$.
\end{prop}
Proof - For $j \neq i, i+1$, $d_j\L_i = 0$, hence
\[ \del S = \del \sum\limits_{i=0}^{T-1} \L_i =
\sum\limits_{i=0}^{T-1}\del \L_i
= \sum\limits_{i=1}^{T-1} d_i\L_i + d_i\L_{i-1}. \qquad \qquad {\BOX}\]
\bex Consider the Lagrangian of the previous example. Then
\begin{eqnarray*}
\delta S &=& \delta \sum_{i=0}^{T-1} {\cal L}(q_i, q_{i+1}) \cr
&=& \sum_{i=0}^{T-1} \delta ({1\over 2}m \dot q_i ^2) - \delta V(q_i) \cr
&=& \sum_{i=1}^{T-1}((-m(\dot q_i - \dot q_{i-1}) -
V^{\prime}(q_i))\delta q_i)
\, - (m\dot q_0 + V^{\prime}(q_0))\delta q_0 + m \dot q_{T-1} \delta
q_T \cr
&=& \sum_{i=1}^{T-1} [-m(\dot q_i - \dot q_{i-1}) -
V^{\prime}(q_i)]\delta q_i
\end{eqnarray*}
where in the last step we use $\del q_0 = \del q_T = 0$. In what
follows we make precise the sense in which the vanishing of $\del S$
yields the equation of motion
\[ m(\dot q_i - \dot q_{i-1}) = - V^{\prime}(q_i). \]
This is the discrete analog of Newton's equation of motion for a
particle moving in a potential, $m \ddot q = -V^{\prime}(q)$.
\bigskip
The vanishing of the expression $d_i\L_i + d_i\L_{i-1}$ is supposed to
correspond to the Euler-Lagrange equation in this framework. But we
must describe precisely in what sense it vanishes. It certainly does
not vanish
as a 1-form on the whole space of histories; rather, it
should only vanish on trajectories satisfying the equations of motion.
In the discrete-time context, the equations of motion express
the configuration at a
particular time as a function of the configurations at the two preceding
times. We formalize this in terms of a homomorphism
$\phi \maps A_2 \to \ata{0}{1}$. Such a homomorphism determines a
homomorphism $\Phi \maps \ata{1}{2} \to \ata{0}{1}$ by
\begin{eqnarray*}
a \tensor 1 &\mapsto& 1 \tensor a \cr
1 \tensor a &\mapsto& \phi(a).
\end{eqnarray*}
which plays the role of a time evolution map. (If it is puzzling that
the indices {\it decrease} by 1 in this map, simply recall that a map from a
space $X$ to a space $Y$ allows one to pull back functions on $Y$ to
functions on $X$.)
We say that $\phi$, or
alternatively $\Phi$, {\bf satisfies the Euler-Lagrange equation}
provided
\[ \Phi_\ast d_1\L_1 + d_1\L_0 = 0 \]
\noindent where $\Phi_{\ast} \maps \Om^1(\ata{1}{2}) \to
\Om^1(\ata{0}{1})$ is the map induced by $\Phi$, and we regard
$\ata{0}{1}$ and $\ata{1}{2}$ as subalgebras of $H$ in order to define
the differential $d_1$.
\bex Continuing the example above, and assuming that $m$ is a unit in
$k$, define $\phi$ by
\[ \phi(q_2) = q_1 + \dot q_0 - m^{-1}V^{\prime}(q_1) .
\]
This map expresses the particle's position at time 2 as a function of
its positions at times 0 and 1. Let us show $\phi$
satisfies the equations of motion. We have $\ata{0}{1} \cong
k[q_0,q_1]$, $\ata{1}{2} \cong
k[q_1,q_2]$, and $\Phi \maps k[q_1, q_2] \to k[q_0, q_1]$ satisfies
\[ \Phi(q_1) = q_1 , \quad
\Phi(q_2) = \phi(q_2) = 2q_1 - q_0 - m^{-1}V^{\prime}(q_1), \]
\[ \Phi_{\ast}(dq_1) = dq_1, \quad
\Phi_{\ast}(dq_2) = 2dq_1 - dq_0 - m^{-1}V^{\prime \prime}(q_1)dq_1\]
so
\begin{eqnarray*}
\Phi_{\ast}d_1\L_1 + d_1\L_0 &=& \Phi_{\ast}\partial_{q_1}\L(q_1, q_2)dq_1 +
\partial_{q_1}\L(q_0, q_1)dq_1 \\
&=& \Phi_{\ast}\left((-m(q_2 - q_1) - V^{\prime}(q_1))dq_1\right)
+ m(q_1 - q_0)dq_1 \\
&=& (-m(2q_1 - q_0 - m^{-1}V^{\prime}(q_1) - q_1) - V^{\prime}(q_1))dq_1 \\
& & + m(q_1 - q_0)dq_1 \\
&=& 0
\end{eqnarray*}
as desired.
\bigskip
\section{Symplectic Geometry}
In continuous-time classical mechanics the phase space is
defined to be the cotangent bundle over the configuration space. Here,
interestingly, it is the Cartesian product of the configuration space
with itself that plays the role of a phase space. Thus, the
algebra $\ata{}{}$ is the analog of the functions on phase space. To
clarify this analogy, we would like to define a symplectic structure on
$\ata{}{}$ that is preserved by time evolution.
In this context it is more convenient to think of the time evolution map
$\Phi$ as a map from a fixed copy of $\ata{}{}$ to itself. This requires
a certain change in indexing; we say that
$\Phi \maps \ata{1}{2} \to \ata{1}{2}$ satisfies the Euler-Lagrange
equation if
\[ \Phi_\ast d_1\L + d_2 \L = 0 ,\]
where $\L = \L_1 \in \ata{1}{2}$.
Note that $d\L = d_1\L + d_2\L$. We define the closed 2-form $\om
\in \Om^2(\ata{1}{2})$ by $\om = -dd_1\L = dd_2\L$. This plays
the role of a symplectic structure on phase space. It is
always preserved by time evolution:
\begin{prop}\DOT $\om$ is preserved by the time evolution map $\Phi$,
that is, $\Phi_\ast \om = \om$,
provided $\Phi$ satisfies the Euler-Lagrange equations.
\end{prop}
Proof -
\[ \Phi_{\ast}\om = -\Phi_{\ast}dd_1\L = -d\Phi_{\ast}d_1\L =
dd_2\L = \om. \qquad \qquad \BOX \]
\bex Consider $\L \in \ata{1}{2} \cong
k[q_1, q_2]$. Then
\begin{eqnarray*}
d_1 \L &=& \partial_{q_1} \L(q_1, q_2)dq_1 \\
d_2\L &=& \partial_{q_2}\L(q_1,q_2)dq_2 \end{eqnarray*}
so
\[ \om = \partial_{q_1}\partial_{q_2}\L(q_1,q_2)dq_1 \wedge dq_2 .\]
Continuing the example of a particle moving in a potential and assuming
2 and $m$ are units, we see that:
\begin{eqnarray*}
\om = \partial_{q_1}\partial_{q_2}({1 \over 2}m(q_2 - q_1)^2 -
V(q_1))dq_1 \wedge dq_2 = mdq_2 \w dq_1 \end{eqnarray*}
If we define the ``momentum'' $p_1$ to be $m\dot q_1$, we have the
familiar formula
\[ \om = dp_1 \w dq_1 .\]
Using the time evolution derived above we have, using the new indexing system,
\[ \Phi(q_1) = q_2, \qquad \Phi(q_2) =
2q_2 - q_1 - m^{-1}V^{\prime}(q_2), \]
so the symplectic structure $\om$ is preserved:
\begin{eqnarray*}
\Phi_\ast \om &=& \Phi_\ast( mdq_2 \w dq_1 ) \\
&=& m(2dq_2 - dq_1 - m^{-1}V^{\prime\prime}(q_2)dq_2) \w dq_2 \\
&=& \om .
\end{eqnarray*}
\bigskip
Under certain conditions the symplectic structure $\om$ will be
nondegenerate, in the sense that it gives rise to
a map from 1-forms on the phase space,
that is, $\Om^1(\ata{}{})$, to ``vector fields'' on phase space, that
is, derivations of the algebra $\ata{}{}$. In this case there is a
full-fledged analog of Hamiltonian mechanics for the theory, $\ata{}{}$
becomes a Poisson algebra, and so on. We will not, however, pursue this
here.
\section{Noether's Theorem}
Now we consider a simple version of Noether's theorem in this setting.
The analog of a vector field on configuration space
is a derivation of $A$, that is, a $k$-linear map $v \maps A \to A$
map such that $v(ab) = av(b) + v(a)b$ for all $a,b \in A$. We
can construct a derivation $D$ on $\ata{1}{2}$ by $D = 1 \tensor v + v
\tensor 1$; that is,
\[ D(a \tensor b) = a \tensor vb + va \tensor b \]
A derivation $v$ is called an {\bf infinitesimal symmetry} of the
Lagrangian $\L
\in \ata{1}{2}$ provided $(1 \tensor v + v \tensor 1)\L = 0$.
\begin{prop}\DOT Let $\Phi$ be a time evolution map satisfying the
Euler-Lagrange equation and $v$ an infinitesimal symmetry of $\L$,
then the quantity $F \in \ata{}{}$ defined by $F = -(v \tensor 1)\L$ is
preserved by $\Phi$. \end{prop}
Proof - We need to use the pairing between 1-forms and derivations. For
any commutative $k$-algebra $B$,
there is a unique $B$-bilinear pairing $\langle \cdot,
\cdot\rangle \maps \Om^1(B) \tensor \Der(B) \to B$ such that $\langle
da,v\rangle = v(a)$ for all $a \in B$, $v \in \Der(B)$. Also, any
isomorphism $f \maps B \to C$ of such algebras induces a map $\Phi_\ast
\maps \Der(C) \to \Der(B)$ given by $\Phi_\ast v = \Phi \circ v
\circ \Phi^{-1}.$ We thus have
\begin{eqnarray*}
\Phi F &=&
-\Phi((v \tensor 1)\L) =
-\Phi \langle d\L, v \tensor 1\rangle =
-\Phi \langle d_1\L, v \tensor 1\rangle \\
&=&
-\langle \Phi_{\ast}d_1\L, \Phi_{\ast}(v \tensor 1)\rangle
= \langle d_2\L, \Phi_\ast (v \tensor 1)\rangle \\
&=& \langle d_2\L, 1 \tensor v\rangle =
\langle d\L, 1 \tensor v\rangle =
(1 \tensor v)\L = -(v \tensor 1)\L = F
\end{eqnarray*}
\hfill{\BOX}
\bex Consider the previous example when $V = 0$, that is, the free particle.
The Lagrangian $\L = {1\over 2}m \dot q_1^2 =
{1\over 2}m(q_2 - q_1)^2$ is translation-invariant,
that is, it has the derivation $v = \partial_x$ as an infinitesimal
symmetry:
\[ (v \tensor 1 + 1 \tensor v) = \partial_{q_1} + \partial_{q_2} \]
and
\[ (\partial_{q_1} + \partial_{q_2})\L = 0.\]
The corresponding conserved quantity is momentum:
\[ F = -(v \tensor 1)\L = -\partial_{q_1} {1\over 2}m(q_2 - q_1)^2 =
m\dot q_1 .\]
\bigskip
\bex Consider a 3-dimensional
configuration space, so that $A = k[x,y,z]$, and let $\L$ be the analog of
the Lagrangian for a particle in a spherically symmetric potential.
If $k = \Z$ this Lagrangian
describes the motion of a particle in the lattice $\Z^3$ in discrete
time steps.
The Lagrangian
$\L$ has as infinitesimal symmetries the derivations corresponding
to infinitesimal rotations:
\[ x\partial_y - y\partial_x,\quad y\partial_z - z\partial_y,\quad
z\partial_x - x\partial_z, \]
so angular momentum is conserved, even
though the lattice does not have $SO(3)$ symmetry. \bigskip
In future work we hope to treat more interesting examples of discrete
mechanical systems using Lagrangian and symplectic methods. In
particular, as Wolfram \cite{Wolfram} has noted, it would be interesting
to seek ``completely integrable'' 1-dimensional cellular automata
analogous to the Toda model, KdV equation, and other
1-dimensional completely integrable systems \cite{Mum,Nov}.
\begin{thebibliography}{12}
\bibitem{Hart} R.\ Hartshorne, {\sl Algebraic Geometry},
Springer-Verlag, New York, 1977.
\bibitem{IA} T.\ Itoh and K.\ Abe, Discrete Lagrange's equations and
canonical equations based on the principle of least action, Appl.\ Math.\
Comput.\ {\bf 29} (1989), 161-183.
\bibitem{K} K.\ Kaneko, Symplectic cellular automata,
Phys.\ Lett.\ A {\bf 129} (1988) 9-16.
\bibitem{M} N.\ Margolus, Physics and computation,
MIT Technical Report MIT/LCS/TR-415.
Physics-like models of computation,
Physica {\bf 10D} (1984), 81 - 95.
\bibitem{Mat} H.\ Matsumura, Commutative algebra, Benjamin, New York,
1970.
\bibitem{Mum} D.\ Mumford, An algebro-geometric construction of commuting
operators and of solutions to the Toda lattice equation, Korteweg de Vries
equation and related non-linear equations, Intl.\ Symp.\ on Algebraic
Geometry, Kyoto, 1977, pp. 115-153.
\bibitem{Nam}
Y.\ Nambu, Field theory of Galois' fields, in {\sl Quantum
Field Theory and Quantum Statistics}, edited by
I.\ A.\ Batalin, C.\ J.\ Isham, and G.\ A.\ Vilkovisky,
Adam Hilger, Bristol, 1987.
\bibitem{Nov} {\sl Integrable Systems}, edited
by S.\ Novikov, London Mathematical Lecture Note Series 60,
Cambridge U.\ P., Cambridge, 1981.
\bibitem{TM} T.\ Toffoli and N.\ Margolus, {\sl Cellular
Automata Machines: a New Environment for Modeling},
MIT Press, Cambridge, Mass., 1987.
\bibitem{TVW}
E.\ Thiram, D.\ Verstegen and J.\ Weyers, p-Adic dynamics, Jour.\ Stat.\
Phys.\ {\bf 54} 893-913 (1989).
\bibitem{Wolfram} S.\ Wolfram, personal communication.
\bibitem{Z} A.\ P.\ Veselov, What is an integrable mapping?, in
{\sl What Is Integrability?}, V.\ E.\ Zakharov, ed.,
Springer-Verlag, New York, 1991, pp.\ 251-272.
\end{thebibliography}
\vfill
\end{document}