# Membrane Computing (P Systems)

**Origin.** Păun (2000). Cell-inspired computation. Nested membranes. Object transformation. Foundation for natural computing.

**Models.** Hierarchical membrane structure. Multisets of objects. Rules transform and transport. Parallelism within membranes. Dissolution and creation.

**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.

*Computation:*
Sequence of configurations.
Halts when no rules apply.
Result: objects in specified region.

*Variants:*
Symport/antiport: communication
Active membranes: division
Spiking neural P systems
Tissue P systems

**Symbols.**

| Symbol | Unicode | Name | Meaning |
|--------|---------|------|---------|
| [ ]ᵢ | — | Membrane | Region i |
| u → v | — | Rule | Transformation |
| δ | U+03B4 | Dissolve | Remove membrane |
| out, in | — | Direction | Transport |

**Metatheory.** Turing complete. Polynomial solutions to NP-complete. Complexity theory connections. Decidability varies.

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

**Limitations.** Abstract model. Implementation challenges. Resource assumptions. Theoretical focus mainly.

© 2026 Lingenic LLC