Making and Using a Rotary Element in Reversible Cellular Automata

A rotary element (RE) is a reversible logic element with one-bit memory (RLEM) proposed by Morita (2001). Though it is a very simple RLEM and its operation is easily understood, it is universal in the sense that any other RLEM is composed only of it. In this survey, we discuss how we can compose an RE in simple reversible cellular automata (RCAs), and how it is used to show universality of RCAs. Here, we consider two examples of RCAs, which are reversible elementary square partitioned CAs (ESPCAs). We first explain that in each of these RCAs, an RE is implemented using only a few kinds of small patterns and their interactions. We then discuss how an RE is used to show Turing universality and intrinsic universality of RCAs. Turing universality of RCAs is derived by constructing reversible Turing machines (RTMs) out of the implemented RE. Utilizing an RE, we can also show intrinsic universality of the RCAs, which is the property of a particular RCA that any RCA in some large class of RCAs can be simulated in it. Computing processes of them can be seen on the CA simulator Golly.