ABSTRACT
Complex phenomena can emerge even in a collection of elements that obey a simple reversible rule. To investigate this problem, we use a framework of a reversible cellular automaton (RCA). Since reversibility is one of the fundamental microscopic laws of nature, it is important to know how high-order functions appear in a reversible cellular space. The CA model considered here is an elementary triangular partitioned cellular automaton (ETPCA). ETPCAs are very simple, since each of their local functions is described by only four local transition rules. Here, we use a specific reversible ETPCA 0347, where 0347 is its identification number in the class of ETPCAs. In this cellular space, various useful objects (i.e., patterns) that exhibit interesting behaviour exist. Here, we discuss how such objects are identified, how useful phenomena are found by interacting these objects, how a reversible logic element is implemented using these phenomena, and how reversible Turing machines are composed of the logic elements and realised in the cellular space. By this, we can see that even from a collection of quite simple reversible elements, universal computing capability emerges by suitably finding a pathway from reversible microscopic objects to reversible computers.
