Studying Encoder–Decoder Relation Between Cellular Automata to Uncover Their Computational Structure

Abstract

Studying relationships between cellular automata can provide important insight into their structure and computational capacity. In this chapter, we study a notion called the encoder-decoder relation between cellular automata. Though variants of this notion have been used to construct intrinsically universal systems, there are many of its properties yet to be explored. Our work mainly focuses on two new results: we relate the encoder-decoder simulation to other previously studied notions and show that it is the strongest among them. And secondly, we propose a method to efficiently search for such relations between two given automata. This problem is non-trivial because verifying that automaton A can simulate B requires checking infinitely many conditions. We demonstrate the results we obtained on the class of elementary cellular automata, presenting a rich hierarchy of their relationships that were not known before. We show that the number of elementary automata with unique dynamics can be reduced from 88 to 52. Further, we show that some automata thought as unique, such as 14, 43, and 142, have in fact equivalent computational capacity. We believe that using similar approaches, the number of unique automata can be dramatically reduced in the future.

Publication
Advances in Cellular Automata