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 [24]; some applications of the membrane systems are presented in [15]. 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 [11] and brane calculi [10]. 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 R {\displaystyle R} . The mobility is provided by consumption and rewriting of objects. In terms of computation, the work is performed using membrane configurations. A the set M {\displaystyle {\mathcal {M}}} of membrane configurations (ranged by M , N , … {\displaystyle M,N,\dots } ) os defined by using the free monoid V ∗ {\displaystyle V^{*}} (ranged over by u , v , … {\displaystyle u,v,\dots } ) generated by a finite alphabet V {\displaystyle V} (ranged over by a , b , … {\displaystyle a,b,\dots } ):
M ::= u ∣ [ M ] u ∣ M ‖ M {\displaystyle \qquad \qquad M::=u\;\mid \;[\;M\;]_{u}\;\mid \;M\|M}
If M {\displaystyle M} and N {\displaystyle N} are two membrane configurations, M {\displaystyle M} reduces to N {\displaystyle N} (denoted by M → N {\displaystyle M\rightarrow N} ) if there exists a rule in the set of rules R {\displaystyle R} applicable to the configuration M {\displaystyle M} such that the new configuration N {\displaystyle N} is obtained. When applying the rules of R {\displaystyle R} , also the following inference rules are used:
( C o m p 1 ) M → M ′ M ‖ N → M ′ ‖ N ; ( C o m p 2 ) M → M ′ N → N ′ M ‖ N → M ′ ‖ N ′ {\displaystyle \qquad {\it {(Comp1)}}\quad {\frac {\displaystyle M\ \rightarrow \ M'}{\displaystyle M\|N\ \rightarrow \ M'\|N}};\qquad \qquad {\it {(Comp2)}}\quad {\frac {\displaystyle M\ \rightarrow \ M'\qquad \displaystyle N\ \rightarrow \ N'}{\displaystyle M\|N\ \rightarrow \ M'\|N'}}} ;
( M e m ) M → M ′ [ M ] u → [ M ′ ] u ; ( S t r u c ) M ≡ m e m M ′ M ′ → N ′ N ′ ≡ m e m N M → N {\displaystyle \qquad {\it {(Mem)}}\ {\frac {\displaystyle M\ \rightarrow \ M'}{\displaystyle [\;M\;]_{u}\rightarrow [\;M'\;]_{u}}};\qquad \qquad {\it {(Struc)}}\ {\frac {\displaystyle M\equiv _{mem}M'\quad M'\rightarrow N'\quad \ N'\equiv _{mem}N}{\displaystyle M\rightarrow N}}}
When describing a computation of a systems of mobile membranes, an initial configuration M 0 {\displaystyle M_{0}} and a set of rules R {\displaystyle R} are given. The rules used in this paper describe an o b j e c t e v o l u t i o n {\displaystyle {\it {object~evolution}}} (object rewriting), e n d o c y t o s i s {\displaystyle {\it {endocytosis}}} movement (moving an elementary membrane inside a neighbouring membrane), e x o c y t o s i s {\displaystyle {\it {exocytosis}}} movement (moving an elementary membrane outside the membrane where it is placed), p i n o c y t o s i s {\displaystyle {\it {pinocytosis}}} (engulfing zero external membranes), and p h a g o c y t o s i s {\displaystyle {\it {phagocytosis}}} (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 M {\displaystyle {\mathcal {M}}} , 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 R {\displaystyle R} defined as follows:
[ [ a ‖ M ] m ‖ N ] k → [ [ v ‖ M ] m ‖ N ] k {\displaystyle [[a\;\|\;M]_{m}\;\|\;N]_{k}\rightarrow [[v\;\|\;M]_{m}\;\|\;N]_{k}} , for k , m ∈ N {\displaystyle k,m\in {\mathcal {N}}} , a ∈ V {\displaystyle a\in V} , v ∈ V ∗ {\displaystyle v\in V^{*}} ; (local object evolution)
[ a ‖ M ] m → [ v ‖ M ] m {\displaystyle [a\;\|\;M]_{m}\rightarrow [v\;\|\;M]_{m}} , for m ∈ N {\displaystyle m\in {\mathcal {N}}} , a ∈ V {\displaystyle a\in V} , v ∈ V ∗ {\displaystyle v\in V^{*}} ; (global object evolution)
[ a ‖ M 1 ] h ‖ [ M ] m → [ [ b ‖ M 1 ] h ‖ M ] m {\displaystyle [a\;\|\;M_{1}]_{h}\;\|\;[M]_{m}\rightarrow [[b\;\|\;M_{1}]_{h}\;\|\;M]_{m}} , for h , m ∈ N {\displaystyle h,m\in {\mathcal {N}}} , a , b ∈ V {\displaystyle a,b\in V} ; (endocytosis)
[ [ a ‖ M 1 ] h ‖ M ] m → [ b ‖ M 1 ] h ‖ [ M ] m {\displaystyle [[a\;\|\;M_{1}]_{h}\;\|\;M]_{m}\rightarrow [b\;\|\;M_{1}]_{h}\;\|\;[M]_{m}} , for h , m ∈ N {\displaystyle h,m\in {\mathcal {N}}} , a , b ∈ V {\displaystyle a,b\in V} ; (exocytosis) where M 1 {\displaystyle M_{1}} is a multiset, and M {\displaystyle M} , N {\displaystyle N} are arbitrary membrane configurations. Turing completeness can be obtained by using nine membranes together with the operations of endocytosis and exocytosis [21]. In [17] it is proven that four mobile membranes are enough to get the power of a Turing machine, while in [4] the number of membranes is decreased to three.
S M ( l e v o l , e n d o , e x o ) {\displaystyle SM(levol,endo,exo)} denotes the family of all sets generated inside a given membrane by simple mobile membranes using local evolution rules ( l e v o l {\displaystyle levol} ), endocytosis and exocytosis rules. Whenever global evolution rules ( g e v o l {\displaystyle gevol} ) are used, the parameter l e v o l {\displaystyle levol} is replaced by g e v o l {\displaystyle gevol} . 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 S M n ( g e v o l , e n d o , e x o ) {\displaystyle SM_{n}(gevol,endo,exo)} denotes the family of sets of vectors of natural numbers computed by using at most $n$ membranes. R E {\displaystyle RE} denoted the family of Turing computable sets of vectors generated by arbitrary grammars. It is proved in [17] that S M 4 ( g e v o l , e n d o , e x o ) = R E {\displaystyle SM_{4}(gevol,endo,exo)=RE} . 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 [17] 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. S M 3 ( l e v o l , e n d o , e x o ) = R E {\displaystyle SM_{3}(levol,endo,exo)=RE} . The proof of this result uses a similar technique to that used in [4].
Enhanced Mobile Membranes The systems of enhanced mobile membranes are a variant of simple membrane systems proposed in [1] 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 R {\displaystyle R} defined as follows:
[ u ‖ v ‖ M ] h ‖ [ v ′ ‖ N ] m → [ w ′ ‖ [ w ] h ] m {\displaystyle [u\;\|\;v\;\|\;M]_{h}\;\|\;[v'\;\|\;N]_{m}\!\rightarrow \![w'\;\|\;[w]_{h}]_{m}} for h , m ∈ N ; u ∈ V + , v , v ′ , w , w ′ ∈ V ∗ {\displaystyle h,m\!\in \!{\mathcal {N}};u\!\in \!V^{+},v,v',w,w'\!\in \!V^{*}} ; (endocytosis)
[ v ′ ‖ N ‖ [ u ‖ v ‖ M ] h ] m → [ w ‖ M ] h ‖ [ w ′ ‖ N ] m {\displaystyle [v'\;\|\;N\;\|\;[u\;\|\;v\;\|\;M]_{h}]_{m}\!\rightarrow \![w\;\|\;M]_{h}\;\|\;[w'\;\|\;N]_{m}} , for h , m ∈ N ; u ∈ V + , v , v ′ , w , w ′ ∈ V ∗ {\displaystyle h,m\!\in \!\!{\mathcal {N}};u\in V^{+},v,v',w,w'\in V^{*}} ; (exocytosis)
[ v ‖ M ] h ‖ [ u ‖ v ′ ‖ N ] m → [ [ w ‖ M ] h ‖ w ′ ‖ N ] m {\displaystyle [v\;\|\;M]_{h}\;\|\;[u\;\|\;v'\;\|\;N]_{m}\!\!\rightarrow \!\![[w\;\|\;M]_{h}\;\|\;w'\;\|\;N]_{m}} for h , m ∈ N {\displaystyle h,m\!\!\in \!\!{\mathcal {N}}} ,
u ∈ V + , v , v ′ , w , w ′ ∈ V ∗ {\displaystyle u\!\in \!V^{+},v,v'\!,w,w'\!\in \!V^{*}} ; (enhanced endocytosis)
[ u ‖ v ′ ‖ [ v ‖ M ] h ‖ N ] m → [ w ‖ M ] h ‖ [ w ′ ‖ N ] m {\displaystyle [u\;\|\;v'\;\|\;[v\;\|\;M]_{h}\;\|\;N]_{m}\!\!\rightarrow \!\![w\;\|\;M]_{h}\;\|\;[w'\;\|\;N]_{m}} for h , m ∈ N , u ∈ V + , v , v ′ , w , w ′ ∈ V ∗ {\displaystyle h,m\!\in \!{\mathcal {N}},u\in V^{+},v,v',w,w'\in V^{*}} ;(enhanced exocytosis) \noindent where M {\displaystyle M} is a multiset and N {\displaystyle N} is an arbitrary membrane configuration. The computational power of the systems of enhanced mobile membranes using these four operations was studied in [20] where it is proved that twelve membranes can provide the computational universality, while in [4] 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 [20]. The family of all sets generated inside a given membrane by enhanced mobile membranes of degree at most n {\displaystyle n} using rules α ⊆ { e x o , e n d o , f e n d o , f e x o } {\displaystyle \alpha \subseteq \{exo,endo,fendo,fexo\}} , is denoted by E M n ( α ) {\displaystyle EM_{n}(\alpha )} . Theorem. E M 3 ( e n d o , e x o ) = E M 3 ( f e n d o , f e x o ) {\displaystyle EM_{3}(endo,exo)=EM_{3}(fendo,fexo)} . Theorem. E M 12 ( e n d o , e x o , f e n d o , f e x o ) = R E {\displaystyle EM_{12}(endo,exo,fendo,fexo)=RE} . 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. E M 9 ( e n d o , e x o , f e n d o , f e x o ) = R E {\displaystyle EM_{9}(endo,exo,fendo,fexo)=RE} . The proof is similar to that presented in [4].
Mutual Mobile Membranes Following the approach presented in [3], "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 a {\displaystyle a} and a ¯ {\displaystyle {\overline {a}}} 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 R {\displaystyle R} defined as follows:
[ u ‖ v ‖ M ] h ‖ [ u ¯ ‖ v ′ ‖ N ] m → [ [ w ‖ M ] h ‖ w ′ ‖ N ] m {\displaystyle [u\;\|\;v\;\|\;M]_{h}\;\|\;[{\overline {u}}\;\|\;v'\;\|\;N]_{m}\rightarrow [\;[w\;\|\;M]_{h}\;\|\;w'\;\|\;N]_{m}} for h , m ∈ N , u , u ¯ ∈ V + , v , v ′ , w , w ′ ∈ V ∗ {\displaystyle h,m\in {\mathcal {N}},u,{\overline {u}}\in V^{+},v,v',w,w'\!\!\in V^{*}} ; (mutual endocytosis)
[ u ¯ ‖ v ′ ‖ N ‖ [ u ‖ v ‖ M ] h ] m → [ w ‖ M ] h ‖ [ w ′ ‖ N ] m {\displaystyle [{\overline {u}}\;\|\;v'\;\|\;N\;\|\;[u\;\|\;v\;\|\;M]_{h}]_{m}\rightarrow [w\;\|\;M]_{h}\;\|\;[w'\;\|\;N]_{m}} for h , m ∈ N , u , u ¯ ∈ V + , v , v ′ , w , w ′ ∈ V ∗ {\displaystyle h,m\in {\mathcal {N}},u,{\overline {u}}\in V^{+},v,v',w,w'\!\!\in V^{*}} ; (mutual exocytosis) where M {\displaystyle M} is a multiset and N {\displaystyle N} 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 [6]. 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 n {\displaystyle n} using mutual endocytosis rules (mendo) and mutual exocytosis rules (mexo) is denoted by M M n ( m e n d o , m e x o ) {\displaystyle MM_{n}(mendo,mexo)} . Therefore, the result can be formulated as following. Theorem. M M 3 ( m e n d o , m e x o ) = R E {\displaystyle MM_{3}(mendo,mexo)=RE} . 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 [20].
Mutual Membranes with Objects on Surface Membrane systems [24] and brane calculus [10] 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 [12] 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 [2] 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 R {\displaystyle R} defined as follows:
[ M ] v ‖ a ‖ u → [ [ ] u ‖ x ‖ M ] v ‖ y {\displaystyle [M]_{v\;\|\;a\;\|\;u}\rightarrow [[~]_{u\;\|\;x}\;\|\;M]_{v\;\|\;y}} , for a ∈ V , u , v , x , y ∈ V ∗ , u x , v y ∈ V + {\displaystyle a\in V,u,v,x,y\in V^{*},ux,vy\in V^{+}} (pino)
[ [ M ] a ‖ u ‖ N ] a ¯ ‖ v → M ‖ [ N ] u ‖ v ‖ x {\displaystyle [[M]_{a\;\|\;u}\;\|\;N]_{{\overline {a}}\;\|\;v}\rightarrow M\;\|\;[N]_{u\;\|\;v\;\|\;x}} , for a , a ¯ ∈ V , u , v , x ∈ V ∗ , u v x ∈ V + {\displaystyle ,{\overline {a}}\in V,u,v,x\in V^{*},uvx\in V^{+}} (exo)
[ M 1 ] a ‖ u ‖ [ N ] a ¯ ‖ b ‖ v → [ [ [ M 1 ] u ‖ x ] b ‖ N ] v ‖ y {\displaystyle [M_{1}]_{a\;\|\;u}\;\|\;[N]_{{\overline {a}}\;\|\;b\;\|\;v}\rightarrow [[[M_{1}]_{u\;\|\;x}]_{b}\;\|\;N]_{v\;\|\;y}} , for a , a ¯ , b ∈ V , u , v , x , y ∈ V ∗ , u x , v y ∈ V + {\displaystyle a,{\overline {a}},b\!\in \!V,u,v,x,y\in V^{*},ux,vy\in V^{+}} (phago) \noindent where M