Editing P system

{{Short description|Computational model}}
: ''For the computer p-System, see [[UCSD p-System]].''

A '''P system''' is a computational [[Model (abstract)|model]] in the field of [[computer science]] that performs [[calculation]]s using a biologically inspired process. They are based upon the structure of biological [[cell (biology)|cells]], abstracting from the way in which [[chemical substance|chemicals]] interact and cross [[cell membranes]]. The concept was first introduced in a 1998 report<ref>{{cite book|last=Păun |first=Gheorghe|author-link=Gheorghe Paun|title=Computing with Membranes|url=https://books.google.com/books?id=lyzoAAAACAAJ|accessdate=16 December 2012|series=TUCS Report 208|year=1998|publisher=Turku Centre for Computer Science|isbn=978-952-12-0303-9}}</ref> by the computer scientist [[Gheorghe Paun|Gheorghe Păun]], whose last name is the origin of the letter [[P]] in 'P Systems'. Variations on the P system model led to the formation of a branch of research known as '[[membrane computing]].'

Although inspired by biology, the primary research interest in P systems is concerned with their use as a computational model, rather than for [[Mathematical biology|biological modeling]],<ref name="paun2002">{{cite journal |last=Păun |first=Gheorghe |author-link=Gheorghe Paun |author2=Grzegorz Rozenberg |year=2002 |title=A guide to membrane computing |journal=Theoretical Computer Science |volume=287 |issue=1 |pages=73–100 |doi=10.1016/S0304-3975(02)00136-6 |issn=0304-3975 |citeseerx=10.1.1.76.8425 }}</ref> although this is also being investigated.<ref>{{cite journal |last=Ardelean |first=Ioan |author2=Matteo Cavaliere |date=June 2003|title=Modelling biological processes by using a probabilistic p system software |journal=Natural Computing |volume=2|issue=2 |pages=173–197 |doi=10.1023/A:1024943605864 |issn=1567-7818}}</ref><ref name="paun2006">{{cite book|last=Păun|first=Gheorghe|title=Applications of Membrane Computing|year=2006|publisher=Springer Berlin Heidelberg|isbn=978-3-540-29937-0|pages=1–42|chapter=Introduction to Membrane Computing}}</ref><ref>{{cite journal |last=Nash |first=Anthony |author2=Sara Kalvala |date=2019|title=A P system model of swarming and aggregation in a Myxobacterial colony |journal=Journal of Membrane Computing |volume=1 |issue=2 |pages=103–11 |doi=10.1007/s41965-019-00015-0|doi-access=free }}</ref>

==Informal description==
A P system is defined as a series of membranes containing chemicals (in [[Wikt:finite|finite]] quantities), [[catalysts]] and rules which determine possible ways in which chemicals may react with one another to form products. Rules may also cause chemicals to pass through membranes or even cause membranes to [[Dissolution (chemistry)|dissolve]].

Just as in a biological cell, where a chemical reaction may only take place upon the chance event that the required chemical [[molecule]]s collide and interact (possibly also with a catalyst), the rules in a P system are applied at random. This causes the computation to proceed in a [[Nondeterministic algorithm|non-deterministic]] manner, often resulting in multiple solutions being encountered if the computation is repeated.

A P system continues until it reaches a state where no further reactions are possible. At this point the result of the computation is all those chemicals that have been passed outside of the outermost membrane, or otherwise those passed into a designated 'result' membrane.<ref name="paun2006" />

==Components of a P system==
Although many varieties of P system exist, most share the same basic components. Each element has a specific role to play, and each has a founding in the biological cell architecture upon which P systems are based.

===The environment===
The environment is the surroundings of the P system. In the initial state of a P system it contains only the container-membrane, and while the environment can never hold rules, it may have objects passed into it during the computation. The objects found within the environment at the end of the computation constitute all or part of its “result.”

===Membranes===
Membranes are the main “structures” within a P system. A membrane is a discrete unit which can contain a set of objects (symbols/catalysts), a set of rules, and a set of other membranes contained within. The outermost membrane, held within the environment, is often referred to as the 'container membrane' or 'skin membrane'. As implied to by their namesake, membranes are [[Semipermeable membrane|permeable]] and symbols resulting from a rule may cross them. A membrane (but not the container membrane) may also “dissolve”, in which case its content, except for rules (which are lost), migrate into the membrane in which it was contained.<ref name=paun2002 />

Some P system variants allow for a membrane to divide, possess a [[Electric charge|charge]] or have varying [[Semipermeable membrane|permeability]] by changing membrane thickness.<ref name=paun2002 />

===Symbols===
Symbols represent chemicals that may react with other chemicals to form some product. In a P system, each type of symbol is typically represented by a different letter. The symbol content of a membrane is therefore represented by a string of letters. Because the [[Multiplicity (mathematics)|multiplicity]] of symbols in a region matters, [[multisets]] are commonly used to represent the symbol content of a region.

Special case symbols exist, for example, a lower case [[Delta (letter)|delta]] (δ) is often used to initiate the dissolving of a membrane, and this will only ever be found in the output of a rule: upon being encountered it invokes a reaction, and is used in the process.

====Catalysts====
Catalysts are similar to their namesakes in chemistry. They are represented and used in the same way as symbols, but are never consumed during a “[[chemical reaction|reaction]],” they are simply a requirement for it to occur.

===Rules===
Rules represent a possible chemical reaction within a membrane, causing it to evolve to a new state. A rule has a required set of input objects (symbols or catalysts) that must be present in order for it to be applied. If the required objects are present, it consumes them and produces a set of output objects. A rule may also be specified to have a priority over other rules, in which case less dominant rules will only be applied when it is not possible to apply a more dominant rule (i.e. the required inputs are not present).

There are three (in the basic P system model) distinct ways in which a rule may handle its output objects. Usually, the output objects are passed into the current membrane (the same membrane in which the rule and the inputs reside), known as a ''here'' rule. However, there are two modifiers that can be specified upon output objects when rules are defined, ''in'' and ''out''. The ''in'' modifier causes the object to be passed to one of the current membrane's children (travelling inwards relative to the structure of the P system), chosen at [[Randomness|random]] during the computation. The ''out'' modifier causes the object to be passed out of the current membrane and into either its parent membrane or to a sibling membrane, specified during specification of the P system.

==Computation process==
A computation works from an initial starting state towards an end state through a number of [[wiktionary:Discrete|discrete]] steps. Each step involves iterating through all membranes in the P system and the application of rules, which occurs in both a [[maximally parallel]] and [[Nondeterministic algorithm|non-deterministic]] manner.<ref name="paun2006" />

Working through step-by-step, a computation halts when no further evolution can take place (i.e. when no rules are able to be applied). At this point whatever objects have been passed to the environment, or into a designated 'result' membrane, are counted as the result of the computation.<ref name=paun2006 />

===Rule application===
At each step of a computation an object may only be used once, as they are consumed by rules when applied. The method of applying a rule within a membrane is as follows: 
#Assign symbols from a membrane's content to the rule's inputs
#If all inputs are satisfied, remove all assigned symbols from membrane 
#Create output symbols and hold until all rule assignment, for all membranes, has taken place. 
#Add output symbols to targeted membranes. 
#Dissolve membranes as necessary 
Outputs are not passed immediately into membranes because this would contravene the maximally parallel nature of rule application, instead they are distributed after all possible rules have been applied.

====Non-deterministic application====
The order of rule application is chosen at random. Rule application order can have a significant effect on which rules may be applied at any given time, and the outcome of a step of execution.

Consider a membrane containing only a single "a" symbol, and the two rules a → ab and a → aδ. As both rules rely on an “a” symbol being present, of which there is only one, the first step of computation will allow either the first or second rule to be applied, but not both. The two possible results of this step are very different:
#The membrane carries over to the next step of the computation with both an "a" symbol and a "b" symbol present, and again one of the two rules is randomly assigned to the "a" symbol.
#The membrane dissolves and a single "a" symbol is passed out to the containing membrane.

====Maximally parallel application====
This is a property of rule application whereby all possible rule assignments must take place during every step of the computation. In essence this means that the rule a → aa has the effect of doubling the number of "a" symbols in its containing membrane each step, because the rule is applied to every occurrence of an "a" symbol present.

==As a computational model==
Most P systems variants are [[computationally universal]].<ref name=paun2006 /> This extends even to include variants that do not use rule priorities, usually a fundamental aspect of P systems.<ref>{{cite journal |last1=Freund |first1=Rudolf |last2=Kari |first2=Lila |last3=Oswald |first3=Marion |last4=Sosík |first4=Petr |year=2005 |title=Computationally universal P systems without priorities: two catalysts are sufficient |journal=Theoretical Computer Science |volume=330 |issue=2 |pages=251–266 |doi=10.1016/j.tcs.2004.06.029 |issn=0304-3975|doi-access= }}</ref>

As a model for computation, P systems offer the attractive possibility of solving [[NP-complete]] problems in less-than [[exponential time]].<ref name=paun2006 /> Some P system variants are known to be capable of solving the [[Boolean satisfiability problem|SAT]] (boolean satisfiability) problem in [[linear time]]<ref>{{cite journal |last=Păun |first=Gheorghe |author-link=Gheorghe Paun |year=2001 |title=P systems with active membranes: attacking NP-complete problems |journal=Automata, Languages and Combinatorics |volume=6 |issue=1 |pages=75–90 |url=http://www.cs.auckland.ac.nz/CDMTCS/researchreports/102paun.pdf |accessdate=2008-02-03 }}</ref> and, owing to all NP-complete problems being [[Logical equivalence|equivalent]], this capability then applies to all such problems. As there is no current method of directly implementing a P system in its own right, their functionality is instead emulated<ref>{{cite conference |first=Claudio |last=Zandron |author2=Claudio Ferretti |author3=Giancarlo Mauri |title=Solving NP-Complete Problems Using P Systems with Active Membranes |book-title=Unconventional Models of Computation |pages=289–301 |date=2000  |isbn=1-85233-415-0}}</ref> and therefore solving NP-complete problems in linear time remains theoretical. However, it has also been proven that any deterministic P system may be [[simulated]] on a [[Turing Machine]] in [[polynomial time]].<ref name="paun2002" />

==Example computation==
[[Image:P-system-example.svg|frame|right|The graphical representation of a P system which outputs square numbers]]
The image shown depicts the initial state of a P system with three membranes. Because of their hierarchical nature, P systems are often depicted graphically with drawings that resemble [[Venn diagram]]s or [[David Harel]]'s [[Higraph]] (see [[Statechart]]).

The outermost membrane, 1, is the container membrane for this P system and contains a single ''out'' rule. Membrane 2 contains four ''here'' rules, with two in a priority relationship: cc → c will always be applied in preference to c → δ. The delta symbol represents the special “dissolve” symbol. The innermost membrane, 3, contains a set of symbols (“ac”) and three rules, of type ''here''. In this initial state no rules outside of membrane 3 are applicable: there are no 
symbols outside of that membrane. However, during evolution of the system, as objects are passed between membranes, the rules in other membranes will become active.

===Computation===
Because of the non-deterministic nature of P systems, there are many different paths of computation a single P system is capable of, leading to different results. The following is one possible path of computation for the P system depicted.

====Step 1====
From the initial configuration only membrane 3 has any object content: "ac"
*"c" is assigned to c → cc 
*"a" is assigned to a → ab

====Step 2====
Membrane 3 now contains: "abcc" 
*"a" is assigned to a → bδ 
*"c" is assigned to c → cc 
*"c" is assigned to c → cc
Notice the maximally parallel behaviour of rule application leading to the same rule being applied twice during one step.

Notice also that the application of the second rule (a → bδ) as opposed to the first (a → ab) is non-deterministic and can be presumed random. The system could just as well have continued applying the first rule (and at the same time doubling the c particles) indefinitely.

Membrane 3 now dissolves, as the dissolve symbol (δ) has been encountered and all object content from this membrane passes into membrane 2.

====Step 3====
Membrane 2 now contains: "{{not a typo|bbcccc}}" 
*"b" is assigned to b → d 
*"b" is assigned to b → d 
*"cc" is assigned to cc → c 
*"cc" is assigned to cc → c

====Step 4====
Membrane 2 now contains: "{{not a typo|ddcc}}" 
*"d" is assigned to d → de 
*"d" is assigned to d → de 
*"cc" is assigned to cc → c

====Step 5====
Membrane 2 now contains: "{{not a typo|dedec}}" 
*"d" is assigned to d → de 
*"d" is assigned to d → de 
*"c" is assigned to c → δ

Notice that the priority over c → δ has been lifted now the required inputs for cc→ c no longer exist. Membrane 2 now dissolves, and all object content passes 
to membrane 1.

====Step 6====
Membrane 1 now contains: "{{not a typo|deedee}}" 
*"e” is assigned to e → e<sub>out</sub> 
*"e” is assigned to e → e<sub>out</sub> 
*"e” is assigned to e → e<sub>out</sub> 
*"e” is assigned to e → e<sub>out</sub>

====Computation halts====
Membrane 1 now contains: "dd" and, due to the out rule e → e<sub>out</sub>, the environment contains: "eeee." At this point the computation halts as no further 
assignments of objects to rules is possible. The result of the computation is four "e" symbols.

The only non-deterministic choices occurred during steps 1 and 2, when choosing where to assign the solitary "a" symbol. Consider the case where "a" is assigned to a → bδ during step 1: upon membrane 3 dissolving only a single "b" and two "c" objects would exist, leading to the creation of only a single "e" object to eventually be passed out as the computation's result.

==See also==
*[[Cell (biology)]]
*[[Biologically inspired computing]]
*[[Formal language]]
*[[Hypergraph]]
*[[Modelling of General Systems|MGS]]
*[[Systems biology]]

==References==
<references/>

==External links==
*[http://ppage.psystems.eu/ P Systems] &ndash; website for P systems research.

[[Category:Models of computation]]