Simulating the Fredkin Gate with Energy-Based P Systems

Alberto Leporati (Universita degli Studi di Milano, Italy)

Claudio Zandron (Universita degli Studi di Milano, Italy)

Giancarlo Mauri (Universita degli Studi di Milano, Italy)

Abstract: Reversibility plays a fundamental role when the possibility to perform computations with minimal energy dissipation is considered. Many papers on reversible computation have appeared in literature, the most famous of which is certainly the work of Bennett on (universal) reversible Turing machines. Here we consider the work of Fredkin and Toffoli on conservative logic, which is a mathematical model that allows to describe computations which reflect some properties of microdynamical laws of physics, such as reversibility and conservation of the internal energy of the physical system used to perform the computations. The model is based upon the Fredkin gate, a reversible and "conservative" (according to a definition given by Fredkin and Toffoli) three-input/three-output boolean gate. In this paper we introduce energy{based P systems as a parallel and distributed model of computation in which the amount of energy manipulated and/or consumed during computations is taken into account. Moreover, we show how energy-based P systems can be used to simulate the Fredkin gate. The proposed P systems that perform the simulations turn out to be themselves reversible and conservative.

Keywords: Energy-based P systems, Fredkin gate, conservative logic, conservativeness, reversibility

Categories: F.1.1, F.4.2