Turing Completeness by Using Three Mobile Membranes (regular paper)

Bogdan AMAN and Gabriel CIOBANU

Abstract. The mutual mobile membrane systems represent a variant of mobile membrane systems in which the endocytosis and exocytosis are working whenever the involved membranes "agree" on the movement; this agreement is described by using dual objects a and a¯ in the involved membranes. We study the computational power of this variant of mobile membrane systems, proving that only three membranes are enough to get the computational power of a Turing machine.