Reversible computing
Encyclopedia
Reversible computing is a model of computing
where the computational process to some extent is reversible, i.e., time
-invertible. A necessary condition for reversibility of a computational model
is that the transition function
mapping states to their successors at a given later time should be one-to-one
. Reversible computing is generally considered an unconventional
form of computing.
There are two major, closely related, types of reversibility that are of particular interest for this purpose: physical reversibility and logical reversibility.
A process is said to be physically reversible if it results in no increase in physical entropy
; it is isentropic. These circuits are also referred to as charge recovery logic or adiabatic computing. Although in practice no nonstationary physical process can be exactly physically reversible or isentropic, there is no known limit to the closeness with which we can approach perfect reversibility, in systems that are sufficiently well-isolated from interactions with unknown external environments, when the laws of physics describing the system's evolution are precisely known.
Probably the largest motivation for the study of technologies aimed at actually implementing reversible computing is that they offer what is predicted to be the only potential way to improve the energy efficiency
of computers beyond the fundamental von Neumann-Landauer limit of kT ln(2) energy dissipated per irreversible bit operation.
As was first argued by Rolf Landauer
of IBM
, in order for a computational process to be physically reversible, it must also be logically reversible. Landauer's principle
is the loosely formulated notion that the erasure of n bits of information must always incur a cost of nk ln(2) in thermodynamic entropy
. A discrete, deterministic computational process is said to be logically reversible if the transition function
that maps old computational states to new ones is a one-to-one function; i.e. the output logical states uniquely defines the input logical states of the computational operation.
For computational processes that are nondeterministic (in the sense of being probabilistic or random), the relation between old and new states is not a single-valued function
, and the requirement needed to obtain physical reversibility becomes a slightly weaker condition, namely that the size of a given ensemble of possible initial computational states does not decrease, on average, as the computation proceeds forwards.
itself) can also be understood to be a direct logical consequence of the underlying reversibility of physics
, as is reflected in the general Hamiltonian formulation of mechanics
, and in the unitary time-evolution operator
of quantum mechanics
more specifically.
In the context of reversible physics, the phenomenon of entropy increase (and the observed arrow of time
) can be understood to be consequences of the fact that our evolved predictive capabilities are rather limited, and cannot keep perfect track of the exact reversible evolution of complex physical systems, especially since these systems are never perfectly isolated from an unknown external environment, and even the laws of physics themselves are still not known with complete precision. Thus, we (and physical observers generally) always accumulate some uncertainty about the state of physical systems, even if the system's true underlying dynamics is a perfectly reversible one that is subject to no entropy increase if viewed from a hypothetical omniscient perspective in which the dynamical laws are precisely known.
The implementation of reversible computing thus amounts to learning how to characterize and control the physical dynamics of mechanisms to carry out desired computational operations so precisely that we can accumulate a negligible total amount of uncertainty regarding the complete physical state of the mechanism, per each logic operation that is performed. In other words, we would need to precisely track the state of the active energy that is involved in carrying out computational operations within the machine, and design the machine in such a way that the majority of this energy is recovered in an organized form that can be reused for subsequent operations, rather than being permitted to dissipate into the form of heat.
Although achieving this goal presents a significant challenge for the design, manufacturing, and characterization of ultra-precise new physical mechanisms for computing
, there is at present no fundamental reason to think that this goal cannot eventually be accomplished, allowing us to someday build computers that generate much less than 1 bit's worth of physical entropy (and dissipate much less than kT ln 2 energy to heat) for each useful logical operation that they carry out internally.
The motivation behind much of the research that has been done in reversible computing was the first seminal paper on the topic, which was published by Charles H. Bennett
of IBM research in 1973. Today, the field has a substantial body of academic literature behind it. A wide variety of reversible device concepts, logic gate
s, electronic circuit
s, processor architectures, programming language
s, and application algorithm
s have been designed and analyzed by physicist
s, electrical engineers, and computer scientist
s.
This field of research awaits the detailed development of a high-quality, cost-effective, nearly reversible logic device technology, one that includes highly energy-efficient clocking and synchronization
mechanisms. This sort of solid engineering progress will be needed before the large body of theoretical research on reversible computing can find practical application in enabling real computer technology to circumvent the various near-term barriers to its energy efficiency, including the von Neumann-Landauer bound. This may only be circumvented by the use of logically reversible computing, due to the Second Law of Thermodynamics
.
Computing
Computing is usually defined as the activity of using and improving computer hardware and software. It is the computer-specific part of information technology...
where the computational process to some extent is reversible, i.e., time
DTIME
In computational complexity theory, DTIME is the computational resource of computation time for a deterministic Turing machine. It represents the amount of time that a "normal" physical computer would take to solve a certain computational problem using a certain algorithm...
-invertible. A necessary condition for reversibility of a computational model
Computational model
A computational model is a mathematical model in computational science that requires extensive computational resources to study the behavior of a complex system by computer simulation. The system under study is often a complex nonlinear system for which simple, intuitive analytical solutions are...
is that the transition function
Transition function
In mathematics, a transition function has several different meanings:* In topology, a transition function is a homeomorphism from one coordinate chart to another...
mapping states to their successors at a given later time should be one-to-one
Injective function
In mathematics, an injective function is a function that preserves distinctness: it never maps distinct elements of its domain to the same element of its codomain. In other words, every element of the function's codomain is mapped to by at most one element of its domain...
. Reversible computing is generally considered an unconventional
Unconventional computing
Unconventional computing is computing by a wide range of new or unusual methods. It is also known as alternative computing. The different methods of unconventional computing include optical computing, quantum computing, chemical computing, natural computing, biologically-inspired computing, wetware...
form of computing.
There are two major, closely related, types of reversibility that are of particular interest for this purpose: physical reversibility and logical reversibility.
A process is said to be physically reversible if it results in no increase in physical entropy
Entropy
Entropy is a thermodynamic property that can be used to determine the energy available for useful work in a thermodynamic process, such as in energy conversion devices, engines, or machines. Such devices can only be driven by convertible energy, and have a theoretical maximum efficiency when...
; it is isentropic. These circuits are also referred to as charge recovery logic or adiabatic computing. Although in practice no nonstationary physical process can be exactly physically reversible or isentropic, there is no known limit to the closeness with which we can approach perfect reversibility, in systems that are sufficiently well-isolated from interactions with unknown external environments, when the laws of physics describing the system's evolution are precisely known.
Probably the largest motivation for the study of technologies aimed at actually implementing reversible computing is that they offer what is predicted to be the only potential way to improve the energy efficiency
Energy conversion efficiency
Energy conversion efficiency is the ratio between the useful output of an energy conversion machine and the input, in energy terms. The useful output may be electric power, mechanical work, or heat.-Overview:...
of computers beyond the fundamental von Neumann-Landauer limit of kT ln(2) energy dissipated per irreversible bit operation.
As was first argued by Rolf Landauer
Rolf Landauer
Rolf William Landauer was an IBM physicist who in 1961 argued that when information is lost in an irreversible circuit, the information becomes entropy and an associated amount of energy is dissipated as heat...
of IBM
IBM
International Business Machines Corporation or IBM is an American multinational technology and consulting corporation headquartered in Armonk, New York, United States. IBM manufactures and sells computer hardware and software, and it offers infrastructure, hosting and consulting services in areas...
, in order for a computational process to be physically reversible, it must also be logically reversible. Landauer's principle
Landauer's Principle
Landauer's Principle, first argued in 1961 by Rolf Landauer of IBM, 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...
is the loosely formulated notion that the erasure of n bits of information must always incur a cost of nk ln(2) in thermodynamic entropy
Entropy
Entropy is a thermodynamic property that can be used to determine the energy available for useful work in a thermodynamic process, such as in energy conversion devices, engines, or machines. Such devices can only be driven by convertible energy, and have a theoretical maximum efficiency when...
. A discrete, deterministic computational process is said to be logically reversible if the transition function
Transition function
In mathematics, a transition function has several different meanings:* In topology, a transition function is a homeomorphism from one coordinate chart to another...
that maps old computational states to new ones is a one-to-one function; i.e. the output logical states uniquely defines the input logical states of the computational operation.
For computational processes that are nondeterministic (in the sense of being probabilistic or random), the relation between old and new states is not a single-valued function
Single-valued function
A single-valued function is an emphatic term for a mathematical function in the usual sense. That is, each element of the function's domain maps to a single, well-defined element of its range. This contrasts with a general binary relation, which can be viewed as being a multi-valued function...
, and the requirement needed to obtain physical reversibility becomes a slightly weaker condition, namely that the size of a given ensemble of possible initial computational states does not decrease, on average, as the computation proceeds forwards.
The reversibility of physics and reversible computing
Landauer's principle (and indeed, the second law of thermodynamicsSecond law of thermodynamics
The second law of thermodynamics is an expression of the tendency that over time, differences in temperature, pressure, and chemical potential equilibrate in an isolated physical system. From the state of thermodynamic equilibrium, the law deduced the principle of the increase of entropy and...
itself) can also be understood to be a direct logical consequence of the underlying reversibility of physics
Physics
Physics is a natural science that involves the study of matter and its motion through spacetime, along with related concepts such as energy and force. More broadly, it is the general analysis of nature, conducted in order to understand how the universe behaves.Physics is one of the oldest academic...
, as is reflected in the general Hamiltonian formulation of mechanics
Hamiltonian mechanics
Hamiltonian mechanics is a reformulation of classical mechanics that was introduced in 1833 by Irish mathematician William Rowan Hamilton.It arose from Lagrangian mechanics, a previous reformulation of classical mechanics introduced by Joseph Louis Lagrange in 1788, but can be formulated without...
, and in the unitary time-evolution operator
Time evolution
Time evolution is the change of state brought about by the passage of time, applicable to systems with internal state . In this formulation, time is not required to be a continuous parameter, but may be discrete or even finite. In classical physics, time evolution of a collection of rigid bodies...
of quantum mechanics
Quantum mechanics
Quantum mechanics, also known as quantum physics or quantum theory, is a branch of physics providing a mathematical description of much of the dual particle-like and wave-like behavior and interactions of energy and matter. It departs from classical mechanics primarily at the atomic and subatomic...
more specifically.
In the context of reversible physics, the phenomenon of entropy increase (and the observed arrow of time
Arrow of time
The arrow of time, or time’s arrow, is a term coined in 1927 by the British astronomer Arthur Eddington to describe the "one-way direction" or "asymmetry" of time...
) can be understood to be consequences of the fact that our evolved predictive capabilities are rather limited, and cannot keep perfect track of the exact reversible evolution of complex physical systems, especially since these systems are never perfectly isolated from an unknown external environment, and even the laws of physics themselves are still not known with complete precision. Thus, we (and physical observers generally) always accumulate some uncertainty about the state of physical systems, even if the system's true underlying dynamics is a perfectly reversible one that is subject to no entropy increase if viewed from a hypothetical omniscient perspective in which the dynamical laws are precisely known.
The implementation of reversible computing thus amounts to learning how to characterize and control the physical dynamics of mechanisms to carry out desired computational operations so precisely that we can accumulate a negligible total amount of uncertainty regarding the complete physical state of the mechanism, per each logic operation that is performed. In other words, we would need to precisely track the state of the active energy that is involved in carrying out computational operations within the machine, and design the machine in such a way that the majority of this energy is recovered in an organized form that can be reused for subsequent operations, rather than being permitted to dissipate into the form of heat.
Although achieving this goal presents a significant challenge for the design, manufacturing, and characterization of ultra-precise new physical mechanisms for computing
Computing
Computing is usually defined as the activity of using and improving computer hardware and software. It is the computer-specific part of information technology...
, there is at present no fundamental reason to think that this goal cannot eventually be accomplished, allowing us to someday build computers that generate much less than 1 bit's worth of physical entropy (and dissipate much less than kT ln 2 energy to heat) for each useful logical operation that they carry out internally.
The motivation behind much of the research that has been done in reversible computing was the first seminal paper on the topic, which was published by Charles H. Bennett
Charles H. Bennett (computer scientist)
Charles H. Bennett is an IBM Fellow at IBM Research. Bennett's recent work at IBM has concentrated on a re-examination of the physical basis of information, applying quantum physics to the problems surrounding information exchange...
of IBM research in 1973. Today, the field has a substantial body of academic literature behind it. A wide variety of reversible device concepts, logic gate
Logic gate
A logic gate is an idealized or physical device implementing a Boolean function, that is, it performs a logical operation on one or more logic inputs and produces a single logic output. Depending on the context, the term may refer to an ideal logic gate, one that has for instance zero rise time and...
s, electronic circuit
Electronic circuit
An electronic circuit is composed of individual electronic components, such as resistors, transistors, capacitors, inductors and diodes, connected by conductive wires or traces through which electric current can flow...
s, processor architectures, programming language
Programming language
A programming language is an artificial language designed to communicate instructions to a machine, particularly a computer. Programming languages can be used to create programs that control the behavior of a machine and/or to express algorithms precisely....
s, and application algorithm
Algorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
s have been designed and analyzed by physicist
Physicist
A physicist is a scientist who studies or practices physics. Physicists study a wide range of physical phenomena in many branches of physics spanning all length scales: from sub-atomic particles of which all ordinary matter is made to the behavior of the material Universe as a whole...
s, electrical engineers, and computer scientist
Computer scientist
A computer scientist is a scientist who has acquired knowledge of computer science, the study of the theoretical foundations of information and computation and their application in computer systems....
s.
This field of research awaits the detailed development of a high-quality, cost-effective, nearly reversible logic device technology, one that includes highly energy-efficient clocking and synchronization
Synchronization
Synchronization is timekeeping which requires the coordination of events to operate a system in unison. The familiar conductor of an orchestra serves to keep the orchestra in time....
mechanisms. This sort of solid engineering progress will be needed before the large body of theoretical research on reversible computing can find practical application in enabling real computer technology to circumvent the various near-term barriers to its energy efficiency, including the von Neumann-Landauer bound. This may only be circumvented by the use of logically reversible computing, due to the Second Law of Thermodynamics
Second law of thermodynamics
The second law of thermodynamics is an expression of the tendency that over time, differences in temperature, pressure, and chemical potential equilibrate in an isolated physical system. From the state of thermodynamic equilibrium, the law deduced the principle of the increase of entropy and...
.
See also
- Reversible dynamicsReversible dynamics- Mathematics :In mathematics, a dynamical system is invertible if the forward evolution is one-to-one, not many-to-one; so that for every state there exists a well-defined reverse-time evolution operator....
- Maximum entropy thermodynamicsMaximum entropy thermodynamicsIn physics, maximum entropy thermodynamics views equilibrium thermodynamics and statistical mechanics as inference processes. More specifically, MaxEnt applies inference techniques rooted in Shannon information theory, Bayesian probability, and the principle of maximum entropy...
, on the uncertainty interpretation of the second law of thermodynamics - Reversible process
- Toffoli gateToffoli gateIn computer science, the Toffoli gate , invented by Tommaso Toffoli, is a universal reversible logic gate, which means that any reversible circuit can be constructed from Toffoli gates...
- Fredkin gateFredkin gateThe Fredkin gate is a computational circuit suitable for reversible computing, invented by Ed Fredkin. It is universal, which means that any logical or arithmetic operation can be constructed entirely of Fredkin gates...
- Quantum computing
- Billiard-ball computerBilliard-Ball ComputerA billiard ball computer, also known as a conservative logic circuit, is an idealized model of a reversible mechanical computer based on newtonian dynamics, proposed in 1982 by Edward Fredkin and Tommaso Toffoli...
- Three-input universal logic gate
- UndoUndoUndo is a command in many computer programs. It erases the last change done to the document reverting it to an older state. In some more advanced programs such as graphic processing, undo will negate the last command done to the file being edited....
- Reversible cellular automatonReversible cellular automatonA reversible cellular automaton is a cellular automaton in which every configuration has a unique predecessor. Several methods of constructing reversible cellular automata are known, including the block cellular automaton and second-order cellular automaton methods...
External links
- Introductory article on reversible computing
- First International Workshop on reversible computing
- Recent publications of Michael P. Frank
- Internet Archive backup of the "Reversible computing community Wiki" that was administered by Dr. Frank