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.