A Reversible Instruction Set Architecture and Algorithms

We describe a reversible Instruction Set Architecture using recently developed reversible logic design techniques. Such an architecture has the dual advantage of being able to run backwards and of being, in theory, implementable so as to dissipate less than log 2 kT joules per bit operation. We analyze several basic control structures and algorithms on the architecture, showing that, for example, a sorting algorithm need only dissipate O(n log n) bits even though it makes O(n 2 ) comparisons. Keywords reversible computation, entropy, heat dissipation, reversible algorithms, finite automata, computer architecture, retractile cascade, sorting 1 Introduction In [8] we introduced an "electroid" logic for the design of reversible computer architectures. It was at that time a conjecture, based on an observation of Merkle [10], that such a logic could be used to design a computer architecture that was not radically different from conventional ones at the instruction set level, and yet kept..