Maximal parallelism has been an important feature of membrane systems from the beginning, i.e., only non-extendable multisets of rules are applied to the underlying configuration. During the last two decades many new variants of parallel derivation modes have been investigated, for example, non-extendable sets of rules are used instead of non-extendable multisets of rules. In many cases, computational completeness can be obtained. Recently, derivation modes applying multisets of rules affecting or generating the maximal number of objects or yielding the maximal difference between the objects in the current and the derived configuration have been shown to allow for computational completeness even when using only very restricted variants of rules.
When membrane systems were introduced in [37] more than two decades ago, the application of non-extendable multisets of rules was one of the basic features of this bio-inspired model of computing. An introduction to this fascinating area is documented in two textbooks, see [38] and [39]. For actual information see the P systems webpage [42] and the issues of the Bulletin of the International Membrane Computing Society and of the Journal of Membrane Computing.
The basic model of membrane systems (P systems, see [37] and [38]) can be seen as a multiset rewriting system where objects evolve in parallel in all the regions of a hierarchical membrane structure, but the resulting objects may also pass through the membranes surrounding a membrane region. In every derivation step a non-extendable multiset of rules is applied. The result of a computation is extracted when the system halts, i.e., when no rule is applicable any more. The multiset rewriting rules often can be restricted to non-cooperative rules of the form a ! v and catalytic rules of the form ca ! cv, where c is a catalyst, a is a single object and v is a multiset of objects. Catalysts are special objects which allow only one object to evolve in its context, but in their basic variant never evolve themselves. P systems using only these two types of rules are called catalytic, and if only catalytic rules are allowed we speak of purely catalytic P systems.
In the context of catalytic and purely catalytic P
systems, the question how many catalysts are needed for
obtaining computational completeness has been one of the
most intriguing challenges from the beginning. Without
catalysts only regular (semi-linear) sets can be generated
when using the standard maximally parallel derivation
mode and the standard halting mode. For catalytic P
systems with only one catalyst a lower bound was established
in [
In [
In [
In this paper, after recalling some classic results, I will
focus on the research which has been started in [
The set of natural numbers n 0 is denoted by N. For any two natural numbers m; n, m n, [m::n] denotes the set of natural numbers fk j m k ng. Moreover, m n +1 is defined as m + 1 for 1 m < n and n n +1 = 1.
For an alphabet V , the free monoid generated by V under the operation of concatenation, i.e., the set containing all possible strings over V is denoted by V . The empty string is denoted by l : A multiset M with underlying set A is a pair (A; f ) where f : A ! N is a mapping. If M = (A; f ) is a multiset then its support is defined as supp(M) = fx 2 A j f (x) > 0g. A multiset is empty (respectively finite) if its support is the empty set (respectively a finite set). If M = (A; f ) is a finite multiset over A and supp(M) = fa1; : : : ; akg, then it can also be represented by the string a f (a1) : : : akf (ak) over the alphabet 1 fa1; : : : ; akg, and, moreover, all permutations of this string precisely identify the same multiset M. The set of all multisets over V is denoted by V ◦. The cardinality of a set or multiset M is denoted by jMj.
For further notions and results in formal language
theory I refer to textbooks like [
Register machines are well-known universal devices for
computing on (or generating or accepting) sets of vectors
of natural numbers. The following definitions and
propositions are given as in [
Definition 1. A register machine is a construct
M = (m; B; l0; lh; P) where m is the number of registers,
l0 2 B is the initial label, and lh 2 B is the final label.
p : (ADD(r); q; s); p 2 B n flhg, q; s 2 B, 1 r m.
deterministically jump to instruction q or s. p : (SU B(r); q; s); p 2 B n flhg, q; s 2 B, 1 r m.
lh : HALT .
A configuration of a register machine is described by the contents of each register and by the value of the current label, which indicates the next instruction to be executed. M is called deterministic if the ADD-instructions all are of the form p : (ADD(r); q).
Throughout the paper, BADD denotes the set of labels of ADD-instructions p : (ADD(r); q; s) of arbitrary registers r, and BSUB(r) denotes the set of labels of all SUBinstructions p : (SU B(r); q; s) of a decrementable register r. Moreover, for any p 2 B n flhg, Reg(p) denotes the register affected by the ADD- or SUB-instruction labeled by p; for the sake of completeness, in addition Reg(lh) = 1 is taken.
In the accepting case, a computation starts with the input of an l-vector of natural numbers in its first l registers and by executing the first instruction of P (labeled with l0); it terminates with reaching the HALT -instruction. Without loss of generality, we may assume all registers to be empty at the end of the computation.
In the generating case, a computation starts with all registers being empty and by executing the first instruction of P (labeled with l0); it terminates with reaching the HALT instruction and the output of a k-vector of natural numbers in its last k registers. Without loss of generality, we may assume all registers except the last k output registers to be empty at the end of the computation.
In the computing case, a computation starts with the input of an l-vector of natural numbers in its first l registers and by executing the first instruction of P (labeled with l0); it terminates with reaching the HALT -instruction and the output of a k-vector of natural numbers in its last k registers. Without loss of generality, we may assume all registers except the last k output registers to be empty at the end of the computation.
For useful results on the computational power of register machines, we refer to [36]; for example, to prove our main theorem, we need the following formulation of results for register machines generating or accepting recursively enumerable sets of vectors of natural numbers with k components or computing partial recursive relations on vectors of natural numbers: Proposition 1. Deterministic register machines can accept any recursively enumerable set of vectors of natural numbers with l components using precisely l + 2 registers.
Proposition 2. Register machines can generate any recursively enumerable set of vectors of natural numbers with k components using precisely k + 2 registers. Without loss of generality, we may assume that at the end of a generating computation the first two registers are empty, and, moreover, on the output registers, i.e., the last k registers, no
Proposition 3. Register machines can compute any partial recursive relation on vectors of natural numbers with l components as input and vectors of natural numbers with k components as output using precisely l + 2 + k registers, where without loss of generality, we may assume that at the end of a successful computation the first l + 2 registers are empty, and, moreover, on the output registers, i.e., the last k registers, no SUB-instruction is ever used.
In all cases it is essential that the output registers never need to be decremented.
Remark 1. For any register machine, without loss of generality we may assume that the first instruction is an ADDinstruction on register 1: in fact, given a register machine M = (m; B; l0; lh; P) with having a another instruction as its first instruction, we can immediately construct an equivalent register machine M′ which starts with an increment immediately followed by a decrement of the first register: M′ B′ P′ = = = (m; B′; l0′; lh; P′) ; B [ fl0′; l0′′g;
P [ fl0′ : (ADD(1); l0′′; l0′′); l0′′ : (SUB(1); l0; l0) g: 2.2
Taking into account the well-known flattening process,
which means that computations in a P system with an
arbitrary membrane structure can be simulated in a P
system with only one membrane, e.g., see [
P = (V;C; T; w; R) where
C T
V is the set of catalysts; (V n C) is the alphabet of terminal objects; w 2 V ◦ is the multiset of objects initially present in the membrane region; R is a finite set of evolution rules over V ; these evolution rules are mutiset rewriting rules u ! v with u; v 2 V ◦.
The P system P is called catalytic, if R contains only noncooperative rules of the form a ! cv and catalytic rules of the form ca ! cv, where c 2 C is a catalyst, a is an object from V n C, and v is a multiset over V n C. The P system P is called purely catalytic, if R contains only catalytic rules.
The multiset in the single membrane region of P constitutes a configuration of the P system. The initial configuration is given by the initial multiset w; in case of accepting or computing P systems the input multiset w0 is assumed to be added to w, i.e., the initial configuration then is ww0.
A transition between configurations is governed by the application of the evolution rules, which is done in a given derivation mode. The application of a rule u ! v to a multiset M results in subtracting from M the multiset identified by u, and then in adding the multiset identified by v. 2.3
The definitions and the corresponding notions used in this
subsection follow the definitions and notions elaborated in
[
Given a P system P = (V;C; T; w; R), the set of multisets of rules applicable to a configuration C is denoted by Appl(P;C); this set also equals the set Appl(P;C; asyn) of multisets of rules applicable in the asynchronous derivation mode (abbreviated asyn).
Given a multiset R of rules in Appl(P;C), we write C !R C′ if C′ is the result of applying R to C. The number of objects affected by applying R to C is denoted by Aff(C; R). The number of objects generated in C′ by the right-hand sides of the rules applied to C with the multiset of rules R is denoted by Gen(C; R). The difference between the number of objects in C′ and C is denoted by ∆ob j(C; R).
The set Appl(P;C; sequ) denotes the set of multisets of rules applicable in the sequential derivation mode (abbreviated sequ), where in each derivation step exactly one rule is applied.
The standard parallel derivation mode used in P systems is the maximally parallel derivation mode (max for short). In the maximally parallel derivation mode, in any computation step of P we choose a multiset of rules from R in such a way that no further rule can be added to it so that the obtained multiset would still be applicable to the existing objects in the configuration, i.e., in simple P systems we only take applicable multisets of rules which cannot be extended by further (copies of) rules and are to be applied to the objects in the single membrane region:
Appl(P;C; max) =fR 2 Appl(P;C) j there is no R′ 2 Appl(P;C) such that R′
We first consider the derivation mode maxob jectsmax where from the multisets of rules in Appl(P;C; max) only those are taken which affect the maximal number of objects. As with affecting the maximal number of objects, such multisets of rules are non-extendable anyway, we will also use the notation maxob jects. Formally we may write: Appl(P;C; maxob jectsmax) = fR 2 Appl(P;C; max) j there is no R′ 2 Appl(P;C; max) such that Aff(C; R) < Aff(C; R′)g and
Appl(P;C; maxob jects) = fR 2 Appl(P;C; asyn) j there is no R′ 2 Appl(P;C; asyn) such that Aff(C; R) < Aff(C; R′)g: As already mentioned, both definitions yield the same multiset of rules.
In addition to these well-known derivation modes, in
this paper we also consider several new variants of
derivation modes as already introduced in [
Like for maxob jectsmax in comparison with maxob jects we now can also consider the variants of the other maximal derivation modes where we do not start with imposing the restriction of being non-extendable on the applicable multisets: maxGENob jects a multiset of rules R applicable to the current configuration C is only taken if the number of objects generated by the application of the rules in R to the configuration C is maximal with respect to the number of objects generated by the application of the rules in any other multiset of rules R′ to the configuration C: Appl(P;C; maxGENob jects) = fR 2 Appl(P;C; asyn) j there is no R′ 2 Appl(P;C; asyn) such that Gen(C; R) < Gen(C; R′)g: max∆ob jects a multiset of rules R applicable to the current configuration C is only taken if the difference ∆C = jC′j jCj between the number of objects in the configuration C′ obtained by the application of R and the number of objects in the underlying configuration C is maximal with respect to the differences in the number of objects obtained by applying any other multiset of rules: Appl(P;C; max∆ob jects) = fR 2 Appl(P;C; asyn) j there is no R′ 2 Appl(P;C; asyn) such that ∆ob j(C; R) <∆ob j(C; R′)g:
We illustrate the difference between these new derivation modes in the following examples, thereby emphasizing on catalytic and non-cooperative rules: Example 1. To illlustrate the derivation modes maxGENob jectsmax as well as max∆ob jectsmax, consider a simple P system with the initial configuration caa and the set of rules fa ! b; ca ! cdg.
In case of the derivation mode maxGENob jectsmax, only the multiset of rules fca ! cd; a ! bg can be applied, as Gen(caa; fca ! cdg)= 2 and Gen(cab; fa ! bg)= 1 and therefore Gen(caa; fca ! cd; a ! bg)= 3, whereas Gen(caa; fa ! b; a ! bg)= 2. Hence, the only possible derivation with the derivation mode maxGENob jectsmax is caa fca!cd;a!b!g cdb. In this special case,
Appl(P; caa; maxGENob jectsmax) =
Appl(P; caa; maxob jects):
max∆ob jectsmax both rules yield the same difference of 0, i.e., ∆ob j(caa; fca ! cdg) = ∆ob j(caa; fa ! bg) = 0, which yields all two non-extendable multisets of rules fca ! cd; a ! bg and fa ! b; a ! bg to be applicable to the underlying configuration caa, i.e.,
Appl(P; caa; max∆ob jectsmax) = Appl(P; caa; max): Now let us take the set of rules fa ! bb; ca ! cdg. Observing that Gen(caa; fa ! bbg)= 2 and ∆ob j(caa; fa ! bbg) = 1, we obtain the following sets of applicable multisets of rules: A p pl(P; caa; maxGENob jectsmax) =
ffa ! bb; a ! bbg; fa ! bb; ca ! cdgg, A p pl(P; caa; max∆ob jectsmax) = ffa ! bb; a ! bbgg.
Finally, let us take the set of rules fa ! l ; ca ! cdg. As Gen(caa; fa ! l g)= 0 and ∆ob j(caa; fa ! l g) = 1, we obtain the following sets of applicable multisets of rules: Ap pl(P; caa; maxGENob jectsmax) =
Ap pl(P; caa; max∆ob jectsmax) = ffa ! l ; ca ! cdgg. Example 2. Consider a simple purely catalytic P system with the initial configuration c1c2aa and the following rules: 1. c1a ! c1 2. c2a ! c2b 3. c2a ! c2bb
1. Gen(c1c2aa; fc1a ! c1g)= 1, 2. Gen(c1c2aa; fc2a ! c2bg)= 2, 3. Gen(c1c2aa; fc2a ! c2bbg)= 3.
In case of the derivation mode maxGENob jectsmax, the multiset of rules fc1a ! c1; c2a ! c2bbg has to be applied. Hence, the only possible derivation with the derivation mode maxGENob jectsmax is c1c2aa fc1a!c1;c2a!c2bbg ! c1c2bb. In this special case,
A p pl(P; c1c2aa; maxGENob jectsmax) = A p pl(P; c1c2aa; maxob jects).
rules, we obtain the same results, i.e., in the derivation mode maxGENob jects, the multiset of rules fc1a ! c1; c2a ! c2bbg has to be applied, and the only possible derivation with the derivation mode maxGENob jects is c1c2aa fc1a!c1;c2a!c2bb!g c1c2bb.
1. ∆ob j(c1c2aa; fc1a ! c1g)= 1, 2. ∆ob j(c1c2aa; fc2a ! c2bg)= 0, 3. ∆ob j(c1c2aa; fc2a ! c2bbg)= 1.
As for the derivation mode max∆ob jectsmax, also for the derivation mode maxGENob jectsmax we obtain that the multiset of rules fc1a ! c1; c2a ! c2bbg has to be applied and that the only possible derivation with the derivation mode max∆ob jectsmax is c1c2aa fc1a!c1;c2a!c2bb!g c1c2bb.
On the other hand, if we do not start from nonextendable multisets of rules, now the rule c1a ! c1 must not be applied because it would decrease the number of objects, i.e., in the derivation mode max∆ob jects we obtain that the – not non-extendable – multiset of rules fc2a ! c2bbg has to be applied, and the only possible derivation with the derivation mode max∆ob jects is c1c2aa fc2a!c2bbg ! c1c2abb.
In this section I recall some classic results for P systems being computationally complete: Theorem 4. Every (computation of a) register machine M can be simulated by a simple P system P. If M is deterministic, then the simulation in P is deterministic, too. Proof. Let M = (m; B; l0; lh; P) be an arbitrary register machine with the first n registers being the decrementable ones and the registers n + 1; : : : ; m being the output registers.
Then we construct an equivalent simple P system P = (V; T; l0; R) as follows (as we do not use catalysts, we omit C in the definition of P):
V T R = The contents of a register r is represented by the corresponding number of copies of the symbol ar.
An ADD-instruction p : (ADD(r); q) is simulated by the rules p ! arq and p ! ars.
A SUB-instruction p : (SU B(r); q; s) is simulated by the following rules: 1. p ! p′ p′′; 2. p′ ! p˜, p′′ar ! p¯
(executed in parallel if register is not empty); 3. p˜ p′′ ! s (if register was empty),
p˜ p¯ ! q (if register was not empty).
The HALT-instruction lh : HALT is simulated by the rule lh ! l .
Theorem 5. (see [
Proof. Let M = (m; B; l0; lh; P) be an arbitrary register machine with the first n registers being the decrementable ones and the registers n + 1; : : : ; m being the output registers. According to Remark 1, the first instruction is assumed to be an ADD-instruction on register 1. Moreover, without loss of generality we may assume that to output registers no SUB-instructions are applied and that at the end of a halting computation all registers which allow for SUB-instructions are empty.
As in the original construction given in [
The following abbreviations for specific multisets (written as strings) are used:
Dn;r D′n;r = =
P j2[1::n]nfrgd j and
P j2[1::n]nfr;r n1gd j: The equivalent simple catalytic P system
P = (V;C; T; l0Dn;1; R) (observe that we start with an ADD-instruction on register 1) now is constructed as follows: fcrdr ! cr j 1 ng [ fc1lh ! c1g fcr p ! crarqDn;Reg(q); cr p ! crarsDn;Reg(s) j p : (ADD(r); q; s) 2 Pg fcrdr ! cr j 1 r ng fcr p ! cr p¯Dn;r; cr p ! cr p′D′n;r; crar ! cra′rD′n;r; cr p¯ ! cr#; cr n1 p′ ! cr n1sDn;Reg(s); cra′r ! crdr n1; cr n1 p¯ ! cr n1 p˜D′n;r; cr p˜ ! crqDn;Reg(q) j p : (SU B(r); q; s) 2 Pg fx ! # j x 2 f#g [ fd j; a′j j 1 j ng [fp; p′; p˜ j p 2 BSUB(r); 1 r ngg: For each catalyst cr we use a “dummy” symbol dr, which keeps the catalyst cr busy whenever needed enforcing cr to use the rule crdr ! cr to keep the simulation alive. When one of the instructions works on a specific register r, then only the catalyst cr and in case of SUB-instructions also catalyst cr k1 is involved, whereas the catalysts corresponding to the other registers j have to be kept busy by the corresponding rule c jd j ! c j. For each SUBinstruction labeled by the “program” symbol p also the variants p′; p˜; p¯ are used.
The HALT-instruction lh : HALT is simulated by the rule c1lh ! c1 (observe that Reg(lh) = 1 is assumed).
Each ADD-instruction j : (ADD(r); k; l) is simulated by the two rules cr p ! crarxDk;Reg(x), x 2 fq; sg.
Each SUB-instruction j : (SU B(r); k; l) is simulated in at most four steps as shown in the table given below: Simulation of the SUB-instruction p : (SU B(r); q; s if register r is not empty register r is empty cr p ! cr p¯Dn;r cr n1dr n1 ! cr n1 crar ! cra′rD′n;r cr n1dr n1 ! cr n1 cra′r ! crdr n1 cr n1 p¯ ! cr n1 p˜D′n;r cr p˜ ! crqDn;Reg(q) cr n1dr n1 ! cr n1 cr p ! cr p′D′n;r cr n1dr n1 ! cr n1 cr remains idle cr n1 p′ ! cr n1sDn;Reg(s)
The trap rules x ! # guarantee that all the symbols x are used in a correct way in the rules listed above for the simulation of the register machine instructions. As soon as the trap symbol # has been introduced, the derivation finally will enter an infinite loop with the rule # ! #. In the case of catalytic P systems, the only non-cooperative rules are these trap rules.
In case the assumption about register r being not empty is wrong, then instead of the rule crar ! cra′rD′n;r the trap rule cr p¯ ! cr# must be used. On the other hand, in case the assumption about register r being empty is wrong, then catalyst cr will not stay idle, but will be used with the rule crar ! cra′rD′n;r instead. Yet then in the third step in sum 2n 1 objects to be handled by only n catalysts will be present in the configuration, which is impossible and therefore will lead to the introduction of the trap symbol #.
In the purely catalytic case, one additional catalyst cd+1 is needed for all the non-cooperative rules given above. These trap rules, and only those, are associated with this catalyst cd+1; for example, the trap rule # ! # now is replaced by the rule cd+1# ! cd+1#.
The construction given in the proof above works for
both catalytic and purely catalytic P systems. An improved
version for catalytic P systems with respect to the number
of rules needed for simulating SUB-instructions was
presented at the Workshop on Membrane Computing 2015
(Satellite Workshop of UCNC 2015 in Auckland), see [
ADD1(P) + 2 where ADD1(P) denotes the number of deterministic ADD-instructions in P, ADD2(P) denotes the number of non-deterministic ADD-instructions in P, and SUB(P) denotes the number of SUB-instructions in P.
Proof. Again a register machine M = (m; B; l0; lh; P) with n m decrementable registers is simulated by a catalytic P system P = (V;C; T; w; R).
For each of the n decrementable registers, we take a catalyst cr and two specific symbols dr; er, 1 r n, for simulating SUB-instructions on these registers. where w0 stands for additional input present at the beginning, for example, for the given input in case of accepting systems.
Usually, every catalyst cr, r 2 [1::n], is kept busy with the symbol dr using the rule crdr ! cr, as otherwise the symbols dr would have to be trapped by the rule dr ! #, and the trap rule # ! # then enforces an infinite nonhalting computation. Only during the simulation of SUBinstructions on register r the corresponding catalyst cr is left free for decrementing or for zero-checking in the second step of the simulation, and in the decrement case both cr and its “coupled” catalyst cr n1 are needed to be free for specific actions in the third step of the simulation.
For the simulation of instructions, we use the following shortcuts:
Dn Dn;r D′n;r = = = Õi2[1::n] di; Õi2[1::n]nfrg di; Õi2[1::n]nfr;r n1g di:
Each ADD-instruction p : (ADD(r); q; s), for r 2 [1::n], is simulated by the rules p ! arqDn and p ! arsDm; in parallel, the rules crdr ! cr, 1 r n, have to be carried out, as otherwise the symbols dr would have to be trapped by the rules dr ! #.
Each SUB-instruction p : (SU B(r); q; s), is simulated as shown in the table listed below (the rules in brackets [ and ] are those to be carried out in case of a wrong choice): Simulation of the SUB-instruction p : (SU B(r); q; s) if register r is not empty register r is empty p ! p¯erDn;r crar ! crdr [crer ! cr#] p¯ ! p˜D′n;r crdr ! cr [dr ! #] p˜ ! qDn cr n1er ! cr n1 p ! p′Dn;r cr should stay idle p′ ! sDn [dr ! #]
In the first step of the simulation of each instruction (ADD-instruction, SUB-instruction, and even HALTinstruction) due to the introduction of Dn in the previous step (we also start with that in the initial configuration) every catalyst cr is kept busy by the corresponding symbol dr, 1 r m. Hence, this also guarantees that the zerocheck on register r works correctly enforcing dr ! # to be applied, as in the case of a wrong choice two symbols dr are present.
The HALT-instruction lh : HALT is simulated by the rule lh ! l ; observe that no objects ar for 1 r n are present any more when lh has appeared.
Remark 2. Exactly the same construction as elaborated above can be used when allowing for n + 2 catalysts, with catalyst cn+1 being used with the state symbols and catalyst cn+2 being used with the trap rules. If only one additional catalyst cn+1 is allowed to be used with all the non-cooperative rules, a slightly more complicated simulation of SUB-instructions is needed, see [41], where for catalytic P systems and for purely for catalytic P systems jRj jRj 2 6 2 6
ADD1(P) + 3 SUB(P) + 5
Remark 3. In case of deterministic register machines,
especially in the accepting case, every sequence of
consecutive ADD-instructions is bounded by a constant only
depending on the given register machine. Hence, in this case
the calculations for jRj in Theorem 6 and in Remark 2 can
omit the ADD-instructions, because any fixed sequence of
consecutive ADD-instructions can be included directly in
the last simulation step of the preceding SUB-instruction,
see the concept of generalized register machines as used
in [
Remark 4. The use of the trap symbol # to enforce the computation never to stop is a typical element of many proofs to be found in the literature. Only very few variants of P systems are known so far which allow for a deterministic simulation of the SUB-instruction and in that way for a deterministic simulation of a deterministic register machine like the unrestricted variant considered in
4
In [
Proof. We use the trick as elaborated in Remark 1 for getting a specific variant of register machines: without loss of generality, we start with an ADD-instruction on register 1, but we also change the register machine program in such a way that after a SUB-instruction on register n two intermediate instructions are introduced, i.e., as in Remark 1, we use an ADD-instruction on register 1 immediately followed by a SUB-instruction on register 1.
We then may simulate the resulting register machine fulfilling these additional constraints M = (m; B; l0; lh; P) by a corresponding catalytic P system with one membrane and one catalyst P = (V; fcg; T; (l0; 1); R). Without loss of generality, we may assume that, depending on its use as an accepting or generating or computing device, the register machine M, as stated in Proposition 1, Proposition 2, and Proposition 3, fulfills the condition that on the output registers we never apply any SUB-instruction. Moreover, we take the most general case of a register machine computing a partial recursive function on vectors of natural numbers with l components as input and vectors of natural numbers with k components as output using n decrementable registers, where without loss of generality, we may assume that at the end of a successful computation the first n registers are empty, and, moreover, on the output registers, i.e., the last k registers, no SUB-instruction is ever used.
The main idea behind the construction is that all the symbols except the catalyst c and the output symbols (representing the contents of the output registers) go through a cycle of length n + 1 where n is the number of decrementable registers of the simulated register machine. When the symbols are traversing the r-th section of the first n sections, they “know” that they are to probably simulate a SUB-instruction on register r of the register machine M.
V T =
The alphabet V of symbols includes register symbols (ar; i) for every decrementable register r of the register machine and only the register symbol ar for each of the k output registers r, m k + 1 r m.
The construction includes the trap rule # ! # which will always keep the system busy and prevent it from halting and thus from producing a result as soon as the trap symbol # has been introduced, yet the only rule introducing this trap symbol is the single rule e ! #.
For letting the register symbols cycle with a period of n + 1 the following rules are used: (ar; i) ! (ar; i + 1); 1 (ar; n + 1) ! (ar; 1): r n;
For simulating ADD-instructions we need the following rules: c(p; i) ! c(p; i + 1); 1 i < r (p; r) ! (p; r + 1); c(ar; r) ! ce: (1) (2) (3) (4) (5) trap symbol # and therefore is the only reasonable continuation of the computation if register r is empty. 1. the catalyst c correctly erases e, and to the program symbol (p; r + 1) the rule (p; r + 1) ! (p; r + 2) must be applied due to the derivation mode maxobjects; all register symbols evolve in the usual way; 2. the catalyst c takes the program symbol (p; r + 1) using the rule c(p; r + 1) ! c(p; r + 2)0, thus forcing the object e to be trapped by the rule e ! #, and all register symbols evolve in the usual way; 3. the catalyst c takes a register object (ar+1; r + 1), thus leaving the object e to be trapped by the rule e ! #, the program symbol (p; r + 1) evolves with the rule (p; r + 1) ! (p; r + 2) , and all other register objects evolve in the usual way.
In fact, only variant 1 now fulfills the condition given by the derivation mode maxob jects and therefore is the only possible continuation of the computation if register r is not empty.
On the other hand, if register r is empty, no object e is generated, and the catalyst c has only two choices: 1. the catalyst c takes the program symbol (p; r + 1) using the rule c(p; r + 1) ! c(p; r + 2)0, and all register symbols evolve in the usual way; 2. the catalyst c takes a register object (ar+1; r + 1) thereby generating e, the program symbol (p; r + 1) evolves with the rule (p; r + 1) ! (p; r + 2) , and all other register objects evolve in the usual way; this variant leads to the situation that e will be trapped in step r + 2, as otherwise the program symbol stays idle, thus violating the condition of the derivation mode maxob jects. Hence, this variant in any case cannot lead to a halting computation due to the introduction of the trap symbol #. We mention that in case no register object (ar+1; r + 1) is present we have to apply case 1 and thus have a correct computation step.
Both variants fulfill the condition for the derivation mode maxob jects, but only variant 1 is not introducing the (7) (8)
We observe that in this case during the first step of the next cycle we have to guarantee that in the zero-test case the catalyst must be used with the program symbol, hence, we will simulate an ADD-instruction on register 1, as the introduction of the symbol e in the wrong variant of the zero-test case must lead to introducing the trap symbol and not allowing e to be erased by the catalytic rule ce ! c.
The HALT-instruction lh : HALT is simulated by the rule clh ! c.
As the number of decrementable registers in generating register machines needed for generating any recursively enumerable set of (vectors of) natural numbers is only two, the following result is an immediate consequence of the preceding theorem: Corollary 1. For any generating register machine with two decrementable registers we can construct a catalytic
tion mode maxob jects which can simulate every step of the register machine in 3 steps, and therefore such catalytic P systems with only one catalyst and working in the derivation mode maxob jects can generate any recursively enumerable set of (vectors of) natural numbers.
The following results even yield deterministic simulations of SUB-instructions of a register machine and thus can even avoid trapping.
Theorem 8. (see [
Proof. Given an arbitrary register machine M = (m; B; l0; lh; P) we will construct a corresponding catalytic P system with one membrane and one catalyst P = (V; fcg; T; w; R) simulating M. Without loss of generality, we may assume that, depending on its use as an accepting or generating or computing device, the register machine M, as stated in Proposition 1, Proposition 2, and Proposition 3, fulfills the condition that on the output registers we never apply any SUB-instruction.
The following proof is given for the most general case of a register machine computing any partial recursive relation on vectors of natural numbers with l components as input and vectors of natural numbers with k components as output using precisely l + 2 + k registers, where without loss of generality, we may assume that at the end of a successful computation the first l + 2 registers are empty, and, moreover, on the output registers, i.e., the last k registers, no SUB-instruction is ever used. In fact, the proof works for any number n 2 of decrementable registers, no matter how many of them are the l input registers and the working registers, respectively.
The main idea behind the construction is that all the symbols except the catalyst c and the output symbols (representing the contents of the output registers) go through a cycle of length n where n is the number of decrementable registers of the simulated register machine. When the symbols are traversing the r-th section of the n sections, they “know” that they are to probably simulate a SUBinstruction on register r of the register machine M.
As in this construction the simulation of a SUBinstruction takes two steps, the second simulation step in the case of a SUB-instruction on register n is shifted to the first step of the next cycle. Yet in this case we have to guarantee that after a SUB-instruction on register n the next instruction to be simulated is not a SUB-instruction on register 1. Hence, we use a similar trick as already used in the proof of Theorem 7, i.e., we not only do not start with a SUB-instruction, but we also change the register machine program in such a way that after a SUB-instruction on register n two intermediate instructions are introduced, we use an ADD-instruction on register 1 immediately followed by a SUB-instruction on register 1, whose simulation will end at most in step n, as we have assumed n 2.
The following construction is elaborated in such a way that it works both for the derivation mode max∆ob jectsmax and the derivation mode maxGENob jectsmax.
We now simulate the resulting register machine fulfilling these additional constraints M = (m; B; l0; lh; P) by a corresponding simple P system with one catalyst: P = (V; fcg; T; c(l0; 1); R): The construction includes the dummy symbol d which is erased by the rule d ! l . The effect of applying these rules due to the requirement of the chosen multisets of rules to be non-extendable will be ignored in the following calculations for ∆ob j(C; R) and Gen(C; R).
The symbols ar, n + 1 r m, represent the output registers. For the decrementable registers, we use the symbols (ar; i), 1 r n; 1 i n, which go through a loop of n steps. The main idea now is that the only case when such a symbol can be used to decrement register r is when i = r, i.e., in the r-th step of the simulation cycle.
(ar; i) ! (ar; i + 1); 1 r < n; (ar; n) ! (ar; 1): (9)
In the same way as the register symbols ar, the program symbols ( p; i) representing the label p from B undergo the same cycle of length n.
For simulating ADD-instructions we need the following rules:
The catalyst has to be used with the program symbol which otherwise would stay idle when the catalyst is used with a register symbol, and the difference of objects ∆ob j(C; R′) for this other non-extendable multiset of rules R′ would be 0 whereas when using the program symbol for the catalyst, we obtain ∆ob j(C; R)= 1 because of the additional dummy symbol d.
In a similar way we can argue that in the case of the derivation mode maxGENob jectsmax the number of generated objects is maximal when using the catalyst together with the program symbol; in fact, if N is the total number of register symbols for decrementable registers in the underlying configuration C, then with applying the set of rules R described so far we get Gen(C; R)= N + 3 in contrast to Gen(C; R′)= N 1 + 3 = N + 2 where using the catalyst with the rule c(ar; r) ! ced, as described below for the simulation of the SUB-Instruction, results in the multiset of rules R′.
If r is a decrementable register, we end the simulation using one of the following rules: c( p; n) ! c(q; 1)(ar; 1); c( p; n) ! c(s; 1)(ar; 1): (11)
If r is an output register, we end the simulation using one of the following rules introducing output symbols not to be changed any more: c(p; n) ! c(q; 1)ar; c(p; n) ! c(s; 1)ar: (12)
As in both cases, together with the program symbol a new register symbol is generated, we again have ∆ob j(C; R) = 1, thus guaranteeing that the catalyst must take (p; n) and cannot take (an; n) instead.
A similar argument again holds in the case of the derivation mode maxGENob jectsmax as the number of generated objects is only maximal when using the catalyst together with the program symbol; again we have Gen(C; R)= N + 3 with this multiset of rules R in contrast to Gen(C; R′)= N 1 + 3 = N + 2 when using the catalyst with the rule c(ar; r) ! ced results in the multiset of rules R′.
In case that register r is empty, i.e., there is no object (ar; r), then the catalyst will stay idle as in this step there is no other object with which it could react. In case that register r is not empty, i.e., there is at least one object (ar; r), then one of these objects (ar; r) must be used with the catalyst c as the rule c(ar; r) ! ced implies ∆ob j(C; R)= 1, whereas otherwise, if all register symbols are used with the rule (ar; r) ! (ar; r + 1), then ∆ob j(C; R)= 0.
In the same way we argue that with using the rule c(ar; r) ! ced we get one object generated more than if we use the rule (ar; r) ! (ar; r + 1) for that symbol (ar; r), i.e., Gen(C; R)= N 1 + 3 = N + 2 in contrast to Gen(C; R′)= N. (13) (14) If r < n
1: ce ! cdddd; (p; r + 1) ! (p; r + 2) ; c(p; r + 1) ! c(p; r + 2)0dd: (15)
If in the first step of the simulation phase the catalyst did manage to decrement the register, it produced e. Thus, in the second simulation step, the catalyst has three choices: 1. the catalyst c correctly “erases" e using the rule ce ! cdddd, and to the program symbol (p; r + 1) the rule (p; r + 1) ! (p; r + 2) must be applied due to the fact that both derivation modes max∆ob jectsmax and maxGENob jectsmax only allow for non-extendable multisets of rules; all register symbols evolve in the usual way; in total we get ∆ob j(C; R)= 3 and Gen(C; R)= N + 6; (16) (17) (18) 2. the catalyst c takes the program symbol (p; r + 1) using the rule c(p; r + 1) ! c(p; r + 2)0dd, and all register symbols evolve in the usual way; in total we get ∆ob j(C; R)= 2 and Gen(C; R)= N + 4; 3. the catalyst c takes a register object, the program symbol (p; r + 1) evolves with the rule (p; r + 1) ! (p; r + 2) , and all other register objects evolve in the usual way; in total we get ∆ob j(C; R)= 1 and Gen(C; R)= (N 1 + 3) + 1 = N + 3.
In total, only variant 1 fulfills the condition given by the derivation mode max∆ob jectsmax that ∆ob j(C; R) is maximal, and therefore is the only possible continuation of the computation if register r is not empty.
A similar argument holds for the derivation mode maxGenob jectsmax with respect to the number of generated objects ∆ob j(C; R).
On the other hand, if register r is empty, no object e is generated, and the catalyst c has only two choices: 1. the catalyst c takes the program symbol (p; r + 1) using the rule c(p; r + 1) ! c(p; r + 2)0dd, and all register symbols evolve in the usual way; in total we get ∆ob j(C; R)= 2 and Gen(C; R)= N + 4; 2. the catalyst c takes a register object (ar+1; r + 1) thereby generating ed, the program symbol (p; r + 1) evolves with the rule (p; r + 1) ! (p; r + 2) , and all other register objects evolve in the usual way; this variant leads to ∆ob j(C; R)= 1 and Gen(C; R)= (N 1 + 3) + 1 = N + 3.
In total, variant 1 is the only possible continuation of the computation if register r is empty.
c(p; i) c(p; n) ! c(p; i + 1) d; r + 2 ! c(q; 1)d; c(p; i)0 ! c(p; i + 1)0d; r + 2 c(p; n)0 ! c(s; 1)d: i < n; i < n;
Again the catalyst has to be used with the program symbol to get ∆ob j(C; R)= 1 and Gen(C; R)= N + 3, which otherwise would stay idle when the catalyst is used with a register symbol, and the multiset of rules applied in this way would only yield ∆ob j(C; R)= 0 and Gen(C; R′)= N 1 + 3 = N + 2.
If r = n 1: ce ! cdddd; (p; n) ! (q; 1); c(p; n) ! c(s; 1)dd:
In this case, we directly go to the first step of the next cycle. c(p; n + 1) ! c(s; 2)dd:
In this case, the second step of the simulation is already the first step of the next cycle, which means that in this case of r = n the next instruction to be simulated is an ADD-instruction on register 1.
To complete the proof we have to implement the final HALT -instruction lh : HALT with the rule c(lh; 1) ! cdd. In this way, finally no program symbol is present any more in the configuration. As we have assumed all decrementable registers to be empty when the register machine halts, this means the constructed simple P system will also halt after having erased the dummy symbols d in the next step.
We finally observe that the proof construction given above is even deterministic if the underlying register machine to be simulated is deterministic.
In a similar way, the same result can even be shown for the derivation modes max∆ob jects and maxGENob jects, where the condition of non-extendability for the multisets of rules to be applied is not required.
Theorem 9. For any register machine with at least two decrementable registers we can construct a simple catalytic P system with only one catalyst, working in the derivation mode max∆ob jects or in the derivation mode maxGENob jects, which can simulate every step of the register machine in n steps where n is the number of decrementable registers.
As the number of decrementable registers in generating register machines needed for generating any recursively enumerable set of (vectors of) natural numbers is only two, from the theorems above we obtain the following result: Corollary 2. For any generating register machine with two decrementable registers we can construct a simple P system with only one catalyst and working in the derivation mode max∆ob jectsmax, maxGENob jectsmax, max∆ob jects, or maxGENob jects which can simulate every step of the register machine in 2 steps, and therefore such catalytic
the derivation mode max∆ob jectsmax, maxGENob jectsmax, max∆ob jects, or maxGENob jectsmax can generate any recursively enumerable set of (vectors of) natural numbers.
The even more important achievement than the rather expected computational completeness established with (the proof of) Theorem 8 and Theorem 9 is the fact that with the derivation modes max∆ob jectsmax, maxGENob jectsmax, max∆ob jects, and maxGENob jects only one catalyst is needed to obtain computational completeness, which is the optimal result with respect to the number of catalysts, because with non-cooperative rules, only semilinear sets can be generated. Moreover, the simulation of a deterministic register machine is deterministic in the P system, too.
The technique used for catalytic P systems in the proof of Theorem 8 cannot be taken over to purely catalytic P systems, where the number of rules to be used in every step is bounded by the number of catalysts. Hence, a similar technique as already known from the proof of the classic result given in Theorem 4 is used for proving Theorem 10, yet still the result to be obtained with the derivation modes max∆ob jectsmax, maxGENob jectsmax, max∆ob jects, and maxGENob jects is better than that one known for the derivation mode max, because one catalyst less is needed.
Theorem 10. For any register machine with n 2 decrementable registers we can construct a simple purely catalytic P system with only n catalysts, working in one of the derivation modes max∆ob jectsmax, maxGENob jectsmax, max∆ob jects, or maxGENob jects, which can simulate any computation of the register machine.
Proof. Given an arbitrary register machine M = (m; B; l0; lh; P) with n decrementable registers we will construct a corresponding simple purely catalytic P system with n catalysts
P = (V; fck j 1 k ng; T; w; R) simulating M. Without loss of generality, we may assume that, depending on its use as an accepting or generating or computing device, the register machine M, as stated in Proposition 1, Proposition 2, and Proposition 3, fulfills the condition that on the output registers we never apply any SUB-instruction. Moreover, according to Remark 1 we may assume that the first instruction is an ADDinstruction on the first register. Finally, we assume the n decrementable registers to be the first ones.
The following proof again is elaborated for all the derivation modes max∆ob jectsmax, maxGENob jectsmax, max∆ob jects, and maxGENob jects, with only a few subtle technical details to be mentioned additionally.
The main part of the proof is to show how to simulate the instructions of M in P; in all cases we have to take care that the n catalysts are kept busy – using corresponding dummy objects dr – in order to guarantee that the simulation is executed in a correct way; especially we have to guarantee that one of the rules using the catalysts ck; 1 k n; must be used if possible, i.e., a catalyst can only stay idle if the underlying configuration does not contain any object which can evolve together with the catalyst. Again the priority between different rules for a catalyst is guarded by the number of objects on the right-hand side of the rules, which argument applies for all the derivation modes under consideration, as every rule in a purely catalytic P system has exactly two objects on its left-hand side.
During the simulation of all instructions, we use the following multisets:
D′n;r = Õi2[1::n]nfr;r n1g di; 1 decrement case If the value of register r (denoted by jreg(r)j) is not zero then the number of register objects ar is decreased by one using the corresponding rule crar ! craˆrd2 in the first step of the simulation. In sum three steps are needed for the simulation, see table below. zero-test case.
If the value of register r is zero, then the corresponding catalyst is already free for eliminating the label object p so that already in the second step of the simulation the simulation of the next instruction s can be initiated. In sum only two steps are needed for the simulation of this case, see table below.
The following table summarizes the rules to be used for the simulation of the SUB-instruction on register r, 1 r n, i.e., we use the following rules; we emphasize that again the simulation is deterministic. step 1 jreg(r)j rule for cr and cr n1 > 0 crar ! craˆrd2
As the first instruction to be simulated is an ADDinstruction on the first register, we start with the initial multiset w = l0l0′D′n;1
As usual, the number of objects ar in a configuration represents the number stored in register r at that moment of the computation. Objects ar for r > n are never changed again, as they represent output registers.
V T =
The dummy objects di, 1 i n, are used to keep the corresponding catalyst ci busy whenever it is not needed during the simulation of a SUB-instruction, which is accomplished by the following rule erasing di, but instead introducing the necessary amount of objects d to keep the catalyst ci away from erasing a register object ar: Moreover, for erasing d we use the rules cidi ! cid4; 1 k
n: ckd ! ck; 1 k n: In the derivation mode max∆ob jects these erasing rules can only be used at the end of a computation when no other rules can be applied any more.
The remaining rules in the set R of catalytic rules can be captured from the description of how the simulation of the register machine instructions works as described in the following: p : (ADD (r) ; q; s), with p 2 BADD, q; s 2 B, 1 r
An ADD-instruction can be simulated in one step by letting every catalyst make one evolution step: cReg(p) p ! cReg(p)qq′ardD′n;Reg(q) or cReg(p) p ! cReg(p)ss′ardD′n;Reg(s); cReg(p) n1 p′ ! c2d4: We recall that all other catalysts ci with i 2 [1::n] n fReg(p); Reg(p) n 1g are forced to apply the rule cidi ! cid4. The dummy objects d are used to guarantee that the rules given above, with in sum at least 5 objects on their right-hand sides, have priority over the rules crar ! craˆrd2, 1 r n, with in sum only 4 objects on their right-hand sides.
The the rule crd ! cr marked with ( ) is only applied in the derivation modes max∆ob jectsmax and maxGENob jectsmax as well as maxGENob jects, whereas in the derivation mode max∆ob jects it will not be applied as it would decrease the difference between generated and consumed objects. lh : HALT .
Taking into account that we have defined Reg(lh) = 1, we take: c1lh ! c1dd c2lh′ ! c2dd
After the register machine has halted (with the first n registers being empty), which is simulated by the rules 2 3 above, finally all dummy objects generated during the simulation steps before are deleted by using the rules cid ! ci; 1 i n:
Whereas in the derivation modes max∆ob jectsmax and maxGENob jectsmax as well as maxGENob jects some of these objects d can already be erased during the simulation of SUB-instructions, see above, in the derivation mode max∆ob jects, these erasing rules are only executed at the end of the computation. These observations complete the proof.
As a consequence, we obtain the following result: Corollary 3. Purely catalytic P systems working in any of the derivation modes max∆ob jectsmax, maxGENob jectsmax, max∆ob jects, or maxGENob jects are computationally complete, i.e., they can compute any partial recursive relation on natural numbers.
Yet besides this computational completeness result, the even more relevant achievement of the result established with Theorem 10 is the fact that, when we compare with the results given in (the proof of) Theorem 5, with all these new derivation modes, i.e., max∆ob jectsmax, maxGENob jectsmax, max∆ob jects, and maxGENob jects, only one catalyst for each decrementable register is needed, which is an improvement of needing one catalyst less than with the derivation mode max, and moreover the simulation is deterministic, hence, no trapping is needed. 6
In this overview paper I have collected several classic as well as many new results established just recently for simple P systems working in variants of the maximally parallel derivation mode allowing for computational completeness. In case of the parallel derivation modes (i) affecting or (ii) generating the maximal number of objects or (iii) yielding the maximal difference between the objects in the current and the derived configuration, in simple catalytic P systems only one catalyst is needed to obtain computational completeness, which is the optimal result with respect to the number of catalysts, because with noncooperative rules only semi-linear sets can be obtained. In case of simple purely catalytic P systems at least one catalyst less is needed than in the classic proofs showing computational completeness.
I am very grateful to Gheorghe Pa˘un for involving me from the beginning in this new area of membrane systems. Moreover, many results as presented above have been developed together with my other co-authors, especially with my colleague Marion Oswald at the TU Wien and the “Moldovan team” Artiom Alhazov, Sergiu Ivanov, and Sergey Verlan. [35] Krithivasan, K., Pa˘un, Gh., Ramanujan, A.: On controlled P systems. Fundam. Inform. 131(3–4), 451–464 (2014). https://doi.org/10.3233/FI-2014-1025 [36] Minsky, M.L.: Computation. Finite and Infinite Machines.
Prentice Hall, Englewood Cliffs, NJ (1967) [37] Pa˘un, Gh.: Computing with membranes. Journal of Computer and System Sciences 61(1), 108–143 (2000). https://doi.org/10.1006/jcss.1999.1693 [38] Pa˘un, Gh.: Membrane Computing: An Introduction.
Springer (2002). https://doi.org/10.1007/978-3-642-561962 [39] Pa˘un, Gh., Rozenberg, G., Salomaa, A. (eds.): The Oxford Handbook of Membrane Computing. Oxford University Press (2010) [40] Rozenberg, G., Salomaa, A. (eds.): Handbook of Formal Languages. Springer (1997). https://doi.org/10.1007/9783-642-59136-5 [41] Sosík, P., Langer, M.: Small (purely) catalytic P systems simulating register machines. Theoretical Computer Science 623, 65–74 (2016). https://doi.org/10.1016/j.tcs.2015.09.020 [42] The P Systems Website. http://ppage.psystems.eu/