P жүйесі: Биологиялық шабыттанған есептеу моделі

Computational model
For the computer p System, see UCSD p System. A P system is a computational model in the field of computer science that performs calculations using a biologically inspired process. They are based upon the structure of biological cells, abstracting from the way in which chemicals interact and cross cell membranes. The concept was first introduced in a 1998 report by the computer scientist 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 biological modeling, although this is also being investigated.

A P system is defined as a series of membranes containing chemicals (in 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 dissolve. Just as in a biological cell, where a chemical reaction may only take place upon the chance event that the required chemical molecules 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 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. As a model for computation, P systems offer the attractive possibility of solving NP complete problems in less than exponential time. and, owing to all NP complete problems being 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 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.

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

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.

Membrane 1 now contains: "dd" and, due to the out rule e → eout, 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.