What is Reversible Computing and why do we need it

What are reversible computing and reversible programming

Reversible computing is a computing paradigm that can deterministically undo a computational process, it requires a user not erasing any information during computations. It boomed during 1970-2005, however, but runs into a winter after that. It can do anything that a traditional computing device can do, with possible overheads in time and space. Reversible programing is often considered as the computing model designed for reversible computing, while it can also be executed on a irreversible device. The following book covers a lot about reversible programming.

Why reversible computing is the future of computing: from a physicist's perspective

The driving force of studying reversible computing is improving the energy efficiency of our computing devices. Energy efficiency of computing devices affect the value of bitcoins, the battery size of a spacecraft and artificial intelligence (AI) industry as we will cover bellow.

As is well know, the fundamental laws of physics are reversible. Have you ever had such a confusion that why our computing model is irreversible while our world is governed by reversible laws? This discrepency is due to the fact that the irreversibility is an emergent phenomenon of statistic physics, we need a ideal heat bath that having an "infinite size" to create irreversibility. This is why the energy efficiency of traditional devices is getting harder and harder to improve, although they are still several orders above the Landauer's limit. The Landauer's principle states that irreversible computing has a lower bound of energy cost ~$\ln 2 k_b T$

Landauer's principle is a physical principle pertaining to the lower theoretical limit of energy consumption of computation. It holds that "any logically irreversible manipulation of information, such as the erasure of a bit or the merging of two computation paths, must be accompanied by a corresponding entropy increase in non-information-bearing degrees of freedom of the information-processing apparatus or its environment".Another way of phrasing Landauer's principle is that if an observer loses information about a physical system, the observer loses the ability to extract work from that system.

Microscopic systems that can be used to build up a reversible computing device are ubiquitous, like fluxon, cold atoms, DNA and quantum dots. Even the adiabatic CMOS (a reversible computing device utilizing CMOS technology) can potentially be orders more energy efficient than traditional CMOS, and it is already useful in spacecrafts. The detailed analysis of the energy-speed trade off in adiabatic CMOS can be found here.

In reversible programming, automatically differentiating any program is directly achievable. Automatic differentiation is a building block of artificial intelligence, crunching this problem can potentially lead to the next boom of AI. Programs are built on top of basic instructions like "+", "*", "/", "-". We can use these basic instructions to write Bessel functions, singular value decompositions et. al. Traditional autodiff frameworks keep track of intermediate states in a global stack and use them for back-propagation. However, doing this brings space overheads that linear to time, which can easily explode the memory. Reversible programming reverse the tape directly for you, while having flexible yet efficient time-space tradeoff algorithms to control the memory usage.

I am optimistic about reversible computing also because we have so much room to improve in the energy perspective. Our computer computes one bit information at the energy cost ~$10^8 k_b T$, while in our body, DNA copy machine computes a bit information at an energy cost ~$10 k_b T$. To embrace the true artificial intelligence, we still have a long way to go.