Reversible Computing: An Introduction

Author/s

Federica Eftimiadi

Student of Electronics, Information and Bioengineering (Elettronica, Informazione e Bioingegneria), Polytechnic University, Milan., Italy

Enrico Pugni Trimigliozzi

Faculty of Electronics, Information and Bioengineering (Elettronica, Informazione e Bioingegneria), Polytechnic University, Milan., Italy

 

Abstract

Reversible computing is a paradigm where computing models are defined so that they reflect physical reversibility, one of the fundamental microscopic physical property of Nature. Also, it is one of the basic microscopic physical laws of nature. Reversible computing refers to the computation that could always be reversed to recover its earlier state. It is based on reversible physics, which implies that we can never truly erase information in a computer. Reversible computing is very difficult and its engineering hurdles are enormous. This paper provides a brief introduction to reversible computing. With these constraints, one can still satisfactorily deal with both functional and structural aspects of computing processes; at the same time, one attains a closer correspondence between the behavior of abstract computing systems and the microscopic physical laws (which are presumed to be strictly reversible) that underlay any implementation of such systems

Keywords

Composition Rule, reversible computing, reverse computation, quantum computing, adiabatic computing.

To cite this article

Eftimiadi, F., & Trimigliozzi, E.P. (2019). Reversible Computing: An Introduction, International Journal of Engineering, IT and Scientific Research (IJEISR). Vol. 3, No. 1, pp.1-4. Doi:10.31219/osf.io/z9a23

 

Copyright

Copyright © 2019 Authors retain the copyright of this article.
This article is an open access article distributed under the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0/) which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

References

    1. Bennett, C.H., (1973). Logical Reversibility of Computation,” IBM J. Res. Dev.6, 525–532. [Google Scholar]
    1. Fredkin, Edward, and Toffoli, T. (2007). “Conservative Logic,” (in preparation). Some of the material of this paper is tentatively available in the form of unpublished notes from Prof. Fredkin’s lectures, collected and organized by Bill Silver in a 895 Term Paper, “Conservative Logic,” and in the form of another 6.895 Term Paper, “A Reversible Computer Using Conservative Logic,” by Edward Barton, both at the MIT Dept. of Electr. Eng. Comp. Sci. [Google Scholar]
    1. Kinoshita, Kozo, et al., “On Magnetic Bubble Circuits,” IEEE Trans. ComputersC-25(1976), 247–253.[Google Scholar]
    1. Landauer, Rolf, “Irreversibility and Heat Generation in the Computing Process,” IBM J.5(1961), 183–191.[Google Scholar]
    1. Toffoli, Tommaso, “computation and Construction Universality of Reversible Cellular Automata,”  Comput. Syst. Sci.15(1977), 213–231.[Google Scholar]
    1. Toffoli, Tommaso, “Cellular Automata Mechanics” (Ph. D. Thesis),  Rep. no. 208, Logic of Computers Group, Univ. of Michigan (1977).[Google Scholar]
    1. Toffoli, Tommaso, “The Role of the Observer in Uniform Systems,” Applied General Systems Research(ed. G. J. Klir), 395–400 (Plenum Press, 1978).Google Scholar]
    1. Toffoli, Tommaso, (1979). “Bicontinuous Extensions of Invertible Combinatorial Functions,”  Memo MIT/LCS/TM-124, MIT Lab. for Comp. Sci. (to appear in Math. Syst. Theory).[Google Scholar]
    1. Toffoli, Tommaso, (1980).[ “Reversible Computing,”  Memo MIT/LCS/TM-151, MIT Lab. for Comp. Sci. Google Scholar]
    1. Van Rentergem, Y., De Vos, A. (2005). Optimal design of a reversible full adder. International Journal of Unconventional Computing 1(4), 339–355. [Google Scholar]
    1. Vedral, V., Barenco, A., Ekert, A. (1996). Quantum networks for elementary arithmetic operations. Physical Review A 54(1), 147–153.http://www.ams.org/mathscinet-getitem?mr=1398399 [CrossRef[ [Google Scholar]
    1. Vieri, C.J. (1999). Reversible Computer Engineering and Architecture. Ph.D. thesis, EECS Department, Massachusetts Institute of Technology. Google Scholar]
    1. Wille, R., Drechsler, R. (2010). Towards a Design Flow for Reversible Logic. Springer Science [Google Scholar]
    1. Wille, R., Offermann, S., Drechsler, R. (2010). SyReC: A programming language for synthesis of reversible circuits. In: Proceedings of the Forum on Specification & Design Languages, pp. 1–6. IET, Southhampton. [Google Scholar]
    1. Yokoyama, T., Axelsen, H. B., & Glück, R. (2008, May). Principles of a reversible programming language. In Proceedings of the 5th conference on Computing frontiers (pp. 43-54). ACM. [Google Scholar]
    1. Yokoyama, T., Glück, R. (2007). A reversible programming language and its invertible self-interpreter. In: Proceedings of Partial Evaluation and Program Manipulation, pp. 144–153. [Google Scholar]