A Short Note on Reversibility in P Systems

A Short Note on Reversibility in P Systems Artiom Alhazov1,2, Kenichi Morita1 1IEC, Department of Information Engineering, Graduate School of Engineering Hiroshima University, Higashi-Hiroshima 739-8527 Japan [email protected] 2Institute of Mathematics and Computer Science Academy of Sciences of Moldova, Academiei 5, Chi¸sin˘au MD-2028 Moldova [email protected] Summary. Membrane computing is a formal framework of distributed parallel computing. In this paper we study the reversibility and maximal parallelism of P systems from the computability point of view. The notions of reversible and strongly reversible systems are considered. The universality is shown for one class and a negative conjecture is stated for a more restricted class of reversible P systems. For one class of strongly reversible P systems, a very strong limitation is found, and it is shown that this limitation does not hold for a less restricted class. 1 Introduction Reversibility is an important property of computational systems. It has been well studied for circuits of logical elements ([3]), circuits of memory elements ([7]), cellular automata ([8]), Turing machines ([1], [10]), register machines ([6]). Reversibility as a syntactical property is closely related to the microscopic reversibility, so it implies that the computation does not increase the entropy of the system, which in turn assume better miniaturization possibilities for potential implementation. A slightly different view on reversible systems is given for type-0 grammars ([9]). The so-called uniquely parsable grammars are studied. In very simple words, this property (still being syntactical) implies that the generation of any word in the language is unique (modulo the order of applying the rules in case when the composition of applying them is commutative). The advantage of having such a property is that it is easier to analyze their behavior. Clearly, this reason remains valid even if the property of reversibility becomes undecidable (just like the property of determinism in certain membrane systems). Moreover, reversibility essentially is backward determinism. Reversible P systems already were considered ([4]), but the model is energy-based (so the parallelism is invariant-driven rather than maximal) and the main result is the simulation of the Fredkin gate (so construction of a universal system in this way would use an 24 A. Alhazov, K. Morita infinite structure). In this paper we focus on the interplay between reversibility and maximal parallelism, from the viewpoint of computability. 2 Definitions In this paper we illustrate the reversibility concepts on P systems with symport/antiport and one membrane, sometimes with inhibitors or priorities. For simplicity, we also assume that the environment contains an unbounded supply of all objects. The system thus can be defined by the alphabet, the initial multiset, the set of rules associated to the membrane, and the set of terminal objects. Throughout this paper we represent multisets by strings. We write an antiport rule sending a multiset xout and bringing a multiset yin as x/y, and the symport case corresponds to y=λ. If a rule has inhibitor a, we write it as x/y|¬a. The priority relationship is denoted by >. It is not difficult to generalize the definitions for the models with multiple membranes and changing membrane structure, but it is not important here. Consider a P system Πwith alphabet O. In our setting, a configuration is defined by the multiset of objects inside the membrane, represented by some string u∈O∗. The space Cof configurations is essentially |O|-dimensional space with non-negative integer coordinates. We use the usual definitions of maximally parallel transition ([11]). It induces an infinite graph of C. Notice that the halting configurations (and only them) have out-degree zero. We call Πstrongly reversible if every configuration has in-degree at most one. We call Πreversible if every reachable configuration has in-degree at most one. A property equivalent to reversibility is determinism of a dual P system ([2]). The result of a halting computation is the number of terminal objects inside the membrane when the system halts. The set N(Π) of numbers generated by a P system Πis the set of results of all its computations. The family of number sets generated by reversible P systems with features αis denoted by NrOP1(α)T, where α⊆ {sym∗, anti∗, inh, Pri}and the braces of the set notation are omitted. Subscript Tmeans that only terminal objects contribute to the result of computations; if T=O, we may omit specifying it in the description and we then also omit the subscript Tin the notation. To bound the weight (i.e., maximal number of objects sent in a direction) of symport or antiport rule, associated ∗is replaced by the actual number. For strong reversible systems, we replace in the notation r by rs. 2.1 Register machines In this paper we consider register machines with increment, unconditional decrement and test instructions, see also [6]. A register machine is a tuple M= (n, Q, q0, qf, I) where A Short Note on Reversibility in P Systems 25 •nis the number of registers; •Iis a set of instructions labeled by elements of Q; •q0∈Qis the initial label; •qf∈Qis the final label. The allowed instructions are: •(q:i?, q0, q00 ) - jump to instruction q00 if the contents of register iis zero, otherwise proceed to instruction q0; •(q:i+, q0, q00 ) - add one to the contents of register iand proceed to either instruction q0or q00, non-deterministically; •(q:i−, q0, q00 ) - subtract one from the contents of register iand proceed to either instruction q0or q00, non-deterministically; •(qf:halt) - finish the computation; it is a unique instruction with label qf. If q0=q00 for every instruction (q:i+, q0, q00 ) and for every instruction (q: i−, q0, q00 ), then the machine is called deterministic. A register machine is called reversible if for some state qthere is more than one instruction leading to it, then exactly two exist, they test the same register, one leads to qif the register is zero and the other one leads to qif the register is positive. More formally, for any two different instructions (q1:i1α1, q0 1, q00 1) and (q2:i2α2, q0 2, q00 2), it holds that q0 16=q0 2and q00 16=q00 2. Moreover, if q0 1=q00 2or q00 1=q0 2, then α1=α2=? and i1=i2. It has been shown ([6]) that reversible register machines are universal. It follows that non-deterministic reversible register machines can generate any recursively enumerable set of non-negative integers as a value of the first register by all its possible computations starting from all registers having zero value. 3 Examples and Universality We now present a few examples to illustrate the definitions. Example 0: Consider a P system Π0= ({a, b}, a, {a/ab}). It is strongly reversible (for a preimage, remove as many copies of bas there are copies of a, in case it is possible and there is at least one copy of a), but no halting configuration is reachable. Therefore, ∅ ∈ NrsOP1(anti∗). Example 1: Consider a P system Π1= ({a, b, c}, a, {a/ab, a/c}). It generates the set of positive integers and it is reversible (for the preimage, replace cwith aor ab with b), but not strongly reversible (e.g., aa ⇒cc and ac ⇒cc). Hence, N+∈NrOP(anti2). Example 2: Consider a P system Π2= ({a, b}, aa, {aa/ab, ab/bbb}). It is reversible (aa has in-degree 0, while ab and bbb have in-degree 1, and no other configuration is reachable), but not strongly reversible (e.g., aab ⇒abbb and aabb ⇒abbb). 26 A. Alhazov, K. Morita Example 3: Any P system with a rule x/λ,x∈O+, is not reversible. Therefore, symport rules cannot be actually used in a reversible P systems with one membrane. Example 4: Any P system with rules x1/y,x2/y that applied at least one of them in some computation is not reversible. We now show that reversible P systems with either inhibitors or priorities are universal. Theorem 1. NrOP1(anti2, Pri)T=NrOP1(anti2, inh)T=NRE. Proof. We reduce the theorem statement to the claim that such P systems simulate the work of any reversible register machine M= (n, Q, q0, qf, I). Consider a P system Π= (O, q0, R, {r1}),where O={ri|1≤i≤n} ∪ Q, R={q/q0ri, q/q00ri|(q:i+, q0, q00)∈I} ∪ {qri/q0, qri/q00 |(q:i−, q0, q00)∈I} ∪ Rt, Rt={q/q00 |¬ri, qri/q0ri|(q:i?, q0, q00)∈I}. Inhibitors can be replaced by priorities by redefining Rtas follows. Rt={qri/q0ri> q/q00 |(q:i?, q0, q00)∈I}. Since there is a bijection between the configurations of Πcontaining one symbol from Qand the configurations of M, the reversibility of Πfollows from the correctness of simulation, the reversibility of M, and from the fact that the number of symbols from Qis preserved by transitions of Π. 4 Limitations The construction in the theorem above uses both cooperation and additional control. It is natural to ask whether both inhibitors and priorities can be avoided. Yet, consider the following situation. Let (p:i?, s, q00),(q:i?, q0, s)∈I. It is usual for reversible register machines to have this, since the preimage of configuration sC depends on register i. Nevertheless, P systems with maximal parallelism without additional control can only implement a zero-test by try-and-wait-then-check strategy. In this case, the object containing the information about the register p finds out the result of checking after a possible action of the object related to the register. Therefore, when the state represented in the configuration of the system changes to s, it obtains an erroneous preimage representing state q. This leads to the following Conjecture 1. Reversible P systems without priorities and without inhibitors are not universal. A Short Note on Reversibility in P Systems 27 Now consider a strongly reversible P system. The following theorem establishes a very serious limitation on such systems if no additional control is used. Theorem 2. In strongly reversible P systems without inhibitors and without priorities, every configuration is either halting or induces only infinite computation(s). Proof. If the right-hand side of every rule contains a left-hand side of some rule, then the claim holds. Otherwise, let x/y be a rule of the system such that ydoes not contain the left-hand side of any rule. Then x⇒yand yis a halting configuration. It is not difficult to see that xy ⇒yy (objects yare idle) and xx ⇒yy (the rule can be applied twice). Therefore, such a system is not strongly reversible, which proves the theorem. Therefore, the strongly universal systems without additional control can only generate singletons, i.e., NrsOP1(anti∗)T={{n} | n∈N}, and only in a degenerate way, i.e., without actually computing. It turns out that the theorem above does not hold if inhibitors are used. Consider a system Π3= ({a, b}, a, {a/b|¬b}). If at least one object bis present or no objects aare present, such a configuration is a halting one. Otherwise, all objects aare exchanged by objects b. Therefore, the only possible transitions in the space of all configurations are of the form an⇒bn,n > 1, and the system is strongly reversible. 5 Discussion We outlined the concepts of reversibility and strong reversibility for P systems, concentrating on the case of symport/antiport rules (possibly with control such as priorities or inhibitors) with one membrane, assuming that the environment contains an unbounded supply of all objects. We showed that reversible P systems with control are universal, and we conjectured that this result does not hold without control. Moreover, the strongly reversible P systems without control do not halt unless the starting configuration is halting, but this is no longer true if inhibitors are used. Showing related characterizations might be quite interesting. Many other problems are still open, e.g., reversibility of P systems with active membranes. Acknowledgments Artiom Alhazov gratefully acknowledges the support of the Japan Society for the Promotion of Science and the Grant-in-Aid for Scientific Research, project 20·08364. He also acknowledges the support by the Science and Technology Center in Ukraine, project 4032. 28 A. Alhazov, K. Morita References 1. C.H. Bennett: Logical reversibility of computation. IBM J. Res. Dev., 17 (1973), 525-532. 2. O. Agrigoroaiei, G. Ciobanu: Dual P systems. Membrane Computing - 9th International Workshop, LNCS 5391, 2009, 95–107. 3. E. Fredkin, T. Toffoli: Conservative logic. Int. J. Theoret. Phys., 21 (1982), 219-253. 4. A. Leporati, C. Zandron, G. Mauri: Reversible P systems to simulate Fredkin circuits. Fundam. Inform., 74, 4 (2006), 529–548. 5. M.L. Minsky: Computation: Finite and Infinite Machines. Prentice-Hall, Englewood Cliffs, NJ, 1967. 6. K. Morita: Universality of a reversible two-counter machine. Theoret. Comput. Sci., 168 (1996), 303-320. 7. K. Morita: A simple reversible logic element and cellular automata for reversible computing. Proc. 3rd Int. Conf. on Machines, Computations, and Universality, LNCS 2055, 2001, 102-113. 8. K. Morita: Simple universal one-dimensional reversible cellular automata. J. Cellular Automata, 2 (2007), 159-165. 9. K. Morita, N. Nishihara, Y. Yamamoto, Zh. Zhang: A hierarchy of uniquely parsable grammar classes and deterministic acceptors. Acta Inf., 34, 5 (1997), 389–410. 10. K. Morita, Y. Yamaguchi: A universal reversible Turing machine. Proc. 5th Int. Conf. on Machines, Computations, and Universality, LNCS 4664, 2007, 90-98. 11. Gh. P˘aun: Membrane Computing. An Introduction. Springer, Berlin, 2002. 12. P systems website: http://ppage.psystems.eu/.