: ''For the computer p-System, see
UCSD p-System
UCSD Pascal is a Pascal programming language system that runs on the UCSD p-System, a portable, highly machine-independent operating system. UCSD Pascal was first released in 1977. It was developed at the University of California, San Diego (UCS ...
.''
A P system is a computational
model
A model is an informative representation of an object, person or system. The term originally denoted the Plan_(drawing), plans of a building in late 16th-century English, and derived via French and Italian ultimately from Latin ''modulus'', a mea ...
in the field of
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 performs
calculation
A calculation is a deliberate mathematical process that transforms one or more inputs into one or more outputs or ''results''. The term is used in a variety of senses, from the very definite arithmetical calculation of using an algorithm, to th ...
s using a biologically inspired process. They are based upon the structure of biological
cells, abstracting from the way in which
chemicals
A chemical substance is a form of matter having constant chemical composition and characteristic properties. Some references add that chemical substance cannot be separated into its constituent elements by physical separation methods, i.e., wit ...
interact and cross
cell membranes
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 ( ...
. The concept was first introduced in a 1998 report by the computer scientist
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 ...
, 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 Membrane computing (or MC) is an area within computer science that seeks to discover new computational models from the study of biological cells, particularly of the cellular membranes. It is a sub-task of creating a cellular model.
Membrane comp ...
.'
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.
Informal description
A P system is defined as a series of membranes containing chemicals (in
finite
Finite is the opposite of infinite. It may refer to:
* Finite number (disambiguation)
* Finite set, a set whose cardinality (number of elements) is some natural number
* Finite verb, a verb form that has a subject, usually being inflected or marked ...
quantities),
catalysts
Catalysis () is the process of increasing the rate of a chemical reaction by adding a substance known as a catalyst (). Catalysts are not consumed in the reaction and remain unchanged after it. If the reaction is rapid and the catalyst recyc ...
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
molecule
A molecule is a group of two or more atoms held together by attractive forces known as chemical bonds; depending on context, the term may or may not include ions which satisfy this criterion. In quantum physics, organic chemistry, and bioch ...
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
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.
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
permeable
Permeability, permeable, and semipermeable may refer to:
Chemistry
*Semipermeable membrane, a membrane which will allow certain molecules or ions to pass through it by diffusion
*Vascular permeability, the movement of fluids and molecules betwe ...
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.
Some P system variants allow for a membrane to divide, possess a
charge
Charge or charged may refer to:
Arts, entertainment, and media Films
* '' Charge, Zero Emissions/Maximum Speed'', a 2011 documentary
Music
* ''Charge'' (David Ford album)
* ''Charge'' (Machel Montano album)
* ''Charge!!'', an album by The Aqu ...
or have varying
permeability by changing membrane thickness.
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
Multiplicity may refer to: In science and the humanities
* Multiplicity (mathematics), the number of times an element is repeated in a multiset
* Multiplicity (philosophy), a philosophical concept
* Multiplicity (psychology), having or using multi ...
of symbols in a region matters,
multisets
In mathematics, a multiset (or bag, or mset) is a modification of the concept of a set that, unlike a set, allows for multiple instances for each of its elements. The number of instances given for each element is called the multiplicity of that ...
are commonly used to represent the symbol content of a region.
Special case symbols exist, for example, a lower case
delta
Delta commonly refers to:
* Delta (letter) (Δ or δ), a letter of the Greek alphabet
* River delta, at a river mouth
* D ( NATO phonetic alphabet: "Delta")
* Delta Air Lines, US
* Delta variant of SARS-CoV-2 that causes COVID-19
Delta may also ...
(δ) 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 “
reaction
Reaction may refer to a process or to a response to an action, event, or exposure:
Physics and chemistry
*Chemical reaction
*Nuclear reaction
*Reaction (physics), as defined by Newton's third law
*Chain reaction (disambiguation).
Biology and me ...
,” 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
random
In common usage, randomness is the apparent or actual lack of pattern or predictability in events. A random sequence of events, symbols or steps often has no :wikt:order, order and does not follow an intelligible pattern or combination. Ind ...
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
discrete
Discrete may refer to:
*Discrete particle or quantum in physics, for example in quantum theory
* Discrete device, an electronic component with just one circuit element, either passive or active, other than an integrated circuit
*Discrete group, a ...
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
non-deterministic manner.
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.
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.
This extends even to include variants that do not use rule priorities, usually a fundamental aspect of P systems.
As a model for computation, P systems offer the attractive possibility of solving
NP-complete
In computational complexity theory, a problem is NP-complete when:
# it is a problem for which the correctness of each solution can be verified quickly (namely, in polynomial time) and a brute-force search algorithm can find a solution by tryi ...
problems in less-than
exponential time
In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by ...
.
Some P system variants are known to be capable of solving the
SAT
The SAT ( ) is a standardized test widely used for college admissions in the United States. Since its debut in 1926, its name and scoring have changed several times; originally called the Scholastic Aptitude Test, it was later called the Schol ...
(boolean satisfiability) problem in
linear time
In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by ...
and, owing to all NP-complete problems being
equivalent
Equivalence or Equivalent may refer to:
Arts and entertainment
*Album-equivalent unit, a measurement unit in the music industry
* Equivalence class (music)
*'' Equivalent VIII'', or ''The Bricks'', a minimalist sculpture by Carl Andre
*''Equiva ...
, 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
A simulation is the imitation of the operation of a real-world process or system over time. Simulations require the use of models; the model represents the key characteristics or behaviors of the selected system or process, whereas the s ...
on a
Turing Machine
A Turing machine is a mathematical model of computation describing an abstract machine that manipulates symbols on a strip of tape according to a table of rules. Despite the model's simplicity, it is capable of implementing any computer algori ...
in
polynomial time
In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by ...
.
Example computation
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
A Venn diagram is a widely used diagram style that shows the logical relation between set (mathematics), sets, popularized by John Venn (1834–1923) in the 1880s. The diagrams are used to teach elementary set theory, and to illustrate simple ...
s or
David Harel
David Harel ( he, דוד הראל; born 12 April 1950) is a computer scientist, currently serving as President of the Israel Academy of Sciences and Humanities. He has been on the faculty of the Weizmann Institute of Science in Israel since 1980, ...
'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: ""
*"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: ""
*"d" is assigned to d → de
*"d" is assigned to d → de
*"cc" is assigned to cc → c
Step 5
Membrane 2 now contains: ""
*"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
out
*"e” is assigned to e → e
out
*"e” is assigned to e → e
out
*"e” is assigned to e → e
out
Computation halts
Membrane 1 now contains: "dd" and, due to the out rule e → e
out, 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)
The cell is the basic structural and functional unit of life forms. Every cell consists of a cytoplasm enclosed within a membrane, and contains many biomolecules such as proteins, DNA and RNA, as well as many small molecules of nutrients a ...
*
Biologically inspired computing
Bio-inspired computing, short for biologically inspired computing, is a field of study which seeks to solve computer science problems using models of biology. It relates to connectionism, social behavior, and emergence. Within computer science, ...
*
Formal language
In logic, mathematics, computer science, and linguistics, a formal language consists of words whose letters are taken from an alphabet and are well-formed according to a specific set of rules.
The alphabet of a formal language consists of symb ...
*
Hypergraph
In mathematics, a hypergraph is a generalization of a graph in which an edge can join any number of vertices. In contrast, in an ordinary graph, an edge connects exactly two vertices.
Formally, an undirected hypergraph H is a pair H = (X,E) wh ...
*
MGS
*
Systems biology
Systems biology is the computational modeling, computational and mathematical analysis and modeling of complex biological systems. It is a biology-based interdisciplinary field of study that focuses on complex interactions within biological syst ...
References
External links
P Systems– website for P systems research.
Models of computation