<p>The paper you mention is probably one of Paul Vitányi's, possibly <a href="http://dx.doi.org/10.1145/1062261.1062335" title="Time, Space, and Energy in Reversible Computing">Time, Space, and Energy in Reversible Computing</a>.</p>

<p>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 <a href="http://dx.doi.org/10.1147/rd.176.0525" title="Logical Reversibility of Computation">Logical Reversibility of Computation</a> on reversible Turing machines. See <a href="http://dx.doi.org/10.1007/978-3-642-19805-2_4" title="What Do Reversible Programs Compute?">this paper</a> for an elaboration of these ideas.</p>

<p>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. <a href="http://dx.doi.org/10.1103/PhysRevA.54.147" title="Quantum networks for elementary arithmetic operations">Quantum networks for elementary arithmetic operations</a>, 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 <em>not</em> rely on "irreversible thinking", do <em>not</em> use a history, and display a significant amount of ingenuity in their design.</p>

CC BY-SA 3.0
2012-02-01T09:19:33.940Z
2012-02-01T09:19:33.940Z
funkstar
<p>Ryan Williams surveyed and studied the complexity of reversibility in this paper, <a href="http://www.cs.cmu.edu/~ryanw/spacesim9_22.pdf" rel="nofollow">space efficient reversible simulations</a> which contains various constructions. The problem seems to be closely linked to lower bounds on time/space tradeoffs.. </p>

<p>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.</p>

CC BY-SA 3.0
2012-02-01T15:47:22.377Z
2012-02-03T00:04:05.437Z
2012-02-03T00:04:05.437Z
vzn
<p>I have realized one very good example: <a href="http://en.wikipedia.org/wiki/Langton%27s_ant" rel="nofollow">Langton's ant</a>. 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.</p>

CC BY-SA 3.0
2012-02-01T14:40:39.923Z
2012-02-03T00:07:53.670Z
2012-02-03T00:07:53.670Z
Mooncer
<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2012-02-01T11:29:41.440Z
2012-02-01T11:29:41.440Z
Strin
<p>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.</p>

<p>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).</p>

<p>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. <strong>But also:</strong> 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).</p>

CC BY-SA 3.0
2012-02-01T05:22:51.453Z
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).
Ross Snider
CC BY-SA 3.0
2012-02-01T05:41:01.847Z
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".
Mooncer
CC BY-SA 3.0
2012-02-01T08:59:51.513Z
What is the difference between "reversible computation" and "irreversible calc + save all history so that we can go back"?
Jeffε
CC BY-SA 3.0
2012-02-01T09:34:36.043Z
@JɛﬀE You can do reversible computations without having to save history.
funkstar
CC BY-SA 3.0
2012-02-03T20:28:42.187Z
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.
Ross Snider
<reference-request><computability><machine-models>
Examples of reversible computations
Mooncer
# Examples of reversible computations

(Asked by: username_0 on 2012-02-01)

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).

**Tags:** reference-request, computability, machine-models
> **Comments:**
> **username_1**: 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).  
> **username_0**: 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".  
> **username_2**: What is the difference between "reversible computation" and "irreversible calc + save all history so that we can go back"?  
> **username_3**: @JɛﬀE You can do reversible computations without having to save history.  
> **username_1**: 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.  

---

## 4 answers

### Answer by username_3 on 2012-02-01. Score: 8 | Accepted answer

The paper you mention is probably one of Paul Vitányi's, possibly [Time, Space, and Energy in Reversible Computing](http://dx.doi.org/10.1145/1062261.1062335 "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](http://dx.doi.org/10.1147/rd.176.0525 "Logical Reversibility of Computation") on reversible Turing machines. See [this paper](http://dx.doi.org/10.1007/978-3-642-19805-2_4 "What Do Reversible Programs Compute?") 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](http://dx.doi.org/10.1103/PhysRevA.54.147 "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.


---

### Answer by username_4 on 2012-02-01. Score: 6

Ryan Williams surveyed and studied the complexity of reversibility in this paper, [space efficient reversible simulations](http://www.cs.cmu.edu/~ryanw/spacesim9_22.pdf) 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.


---

### Answer by username_0 on 2012-02-01. Score: 4

I have realized one very good example: [Langton's ant](http://en.wikipedia.org/wiki/Langton%27s_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.


---

### Answer by username_5 on 2012-02-01. Score: 3

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.


---

