Computability in Europe 2006
Logical Approaches to Computational Barriers
|THIS TALK HAS BEEN 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 sufficient 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||2006-06-09|