When people first hear of reversible computation and how reversible computation is potentially more energy efficient than conventional computation, they automatically think that reversible computation can never be practical except for very specific algorithms because one will always accumulate garbage information that one will eventually have to delete anyways which brings us back to irreversible computation. This thought is not correct. Reversible computation can compute anything that can be computed with a conventional computer with very little space and time overhead and where very little garbage information is produced.

Most people do not realize that in the future reversible algorithms will be efficient and powerful enough to replace conventional algorithms when one takes energy usage into consideration. I have heard mathematicians, computer scientists, and many otherwise knowledgable people claim that certain problems cannot be solved by reversible computers because these problems are inherently irreversible.

To give you some background, reversible computing is the type of computing where all of the computational processes are bijective.

For example, in a reversible combinatorial circuit, all of the logic gates such as NOT gates, Toffoli gates, Fredkin gates, and CNOT gates are bijective. Quantum computing in a sense is a version of reversible computing since unitary transformations are always bijective, and reversible computing is the special case of quantum computing without superposition. On the software level, there are even some reversible programming languages where you can automatically find the inverse of a computer program.

Now, reversibility at first glance appears to be much weaker than conventional computation and practically useless. This is not true. Landauer's principle states that every bit deleted costs $k*T*\ln(2)$ energy ($k=1.38\cdot 10^{-23}J/K$ is Boltzmann's constant and $T$ is the temperature) and information is deleted every time one makes an irreversible computation in any way. Reversible computation is not subject to Landauer's limit, so we should expect for reversible computers to start to outperform conventional computers in very specialized reversible tasks in the near future. Now, many people who accept Landauer's principle then assume that reversible computation is inherently weak and unable to do anything interesting because either the computational overhead is too great or because one reversible computation invariably produces so much garbage information that one will need to expend the energy in reversible computation anyways after one performs the calculation. This is not true.

First of all, Charles Bennett has shown that all conventional computation can be emulated by a reversible computer with only a slight computational overhead in this paper and (see this paper by Emanuel Knill for the optimal solution to Bennett's pebble game). Any $S$ space and $T$ time computation can be calculated reversibly in $O(T\cdot(\frac{T}{S})^{\epsilon})$ time and $O(S\cdot\log(\frac{S}{T}))$ space. If $TS(n)$ denotes the least product of the space times the time required to perform an $n$ unit of time and $1$ unit of space computation reversibly using Bennett's pebble game, then Knill has shown that $TS(n)=n\cdot 2^{2\sqrt{\log(n)}\cdot(1+o(n))}$.

This computational overhead can be further managed by using partially reversible computation instead of completely reversible computation. Now, Bennett's bounds are the bounds in the worst case scenario, and in many cases, reversible computation can perform a calculation in nearly as many steps as conventional computation.

Now for some reason, people often seem to think that brute force search algorithms such as Bitcoin mining are inherently irreversible and that by
Landauer's principle, Bitcoin mining on a classical computer requires one to spend a certain minimum amount of energy per hash.

I have written some code in the completely reversible programming language Janus which emulates cryptocurrency mining but which does not require one to build up any garbage information. You can find an online interpreter for Janus at http://topps.diku.dk/pirc/?id=janusB and some details about Janus in the book Introduction to Reversible Computing by Kaylan Perumalla.

The goal of the following POW problem is to find an input `i`

where `w=12321`

after we perform the assignments
`w=i; x=((i+214)^(i+142211))+(w&1231); w-=(x&13321).`

```
i w x
procedure proofofwork
w+=i
x^=((i+214)^(i+142211))+(w&1231)
w-=(x&13321)
procedure main
call proofofwork
from i=0 do
uncall proofofwork
i+=1
call proofofwork
until (w=12321)
uncall proofofwork
```

_{(Implementation)}

The output of this program for solving a POW problem (and this output includes all possible garbage information) is

```
i = 20513
w = 0
x = 0
```

and `i=20513`

is a solution to this POW problem. This technique for solving POW problems reversibly holds for all POW problems such as that of finding SHA-256 hashes for Bitcoin mining and more generally for all pure brute force search problems.

You can find this erroneous claim in the following sources.

https://download.wpsoftware.net/bitcoin/asic-faq.pdf

https://download.wpsoftware.net/bitcoin/pos.pdf

I have contacted Andrew Poelstra and he has refused to admit that yes reversible computation actually can be used to effectively mine Bitcoin.

Bitcoin for the Befuddled-Conrad Barski, Chris Wilmer

Bitcoin and Cryptocurrency Technologies-I have contacted the authors of this book, and they have refused to put a correction on their errata page or say that their errata page is no longer being updated.

Notice how in none of the above papers do any of the authors attempt to calculate nor estimate how many times $k\cdot T$ energy must be spent per Bitcoin hash. They do not even attempt to define an instructional mining algorithm that is much simpler to describe than Bitcoin's mining algorithm just so that it will be easy to calculate how many times $k\cdot T$ energy must be spent on solving these mining problems or how much information must be deleted in order to mine Bitcoin. I have contacted the authors of the above papers and books and they have so far refused to post errata or retractions. Unfortunately, unlike most misconceptions in mathematics and computer science, for some reason even so-called experts do not seem to be able to let go of this one.

Metacreated tea.mathoverflow.net/discussion/1165/… $\endgroup$ – user9072 Oct 8 '11 at 14:27