Technical Report Number
Theory of Computation, Computing Methodologies
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 Lambda parameter.