From cells to computers: computing with membranes (P systems)☆
Section snippets
The computing bio-cell
Assertions about the computing-like activities which take place in alive cells can be found in many places, the reactions by which chemical compounds, energy, and information are handled in the complex structure of a cell being often interpreted as computing processes (see e.g. Bray (1995) and references therein). The incentive to define P systems (initially, in Păun (1998), they were called supper-cell systems) was the question whether or not these statements are just metaphoras, or a formal
The cell membrane: structure and functions
The many (formal) notions which we will soon consider when defining our computing devices will not only be biology-like, but most of them will correspond in a direct way to notions from the biochemistry of the membranes of alive cells.
A cell has a complex structure, with several compartments delimited inside the main membrane by several inner membranes: the nucleus, the Golgi aparatus, several vesicles, etc. In principle, all these membranes are similar, they are separators and filters, so that
The computing math-cell
Let us now try to abstract from the structure and the functioning of an alive cell and informally describe the symbolic counterpart of the bio-cell. A partial formalization of the notions discussed below can be found in Section 5.
Everything takes place in a membrane structure, which is a hierarchical arrangement of membranes, all of them placed in a main membrane, called the skin membrane. This one delimits the system from its environment. The membranes should be understood as three-dimensional
Membrane computing and natural computing
The details from the biochemistry of (animal and vegetal, alike) membranes sketched in Section 2 only show that the ingredients we use in P systems, mainly in what concerns the way of communicating through membranes, are ‘realistic’, in the sense that they have a resemblance with actual biochemical facts. However, this means nothing in what concerns the possible implementations of the model.
Up to now, there was no attempt to carry out a computation, even for solving a toy problem, by using
A formal definition of a P system
In this section, we go closer to mathematics and introduce a formal counterpart of the computing cell as sketched in Section 3.
A membrane structure can be mathematically represented by a tree, in the natural way, or by a string of matching parentheses. The tree of the structure in Fig. 1 is given in the same figure, while the parenthetic representation of that structure is the following:
The tree representation makes possible considering various parameters,
Examples
Before recalling some results about the computing power of P systems of the types introduced in the previous section or involving further ingredients, we shall consider three examples for the basic variant considered above, one for each type of tasks a P system can solve. Example 1 (Generative task) Consider the P system of degree 4
Computational completeness
At the end of Section 3, we have mentioned that P systems as introduced above are equivalent with Turing machines. More precisely, we have the following theorem (the family of recursively enumerable sets of vectors of natural numbers is denoted3 by PsRE): Theorem 1 NP2(Pri,
P systems with string objects
In P systems with symbol objects, as discussed in the previous sections, we use a rather noneconomical representation of numbers, the base one. Having in mind that many of the objects present in cells are complex molecules, even strings, such as the DNA molecules, it is natural to consider also P systems with the objects represented by strings. Then, the evolution rules should be string processing operations.
An important distinction here is whether or not we take into account the multiplicities
P systems with worm objects
In P systems with symbol objects, we work with multisets and the result of a computation is a natural number or a vector of natural numbers; in the case of P systems with string objects, we work with sets of strings and the result of a computation is a string. We can combine the two ideas: we can work with multisets of strings and consider as the result of a computation the number of strings present in the halting configuration in a given membrane or sent out of the system during the
Solving NP in P by P
Let us now pass to a fundamental question: are P systems computationally useful? From a theoretical point of view, the answer is affirmative: in the framework of P systems we can naturally create an exponential working space and this can be used for solving hard problems in a feasible time. Exponentially many objects can be produced in all types of P systems – see the very first example from Section 6. However, such a work space is not sufficient: an important theorem from Zandron et al. (2000d)
Further results, research topics
There are many results in P systems area, other than referring to characterizations of the power of Turing machines and to solving hard problems in a feasible (parallel) time. The bibliography which follows is meant to help the reader in having an image about the current state of the domain. We only mention here some of the main problems approached and results given in some of these papers: bridge theorems, relating the internal and the external modes of reading the result of a computation (
Further Suggested Reading
Atanasiu, 2000, Calude and Păun, 2000, Dassow and Păun, 2000, Freund and Freund, 2000, Freund, 2000, Frisco, 2000, Krishna et al., 2000, Manca, 2000, Martin-Vide and Mitrana, 2000, Martin-Vide and Păun, 2000b, Păun, 1999, Păun et al., 2000c, Păun and Yokomori, 2000, Zandron et al., 2000a, Zandron et al., 2000b, Zandron et al., 2000e, Rama, 2000, Krishna, 2000, Krishna and Rama, 2000e, Păun, 2000c, Păun, 2000d
Acknowledgements
Work partially supported by a grant of NATO Science committee, Spain 2000–2001.
References (68)
Formal language theory and DNA: an analysis of the generative capacity of specific recombinant behaviors
Bullet. Mathemat. Biol.
(1987)Molecular computation of solutions to combinatorial problems
Science
(1994)Essential Cell Biology. An Introduction to the Molecular Biology of the Cell
(1998)- Atanasiu, A., 2000. Arithmetic with membranes. Pre-proc. Workshop on Multiset Processing, Curtea de Argeş, Romania, TR...
- Atanasiu, A., Martin-Vide, C., 2000a. Recursive calculus with membranes. Submitted for...
- Atanasiu, A., Martin-Vide, C., 2000b. P systems and context-free languages. Submitted for...
- Baranda, A.V., Castellanos, J., Molina, R., Arroyo, F., Mingo, L.F., 2000. Data structures for implementing transition...
Protein molecules as computational elements in living cells
Nature
(1995)- Calude, C., Păun, Gh., 2000. Computing with Cells and Atoms. Taylor and Francis, London (Chapter 3: Computing with...
- Castellanos, J., Păun, Gh., Rodriguez-Paton, A., 2000. P systems with worm objects. IEEE Seventh Intern. Conf. on...
Regulated Rewriting in Formal Language Theory
On the power of membrane computing
J. Univ. Comput. Sci.
Generalized P systems with splicing and cutting/recombination
Grammars
A variant of P systems with active membranes: solving NP-complete problems
Rom. J. Info. Sci. Technol.
On the power of P systems with sequential and parallel rewriting
Int. J. Comput. Math.
Using DNA to solve NP-complete problems
Science
The Touchstone of Life. Molecular Information, Cell Communication, and the Foundations of Life
Membrane structure and function
Cited by (52)
Emergence of random selections in evolution of biological populations
2021, Theoretical Computer ScienceVerification of Spatial and Temporal Modalities in Biochemical Systems
2015, Electronic Notes in Theoretical Computer ScienceConverting differential-equation models of biological systems to membrane computing
2013, BioSystemsCitation Excerpt :structural (Muniyandi and Zin, 2010b) and distributed (Ciobanu et al., 2006) arrangements are captured, in which objects and processes evolve according to the rules local to their compartment; furthermore the compartmentalized biological processes lead to emergent behaviour (Teuscher, 2007) in the overall system; the stochastic nature of biological systems are expressed (Besozzi et al., 2008a; Spicher et al., 2008) by the non-deterministic (Baranda et al., 2001) and maximal parallel evolution (Păun, 2001) strategy of membrane systems. In an ODE model, a stochastic ODE (Gard, 1987) would be required (although the stochastic influence is incorporated by introducing parameters as stochastic processes or inserting stochastic processes to the driving system equations (Carletti et al., 2004), once again modularity of stochastic behaviour is not achieved).
Developmental modelling with SDS
2010, Computers and Graphics (Pergamon)Citation Excerpt :Using an evolutionary algorithm, he was able to evolve a 2D cell pattern that resembled the French flag from a single zygote cell. Some developmental models incorporate hierarchies as an explicit feature, for example, P-systems [44], Vaario's Multi-Level Interaction Simulation (MLIS) language [16] and McCormack's Cellular Developmental Model (CDM) [45]. To date, the predominant applications for P-systems and MLIS have not been in the creative domain (P-systems have been used primarily for studying computation and MLIS was designed to evolve artificial neural networks).
Timed P Automata
2009, Electronic Notes in Theoretical Computer Science
- ☆
A preliminary version of this paper has been presented at the workshop on grammar systems, Bad Ischl, Austria, July 2000.