Membrane Computing

The history of formalizing the notion of algorithm (and of computation) dates back to G.W. Leibniz (1646–1716) when it focused on trying to model the computations performed by humans, for example bank clerks. These efforts culminated in the first part of the 20th century with the formalization in the form of machines, in the work of Turing [238]. These formalizations were very successful, because they led to the construction of the first electronic computers in the 1940’s. These efforts already were using some ideas from biology, for example, the functioning of neurons in neural networks (Kleene [106], McCulloch and Pitts [165]).

The main paradigms of membrane computing are abstracted from the structure and the functioning of living cells. That is why we start by briefly recalling some information about the plasma membrane, the cell compartmentalization, the trans-membrane transfer of chemicals, and the inter-cellular communication. To this end we use standard biological books, mainly [4] (but also other sources, such as [9, 127, 129, 237]). The presentation will be schematic, bearing in mind the models we will define in the subsequent chapters of the book, and having as our audience the computer scientist.

We proceed now to introduce the basic model of a membrane system (P system), the one with the membranes arranged in a hierarchical structure, as in a cell, and processing multisets of symbol—objects. We discuss first the simplest model, and the definition will be only partially formalized, in order to introduce the main ideas in a friendly manner. We then prove that this class of systems is not powerful enough, an observation which makes necessary the introduction of further features (such as a priority relation among rules and the membrane dissolving action). This is the first significant class of membrane systems, and we investigate it in several details. First, we illustrate the definition with several examples, then, in Section 3.3, we investigate the power of these basic extensions. A complete formalization is given in Section 3.5. Several further extensions of the model, with additional features, are discussed and investigated in Section 3.6.

In this chapter we still deal with membrane systems which have multisets of symbol—objects in their regions, but with the evolution rules of a type much different from the rewriting-like rules considered in the previous chapter, and closer to ways of transferring chemicals through membranes as encountered in biology. Specifically, we will compute by communication only, by changing the places of objects with respect to the membranes of a system, and not by changing the objects themselves. We will find that also in this framework we can get computational universality, and this is a rather interesting result, from various points of view. First, as we will see, the rules we use correspond directly to well-known biochemical processes. Second, because we do not change the objects, we do not create and we do not destroy them, and this means that the systems which follow observe the conservation law (which is not necessarily the case with the systems considered in the previous chapter, where rules of the form a → aa were used without taking care of the way of producing two copies of an object from only one existing copy). Third, the universality results show that in our framework communication is rather powerful. Communication makes the difference between a collection of separate computing agents and a system of cooperating agents; it is related to the so-called “system effect” (to synergy, emergent behaviour), so it is somewhat a common sense statement that communication is powerful.

In the systems considered in the previous chapters, the membrane structure corresponds to a cell-like structure, with the membranes arranged hierarchically. Such an arrangement is described by a tree. From a mathematical point of view it is then natural to consider related machineries whose underlying membrane structure is described by a graph of a given form, more restrictive or more general than a tree. More restrictive can be, for instance, a binary tree (each membrane directly contains two membranes), a linear tree (with all membranes arranged vertically, one into another), or a star (a tree with only two levels, hence with all internal membranes placed in the skin membrane). Because many universality results given in the previous chapters refer to systems with only two membranes, we implicitly have a sort of “normal form” in what concerns the underlying tree: of depth 2, linear.

In Subsection 2.3.11, we mentioned that many practical problems are intractable for normal computers, and that the parallelism is a possible way to cope with this situation. One of the main features of membrane systems is their inherent parallelism. Can this parallelism be used for solving — in theory — hard problems in a feasible time? The answer is positive, and we will illustrate it for various classes of P systems (with enhanced parallelism), which will be shown to be able to solve NP-complete problems in polynomial (often, linear) time. In order to have a systematic framework for assessing the quality of such a solution to a given problem, we start by introducing some new complexity classes, which seem to be appropriate to the membrane computing area.

In the previous chapters we have systematically considered only two types of problems and results related to them: computability power (also looking for normal forms, from various points of view, especially in what concerns the number of membranes) and computability efficiency. However, in the membrane computing literature there are several directions of research which are different from the above two, some of them mathematically motivated, others having computer science motivations, and others aiming to get closer to reality (in two directions: to the living cell, and to possible applications). In the present chapter we briefly present some results from the first two categories, that is with mathematical or computer science motivations, while in the next chapter we will consider attempts to bring membrane systems closer to biology or to other areas where the paradigms of membrane computing seem to be useful.

In the Introduction, we stressed the fact that membrane computing is inspired by the biology of the cell, but it is a theoretical computer science enterprise, aiming to provide new computing paradigms abstracted from the cell structure and functioning, but not (yet) trying to model the cell in such a way as to return relevant conclusions to the biologist. Anyway, this was the style of the developments in this area up to now and this was the style of this book. On the other hand, the mathematical developments in membrane computing already seem to make possible attempts to capture more real-life features of living cells, so that, to try to build a model of the cell, starting from the computing models inspired by the cell. The usefulness of such a model can be proved by (making possible) computer simulations of various aspects of a cell.