# Structure and Dynamics of Cellular Automata

### Martin Zwick and Hui Shu

Presented at the International Institute for General Systems Studies,
Second Workshop, Jan. 9-11, 1997, Southwest Texas State University, San
Marcos, Texas.

### Abstract

Reconstructability analysis is a method to determine whether a
multivariate relation, defined set- or information-theoretically, is
decomposable with or without loss (reduction in constraint) into lower
ordinality relations. Set-theoretic reconstructability analysis (SRA) is
used to characterize the mappings of elementary cellular automata. The
degree of lossless decomposition possible for each mapping is more
effective than the lambda parameter (Walker & Ashby, Langton) as a
predictor of chaotic dynamics. Complete SRA yields not only the simplest
lossless structure but also a vector of losses of all decomposed
structures. This vector subsumes lambda, Wuensche's Z parameter, and
Walker & Ashby's "fluency" and "memory" parameters
within a single framework, and is a strong but still imperfect predictor
of the dynamics: less decomposable mappings more commonly produce chaos.
The set-theoretic constraint losses are analogous to information distances
in information-theoretic reconstructability analysis (IRA). IRA captures
the same information as SRA, but allows lambda, fluency, and memory to be
explicitly defined.