Improving Universality Results on Parallel Enzymatic Numerical P Systems

Improving Universality Results on Parallel Enzymatic Numerical P Systems Alberto Leporati, Antonio E. Porreca, Claudio Zandron, Giancarlo Mauri Dipartimento di Informatica, Sistemistica e Comunicazione Universit`a degli Studi di Milano-Bicocca Viale Sarca 336/14, 20126 Milano, Italy E-mail: {leporati,porreca,zandron,mauri}@disco.unimib.it Summary. We improve previously known universality results on enzymatic numerical P systems (EN P systems, for short) working in all-parallel and one-parallel modes. By using a flattening technique, we first show that any EN P system working in one of these modes can be simulated by an equivalent one-membrane EN P system working in the same mode. Then we show that linear production functions, each depending upon at most one variable, suffice to reach universality for both computing modes. As a byproduct, we propose some small deterministic universal enzymatic numerical P systems. 1 Introduction Numerical P systems have been introduced in [10] as a model of membrane systems inspired both from the structure of living cells and from economics. Each region of a numerical P system contains some numerical variables, that evolve from initial values by means of programs. Each program consists of a production function and arepartition protocol; the production function computes an output value from the values of some variables occuring in the same region in which the function is located, while the repartition protocol distributes this output value among the variables in the same region as well as in the neighbouring (parent and children) ones. In [10], and also in Chapter 23.6 of [11], some results concerning the computational power of numerical P systems are reported. In particular, it is proved that nondeterministic numerical P systems with polynomial production functions characterize the recursively enumerable sets of natural numbers, while deterministic numerical P systems, with polynomial production functions having non-negative coefficients, compute strictly more than semilinear sets of natural numbers. Enzymatic Numerical P systems (EN P systems, for short) have been introduced in [13] as an extension of numerical P systems in which some variables, named the enzymes, control the application of the rules, similarly to what happens in P systems with promoters and inhibitors [1]. Although in [10] it is claimed 178 A. Leporati et al. that numerical P systems have been inspired by economic and business processes, the most promising application of their enzymatic version seems to be the simulation of control mechanisms of mobile and autonomous robots [12, 2, 14, 15]. In [17, 16] some results concerning the computational power of enzymatic P systems are reported. In particular, in [17] it is shown that EN P systems with 7 membranes and polynomial production functions of degree 5 involving at most 5 variables, working in the sequential mode (at each step, only one of the active programs is applied in each membrane) are universal. The computational power of EN P systems working in the so called one-parallel mode — programs are applied in parallel in each membrane, but each variable can appear only in one of the production functions — is also investigated, showing universality of these systems with an unlimited number of membranes and linear production functions (that is, polynomial functions of degree 1), each involving at most 2 variables. Finally, the universality of (deterministic) EN P systems working in the all-parallel mode — in each membrane all programs which can be applied are applied, possibly using the same variable in many production functions — having 254 membranes and polynomial production functions of degree 2 involving at most 253 variables, is established. A considerable improvement of the last result has subsequently been presented in [16], where it is proved that 4 membranes and linear production functions involving at most 6 variables suffice to obtain universal deterministic EN P systems working in the all-parallel mode. In this paper we continue the study of the computational power of enzymatic numerical P systems. In particular we first show that, given any EN P system Π working either in the one-parallel or in the all-parallel mode, it is possible to build an equivalent EN P system Π0whose structure consists of a single membrane. This flattening technique already improves some of the above mentioned results, reducing to 1 the number of membranes required by all-parallel or one-parallel EN P systems to reach universality — albeit, despite this transformation, oneparallel EN P systems still require an unbounded number of variables. Then, we prove that for EN P systems working either in the all-parallel or in the one-parallel mode one membrane and linear production functions — each involving at most 1 variable — suffice to reach universality. These results are all obtained by simulating deterministic and/or nondeterministic register machines; by considering a small deterministic universal register machine described in [6], we obtain as byproducts some small deterministic universal EN P systems, working in the all-parallel mode. A point to be considered is that the output of our EN P systems is defined as the value of some specified variables in a final configuration, that is, a configuration which is not changed by further applying programs. This allows us to simplify some of our constructions, but it is a bit different from the way EN P systems produce their output in most existing papers, where some specified output variables are considered, and the output of the system is the set of all values assumed by these variables during the entire computation. However, we prove that each of our EN P systems can be easily modified in order to produce its output according to the latter mode. Universality Results on Parallel Enzymatic Numerical P Systems 179 The rest of the paper is organized as follows. In section 2 we recall the definitions of EN P systems and register machines, along with the terms, tools and notation that will be used in the following. In section 3 we first show that any EN P system working either in the all-parallel or in the one-parallel mode can be “flattened” to one membrane, and then we prove our universality results on one-membrane EN P systems working in all-parallel or in one-parallel modes. In section 4 we show that the EN P systems used to obtain these results can be modified in order to produce their output into separate variables, as it is usually done in the literature. The conclusions and some directions for further work are given in section 5. 2 Definitions and Mathematical Preliminaries We denote by Nthe set of non-negative integers. An alphabet Ais a finite nonempty set of abstract symbols. Given A, the free monoid generated by Aunder the operation of concatenation is denoted by A∗; the empty string is denoted by λ, and A∗− {λ}is denoted by A+. By |w|we denote the length of the word w over A. If A={a1, . . . , an}, then the number of occurrences of symbol aiin wis denoted by |w|ai; the Parikh vector associated with wwith respect to a1, . . . , anis (|w|a1,...,|w|an). The Parikh image of a language Lover {a1, . . . , an}is the set of all Parikh vectors of strings in L. For a family of languages FL, the family of Parikh images of languages in FL is denoted by PsFL. The family of recursively enumerable languages is denoted by RE; the family of all recursively enumerable sets of k-dimensional vectors of non-negative integers can thus be denoted by Ps(k)RE. Since numbers can be seen as one-dimensional vectors, we can replace Ps(1) by Nin the notation, thus obtaining NRE. 2.1 Enzymatic Numerical P Systems An enzymatic numerical P system (EN P system, for short) is a construct of the form: Π= (m, H, µ, (V ar1, Pr1, V ar1(0)),...,(V arm, Prm, V arm(0))) where m≥1 is the degree of the system (the number of membranes), His an alphabet of labels, µis a tree-like membrane structure with mmembranes injectively labeled with elements of H,V ariand Priare respectively the set of variables and the set of programs that reside in region i, and V ari(0) is the vector of initial values for the variables of V ari. All sets V ariand P riare finite. In the original definition of EN P systems [13] the values assumed by the variables may be real, rational or integer numbers; in what follows we will allow instead only integer numbers. The variables from V ariare written in the form xj,i, for jrunning from 1 to |V ari|, the cardinality of V ari; the value assumed by xj,i at time t∈Nis 180 A. Leporati et al. denoted by xj,i(t). Similarly, the programs from Priare written in the form Pl,i, for lrunning from 1 to |Pri|. The programs allow the system to evolve the values of variables during computations. Each program is composed of two parts: a production function and a repartition protocol. The former can be any function using variables from the region that contains the program. Usually only polynomial functions are considered, since these are sufficient to reach the computational power of Turing machines, as proved in [17]. Using the production function, the system computes a production value, from the values of its variables at that time. This value is distributed to variables from the region where the program resides, and to variables in its upper (parent) and lower (children) compartments, as specified by the repartition protocol. Formally, for a given region i, let v1, . . . , vnibe all these variables; let x1,i, . . . , xki,i be some variables from V ari, let Fl,i(x1,i, . . . , xki,i) be the production function of a given program Pl,i ∈P ri, and let cl,1, . . . , cl,nibe natural numbers. The program Pl,i is written in the following form: Fl,i(x1,i, . . . , xki,i)→cl,1|v1+cl,2|v2+· · · +cl,ni|vni(1) where the arrow separates the production function from the repartition protocol. Let Cl,i =Pni s=1 cl,s be the sum of all the coefficients that occur in the repartition protocol. If the system applies program Pl,i at time t≥0, it computes the value q=Fl,i(x1,i(t), . . . , xki,i(t)) Cl,i that represents the “unitary portion” to be distributed to variables v1, . . . , vni proportionally with coefficients cl,1, . . . , cl,ni. So each of the variables vs, for 1 ≤ s≤ni, will receive the amount q·cl,s. An important observation is that variables x1,i, . . . , xki,i involved in the production function are reset to zero after computing the production value, while the other variables from V ariretain their value. The quantities assigned to each variable from the repartition protocol are added to the current value of these variables, starting with 0 for the variables which were reset by a production function. As pointed out in [17], a delicate problem concerns the issue whether the production value is divisible by the total sum of coefficients Cl,i. As it is done in [17], in this paper we assume that this is the case, and we deal only with such systems; see [10] for other possible approaches. Besides programs (1), EN P systems may also have programs of the form Fl,i(x1,i, . . . , xki,i)|ej,i →cl,1|v1+cl,2|v2+· · · +cl,ni|vni where ej,i is a variable from V aridifferent from x1,i, . . . , xki,i and from v1, . . . , vni. Such a program can be applied at time tonly if ej,i(t)>min(x1,i(t), . . . , xki,i(t)). Stated otherwise, variable ej,i operates like an enzyme, that enables the execution of the program, but — like it happens also with catalysts — it is neither consumed nor modified by the execution of the program. However, in EN P systems enzymes can evolve by means of other programs, that is, enzymes can receive “contributions” from other programs and regions. Universality Results on Parallel Enzymatic Numerical P Systems 181 Aconfiguration of Πat time t∈Nis given by the values of all the variables of Πat that time; in a compact notation, we can write it as the sequence (V ar1(t), . . . , V arm(t)), where mis the degree of Π. The initial configuration can thus be described as the sequence (V ar1(0), . . . , V arm(0)). The system Πevolves from an initial configuration to other configurations by means of computation steps, in which one or more programs of Π(depending upon the mode of computation) are executed. In [17], at each computation step the programs to be executed are chosen in the so called sequential mode: one program is nondeterministically chosen in each region, among the programs that can be executed at that time. Another possibility is to select the programs in the so called all-parallel mode: in each region, all the programs that can be executed are selected, with each variable participating in all programs where it appears. Note that in this case EN P systems become deterministic, since nondeterministic choices between programs never occur. A variant of parallelism, analogous to the maximal one which is often used in membrane computing, is the so called one-parallel mode: in each region, all the programs which can be executed can be selected, but the actual selection is made in such a way that each variable participates in only one of the chosen programs. We say that the system reaches a final configuration if and when it happens that no applicable set of programs produces a change in the current configuration. In such a case, a specified set of variables contains the output of the computation. Of course, a computation may never reach a final configuration. Note that in the usual definition of EN P systems the output of a computation is instead defined as the collection of values taken by a specified set of variables during the whole computation. In what follows we prove our results both by considering outputs in the final configurations, and by the latter notion of producing the output. EN P systems can be used to compute functions, in the so called computing mode, by considering some input variables and output variables. The initial values of the input variables are considered the actual arguments of the function, while the value of the output variables in the final configuration (provided that the system reaches it) is viewed as the output of the computed function. If the system never reaches a final configuration, then the computed function is undefined for the specified input values. By neglecting input variables, (nondeterministic) EN P systems can also be used in the generating mode, whereas by neglecting output variables we can use (deterministic or nondeterministic) EN P systems in the accepting mode, where the input is accepted if the system reaches a final configuration. A technical detail to take care of is the fact that normally we would like to characterize families of sets of natural numbers (sometimes including and sometimes excluding zero), while the input and output variables of EN P systems may also assume negative values. The systems we will propose are designed to produce only non-negative numbers in the output variables when the input variables (if present) are assigned with non-negative numbers. So if the systems are used in the intended way, they always produce meaningful (and correct) results. Another possibility, mentioned in [17] but not considered here, is to filter the output values so that only the positive ones are considered as output. 182 A. Leporati et al. When using EN P systems in the generating or accepting modes, we denote by ENPm(polyn(r), app mode) the family of sets of (possibly vectors of) nonnegative integer numbers which are computed by EN P systems of degree m≥1, using polynomials of degree at most n≥0 with at most r≥0 arguments as production functions; the fact that the programs are applied in the sequential, one-parallel or all-parallel mode is denoted by assigning the value seq,oneP or allP to the app mode parameter, respectively. When app mode ∈ {seq, oneP}and the P system is deterministic, we write det after the app mode parameter; this specification is not needed for all-parallel EN P systems, since they are always deterministic. If one of the parameters m,n,ris not bounded by a constant value, we replace it by ∗. With this notation, we can summarize the characterizations of NRE proved in [17] as follows: NRE =ENP7(poly5(5), seq) = ENP∗(poly1(2), oneP ) =ENP254(poly2(253), allP) whereas the improvement of the last equality given in [16] can be written as NRE = ENP4(poly1(6), allP ). In section 3 we further improve the results concerning EN P systems working in the all-parallel and in the one-parallel modes: in both cases, we will obtain characterizations of NRE by using just one membrane, and linear production functions that use each at most one variable. 2.2 Register Machines In what follows we will simulate register machines, so we briefly recall their definition and some of their computational properties. An n–register machine is a construct M= (n, P, m), where n > 0 is the number of registers, Pis a finite sequence of instructions bijectively labelled with the elements of the set {0,1, . . . , m −1}, 0 is the label of the first instruction to be executed, and m−1 is the label of the last instruction of P. Registers contain non-negative integer values. The instructions of Phave the following forms: •j: (inc(r), k, l), with 0 ≤j < m, 0 ≤k, l ≤mand 1 ≤r≤n. This instruction, labelled with j, increments the value contained in register r, then nondeterministically jumps either to instruction kor to instruction l. •j: (dec(r), k, l), with 0 ≤j < m, 0 ≤k, l ≤mand 1 ≤r≤n. If the value contained in register ris positive then decrement it and jump to instruction k. If the value of ris zero then jump to instruction l(without altering the contents of the register). Adeterministic n-register machine is an n-register machine in which all inc instructions have the form j: (inc(r), k, k); in what follows, we will write these instructions simply as j: (inc(r), k). Universality Results on Parallel Enzymatic Numerical P Systems 183 Aconfiguration of an n-register machine Mis described by the contents of each of its registers and by the program counter, that indicates the next instruction to be executed. Computations start by executing the first instruction of P(labelled with 0), and possibly terminate when the instruction currently executed jumps to label m(we may equivalently assume that Pincludes the instruction m:halt, explicitly stating that the computation must halt). It is well known that register machines provide a simple universal computational model, and that machines with three registers suffice to characterize NRE [8]. More precisely, we can use register machines in the computing, generating or accepting mode, obtaining the following results [3, 4, 5]. For the computing mode, we have: Proposition 1. For any partial recursive function f:Nα→Nβ(α, β > 0), there exists a deterministic register machine Mwith (max{α, β}+ 2) registers computing fin such a way that, when starting with n1to nαin registers 1to α,Mhas computed f(n1, . . . , nα)=(r1, . . . , rβ)if it halts in the final label mwith registers 1to βcontaining r1to rβ,and all other registers being empty; if f(n1, . . . , nα)is undefined then the final label of Mis never reached. In accepting register machines, a vector of non-negative integers is accepted if and only if the register machine halts: Proposition 2. For any recursively enumerable set L⊆Ps(α)RE of vectors of non-negative integers there exists a deterministic register machine Mwith (α+ 2) registers accepting Lin such a way that, when starting with n1to nαin registers 1to α,Mhas accepted (n1, . . . , nα)∈Lif and only if it halts in the final label m with all registers being empty. To generate vectors of non-negative integers, we need nondeterministic register machines: Proposition 3. For any recursively enumerable set L⊆Ps(β)RE of vectors of non-negative integers there exists a non-deterministic register machine Mwith (β+ 2) registers generating L, i.e., when starting with all registers being empty, Mgenerates (r1, . . . , rβ)∈Lif it halts in the final label mwith registers 1to β containing r1to rβ,and all other registers being empty. 3 Universality of EN P Systems As stated above, our aim is to improve the universality results shown in [17, 16], concerning all-parallel and one-parallel EN P systems. We first prove that these P systems can be “flattened”. Theorem 1. Let Πbe any computing (or generating, or accepting) EN P system of degree m≥1, working in the all-parallel or in the one-parallel mode. Then there exists an EN P system Π0of degree 1that computes (resp., generates, accepts) the same function (resp., family of sets) using the same rule application mode. 184 A. Leporati et al. Proof. Let Π= (m, H, µ, (V ar1, P r1, V ar1(0)),...,(V arm, P rm, V arm(0))) be an EN P system, computing a function f:Nα→Nβ(α, β ≥0) and working in the all-parallel mode. All the other cases (one-parallel, generating and accepting modes) can be simply deduced from the following argumentation. Note that each variable xj,i ∈V ariand each program Pl,i ∈P rialready indicates in one of its indexes the region that contains it. We build a new EN P system Π0of degree 1, by putting all the variables and all the programs of Π — keeping both indexes, also in the variables occurring in programs — in the membrane of Π0. Clearly, this establishes a bijection between the variables (resp., programs) of Πand the corresponding variables (resp., programs) of Π0, since the presence of both indexes in Π0allows one to keep track of the region of Πfrom which each variable and each program comes from. So any program Pl,i of Πstill operates on the correct variables when transformed and put into Π0, regardless of whether or not it uses an enzyme. Also input and output variables are preserved, and so the only issue is related with the mode used to select the programs to be applied. If Πworks in the sequential mode, then at each computation step only (at most) one program is selected in each region; this means that globally Πexecutes a set of programs which cannot be captured in Π0by any of the sequential, oneparallel and all-parallel modes. Instead, if Πworks in the all-parallel mode then at each computation step all the programs that can be executed are selected, and the same happens in Π0by letting it work in the all-parallel mode. The same applies when Πand Π0work in the one-parallel mode, and so the claim of the theorem follows. ut This result already allows to improve the universality results shown in [17, 16] for all-parallel and one-parallel EN P systems, obtaining the following characterizations of NRE: NRE =ENP1(poly1(6), allP ) = ENP1(poly1(2), oneP ) However — as stated in the Introduction — despite this simplification, one-parallel EN P systems still require an unbounded number of variables, since each “new” variable in Π0is indexed with the region of Πit comes from. Anyhow, we can improve both results. We start with the first equality, concerning all-parallel EN P systems. Theorem 2. Each partial recursive function f:Nα→Nβ(α > 0, β ≥0) can be computed by a one-membrane EN P system working in the all-parallel mode, having linear production functions that use each at most one variable. Proof. Since all-parallel EN P systems are deterministic, we prove the statement by simulating deterministic register machines. Let M= (n, P, m) be such a machine with nregisters, computing fby means of program P. The initial instruction of Phas the label 0 and the machine halts if and when the program counter assumes the value m. Observe that according to the result stated in Proposition 1, n= max{α, β}+2 is enough. The input values x1, . . . , xαare expected to be in the Universality Results on Parallel Enzymatic Numerical P Systems 185 first αregisters before the computation starts, and the values of f(x1, . . . , xα) — if any — are expected to be in registers 1 to βat the end of a halting computation. Moreover, without loss of generality, we may assume that at the beginning of a computation all the registers except possibly the registers 1 to αcontain zero. We construct the EN P system ΠM= (1, H, µ, (V ar1, P r1, V ar1(0))) of degree 1, where: •H={s}is the label of the only membrane (the skin) of ΠM; •µ= [ ]sis the membrane structure; •V ar1={r1, . . . , rn}∪{p0, . . . , pm}; •Pr1={2pj→1|ri+ 1|pkfor all instructions j: (inc(i), k)∈P} ∪ {−pj→ 1|ri, ri+ 2|pj→1|ri+ 1|pl, pj→1|pk, ri−1|pj→1|pkfor all instructions j: (dec(i), k, l)∈P}; •V ar1(0) is the vector of initial values of the variables of V ar1, obtained by putting: –ri=xifor all 1 ≤i≤α; –ri= 0 for all α+ 1 ≤i≤n; –p0= 1; –pj= 0 for all 1 ≤j≤m. The value of register i, for 1 ≤i≤m, is contained in variable ri. The input values x1, . . . , xαare introduced into the P system as the initial values of variables r1, . . . , rα. Variables p0, . . . , pmare used to indicate the value of the program counter; at the beginning of each computation step, the variable corresponding to the value of the program counter of Mwill assume value 1, while all the others will be equal to zero. The simulation of Mby ΠMworks as follows. Each increment instruction j: (inc(i), k) is simulated in one step by the execution of the program 2pj→1|ri+ 1|pk This program is executed at every computation step of ΠM; however, when pj= 0 it has no effect: pjis once again set to zero, and a contribution of zero is distributed among variables riand pk. All variables are thus unaffected in this case. When pj= 1, the production value 2pj= 2 is distributed among riand pk, giving a contribution of 1 to each of them. Hence the value of riis incremented, the value of pkpasses from 0 to 1, while the value of pjis zeroed. All the other variables are unaffected, and the system is now ready to simulate the next instruction of M. Each decrement instruction j: (dec(i), k, l) is simulated in one step by the parallel execution of the following programs: −pj→1|ri(2) ri+ 2|pj→1|ri+ 1|pl(3) pj→1|pk(4) ri−1|pj→1|pk(5) 192 A. Leporati et al. ΠM= (1, H, µ, (V ar1, Pr1, V ar1(0))) where: •H={s}is the label of the only membrane (the skin) of ΠM; •µ= [ ]sis the membrane structure; •V ar1={r1, . . . , rn} ∪ {p0, . . . , pm} ∪ {q0, . . . , qm} ∪ {zj,1, zj,2, zj,3for all 0 ≤ j < m}; •Pr1={zj,1+4|pj→2|ri+1|pk+1|qk, zj,1+4|pj→2|ri+1|pl+1|ql, zj,2−1|pj→ 1|qj, zj,3−1|qj→1|pjfor all instructions j: (inc(i), k, l)∈P}∪{zj,1−2|pj→ 1|ri, ri+4|pj→2|ri+1|pl+1|ql,2pj|ri→1|pj+1|pk,2qj|ri→1|qj+1|qk, zj,2− 1|pj→1|qj, zj,3−1|qj→1|pj}for all instructions j: (dec(i), k, l)∈P}; •V ar1(0) is the vector of initial values of the variables of V ar1, obtained by putting: –ri= 2xifor all 1 ≤i≤α; –ri= 0 for all α+ 1 ≤i≤n; –p0=q0= 1; –pj=qj= 0 for all 1 ≤j≤m; –zj,1=zj,2=zj,3= 0 for all 0 ≤j < m. As stated above, now the value of riis the double of the value of register i, for 1 ≤i≤n. So, in particular, the double of the input values x1, . . . , xαare introduced into the P system as the initial values of variables r1, . . . , rα. Once again, like in the proof of Theorem 4, the system uses both variables p0, . . . , pm and q0, . . . , qmto indicate the value of the program counter of M, so that when simulating the j-th instruction of Pvariables pjand qjare both equal to 1, while all the others are zero. The value of variables zj,1, zj,2, zj,3is always zero during the entire computation. Each increment instruction j: (inc(i), k, l) of Mis simulated in one step by the execution of the following programs: zj,1+ 4|pj→2|ri+ 1|pk+ 1|qk(16) zj,1+ 4|pj→2|ri+ 1|pl+ 1|ql(17) zj,2−1|pj→1|qj(18) zj,3−1|qj→1|pj(19) The simulation is analogous to the one described in the proof of Theorem 4, with the difference that instead of incrementing rithe system now adds 2 to it; to do so, the production value computed by the first two programs must be 4 instead of 3. Nondeterminism is given by the fact that, when pj=qj= 1, variable zj,1makes programs (16) and (17) compete in the one-parallel mode. If the machine Mto be simulated is deterministic, then program (17) disappears, and so the simulation becomes deterministic. Each decrement instruction j: (dec(i), k, l) is simulated in one step by the execution of the following programs: Universality Results on Parallel Enzymatic Numerical P Systems 193 zj,1−2|pj→1|ri(20) ri+ 4|pj→2|ri+ 1|pl+ 1|ql(21) 2pj|ri→1|pj+ 1|pk(22) 2qj|ri→1|qj+ 1|qk(23) zj,2−1|pj→1|qj(24) zj,3−1|qj→1|pj(25) The simulation is analogous to the one described in the proof of Theorem 4, with small differences. The case when pj=qj= 0 operates just like in the proof of Theorem 4: programs (20), (21), (24) and (25) are not active, while programs (22) and (23) are executed only if ri>0; however, in such a case, a contribution of 0 is distributed to variables pj,qj,pk,qkafter setting pjand qjto zero. Now assume that pj=qj= 1 and ri>0. Program (20) correctly decrements ri (subtracting 2 from its value), whereas program (21) is not executed since ri> pj. Programs (22) and (23) set to 1 variables pkand qk(thus pointing at the next instruction of Mto be simulated), and send a contribution of 1 to variables pjand qj, after setting their value to zero. On the other hand, programs (24) and (25) send a contribution of −1 to pjand qj, so that their final value will be zero. Now assume that pj=qj= 1 and ri= 0. In this case, the value of rishould be kept equal to zero, and the computation should continue with instruction l. Program (20) sends a contribution of −2 to ri. This time, however, program (21) is also executed; its effect is sending a contribution of 2 to ri, after setting it to zero (so that its final value will be zero), and setting to 1 the value of variables pl and ql. Programs (22) and (23) are inactive, and hence are not executed. Finally, programs (24) and (25) send a contribution of −1 to pjand qj, so that their final value will be zero. It follows from the description given above that the simulation is correct, and that after the simulation of each instruction the value of variable riis exactly the double of the contents of register i, for 1 ≤i≤n. If and when the program counter of Mreaches the value m, the corresponding variables pmand qmassume value 1 and the computation reaches a final configuration; the result of the computation is then contained in variables r1, . . . , rβ.ut Let 2NRE denote the family of recursively enumerable sets of even natural numbers: 2NRE ={{2x|x∈X} | X∈NRE}. By taking β= 0 and α≥1 (resp., α= 0 and β≥1) in the previous proof one obtains a characterization of the recursively enumerable sets of vectors of even natural numbers by accepting (resp., generating) one-parallel EN P systems. In particular, by putting β= 0 and α= 1 or α= 0 and β= 1, we obtain: 2NRE =ENP1(poly1(1), oneP) As a byproduct of Theorem 6 we also obtain a small universal deterministic EN P system that computes any partial recursive function f: 2N→2N, by simulating 194 A. Leporati et al. the universal deterministic register machine illustrated in Figure 1. With respect to the small EN P system described in the proof of Theorem 5 we have removed two auxiliary variables from the programs that simulate each decrement instruction, hence the new system consists of 105 programs and 120 variables. As discussed after the proof of Theorem 5, this small EN P system is deterministic too and hence it also works in the all-parallel mode; however, it works only with even natural numbers as inputs and outputs. Of course one would desire a characterization of NRE (instead of 2NRE) by one-parallel EN P systems having linear production functions, each depending upon just one variable. We can actually obtain such a characterization by using the EN P system ΠMdescribed in the proof of the previous theorem as a subroutine. The idea is to produce a new one-parallel EN P system Π0 Mthat, given a vector from Nαas input, prepares a corresponding input vector for ΠMby doubling its components. Then ΠMis used to compute the output vector from Nβ, if it exists. At this point Π0 Mshould take this output and halve each component, to produce its output. To avoid this further step, we proceed as follows: while preparing the input for ΠM,Π0 Malso makes a copy of its input into additional variables si, for 1 ≤ i≤n. Then we modify the programs of ΠMin such a way that, while simulating a (possibly nondeterministic) register machine M, it keeps in sithe contents of the registers, and in rithe doubles of such contents. So the programs use variables ri to correctly perform the simulation, while at the end of the computation the result will be immediately available in variables si. The details are given in the proof of the following theorem, where the systems ΠMand Π0 Mare combined together. Theorem 7. Each partial recursive function f:Nα→Nβ(α≥0, β ≥0) can be computed by a one-membrane EN P system working in the one-parallel mode, having linear production functions that use each at most one variable. Proof. Like in the proofs of Theorems 4 and 6, we build a one-parallel EN P system ΠM= (1, H, µ, (V ar1, Pr1, V ar1(0))) that simulates a nondeterministic register machine M= (n, P, m) that computes f, as follows: •H={s}is the label of the only membrane (the skin) of ΠM; •µ= [ ]sis the membrane structure; •V ar1={r1, . . . , rn} ∪ {s1, . . . , sn} ∪ {t1, . . . , tn} ∪ {p} ∪ {p0, . . . , pm} ∪ {q0, . . ., qm}∪{zj,1, zj,2, zj,3for all 0 ≤j < m}; •Pr1={3ti→2|ri+1|sifor all 1 ≤i≤α}∪{2p→1|p0+1|q0}∪{zj,1+5|pj→ 2|ri+ 1|si+ 1|pk+ 1|qk, zj,1+ 5|pj→2|ri+ 1|si+ 1|pl+ 1|ql, zj,2−1|pj→ 1|qj, zj,3−1|qj→1|pjfor all instructions j: (inc(i), k, l)∈P}∪{zj,1−3|pj→ 2|ri+ 1|si, ri+ 5|pj→2|ri+ 1|si+ 1|pl+ 1|ql,2pj|ri→1|pj+ 1|pk,2qj|ri→ 1|qj+ 1|qk, zj,2−1|pj→1|qj, zj,3−1|qj→1|pj}for all instructions j: (dec(i), k, l)∈P}; •V ar1(0) is the vector of initial values of the variables of V ar1, obtained by putting: –ti=xi(the input values of f) for all 1 ≤i≤α; –ti= 0 for all α+ 1 ≤i≤n; Universality Results on Parallel Enzymatic Numerical P Systems 195 –ri=si= 0 for all 1 ≤i≤n; –p= 1; –pj=qj= 0 for all 0 ≤j≤m; –zj,1=zj,2=zj,3= 0 for all 0 ≤j < m. The input values x1, . . . , xαof fare introduced into the P system as the initial values of variables t1, . . . , tα. Moreover, the value of variable pis set to 1. In the first step of its computation, the P system will copy the values of t1, . . . , tαto s1, . . . , sα, and the double of these values to variables r1, . . . , rα. So doing, after the simulation of each instruction of Mvariables s1, . . . , snwill contain the values of the registers of M, while r1, . . . , rnwill contain their doubles. While making these copies, the value of variable pis copied to both p0and q0, in order to start the simulation of M. The simulation proceeds much like in the way described in the proof of Theorem 6; the programs there illustrated are here modified in order to deal with the new variables. If and when the simulation reaches a final configuration, variables s1, . . . , sβcontain the result of the computation. The initialization step is performed by executing the following programs: 3ti→2|ri+ 1|sifor all 1 ≤i≤α 2p→1|p0+ 1|q0 Each increment instruction j: (inc(i), k, l) of Mis simulated in one step by the execution of the following programs: zj,1+ 5|pj→2|ri+ 1|si+ 1|pk+ 1|qk(26) zj,1+ 5|pj→2|ri+ 1|si+ 1|pl+ 1|ql(27) zj,2−1|pj→1|qj(28) zj,3−1|qj→1|pj(29) The simulation is analogous to the one described in the proof of Theorem 6, with the difference that when adding 2 to rithe system now also increments si; to do so, the production value computed by the first two programs must be 5 instead of 4. Once again, if the machine Mto be simulated is deterministic then program (27) disappears and the simulation itself becomes deterministic. Each decrement instruction j: (dec(i), k, l) is simulated in one step by the execution of the following programs: zj,1−3|pj→2|ri+ 1|si(30) ri+ 5|pj→2|ri+ 1|si+ 1|pl+ 1|ql(31) 2pj|ri→1|pj+ 1|pk(32) 2qj|ri→1|qj+ 1|qk(33) zj,2−1|pj→1|qj(34) zj,3−1|qj→1|pj(35) 196 A. Leporati et al. The simulation is analogous to the one described in the proof of Theorem 6, with the only difference that when subtracting or adding 2 to riby programs (30) and (31), respectively, the system now also decrements or increments si, respectively. It can be easily checked that the simulation is correct, and that after simulating each instruction of Mthe values of variable si(resp., ri) is equal to the contents (resp., the double of the contents) of register i, for 1 ≤i≤n. If and when the program counter of Mreaches the value m, the corresponding variables pmand qmassume value 1 and the computation reaches a final configuration; the result of the computation can then be recovered from variables s1, . . . , sβ.ut By taking β= 0 and α≥1 in the previous proof, we obtain the following result concerning the accepting variant of EN P systems working in the one-parallel mode. Corollary 4. For any L∈Ps(α)RE there exists a one-membrane EN P system, having linear production functions each depending upon at most one variable, that accepts Lby working in the one-parallel mode. On the other hand, by taking α= 0 and β≥1 we get the following characterization of Ps(β)RE by the generating variant of EN P systems working in the one-parallel mode. Corollary 5. For any L∈Ps(β)RE there exists a one-membrane (nondeterministic) EN P system, having linear production functions each depending upon at most one variable, that generates Lby working in the one-parallel mode. By putting α= 1 and β= 0 in Corollary 4, and α= 0 and β= 1 in Corollary 5, we obtain the following characterization: NRE =ENP1(poly1(1), oneP) Moreover, it can be easily checked that when the register machine Msimulated in Theorem 7 and in Corollary 4 is deterministic, the simulating EN P system ΠMworks in the all-parallel mode. This means that the above construction leads to a further characterization of NRE by all-parallel recognizing EN P systems having linear production functions of one variable, alternative to the one obtained by Theorem 2. Another consequence of Theorem 7 is that there exists a further small universal one-parallel deterministic EN P system, as stated in the following theorem. Theorem 8. There exists a universal one-parallel deterministic EN P system of degree 1, having 137 variables and 108 programs. Proof. The system mentioned in the statement simulates the small universal deterministic register machine Mureported in Figure 1, and is built according to the description given in the proof of Theorem 7, as we have done in the proofs of Theorems 3 and 5. The number of increment and decrement instructions of Mu are 9 and 13, respectively, and each of them is translated to 3 and 6 programs Universality Results on Parallel Enzymatic Numerical P Systems 197 of the small universal EN P system, respectively. The initialization step requires further α+1 = 3 programs, since Muis fed with two input values: the “code” of f and its input. We thus obtain a total of 108 programs. As for variables, 8 ·3 = 24 are used to simulate the registers of Mu, and 46 are used to denote the value of its program counter; moreover, there are 3 auxiliary variables for each instruction of M, and one variable (p) which used to trigger the start of the simulation, for a total of 137 variables. ut Since the universal register machine Musimulated in Theorem 8 is deterministic, the simulating small EN P system is deterministic too, and works both in the all-parallel as well as in the one-parallel mode. By comparing the number of variables and programs in all “small” EN P systems described in this paper, we see that the smallest is the one described in Theorem 3, containing only 31 variables and 61 programs. However such a small EN P system is not able to work in the one-parallel mode, hence in case we are forced to do so we must resort to one of the others described in this paper; the choice will depend upon the parameter (number of variables or number of programs) we want to minimize, as well as whether we are willing to work with even inputs and outputs. It is left as an open problem to prove that these are the smallest possible universal EN P systems, or finding instead smaller ones. Designing sets of programs that simulate consecutive inc and dec instructions of Mu, as it has already been done in [9] and several other times in the literature, could be a hint for finding smaller systems. 4 Producing Output in Separate Variables In all EN P systems described above, the output is considered to be the value of some specified variables in the final configuration, if and when this is reached. This is different from how EN P systems produce their output in most existing papers: usually, some separate output variables are considered, and the output of the system is defined as the set of all values assumed by these variables during the entire computation. In this section we prove that each of our EN P systems can be easily modified in order to produce its output according to this latter way. Theorem 9. The EN P systems used in Theorems 2, 4, 6 and 7 can be modified so that their output is produced into separate variables. Proof. Let ΠM= (1, H, µ, (V ar1, P r1, V ar1(0)) be one of the EN P systems mentioned in the statement, simulating a register machine Mcomputing the partial recursive function f:Nα→Nβ. Let x1, . . . , xβdenote the output variables of ΠM, that is, variables r1, . . . , rβfor Theorems 2, 4, 6 and variables s1, . . . , sβin Theorem 7. Note that, by construction, these variables contain the value of fif and when a final configuration is reached, and this happens if and only if pm(the variable indicating label mof the program of M) assumes value 1. We modify ΠMby introducing the following new variables: 198 A. Leporati et al. • {y1, . . . , yβ}, whose values are kept identical to x1, . . . , xβuntil pmbecomes 1 (if this happens); • {z1, . . . , zβ}, as the new output variables; • {u1, . . . , uβ}, as flags; and programs: βpm→1|u1+. . . + 1|uβ(36) ui→1|yifor all 1 ≤i≤β(37) xi|yi→zifor all 1 ≤i≤β(38) Moreover, each program already present in ΠMthat changes the value of an output variable xiis modified in order to also apply the same change to the new variable yi, as done in the proof of Theorem 7. So doing, after simulating each instruction of Mthe values of variables xiand yiwill be the same for all 1 ≤i≤β. Since y1, . . . , yβnever appear in the production functions of these modified programs, no change is caused to the behavior of ΠM. All new variables are initialized to zero before the computation starts. During the first computation step variables y1, . . . , yαare initialized to the values of x1, . . . , xα, as in the initialization step of Theorem 7. The computation then proceeds as prescribed by the programs of ΠM. If and when the computation reaches a final configuration then program (36) is executed, with the effect of zeroing pm and setting u1, . . . , uβto 1. When this happens, by programs (37) the values of y1, . . . , yβare incremented, thus becoming larger than the values of x1, . . . , xβ. This means that programs (38) can now be applied, with the effect of copying the values of the original output variables x1, . . . , xβto the new output variables z1, . . . , zβ. On the other hand, note that before and after reaching a final configuration of ΠMthe value of variables z1, . . . , zβis never affected. In fact, when pm= 0 program (36) has no effect, since it distributes a contribution of 0 to u1, . . . , uβ, leaving their value unaltered. This happens both before pmbecomes 1, and after executing program (36). Programs (37) increment the values of y1, . . . , yβonly once, when u1=. . . =uβ= 1, otherwise they produce no effect. Finally, programs (38) are first executed as soon as the values of y1, . . . , yβbecome larger than that of x1, . . . , xβ, after which they distribute a contribution of zero to z1, . . . , zβ. So the only value assumed by the new output variables z1, . . . , zβ, besides zero, is the output value of M.ut 5 Conclusions and Directions for Further Work In this paper we have studied the computational power of enzymatic numerical P systems working in the all-parallel and one-parallel modes. We have improved some previously known universality results, in terms of number of membranes and number of variables used in the production functions. Universality Results on Parallel Enzymatic Numerical P Systems 199 So, by using a flattening technique, we have first shown that every EN P system working either in the all-parallel or in the one-parallel mode can be simulated by an equivalent one-membrane EN P system working in the same mode. Then we have shown that linear production functions, each depending upon at most one variable, suffice to reach universality for both computing modes. As a byproduct we have obtained several small universal deterministic EN P systems, the smallest one having only 31 variables and 61 programs. It is left open whether smaller universal EN P systems exist. It is also left open whether the known universality result on sequential EN P systems contained in [17] — a characterization of NRE by sequential EN P systems of degree 7, whose production functions are polynomials of degree at most 5, each depending upon at most 5 variables — can be improved. Acknowledgements The ideas exposed in this paper emerged during the Eleventh Brainstorming Week on Membrane Computing (BWMC 2013), held in Seville from February 4th to February 8th, 2013. This research was partially funded by Lombardy Region under project NEDD. References 1. P. Bottoni, C. Mart´ın-Vide, Gh. P˘aun, G. Rozenberg: Membrane systems with promoters/inhibitors. Acta Informatica 38(10):695–720, 2002. 2. C. Buiu, C.I. Vasile, O. Arsene: Development of membrane controllers for mobile robots. Information Sciences 187:33–51, 2012. 3. R. Freund, M. Oswald: GP systems with forbidding context. Fundamenta Informaticae 49(1-3):81–102, 2002. 4. R. Freund, Gh. P˘aun: On the number of non-terminals in graph-controlled, programmed, and matrix grammars. In: M. Margenstern, Y. Rogozhin (Eds.), Universal Machines and Computations, Chi¸sin˘au, 2001, LNCS 2055, Springer-Verlag, 2001, pp. 214–225. 5. R. Freund, Gh. P˘aun: From regulated rewriting to computing with membranes: collapsing hierarchies. Theoretical Computer Science 312:143–189, 2004. 6. I. Korec: Small universal register machines. Theoretical Computer Science 168:267– 301, 1996. 7. Y. Matijasevitch: Hilbert’s tenth problem. MIT Press, Cambridge, London, 1993. 8. M.L. Minsky: Computation. finite and infinite machines. Prentice Hall, Englewood Cliffs, New Jersey, 1967. 9. A. P˘aun, Gh. P˘aun: Small universal spiking neural P systems. Biosystems 90(1):48– 60, 2007. 10. Gh. P˘aun, R. P˘aun: Membrane computing and economics: numerical P systems. Fundamenta Informaticae 73:213–227, 2006. 11. Gh. P˘aun, G. Rozenberg, A. Salomaa (eds.): The Oxford handbook of membrane computing. Oxford University Press, 2010. 200 A. Leporati et al. 12. A.B. Pavel: Membrane controllers for cognitive robots. Master’s thesis, Department of Automatic Control and System Engineering, Politechnica University of Bucharest, Romania, 2011. 13. A.B. Pavel, O. Arsene, C. Buiu: Enzymatic numerical P systems – A new class of membrane computing systems. IEEE Fifth International Conference on Bio-Inspired Computing: Theory and Applications (BIC-TA), IEEE, 2010, pp. 1331–1336. 14. A.B. Pavel, C. Buiu: Using enzymatic numerical P systems for modeling mobile robot controllers. Natural Computing 11(3):387–393, 2012. 15. A.B Pavel, C.I. Vasile, I. Dumitrache: Robot localization implemented with enzymatic numerical P systems. In: T.J. Prescott et al. (Eds.), Proceedings of Living Machines 2012, Barcelona, Spain, July 9–12, 2012, LNAI 7375, Springer-Verlag, 2012, pp. 204–215. 16. C.I. Vasile, A.B. Pavel, I. Dumitrache: Universality of enzymatic numerical P systems. International Journal of Computer Mathematics, 2013. DOI: 10.1080/00207160.2012.748897 17. C.I. Vasile, A.B. Pavel, I. Dumitrache, Gh. P˘aun: On the power of enzymatic numerical P systems. Acta Informatica 49(6):395–412, 2012.