Computational Hierarchy of Elementary Cellular Automata
Barbora Hudcová, Tomáš Mikolov · 2021
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.