preprint available

[Cris Moore]

A preprint is available, entitled:

Predicting Non-linear Cellular Automata Quickly
by Decomposing them into Linear Ones

C. Moore and T. Pnin

http://www.santafe.edu/~moore
ftp://ftp.santafe.edu/pub/moore/semi.ps

Abstract:

We show that a wide variety of non-linear cellular automata (CAs)
can be decomposed into a {\em quasidirect product} of linear ones.
These CAs can be predicted by parallel circuits of depth $\ord(\log^2 t)$
using gates with binary inputs, or $\ord(\log t)$ depth if ``sum mod $p$''
gates with an unbounded number of inputs are allowed. Thus these CAs can
be predicted by (idealized) parallel computers much faster than by
explicit simulation, even though they are non-linear.

This class includes any CA whose rule, when written as an algebra,
is a solvable group.  We also show that CAs based on nilpotent groups
can be predicted in depth $\ord(\log t)$ or $\ord(1)$ by circuits
with binary or ``sum mod $p$'' gates respectively.

We use these techniques to give an efficient algorithm for a CA rule
which, like elementary CA rule 18, has diffusing defects that annihilate
in pairs.  This can be used to predict the motion of defects
in rule 18 in $\ord(\log^2 t)$ parallel time.

- Cris moore at santafe.edu