  In order to develop systems capable of artificial evolution, we need to
identify which systems can produce complex behavior. We present a novel
classification method applicable to any class of deterministic discrete space
and time dynamical systems. The method is based on classifying the asymptotic
behavior of the average computation time in a given system before entering a
loop. We were able to identify a critical region of behavior that corresponds
to a phase transition from ordered behavior to chaos across various classes of
dynamical systems. To show that our approach can be applied to many different
computational systems, we demonstrate the results of classifying cellular
automata, Turing machines, and random Boolean networks. Further, we use this
method to classify 2D cellular automata to automatically find those with
interesting, complex dynamics.
  We believe that our work can be used to design systems in which complex
structures emerge. Also, it can be used to compare various versions of existing
attempts to model open-ended evolution (Ray (1991), Ofria et al. (2004),
Channon (2006)).
