Membrane Computing (P Systems)

Origin. Gheorghe Păun, "Computing with membranes", Turku Centre for Computer Science report 208 (1998), published in the Journal of Computer and System Sciences 61 (2000). The model abstracts the compartmental architecture of the living cell: chemical species become objects, compartments become membranes, reactions become multiset rewriting rules. It established membrane computing as a branch of natural computing beside DNA computing and evolutionary computation, and the variants are catalogued in the Handbook of Membrane Computing (Păun, Rozenberg, Salomaa, 2010).

Models. A hierarchy of membranes, nested as a tree with a skin membrane at the root, each enclosing a region that holds a multiset of objects and a set of rules. Objects have no identity beyond their multiplicity and no position within a region, so a region is a chemical soup. Computation proceeds in synchronous steps under maximal parallelism: at each step a maximal applicable multiset of rules is selected and applied everywhere at once. Rules transform objects, transport them across membranes, dissolve membranes, and in some variants divide them.

Formalism.

P system: Π = (V, μ, w₁, ..., wₘ, R₁, ..., Rₘ) V: alphabet (objects) μ: membrane structure (tree) wᵢ: initial multiset in region i Rᵢ: rules in region i

Membrane structure: Nested: [ [ ]₂ [ ]₃ ]₁ Regions: inside membranes. Skin: outermost.

Evolution rules: u → v: transform u to v (in same region) u → v (here) (out) (in_j): target regions δ: membrane dissolves

Example rule: ab → c (out) If a and b present, produce c, send out.

Parallelism: All applicable rules apply simultaneously. Maximal parallelism. Non-determinism if multiple choices.

Rule strength: Non-cooperative: left side a single object, a → v. Catalytic: ca → cv, with c a catalyst neither consumed nor produced. Cooperative: arbitrary multiset on the left. The three are not equivalent in power.

Computation: Sequence of configurations. Halts when no rules apply. Result: objects in a specified region, or objects sent out through the skin. Confluent system: every halting computation gives the same result, so the system computes a value rather than a set.

Variants: Symport/antiport: no objects are created or destroyed, only moved — uv enters, or u exits while v enters. Active membranes: rules divide a membrane, duplicating its contents. Tissue P systems: membranes on a graph rather than a tree. Spiking neural P systems: information carried by the timing of identical spikes.

Symbols.

Symbol	Unicode	Name	Meaning
Π	U+03A0	Pi	A P system, given as a tuple
[ ]ᵢ	—	Membrane	The membrane labelled i and the region it encloses
μ	U+03BC	Mu	Membrane structure, a tree of nested membranes
→	U+2192	Rule	u → v transforms the multiset u into v
δ	U+03B4	Delta	Dissolution: the membrane vanishes, contents joining the parent
out	—	Out	Send the produced objects to the parent region
in	—	In	Send the produced objects into a child region
wᵢ	—	Initial multiset	The objects present in region i at the start

Metatheory. Power depends sharply on rule strength. With non-cooperative rules the sets of numbers generated are semilinear, so such systems are strictly weaker than Turing machines; adding catalysts restores universality, and a small fixed number of catalysts already suffices, so the generated family is exactly the recursively enumerable sets of natural numbers. Symport/antiport systems, which never create or destroy an object, are likewise universal with small rules. The complexity results turn on membrane division. Active-membrane systems solve SAT in polynomial time, but they do so by creating exponentially many membranes in polynomially many steps, and the Milano theorem (Zandron, Ferretti and Mauri, 2000) states that without such exponential workspace no NP-complete problem is solved in polynomial time unless P = NP. With division of non-elementary membranes the class of problems solvable in polynomial time is exactly PSPACE.

Applies to. Natural computing. Biology modeling. Distributed systems. Parallel computation. Ecosystems.

Limitations. The polynomial-time solutions to hard problems come entirely from exponential space: the Milano theorem shows the speedup vanishes without membrane division, so the exponential workspace is doing all the work, and no physical substrate supplies unbounded division. Maximal parallelism is a global synchronization — every step requires choosing a maximal applicable multiset across the whole system, which is itself a nontrivial computation — so there is no asynchronous or distributed reading of a step. Since the systems are universal, halting, confluence and equivalence are all undecidable, and a result is well defined only for confluent systems, which cannot be recognized. Each of the many variants carries its own universality and complexity proofs; nothing transfers automatically between them.