  The complexity of cellular automata is traditionally measured by their
computational capacity. However, it is difficult to choose a challenging set of
computational tasks suitable for the parallel nature of such systems. We study
the ability of automata to emulate one another, and we use this notion to
define such a set of naturally emerging tasks. We present the results for
elementary cellular automata, although the core ideas can be extended to other
computational systems. We compute a graph showing which elementary cellular
automata can be emulated by which and show that certain chaotic automata are
the only ones that cannot emulate any automata non-trivially. Finally, we use
the emulation notion to suggest a novel definition of chaos that we believe is
suitable for discrete computational systems. We believe our work can help
design parallel computational systems that are Turing-complete and also
computationally efficient.
