Taking into account the amount of energy used and/or manipulated during computations may yield formal computational models which are closer to physical reality.
Membrane systems (also known as P systems) were introduced in 1998 by Gheorge Păun as a class of distributed and parallel computing devices, inspired by the structure and function of living cells. The basic model consists of a hierarchical structure composed of several membranes embedded into a main membrane called the skin. Membranes divide the Euclidean space into regions that contain some objects and evolution rules. Using these rules, the objects may evolve and/or move from a region to a neighbouring one. Every computation starts from an initial configuration of the system, in which multisets of objects are scattered among the regions. At each computation step some rules are selected from the pool of active rules, according to a predefined strategy, and are applied; the computation terminates when no evolution rule can be selected. Usually, the result of a computation is the multiset of objects contained in an output membrane or emitted from the skin of the system.
At the Department of Informatics, Systems and Communication (DISCo) of the University of Milano–Bicocca we have been working on P systems since their invention. In particular, we study the computational power of several variants of P systems by using techniques from the theory of Computational Complexity. When I joined the group in 2004, I had just completed my Ph.D. in Computer Science with a thesis on complexity issues related to classical and quantum circuits. It was therefore very natural to me to enter the exciting world of P systems by defining two models that take account of the amount of energy exchanged with the environment and/or manipulated during computations: energy-based P systems and UREM (Unit Rules and Energy assigned to Membranes) P systems.
Figure 1: On the left: an example of an energy-based P system. The skin membrane contains one copy of object a, two copies of c and three energy units. The rule ae2 → (b,1) adds two energy units to a copy of a, produces a copy of object b and sends it to the (until now empty) region enclosed by membrane 1. On the right: illustration of the effect of rule (ini: a, Δe, b) on membrane i. The object a crosses the membrane becoming b; simultaneously, the energy assigned to the membrane passes from ei to ei + Δe.
In energy-based P systems, a given amount of energy is associated with each object. Moreover, instances of a special symbol are used to denote free energy units occurring inside the regions of the system. These energy units can be used to move or transform objects, by rules that satisfy the principle of energy conservation. The transformation is performed by taking/releasing an appropriate amount of free energy units from/to the region where the rule is applied. My colleagues and I have studied several computational properties of energy-based P systems, trying to characterize their computational power. We have thus shown that they are able to simulate any reversible and conservative circuit composed of Fredkin gates, and we have proved that they are universal – that is, they have computational power equivalent to that of Turing machines – provided that a form of local priorities is assigned to the rules of the system. Without such priorities, the computational power decreases and is no more than that of Vector Addition Systems. Characterizing the precise computational power of energy-based P systems is still an open problem; however, the results obtained so far indicate that these systems can be used as a modelling tool just like Petri nets.
On the other hand, in UREM P systems a non-negative value of energy is assigned to each membrane. The rules are of two possible kinds: (ini: a, Δe, b) and (outi: a, Δe, b), controlling the objects trying to enter and leave membrane i, respectively. When one of these rules is applied, the object a on which it operates is transformed to b while crossing the membrane; simultaneously, the amount of energy associated with the membrane is changed by adding the quantity Δe, which may be positive, zero or negative. Also these P systems have undergone an extensive study concerning their computational power. In this case by using a form of local priorities we reach the computational power of Turing machines, whereas by avoiding priorities the computational power decreases. This time, however, we obtain a characterization of PsMATλ, an interesting class of matrix grammars which is not so easy to obtain with other computational models.
Another interesting aspect of UREM P systems is that they have allowed us to define a quantum-inspired variant of P systems. Instead of merely translating each rule of UREM P systems to a unitary matrix, we decided to propose a completely new computation device based on creation and annihilation, which are among the most elementary operations which can be conceived in physics: adding or removing a quantum of energy to/from a quantum system. Studying these P systems will certainly yield interesting observations both from the computational point of view and from the quantum physics side. The first results we have obtained are that – differently from the classical version – these systems do not need to use priorities to be universal; moreover, the use of creation and annihilation allows the definition of linear (but non-unitary) operators, that allow one to efficiently solve NP-complete problems. The latter aspect should be further investigated, since this result is in contrast with what can be done with “traditional” quantum computers.
Please contact:
Alberto Leporati
Dipartimento di Informatica, Sistemistica e Comunicazione
Università degli Studi di Milano – Bicocca
E-mail:
