Publication Date

1996

Technical Report Number

TR96-05

Subjects

Theory of Computation, Computing Methodologies

Abstract

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.

Share

COinS