Compression Depth and the Behavior of Cellular Automata
James I. Lathrop · Iowa State University Digital Repository (Iowa State University) · 1996
A computable complexity measure analogous to computational depth is developed using the Lempel-Ziv compression algorithm. This complexity measure, which we call compression depth, is then applied to the computational output of cellular automata. We find that compression depth captures the complexity found in Wolfram Class III celluar automata, and is in good agreement with his classification scheme. We further investigate the rule space of cellular automata using Langton's parameter. 1 This research was supported in part by National Science Foundation Grant CCR-9157382, with matching funds from Rockwell, Microware Systems Corporation, and Amoco Foundation. 1 Introduction Measures of the complexities of objects are widely used in both theory and applications in order to model, predict, and classify objects. Information theory gives us several methods for measuring the information content of objects. The most widely used of these information measures, entropy and algorithmic informa...