test FOO test
Computability in Europe 2006
Logical Approaches to Computational Barriers
|THIS TALK IS CANCELLED!!!|
We continue the study of P systems with mobile membranes introduced
recently. This is a variant of P systems with active
membranes, but having none of the features like polarizations,
label change and division of non-elementary membranes.
This variant was shown to be computationally universal
using only the simple operations of endocytosis and exocytosis;
moreover, if elementary membrane division
is allowed, it is capable of solving NP-complete problems.
It was proved (refer CiE'05 proceedings) that 4 membranes are
for universality while using only endo/exo operations.
In this paper, we study the computational power of these systems more
systematically: we examine not only the power due to the number of membranes,
but also with respect to the kind of rules used. We show that 3
membranes are sufficient for computational universality, whereas two membranes
are not, if lambda-free rules are used.
websites: Arnold Beckmann