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.


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.