On the power of enzymatic numerical P systems
- PDF / 425,725 Bytes
- 18 Pages / 439.37 x 666.142 pts Page_size
- 94 Downloads / 196 Views
On the power of enzymatic numerical P systems Cristian Ioan Vasile · Ana Brându¸sa Pavel · Ioan Dumitrache · Gheorghe P˘aun
Received: 31 October 2011 / Accepted: 23 July 2012 / Published online: 19 August 2012 © Springer-Verlag 2012
Abstract We study the computing power of a class of numerical P systems introduced in the framework of autonomous robot control, namely enzymatic numerical P systems. Three ways of using the evolution programs are investigated: sequential, all-parallel and one-parallel (with the same variable used in all programs or in only one, respectively); moreover, both deterministic and non-deterministic systems are considered. The Turing universality of some of the obtained classes of numerical P systems is proved (for polynomials with the smallest possible degree, one, also introducing a new proof technique in this area, namely starting the universality proof from the characterization of computable sets of numbers by means of register machines). The power of many other classes remains to be investigated.
C. I. Vasile · A. B. Pavel (B)· I. Dumitrache Department of Automatic Control and Systems Engineering, Politehnica University of Bucharest, Splaiul Independen¸tei 313, 060042 Bucharest, Romania e-mail: [email protected]; [email protected] C. I. Vasile e-mail: [email protected] I. Dumitrache e-mail: [email protected] Gh. P˘aun Institute of Mathematics of the Romanian Academy, PO Box 1-764, Bucharest 014700, Romania e-mail: [email protected] Gh. P˘aun Research Group on Natural Computing, Department of Computer Science and Artificial Intelligence, University of Sevilla, Avda. Reina Mercedes s/n, 41012 Sevilla, Spain e-mail: [email protected]
123
396
C. I. Vasile et al.
1 Introduction In the last years, several classes of computing devices—called P systems—were introduced inspired from the cell architecture and functioning, and vividly investigated in the framework of membrane computing—general references will be given below. Numerical P systems are a class of computing models inspired both from the cell structure and from the economics: numerical variables evolve in the compartments of a cell-like structure by means of so-called production–repartition programs. The variables have a given initial value and the production function is usually a polynomial, whose value for the current values of variables is distributed among variables in certain compartments (close to the place where the polynomial is evaluated—see precise definitions in the next section) according to the “repartition protocol”. In this way, the values of variables evolve; all values taken by a specified variable are said to be computed by the P system. These computing devices were introduced in [9], where their computational completeness (equivalence with the computing power of Turing machines) was proven, by making use of the characterization of Turing computable sets of numbers as the positive values of polynomials with integer coefficients [5]. The results in [9], as well as further connections between
Data Loading...
