Notes:
The original publication is available at link.springer.com.
|
Abstract.
This year marks the 40th anniversary of Charles Bennett's seminal
paper on reversible computing. Bennett's contribution is remembered
as one of the first to demonstrate how any deterministic computation
can be simulated by a logically reversible Turing machine. Perhaps
less remembered is that the same paper suggests the use of nucleic
acids to realise physical reversibility. In context, Bennett's
foresight predates Leonard Adleman's famous experiments to solve
instances of the Hamiltonian path problem using strands of DNA --- a
landmark date for the field of natural computing --- by more than
twenty years. The ensuing time has seen active research in both
reversible computing and natural computing that has been, for the most
part, unrelated. Encouraged by new, experimentally viable DNA
computing models, there is a resurgent interest in logically
reversible computing by the natural computing community. We survey
these recent results, and their underlying ideas, which demonstrate
the potential for logically and physically reversible computation
using nucleic acids
|