Membrane systems have been inspired from the structure and the functioning of the living cells. They were introduced and studied by Gh.Paun under the name of P systems ; some applications of the membrane systems are presented in . Membrane systems are essentially models of distributed, parallel and nondeterministic systems. Here we motivate and present the mobile membranes. Mobile membranes represent a variant of membrane systems inspired by the biological movements given by endocytosis and exocytosis. They have the expressive power of both P systems and process calculi with mobility such as mobile ambients and brane calculi . Computations with mobile membranes can be defined over specific configurations (like process calculi), while they represent also a rule-based formalism (like P systems).

The model is characterized by two essential features: A spatial structure consisting of a hierarchy of membranes (which do not intersect) with objects associated to them. A membrane without any other membranes inside is called elementary. The general rules describing the evolution of the structure: endocytosis (moving an elementary membrane inside a neighbouring membrane) and exocytosis (moving an elementary membrane outside the membrane where it is placed). More specific rules are given by pinocytosis (engulfing zero external membranes) and phagocytosis (engulfing just one external elementary membrane).

The computations are performed in the following way: starting from an initial structure, the system evolves by applying the rules in a nondeterministic and maximally parallel manner. A rule is applicable when all the involved objects and membranes appearing in its left hand side are available. The maximally parallel way of using the rules means that in each step a maximal multiset of rules is applied, namely a multiset of rules such that no further rule can be added to the set. A halting configuration is reached when no rule is applicable. The result is represented by the number of objects associated to a specified membrane.

Mobile membranes represents a formalism which describes the movement of membranes inside a spatial structure by applying rules from a given set of rules . The mobility is provided by consumption and rewriting of objects. In terms of computation, the work is performed using membrane configurations. A the set of membrane configurations (ranged by ) os defined by using the free monoid (ranged over by ) generated by a finite alphabet (ranged over by ):

If and are two membrane configurations, reduces to (denoted by ) if there exists a rule in the set of rules applicable to the configuration such that the new configuration is obtained. When applying the rules of , also the following inference rules are used:

When describing a computation of a systems of mobile membranes, an initial configuration and a set of rules are given. The rules used in this paper describe an (object rewriting), movement (moving an elementary membrane inside a neighbouring membrane), movement (moving an elementary membrane outside the membrane where it is placed), (engulfing zero external membranes), and (engulfing just one external elementary membrane).

Computability Power of Mobile Membranes

A specific feature of the mobile membranes is that this new rule-based model is appropriate to prove computability results in terms of Turing machines rather by reduction to the lambda calculus as in the case of process calculi with mobility. In this section are defined four classes of membranes inspired from biological facts, and it is shown that their computational power depends on the initial configuration and on the set of rules used.

Simple Mobile Membranes

The systems of simple mobile membranes (SM) are defined over the set of configurations , and evolve using endocytosis and exocytosis rules, namely moving a membrane inside a neighbouring membrane, or outside the membrane where it is placed, respectively. The evolution from a configuration to another is made using rules from the set of rules defined as follows:

, for , , ; (local object evolution)

, for , , ; (global object evolution)

, for , ; (endocytosis)

, for , ; (exocytosis)

where is a multiset, and , are arbitrary membrane configurations.

Turing completeness can be obtained by using nine membranes together with the operations of endocytosis and exocytosis . In it is proven that four mobile membranes are enough to get the power of a Turing machine, while in the number of membranes is decreased to three.

denotes the family of all sets generated inside a given membrane by simple mobile membranes using local evolution rules (), endocytosis and exocytosis rules. Whenever global evolution rules () are used, the parameter is replaced by . If a type of rules is not used, then its name is omitted from the list. The number of membranes does not increase during the computation, but it can decrease by sending membranes out of the system. In this case, the denotes the family of sets of vectors of natural numbers computed by using at most $n$ membranes. denoted the family of Turing computable sets of vectors generated by arbitrary grammars.

It is proved in that . The research line initiated in membrane computing is to find membrane systems with a minimal set of ingredients which are powerful enough to achieve the full power of Turing machines. In this way previous result presented in are improved by decreasing the number of membranes to three. Moreover, this is achieved by using local evolution rules instead of global evolution rules.

Theorem. .

The proof of this result uses a similar technique to that used in .

Enhanced Mobile Membranes

The systems of enhanced mobile membranes are a variant of simple membrane systems proposed in for describing some biological mechanisms of the immune system. The operations governing the mobility of the systems of enhanced mobile membranes are endocytosis (endo), exocytosis (exo), forced endocytosis (fendo), forced exocytosis (fexo).The evolution from a configuration to another is made using rules from the set of rules defined as follows:

for ; (endocytosis)

, for ; (exocytosis)

for , ; (enhanced endocytosis)

for ;(enhanced exocytosis)

\noindent where is a multiset and is an arbitrary membrane configuration.

The computational power of the systems of enhanced mobile membranes using these four operations was studied in where it is proved that twelve membranes can provide the computational universality, while in the result is improved by reducing the number of membranes to nine. It is worth to note that unlike the previous results, the rewriting of object by means of context-free rules is not used in any of the results (and their proofs).

The interplay between these four operations is quite powerful, and the computational power of a Turing machine is obtained using twelve membranes without using the context-free evolution of objects .

The family of all sets generated inside a given membrane by enhanced mobile membranes of degree at most using rules , is denoted by .

Theorem. .

Theorem. .

When proving the result of the previous theorem the authors have not used an optimal construction of a membrane system. In what follows it is proven that using the same types of rules (endo, exo, fendo, fexo) a membrane system can be constructed using only nine membranes instead of twelve membranes. If this is an optimal construction remains an open problem.

Theorem. .

The proof is similar to that presented in .

Mutual Mobile Membranes

Following the approach presented in , "systems of mutual mobile membranes" representing a variant of systems of simple mobile membranes in which the endocytosis and the exocytosis work whenever the involved membranes "agree" on the movement are defined; this agreement is described by using dual objects and in the involved membranes. The operations governing the mobility of the systems of mutual mobile membranes are mutual endocytosis (mutual endo), and mutual exocytosis (mutual exo). The evolution from a configuration to another is made using rules from the set of rules defined as follows:

for ; (mutual endocytosis)

for ; (mutual exocytosis)

where is a multiset and is an arbitrary membrane configuration.

It is enough to consider the biologically inspired operations of mutual endocytosis and mutual exocytosis and three membranes to get the full computational power of a Turing machine . Three also represents the minimum number of membranes in order to discuss properly about the movement provided by endocytosis and exocytosis: working with configurations corresponding to a system of two membranes moving inside a skin membrane.

The family of all sets generated inside a given membrane by mutual mobile membranes of degree using mutual endocytosis rules (mendo) and mutual exocytosis rules (mexo) is denoted by . Therefore, the result can be formulated as following.

Theorem. .

In systems of simple mobile membranes with local evolution rules and mobility rules it is known that systems of degree three have the same power as a Turing machine, while in systems of enhanced mobile membranes using only mobility rules the degree of systems having the same power as a Turing machine increases to nine. In each mobility rule from systems of simple and enhanced mobile membranes, in the left hand side of the rules only one object appears in the proofs. By using multisets instead of objects and synchronization by objects and co-objects, it is proved that it is enough to consider only systems of three mutual mobile membranes together with the operations of mutual endocytosis and mutual exocytosis to get the full computational power of a Turing machine.

The proof is done in a similar manner with the proof for the computational universality of the systems of enhanced mobile membranes .

Mutual Membranes with Objects on Surface

Membrane systems and brane calculus start from the same observations; however, they are built having in mind different goals: membrane systems investigate formally the computational nature and power of various features of membranes, while the brane calculus is capable to give a faithful and intuitive representation of the biological reality. In the initiators of these two formalisms describe the goals they had in mind: "While membrane computing is a branch of natural computing which tries to abstract computing models, in the Turing sense, from the structure and the functioning of the cell, making use especially of automata, language, and complexity theoretic tools, brane calculi pay more attention to the fidelity to the biological reality, have as a primary target systems biology, and use especially the framework of process~algebra."

In are defined systems of mutual membranes with objects on surface, following the idea of adding objects on membrane and using the biologically inspired rules pino/exo/phago coming from [12,14,18,19]. Objects and co-objects are used in phago and exo rules in order to illustrate the fact that both involved membranes agree on the movement. The evolution from a configuration to another is made using rules from the set of rules defined as follows:

, for (pino)

, for a (exo)

, for (phago)

\noindent where is a multiset and , are arbitrary membrane configurations.

The computational power of systems of mutual membranes with objects on surface controlled by pairs of rules is investigated: pino/exo or phago/exo, proving that they are universal even using a small number of membranes. These cases were already investigated in ; however better results are provided by improving the number of membranes. A summary of the results (existing and new ones) is given in what follows:

+Summary of Results Operations Number of membranes Weight RE Where Pino, exo 8 4,3 Yes Theorem 6.1 Pino, exo 3 5,4 Yes Here Phago, exo 9 5,2 Yes Theorem 6.2 Phago, exo 9 4,3 Yes Theorem 6.2 Phago, exo 4 6,3 Yes Here