Reversible computing is a paradigm of computation that reflects physical reversibility, one of the fundamental microscopic laws of Nature. In this survey, we discuss topics on reversible logic elements with memory (RLEM), which can be used to build reversible computing systems, and their universality. An RLEM is called universal, if any reversible sequential machine (RSM) can be realized as a circuit composed only of it. Since a finitestate control and a tape cell of a reversible Turing machine (RTM) are formalized as RSMs, any RTM can be constructed from a universal RLEM. Here, we investigate 2state RLEMs, and show that infinitely many kinds of nondegenerate RLEMs are all universal besides only four exceptions. Nonuniversality of these exceptional RLEMs is also argued.
