Membrane computing (or MC) is an area within
computer science
Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied science, practical discipli ...
that seeks to discover new
computational model
A computational model uses computer programs to simulate and study complex systems using an algorithmic or mechanistic approach and is widely used in a diverse range of fields spanning from physics, chemistry and biology to economics, psychology, ...
s from the study of biological
cells, particularly of the
cellular membrane
The cell membrane (also known as the plasma membrane (PM) or cytoplasmic membrane, and historically referred to as the plasmalemma) is a biological membrane that separates and protects the interior of all cells from the outside environment (th ...
s. It is a sub-task of creating a
cellular model.
Membrane computing deals with distributed and parallel computing models, processing multisets of symbol objects in a localized manner. Thus, evolution rules allow for evolving objects to be encapsulated into compartments defined by membranes. The communications between compartments and with the environment play an essential role in the processes. The various types of membrane systems are known as
P systems after
Gheorghe Păun Gheorghe Păun (; born December 6, 1950, in Cicănești, Argeș County) is a computer scientist from Romania, prominent for work on membrane computing and the P system.
Păun studied mathematics at the University of Bucharest, obtaining an MSc. in ...
who first conceived the model in 1998.
An essential ingredient of a
P system is its membrane structure, which can be a hierarchical arrangement of membranes, as in a cell, or a net of membranes (placed in the nodes of a graph), as in a tissue or a neural net.
P systems are often depicted graphically with drawings.
The intuition behind the notion of a membrane is a three-dimensional vesicle from biology. However the concept itself is more general, and a membrane is seen as a separator of two regions. The membrane provides for selective communication between the two regions. As per Gheorghe Păun, the separation is of the
Euclidean space
Euclidean space is the fundamental space of geometry, intended to represent physical space. Originally, that is, in Euclid's Elements, Euclid's ''Elements'', it was the three-dimensional space of Euclidean geometry, but in modern mathematics ther ...
into a finite “inside” and an infinite “outside”. The selective communication is where the computing comes in.
Graphical representations may have numerous elements, according to the variation of the model that is being studied. For example, a rule may produce the special symbol δ, in which case the membrane that contains it is dissolved and all its contents move up in the region hierarchy.
The variety of suggestions from biology and the range of possibilities to define the architecture and the functioning of a membrane-based multiset processing device are practically endless. Indeed, the membrane computing literature contains a very large number of models. Thus, MC is not merely a theory related to a specific model, it is a framework for devising compartmentalized models.
Chemicals are modeled by symbols, or alternatively by strings of symbols. The region, which is defined by a membrane, can contain other symbols or strings (collectively referred to as objects) or other membranes, so that a
P system has exactly one outer membrane, called the skin membrane, and a hierarchical relationship governing all its membranes under the skin membrane.
If objects are symbols, then their multiplicity within a region matters; however multi-sets are also used in some string models. Regions have associated rules that define how objects are produced, consumed, passed to other regions and otherwise interact with one another. The nondeterministic maximally parallel application of rules throughout the system is a transition between system states, and a sequence of transitions is called a computation. Particular goals can be defined to signify a halting state, at which point the result of the computation would be the objects contained in a particular region. Alternatively the result may be made up of objects sent out of the skin membrane to the environment.
Many variant models have been studied, and interest has focused on proving computational universality for systems with a small number of membranes, for the purpose of solving NP-complete problems such as
Boolean satisfiability (SAT) problems and the
traveling salesman problem (TSP). The
P systems may trade space and time complexities and less often use models to explain natural processes in living cells. The studies devise models that may at least theoretically be implemented on hardware. To date, the
P systems are nearly all theoretical models that have never been reduced to practice, although a practical system is given in.
See also
*
Modeling biological systems
*
Unconventional computing
Unconventional computing is computing by any of a wide range of new or unusual methods. It is also known as alternative computing.
The term ''unconventional computation'' was coined by Cristian S. Calude and John Casti and used at the First In ...
References
{{reflist
Models of computation
Classes of computers