Universality Issues in Reversible Computing Systems and Cellular Automata (Extended Abstract)

AbstractIn this survey, we deal with the problem how a universal computer can be constructed in a reversible environment. We discuss this problem based on the frameworks of reversible Turing machines, reversible logic circuits, and reversible cellular automata. We can see that in spite of the constraint of reversibility, there are several very simple reversible systems that have universal computing ability