Autori: Gheorghe Paun

Editorial: Journal of Computer and System Sciences, 61 (1), p.108-143, 2000.

Rezumat:

A computing model is abstracted from the structure and the functioning of the living cell. In short, such a model (called P system) consists of a cell-like hieerarchy of membranes, which define compartments where multisets of objects (described by symbols of a given alphabet) are placed. The objects evolve by means of multiset rewriting rules (similar to bio-chemical reactions). One proves that P systems using the rules in the maximally parallel manner are equivalent in power with Turing machines. Also the case when the objects are described by strings is considered, with rewriting and splicing rules used for evolving the objects; Turing universality is obtained also in these cases.

Cuvinte cheie: calcul natural, sistem P, universalitate // natural computing, P system, universality

URL: http://ppage.psystems.eu