On the Computational Power of Brane Calculi

Brane calculi are a family of biologically inspired process calculi proposed in [3] for modeling the interactions of dynamically nested membranes. In [3] a basic calculus for membranes interactions – called Phago/Exo/Pino – is proposed, whose primitives are inspired by endocytosis and exocytosis. An alternative basic calculus – called Mate/Bud/Drip and inspired by membrane fusion and fission – is also outlined and shown to be encodable in Phago/Exo/Pino in [3]. In this paper we investigate and compare the expressiveness of such two calculi w.r.t. their ability to act as computational devices. We show that (a fragment of) the Phago/Exo/Pino calculus is Turing powerful, by providing an encoding of Random Access Machines. On the other hand, we show the impossibility to define a “faithful” encoding of Random Access Machines in the Mate/Bud/Drip calculus, by providing a proof of the decidability of the existence of a divergent computation in Mate/Bud/Drip.