Symbol/Membrane Complexity of P Systems with Symport/Antiport Rules

We consider P systems with symport/antiport rules and small numbers of symbols and membranes and present several results for P systems with symport/antiport rules simulating register machines with the number of registers depending on the number

s

of symbols and the number

m

of membranes. For instance, any recursively enumerable set of natural numbers can be generated (accepted) by systems with

s

≥ 2 symbols and

m

≥ 1 membranes such that

m

+

s

≥ 6. In particular, the result of the original paper [17] proving universality for three symbols and four membranes is improved (e.g., three symbols and three membranes are sufficient). The general results that P systems with symport/antiport rules with

s

symbols and

m

membranes are able to simulate register machines with max{

m

(

s

-2),(

m

-1)(

s

-1)} registers also allows us to give upper bounds for the numbers

s

and

m

needed to generate/accept any recursively enumerable set of

k

-dimensional vectors of non-negative integers or to compute any partial recursive function

f

: ℕ

α

→ℕ

β

. Finally, we also study the computational power of P systems with symport/antiport rules and only one symbol: with one membrane, we can exactly generate the family of finite sets of non-negative integers; with one symbol and two membranes, we can generate at least all semilinear sets. The most interesting open question is whether P systems with symport/antiport rules and only one symbol can gain computational completeness (even with an arbitrary number of membranes) as it was shown for tissue P systems in [1].