P systems with communication based on concentration (Q2770580)

The P systems are a class of distributed parallel computing devices of biochemical nature \textit{Gh. Păun} [Bull. Eur. Assoc. Theor. Comput. Sci. EATCS, 67, 139-152 (1999; Zbl 0936.68040)], and, apparently, quite a few variants of the original mechanism \textit{J. Dassow} [Int. J. Comput. Math. 7, 187-206 (1979; Zbl 0453.68042)] have been presented and investigated. It is not surprising that most of them, via a definition of the normal concept of computation, are equivalent to the well-known Turing machines in terms of computation power.NEWLINENEWLINENEWLINEA general configuration of a traditional P system is that a collection of objects are distributed among a collection of regions. As a part of the computing mechanism of standard P systems, after a transition rule, in the form of an evolution rule, is applied, an object can either stay here in the original region, or be sent out of the current region, or into a region labeled with \(j\). In observing that some notions associated with this ``standard'' mechanism, particularly, this last option of sending an object to a region associated with a label \(j\), are ``rather unrealistic from a biochemical point of view'', the authors suggested another variant in this paper: when applying an evolution rule, objects will be redistributed among regions based soley on an approximately even concentration of the objects in the regions, and have shown that a general P system so constructed can generate all the recursively enumerable sets, as well. The proofs for the aforementioned technical results related to computational completeness follow a traditional constructive approach \textit{M. Sipser} [Introduction to the Theory of Computation, PWS-KENT Publishing Company, Boston (1997)], with matrix grammars \textit{J. Dassow} and \textit{Gh. Păun} [Regulated Rewriting in Formal Language Theory, Springer-Verlag, Berlin (1989)] as the bridge.NEWLINENEWLINENEWLINERegarding the crucial converting process the traditional system to this concentration based system is only characterized as ``very simple way''. No equivalency result is given between the original system and the new concentration based system. This is somewhat unusual in the area of formal languages. This fact is rather unfortunate since little motivation or explanation about this very conversion is given, either. I personally feel that a few inspiring examples will be useful in this and some other places.