# Examples of reversible computations

Irreversible computations can be intuitive. For example, it is easy to understand roles of AND, OR, NOT gates and design a system without any intermediate, compilable layer. The gates can be directly used as they conform to human's thinking.

I have read a paper where it was stated that it is obviously correct way to code irreversibly, and compile to reversible form (can't find the paper now).

I am wondering if there exists a reversible model, that is as easy to understand as AND, OR, NOT model. The model should be therefore "direct" use of reversibility. So no compilation. But also: no models of form: $f(a) \rightarrow (a,f(a))$ (ie. models created by taking irreversible function $f$ and making it reversible by keeping copy of its input).

• I don't really understand your question, but it is well known (in fact trivial to see) that all quantum computation is reversible. It is also known that AND, OR and NOT gates respectively can each be replaced with a system of Toffoli (controlled controlled not) gates. Every classic circuit has a reversible equivalent (i.e. on restricted input and output they compute the same functions). Feb 1, 2012 at 5:22
• Ross: will you really be able to use Toffoli gate – without preconfigured basic AND blocks etc. – to implement e.g. addition of 8 bit numbers? You will probably revert back to irreversible thinking – and try to handle extra Toffoli's outputs so that they will be separated from result. My question is about reversible computations that are not "irreversible calc + save all history so that we can go back". Feb 1, 2012 at 5:41
• What is the difference between "reversible computation" and "irreversible calc + save all history so that we can go back"? Feb 1, 2012 at 8:59
• @JɛﬀE You can do reversible computations without having to save history. Feb 1, 2012 at 9:34
• How about taking the inverse of a matrix? An inverse in the rationals? Appying a permutation to a deck of cards? What about $f(a) \rightarrow (2a, f(a))$? What about $f(a) \rightarrow (AES(a,k), f(a))$? Are we restricted from computing the other direction from the output entirely? I don't think you are asking your question specificly enough. In fact I still don't know what you want (I have some idea of what you don't want). I don't really think this question is posed well at all, and think it should be closed as not a real question until it is improved. Feb 3, 2012 at 20:28

The paper you mention is probably one of Paul Vitányi's, possibly Time, Space, and Energy in Reversible Computing.

However, not everyone takes the viewpoint that simulation of irreversible computations is the main point. There is some research into what reversible computing can do in addition to such simulations, the beginnings of which is in Bennett's seminal paper Logical Reversibility of Computation on reversible Turing machines. See this paper for an elaboration of these ideas.

In terms of reversible logic circuits, there has been significant effort from the quantum computing community to build non-trivial circuits for arithmetic, e.g. Quantum networks for elementary arithmetic operations, some of which are purely classical, i.e., reversible. These implement a reversible variant of, say, addition, where one of the operands is conserved, but they do not rely on "irreversible thinking", do not use a history, and display a significant amount of ingenuity in their design.

Ryan Williams surveyed and studied the complexity of reversibility in this paper, space efficient reversible simulations which contains various constructions. The problem seems to be closely linked to lower bounds on time/space tradeoffs..

In your question you seem to be making some kind of distinction between "reversibility" and "direct reversibility" but there seems to be no such distinction in the literature. One questions whether your distinction can be formally defined.

I have realized one very good example: Langton's ant. It is reversible. It also does not seem to be a "forced" reversibility model – ie. it is not the "keep input history" approach: $f(a) \rightarrow (a,f(a))$. It also is universal.

Fredkin Gate and Toffoli Gate are two examples of reversible computation in that no information is lost in this process and then according to Boltzman Entrophy Law energy is at least not comsumed. Fredkin Gate and Toffoli Gate can simulate NAND gate and FANOUT, thus simulating any classical circuit. Cook-Levin theorem indicates that classical circuits can efficiently simulate Turing Machine, so coding irreversibly can be done on these reversible circuits.

Another exciting reversible computation model is Quantum Computers! In quantum mechanics, any transformation is carried out through unary operators, which are reversible. So quantum computers are "reversible" computers.