Thirteen Brainstorming Week on Membrane Computing Sevilla, February 2-6, 2015 : RGNC Report 1/2015

13th Brainstorming Week on Membrane Computing Sevilla, February 2 – 6, 2015 Luis F. Mac´ıas-Ramos Gheorghe P˘aun Agust´ın Riscos-N´u˜nez Luis Valencia-Cabrera Editors 13th Brainstorming Week on Membrane Computing Sevilla, February 2 – 6, 2015 Luis F. Mac´ıas-Ramos Gheorghe P˘aun Agust´ın Riscos-N´u˜nez Luis Valencia-Cabrera Editors RGNC REPORT 1/2015 Research Group on Natural Computing Universidad de Sevilla F´enix Editora, Sevilla, 2015 © Autores ISBN: 978-84-84-944366-2-8 Edita: Fénix Editora. [email protected] Movil 620 98 36 94 - SEVILLA Contents Deterministic Non-cooperative P Systems with Strong Context Conditions A. Alhazov, R. Freund ................................................... 1 Polarizationless P Systems with One Active Membrane A. Alhazov, R. Freund ................................................... 9 Variants of P Systems with Toxic Objects A. Alhazov, R. Freund, S. Ivanov ....................................... 19 Extended Spiking Neural P Systems with White Hole Rules A. Alhazov, R. Freund, S. Ivanov, M. Oswald, S. Verlan ................ 45 Simulating Membrane Systems and Dissolution in a Typed Chemical Calculus B. Aman, P. Batty´anyi, G. Ciobanu, G. Vaszil .......................... 63 Notes on Spiking Neural P Systems and Finite Automata F.G.C. Cabarle, H.N. Adorna, M.J. P´erez-Jim´enez...................... 77 Asynchronous Spiking Neural P Systems with Structural Plasticity F.G.C. Cabarle, H.N. Adorna, M.J. P´erez-Jim´enez...................... 91 Automaton-like P Colonies L. Cienciala, L. Ciencialov´a, E. Csuhaj-Varj´u . . . . . . . . . . . . . . . . . . . . . . . . . . 105 Solving SAT with Antimatter in Membrane Computing D. D´ıaz-Pernil, A. Alhazov, R. Freund, M.A. Guti´errez-Naranjo . . . . . . . 121 On The Semantics of Annihilation Rules in Membrane Computing D. D´ıaz-Pernil, R. Freund, M.A. Guti´errez-Naranjo, A. Leporati . . . . . . . 131 How to Go Beyond Turing with P Automata: Time Travels, Regular Observer ω-Languages, and Partial Adult Halting R. Freund, S. Ivanov, L. Staiger ....................................... 143 A Characterization of PSPACE with Antimatter and Membrane Creation Z. Gazdag, M. A. Guti´errez–Naranjo................................... 159 x Contents kPWorkbench: A Software Framework for Kernel P Systems M. Gheorghe, F. Ipate, L. Mierl˘a, S. Konur ............................ 179 The Pole Balancing Problem with Enzymatic Numerical P Systems D. Llorente–Rivera, M.A. Guti´errez–Naranjo........................... 195 Monodirectional P Systems A. Leporati, L. Manzoni, G. Mauri, A.E. Porreca, C. Zandron . . . . . . . . . 207 Parallel Simulation of PDP Systems: Updates and Roadmap M. ´ A. Mart´ınez-del-Amor, L.F. Mac´ıas-Ramos, M.J. P´erez–Jim´enez . . . . 227 Some Quick Research Topics Gh. P˘aun .............................................................. 245 Looking for Computer in the Biological Cell. After Twenty Years Gh. P˘aun .............................................................. 251 Minimal Cooperation in P Systems with Symport/Antiport: A Complexity Approach L. Valencia-Cabrera, B. Song, L.F. Mac´ıas-Ramos, L. Pan, A. Riscos-N´u˜nez, M.J. P´erez-Jim´enez .................................. 301 Computational Efficiency of P Systems with Symport/Antiport Rules and Membrane Separation L. Valencia-Cabrera, B. Song, L.F. Mac´ıas-Ramos, L. Pan, A. Riscos-N´u˜nez, M.J. P´erez-Jim´enez .................................. 325 Author Index ......................................................... 371 Deterministic Non-cooperative P Systems with Strong Context Conditions Artiom Alhazov1, Rudolf Freund2 1Institute of Mathematics and Computer Science, Academy of Sciences of Moldova Academiei 5, Chi¸sin˘au MD-2028 Moldova E-mail: [email protected] 2Faculty of Informatics, Vienna University of Technology Favoritenstr. 9, 1040 Vienna, Austria E-mail: [email protected] Summary. We continue the line of research of deterministic parallel non-cooperative multiset rewriting with control. We here generalize control, i.e., rule applicability context conditions, from promoters and inhibitors checking presence or absence of certain object up to some bound, to regular and even stronger predicates, focusing at predicates over multiplicity of one symbol at a time. 1 Introduction It is known, see [7], that non-cooperative P systems with atomic promoters or atomic inhibitors characterize ET0L, while using either one catalyst, see [6], [3], or promoters or inhibitors of weight 2, see [4], leads to the computational completeness of non-cooperative P systems. A question about the power of deterministic systems was posed in [5], inspired by the fact that all identical objects have the same behavior in the same context. This question was answered in [1]: deterministic non-cooperative P systems have weak behaviour, namely, only accepting finite number sets and their complements, even using generalized context conditions (except the sequential case, when they keep the computational completeness). Generalized context conditions of rule applicability are defined as a list of pairs (pi, Fi), 1 ≤i≤k, applicable to a rule if at least one condition applies, in the following way: pi, called promoter, must be a submultiset of the current configuration (or the contents of the current region), and none of the elements of Fi, called inhibitors, are allowed to be submultisets of the current configuration (or the contents of the current region). A subsequent paper, [2], precisely characterized the power of priorities alone, as well as established how much power of promoters and inhibitors is actually needed to reach NFIN ∪coNF IN. Already in [1] it has been shown that generalized context conditions are equivalent to arbitrary predicates on boundings, i.e., all boolean combinations over conditions < m (and, 2 A. Alhazov, R. Freund hence, also ≥m,> m,≤m, = mand 6=m) for multiplicities of symbols. In other words, generalized context conditions are able to check exactly the multiplicities of symbols up to an arbitrary fixed bound m. In this paper we consider stronger context conditions. 2 Definitions Let Obe a finite alphabet. In this paper we will not distinguish between a multiset, its string representation (having as many occurrences of every symbol as its multiplicity in the multiset, the order in the string being irrelevant), and a vector of multiplicities (assuming that the order of enumeration of symbols from Ois fixed). By O◦we denote the set of all multisets over O. By a strong context in this paper we mean a language of multisets, i.e., a subset of O◦. Let a∈Oand u∈O◦, then a→uis a non-cooperative rule. The rules are applied in the maximally parallel way, which in the case of our interest, i.e., for deterministic non-cooperative P systems, correspond to replacing every occurrence of each symbol aby the corresponding multiset ufrom the right side of the applicable rule (if there is any; no competition between different rules can happen due to the determinism). Let region jof a membrane system contain multiset w. Then rule a→uwith a strong context condition C⊂O◦(written a→u|C) is applicable if and only if |w|a>0 and w∈C. Consider the following examples: •a singleton atomic promoter s∈Ocorresponds to the context +(s) = {w∈ O◦| |w|s>0}; we denote this feature by pro1,1; •a singleton atomic inhibitor s∈Ocorresponds to the complementary context condition: −(s) = {w∈O◦| |w|s= 0}; •a singleton promoter s∈O◦of a higher weight corresponds to the context +(s) = {w∈O◦|s⊆w}; •a singleton inhibitor s∈O◦of a higher weight corresponds to the complementary context condition: −(s) = {w∈O◦|s6⊆ w}; •a (finite) promoter-set S⊂O◦corresponds to the context +(S) = Ss∈S+(s), i.e., at least one promoter must be satisfied; •a (finite) inhibitor-set S⊂O◦corresponds to the complementary −(S) = Ts∈S−(s), i.e., any inhibitor can forbid the rule; •a promoter-set Pand an inhibitor-set Qtogether are called a simple context condition, written (P, Q); it corresponds to the strong context condition +(P)∩ −(Q); •context conditions as considered in [1] and [2] constitute a finite collection of simple context conditions (P1, Q1),· · · ,(Pm, Qm), they correspond to the strong context condition S1≤i≤m(+(Pi)∩ −(Qi)), and were shown to be equivalent to predicates on boundings3; 3the meaning of a promoter-set in [3] is different, but the computational power results are equivalent up to the descriptional complexity parameters such as number of promoters/inhibitors and their weights Deterministic Non-cooperative P Systems with Strong Context Conditions 3 •a bounding bkis an operation on a multiset, for any symbol preserving its multiplicity up to k, or “cropping” it down to kotherwise; a predicate on bounding can be specified by a finite set Mof multisets with multiplicities not exceeding k; it corresponds to a strong context condition {w∈O◦|bk(w)∈ M}, and can express precisely all boolean combinations of conditions |w|a< j, a∈O, 1 ≤j≤k; •a regular strong context condition can be specified by a regular multiset language, or as a Parikh image of a regular string language; e.g., Eq(a, b) = {w∈ O◦| |w|a=|w|b}is an example; we denote the family of such conditions by ctxt(REG); •if a strong context condition only depends on the multiplicities of ksymbols from O(and all other symbols do not affect the applicability), we represent this property by a superscript kof ctxt; for instance, if we denote the symbols mentioned above by S={s1,· · · , sk}, then ctxtk(REG) = {{u∪v|u∈L, v ∈ (O\S)◦} | L⊆S◦, L ∈PsREG}; hence Eq(a, b)∈ctxt2(REG); by ctxt(Eq) we denote being able to compare the multiplicities of two symbols (for different pairs of symbols separately) for being equal, together with the complementary condition; •to stay within Turing computability of the resulting P systems, in this paper we only consider recursive context conditions, i.e., multiset languages with decidable membership, denoted by ctxt(REC); •if a one-symbol strong context condition only depends on the multiplicity of one symbol, it can be specified by a predicate over N; e.g., Sq(a) = {w∈O◦| |w|a=k2, k ≥0}and Sq0(a) = {w∈O◦| |w|a=k2, k ≥1}are examples; hence, Sq,Sq0∈ctxt1(REC); by ctxt(Sq) or ctxt(Sq0) we denote being able to test the multiplicities (of different symbols separately) for squares (including zero or not, respectively), together with the complementary condition. 3 Regular conditions Theorem 1. PsaDOP1(ncoo, ctxt2(REG)) = PsaDOP1(ncoo, ctxt(Eq)) = PsRE. Proof. Consider an arbitrary register machine Mwith mregisters. For each working register i, 1 ≤i≤m, we represent its value by the difference of the multiplicities of associated objects aiand bi. Hence, increment can be performed by producing one copy of ai, decrement can be performed by producing one copy of bi, and zero can be distinguished from non-zero by the following regular conditions: Zi={w∈O◦| |w|ai=|w|bi}=Eq(ai, bi),1≤i≤m, Pi={w∈O◦| |w|ai6=|w|bi}=O◦\Eq(ai, bi),1≤i≤m, We construct the following P system: Π= (O, Σ, µ = [ ]1, w1=q0, R1),where 10 A. Alhazov, R. Freund 2 Definitions 2.1 Formal Language Preliminaries Consider a finite set V. The set of all words over Vis denoted by V∗, the concatenation operation is denoted by •(which is written only when necessary) and the empty word is denoted by λ. Any set L⊆V∗is called a language. For a word w∈V∗and a symbol a∈V, the number of occurrences of ain wis written as |w|a. The permutations of a word w∈V∗are Perm(w) = {x∈V∗| |x|a=|w|afor all a ∈V}. We denote the set of all permutations of the words in Lby Perm(L), and we extend this notation to families of languages. We use F IN,REG,LIN,CF ,MAT ,CS,RE to denote finite, regular, linear, context-free, matrix without appearance checking and with erasing rules, context-sensitive, and recursively enumerable families of languages, respectively. The family of languages generated by extended (tabled) interactionless L systems is denoted by E(T)0L. The family of sets of numbers generated by forbidden random context multiset grammars is denoted by NfRC. For more formal language preliminaries, we refer the reader to [9]. Throughout this paper we use string notation to denote the multisets. When speaking about membrane systems, keep in mind that the order in which symbols are written is irrelevant, unless we speak about the symbols sent to the environment. In particular, speaking about the contents of some membrane, when we write an1 1· · · anm m(or any permutation of it), we mean a multiset consisting of niinstances of symbol ai, 1 ≤i≤m. 2.2 P systems with One (Active) Membrane We present the definition of a P system with active membranes, simplified for studying the generative power in case of one membrane. Π= (O, µ = [ ]1, w1, R1, i0),where Ois a finite set of objects, w1is the initial multiset in region 1, R1is the set of rules associated to membrane 1, i0is the output region; when languages are considered, i0= 0 is assumed. The rules of a membrane system have the forms (a0) [ a→u]1(evolution of an object), and (c0) [ a]1→[ ]1b(sending an object out, possibly renaming it), where a, b ∈Oand u∈O∗. The rules are applied in maximally parallel way: no further rule should be applicable to the idle objects, except rules of type (c0) may be applied to at most one object at any step. Acatalytic P system (with one membrane) is a construct Π= (O, C, µ = [ ]1, w1, R1, i0),where Ois a finite set of objects, Cis a special subset of Owhose elements are called catalysts, w1is the initial multiset in region 1, R1is the set of rules associated to membrane 1, i0is the output region; when languages are considered, i0= 0 is assumed. Polarizationless P Systems with One Active Membrane 11 The rules in Rare either non-cooperative rules of the form a→(b1, tar1)· · · (bk, tark) with aand the bi, 1 ≤i≤k, being from O\Cand the tari∈ {here, out}being the targets for the corresponding symbols bi, or catalytic rules of the form ca → c(b1, tar1)· · · (bk, tark) with c∈C. A configuration of a P system is a construct which contains the information about the contents of the skin membrane as well as the sequence of objects sent out. A sequence of transitions between the configurations is called a computation. The computation halts when such a configuration is reached that no rules are applicable. In case of external output (i0= 0), as the result of a (halting) computation we may consider the sequence of objects sent to the environment; we denote it by L(Π). Both in case of internal output (i0= 1) and in case of external output, we may consider as the result the vector of multiplicities of objects in region i0, we denote it by P s(Π), or the total number of objects in region i0, which we denote by N(Π). The family of P systems with one polarizationless active membrane may be denoted by OP1(a0, c0). The class of sets of numbers/vectors/words generated by a family Fof P system is denoted by NF,P sFand LF, respectively. We use a superscript int or ext when speaking about internal and external output, respectively, and we may omit subscript ext in the case of generating languages, i.e., external output is assumed for LF. Moreover, we may use a subscript Tto denote terminal filtering of the result; in this case, a subset T⊂Ois additionally specified for Π, and the objects not belonging to Tare not considered in the result. For example, the family of sets of vectors of non-negative integers generated internally by P systems with one polarizationless active membrane with terminal filtering are denoted by P sint TOP1(a0, c0). Example 1. To illustrate generation, consider the following P system: Π= (O={S, a, b, c, d, f}, µ = [ ]1, w1=a, R1, i0), R1={[S→Sabcd ]1,[S→f]1, [a]1→[ ]1a, [b]1→[ ]1b, [c]1→[ ]1c}. Object Sproduces objects a,b,c,din arbitrary but equal amounts. Objects a,b,care sent out in arbitrary order. Hence, if i0= 1 then N(Π) = N1(i.e., the set of all positive integers), and if i0= 0 then L(Π) = Sn≥0Perm(anbncn) = {w∈ {a, b, c}∗| |w|a= |w|b=|w|c}. P systems can be also viewed as acceptors. In that case, an input subalphabet Σis additionally specified in the tuple defining P system before µ, and i0= 1 is the input region. An input multiset over Σis additionally placed inside the membrane before the computation starts, and it is accepted if and only if the computation halts. The result P sacc(Π) is the set of all accepted inputs, and the family of vector sets accepted by P systems with one active membrane is P saccOP1(a0, c0). 3 Comparison with a Transitional Model: Catalytic P Systems with One Catalyst The model of P systems with active membranes, for the case of one membrane, can be compared to the following case of transitional P systems: non-distributed P systems 12 A. Alhazov, R. Freund with one catalyst. Indeed, for each P system with one active membrane, there exists a 1-catalytic non-distributed P system with the same behavior, as non-cooperative rules work equivalently in both models: [ A→u]his equivalent to A→u, and sending out corresponds to particular rules with one catalyst, i.e., [ A]h→[ ]hacorresponds with cA →c(a, out), or, if without restricting generality we assume the set of symbols that may appear inside the system to be disjoint from the set of symbols that may be sent to the environment, simply with cA →c(a, here). Notice that for P system with external output, we may ignore the objects remaining inside the system when it halts (as explained in the next section), while for P systems with internal output, we should ignore the objects sent out. In this way, for the case of internal output, sending out corresponds to a catalytic erasing, while for the case of external output sending out corresponds to a catalytic renaming of a non-terminal symbol into a terminal symbol. Hence, we can immediately conclude that Xα βOP1(a0, c0)⊆XβOP1(ncoo, cat1) for X∈ {N, Ps, L}, α ∈ {int, ext}, β ∈ {−, T }, where β=−stands for not specifying a subscript. One-catalytic P systems were investigated in [5], where some subclasses of P systems with one catalyst are defined and certain results on their generative power are presented. In particular, it was shown in [5] that N−cOP1(wsepcat1) = NREG and N−cOP1(complcat1)⊆NfRC. Clearly, the corresponding restrictions might also be considered for polarizationless P systems with one active membrane, and such results can be claimed as upper bounds for the corresponding restrictions, e.g., NOP1(wsep(a0, c0)) = NREG, where the restriction of the weak separation can be reformulated for the model with active membranes as follows: the set Oof objects is divided into three disjoint subsets O0,O00 and O000, such that •objects a∈O0have no associated rules (they cannot evolve or be sent out, so if they are produced, they remain idle inside the system), •objects a∈O00 have associated send-out rules, but no evolution rules, •objects a∈O000 have associated evolution rules, but no send-out rules. It is worth mentioning that the additional requirement from [5] that the objects produced by a catalytic rule cannot undergo a non-cooperative rule is automatically satisfied after translation into the active membrane case, so the only restriction remaining in the case of weak separation is that a rule of type (a0) and a rule of type (c0) are not allowed to compete for the same object. This restriction means, for instance, that all objects that have associated send-out rules cannot evolve inside the system, they simply wait there until they are chosen to be sent out. A different restriction considered in [5] is complete P systems (mentioned above as complcat1). It can be reformulated in the model of polarizationless P systems with active membranes as follows: there is no object having associated rules of type (c0) and no rules of type (a0). This restriction means that no object is allowed to be temporarily idle; if it is not sent out, then it either evolves immediately, or remains idle throughout the computation. It follows that NREG ⊆NOP1(compl(a0, c0)) ⊆NfRC. Polarizationless P Systems with One Active Membrane 13 It is interesting to note that weak separation and completeness are, in some sense, two opposite requirements. While the latter one requires that all objects which can be sent out must evolve if they are not chosen to be sent out, the first special case requires that no objects which can be sent out are allowed to evolve. Of course, in the most general case there can be both kinds of objects which can be sent out. 4 External output The first goal of this section is to present a reduction of any P system with one active membrane without polarizations and external output to an equivalent normal form. Then we will use this normal form to prove an upper bound result. We require the normal form mentioned above to satisfy the following conditions: •Every object appears on the left side of some rule. •The only erasing rule allowed is for the initial object; if so, the initial object does not appear on the right side of any rule. (If we have an initial multiset w, then we add the rule S→wwhere Sis a new symbol now being the initial object.) We approach this goal in a few stages. First, we remark that, without restricting generality, we may assume that no objects may remain inside the system when it halts. Indeed, let Oλbe the set of all objects that do not have associated rules. By adding rules Rλ={[a→λ]1|a∈Oλ}, we make sure that there are no objects that do not have associated rules. On the other side, adding rules Rλdoes not affect the result of a P system with external output, since preserving/erasing objects from Oλhas no alternatives, and it does not affect the environment. Second, we remark that, without restricting generality, we may assume that the initial multiset consists of only one object, say S, which does not appear in the right side of any rule. Indeed, for a P system starting with a multiset (represented by) w, consider an equivalent P system starting with a multiset consisting of a new object S, and adding RS={[S→w]1}to R1. Third, we claim that for any P system satisfying the assumptions mentioned above, there exists a P system without erasing rules (except, possibly, for S). Proof. Indeed, let us first add rules Rt={[a→# ]1|([ a→λ]1)∈R1or a= #}, where # is a new symbol, shared for all such reductions, so if it appears in a configuration, the system will never halt, and will therefore not produce any result. This transformation will certainly not affect the result of the system, since every new computation branch will not be productive, while the existing branches will not be affected (since by construction, one can always apply some other rule to ainstead of trapping). Second, compute the set Oλof erasable objects as follows: •Set Oλto {a∈O|[a→λ]1∈R1, •If [ a→u]1is in R1and u∈O∗ λ, then add ato Oλ, •Iterate the previous procedure until no more elements can be added to Oλ. Third, replace each rule [ a→u]1by rules [ a→u0]1, where the u0are obtained from uby removing (in all possible combinations) some objects from Oλ. This will again yield an equivalent system, because every symbol that could eventually be deleted does not have to be produced in the first place. 14 A. Alhazov, R. Freund Fourth, remove all erasing rules. We claim that the resulting P system is still equivalent to the original P system. Indeed, any object (other than S) that should be erased, could be “pre-erased” by not producing it in the first place. However, any object that should evolve can evolve by other rules, and any object that should be sent out can be sent out (unless some competing object is sent out, in which case the simulation would not be correct, so the computation is discarded by producing symbol #).  Corollary 1. LOP1(a0, c0)⊆CS. Proof. Indeed, the total number of objects (inside and outside the membrane) never decreases throughout the computation (except, possibly, for the empty word, generated in one step), and the length of the result matches the total number of objects when the system halts.  We now proceed with the lower bound result. Theorem 1. LOP1(a0, c0)⊇REG •Perm(REG). Proof. Consider an alphabet Tand two arbitrary regular languages over T. Then there exist reduced regular grammars G1= (N1, T, P1, S1) and G2= (N2, T, P2, S2) generating them, such as N1∩N2=∅. We construct the following P system: Π= (O=N1∪N2∪T∪T0, µ = [ ]1, w1=S1, R1), T0={a0|a∈T}, R1={[A→aB ]1|(A→aB)∈P1} ∪ {[A→S2]1|(A→λ)∈P1} ∪ {[A→a0B]1|(A→aB)∈P2} ∪ {[A→λ]1|(A→λ)∈P2} ∪ {[a0→a0]1|a∈T} ∪ {[a]1→[ ]1a, [a0]1→[ ]1a|a∈T}. The P system constructed above generates L(G1)•L(G2), except the symbols generated by the second grammars are produced in a primed form, and may undergo trivial rewriting for an arbitrarily long time before they are sent out, which ensures that after generating a word from L(G1), any permutation of a word from L(G2) may be generated.  We now present a few closure properties. Lemma 1. The family LOP1(a0, c0)is closed under renaming morphisms. Proof. The statement follows from applying the renaming morphism to the send-out rules.  Theorem 2. LOP1(a0, c0)is closed under union. Proof. The closure under union follows from adding a new axiom and productions of non-deterministic choice between multiple axioms.  Polarizationless P Systems with One Active Membrane 15 5 Internal output In this case the environment is no longer relevant: it does not matter which symbol is written in the right side of a send-out rule. The object sent out no longer affects the result, so sending out is equivalent to a sequential version of erasing. Of course, we can generate P sREG with rules of type (a0) corresponding to the rules of a reduced regular grammar. Hence, P sintOP1(a0, c0)⊇P sREG. Is it an open question whether non-semilinear number sets can be generated, see also the partial results transferred from the one-catalytic model, recalled in Section 3. 6 P systems with input In this section we show that, not very surprisingly, for P systems with one polarizationless active membrane, their accepting power is even smaller than their generative power. More exactly, unless such a P system accepts all allowed inputs, it only accepts specific finite sets. We start by establishing some useful facts (we remind that we use ⊆to denote the submultiset relation, ∪to denote the union of multisets, and \to denote the difference of multisets). Lemma 2. Let Π∈OP1(a0, c0)be a P system with alphabet O, let [u]1⇒[v]1α in Π(α∈O∪ {λ}) Then for every multiset u0⊆u, either [u0]1is already a halting configuration, or there exists a multiset v0⊆vand β∈O∪{λ}such that [u0]1⇒[v0]1β in Π. Proof. In a transition [ u]1⇒[v]1α, one of three possible cases happen for every (copy of) object ain u: •ais rewritten by some rule of Πinto a (possibly empty) multiset, contributing to v; •ais sent out by some rule of Πas α; •aremains idle, contributing to v. Note that vconsists exactly of the resulting objects from the first case and the objects of the third case. More precisely, let the union of multisets of the right side rules for all copies of rewritten objects be vr, and let the multiset of idle objects be vi; then, v=vr∪vi. By definition of the model, the second case was applied to at most one (copy of) an object in u. Also by definition of the model, for each object in the third case, there exist no rules to evolve it, except, possibly, send-out rules, in which case α6=λ. We recall that u0may be obtained from uby erasing some (copies) of objects. Fix some correspondence of (copies of) objects in u0to objects in u, and consider a transition from u0by the same behavior of objects in u0as of objects in u: •rewritten objects will yield some submultiset v0 rof vr; •β0will be produced in the environment, β0=αor β0=λ; •idle objects will yield some submultiset v0 iof vi. 16 A. Alhazov, R. Freund It is obvious that these rules are applicable, and that v0 r∪v0 i⊆v. Maximality also holds, except in one special situation: when α6=λ, but it was produced from a (copy of) an object not in u0, while there exists at least one object bthat was idle in a transition [u]1⇒[v]1α. In this situation, one object b, instead of being idle, should be sent out as β, and the resulting multiset in the skin is v0=v0 r∪v0 i\b(if this situation does not happen, we take β=β0and v0=v0 r∪v0 i). Therefore, [ u0]1⇒[v0]1βin Πif at least one (copy) of object from u0fell into the first or the second case, and otherwise [ u0]1is already a halting configuration.  Lemma 3. If n∈N(Π), then also n0∈N(Π)for any non-negative integer n0≤n. Proof. Let the alphabet of Πbe O, let the initial contents of the skin membrane of Πbe w1, and let the input subalphabet of Πbe Σ. By definition of acceptance, a number n is accepted if there exists a halting computation in Πstarting from configuration [ u]1, for some u∈w1Σn. Consider the “sub-input” of only n0objects, i.e., u0∈w1Σnsuch that u0⊆u. If [u]1is already halting, then so is [ u0]1, so the statement of the lemma holds; now we assume the contrary: [ u]1⇒[v]1α. By the previous lemma, in one step, either the computation with u0in the skin will immediately halt (and the statement of the lemma again holds), or there is a one-step transition [ u0]1⇒[v0]1βwith v0⊆v. Iterating the application of the previous lemma, by induction, we conclude that there exists a computation starting from [ u0]1that will halt in at most as many step as the halting computation starting from [ u]1that we considered. Hence n0∈N(Π).  It follows that the accepted set of numbers is either N, or empty, or it contains all integers less than or equal to the maximal accepted number, so accepting P systems with one polarizationless active membrane cannot be computationally complete, and P systems with one polarizationless active membrane are obviously weaker as acceptors than as generators: NaccOP1(a0, c0)⊆ {∅,N} ∪ {{k|0≤k≤n} | n∈N}. In the rest of the section we show, by all necessary examples, that this inclusion is an equality: Π∅= (O={a}, Σ ={a}, µ = [ ]1, w1=a, R1={[a→a]1}, i0= 1). ΠN= (O={a}, Σ ={a}, µ = [ ]1, w1=λ, R1={[a→λ]1}, i0= 1). Πn= (O={ai|0≤i≤n}, Σ ={a0}, µ = [ ]1, w1=λ, R1, i0= 1),where R1={[ai→ai+1 ]1,[ai]1→[ ]1a0|0≤i < n} ∪ {[an→an]1}. Clearly, Π∅accepts nothing, since with any input it starts with at least one object, and carries out an infinite computation. On the other end of the spectrum, system ΠNaccepts any input, by erasing it in one step and halting. Finally, we claim that system Πnaccepts exactly set {k|0≤k≤n}. Indeed, any object increments its index every step, unless the object is sent out, or the index reaches n(forcing an infinite computation). It is easy to see that at most ninput objects may be sent out in this way; the system with input (a0)khas a halting computation if and only if k≤n. Polarizationless P Systems with One Active Membrane 17 Overall, we have established the following results: REG •Perm(REG)⊆LOP1(a0, c0)⊆CS, P sintOP1(a0, c0)⊆P sREG, NαOP1(wsep(a0, c0)) = NREG, α ∈ {int, ext}, NREG ⊆NαOP1(compl(a0, c0)) ⊆NfRC, α ∈ {int, ext}, NaccOP1(a0, c0) = {{k|0≤k≤n} | n∈N} ∪ {∅,N}. 7 Conclusions In this paper we have considered the family of languages generated by polarizationless P systems with one active membrane. A normal form was given for external output case. It was than shown that the family of generated languages lies between REG •Perm(REG) and CS, and is closed under union and renaming morphisms. The exact characterization is an open question, but polarizationless P systems with one active membrane can be simulated by (and are, therefore, at most as powerful as) P systems with one catalyst, transferring two results on the generative power of two restricted classes, independently from the output region. Then we also considered sets of vectors or numbers generated internally, as well as sets of vectors or numbers accepted by polarizationless P systems with one active membrane. Several questions about the families of these sets are still open, too. Another possible generalization that can be considered is to also allow rules of type (b0) to bring objects from the environment back to the skin. Note that such systems would still correspond to a subclass of 1-catalytic P systems, but some definitions would have to be revised, as well as all related results. We have proved that accepting P systems with one polarizationless active membrane are not computationally complete, unlike those with two polarizations or like those with membrane creation and dissolution, or with multiple membranes and membrane dissolution. The questions about the computational power of polarizationless P systems with active membranes with 2 and 3 membranes in the initial configuration are still open, as well as of polarizationless systems with less than 7 membranes and two labels, or of all polarizationless systems with only one label. References 1. A. Alhazov: P Systems without Multiplicities of Symbol-Objects. Information Processing Letters 100, 3, 2006, 124–129. 2. A. Alhazov, C. Ciubotaru, Yu. Rogozhin, S. Ivanov: The Family of Languages Generated by Non-Cooperative Membrane Systems. In: Gh. P˘aun, M.J. P´erez-Jim´enez, A. Riscos-N´u˜nez, G. Rozenberg, A. Salomaa: Membrane Computing, 11th International Conference, CMC11, Jena, Revised Selected Papers, Lecture Notes in Computer Science 6501, 2011, 65–79. 18 A. Alhazov, R. Freund 3. A. Alhazov, R. Freund, Gh. P˘aun: Computational Completeness of P Systems with Active Membranes and Two Polarizations. In: M. Margenstern: Machines, Computations, and Universality, 4th International Conference, MCU 2004, Saint Petersburg, Revised Selected Papers, Lecture Notes in Computer Science 3354, Springer, 2005, 82–92. 4. A. Alhazov, R. Freund, A. Riscos-N´u˜nez: Membrane Division, Restricted Membrane Creation and Object Complexity in P Systems. International Journal of Computer Mathematics 83, 7, 2006, 529–548. 5. R. Freund: Special Variants of P Systems with One Catalyst in One Membrane. In: H. Leung, G. Pighizzini: 8th International Workshop on Descriptional Complexity of Formal Systems - DCFS 2006, Las Cruces, New Mexico, 2006. Proceedings, 2006, 250–258. 6. Gh. P˘aun: Membrane Computing. An Introduction, Springer, 2002. 7. Gh. P˘aun, G. Rozenberg, A. Salomaa: Membrane Computing with an External Output. Fundamenta Informaticae 41, 3, 2000, 313–340. 8. Gh. P˘aun, G., Rozenberg, A. Salomaa, A. (eds.): The Oxford Handbook of Membrane Computing, Oxford University Press, 2010. 9. G. Rozenberg, A. Salomaa (eds.): Handbook of Formal Languages, 1-3 vol., Springer, 1997. 10. P systems webpage. http://ppage.psystems.eu/ Variants of P Systems with Toxic Objects Artiom Alhazov1, Rudolf Freund2, and Sergiu Ivanov3 1Institute of Mathematics and Computer Science, Academy of Sciences of Moldova Academiei 5, Chi¸sin˘au MD-2028 Moldova Email: [email protected] 2Faculty of Informatics, Vienna University of Technology Favoritenstr. 9, 1040 Vienna, Austria Email: [email protected] 3Universit´e Paris Est, France Email: [email protected] Summary. Toxic objects have been introduced to avoid trap rules, especially in (purely) catalytic P systems. No toxic object is allowed to stay idle during a valid derivation in a P system with toxic objects. In this paper we consider special variants of toxic P systems where the set of toxic objects is predefined – either by requiring all objects to be toxic or all catalysts to be toxic or all objects except the catalysts to be toxic. With all objects staying inside and being toxic, purely catalytic P systems cannot go beyond the finite sets, neither as generating nor as accepting systems. With allowing the output to be sent to the environment, exactly the regular sets can be generated. With non-cooperative systems with all objects being toxic we can generate exactly the Parikh sets of languages generated by extended Lindenmayer systems. Catalytic P systems with all catalysts being toxic can generate at least P sM AT . 1 Definitions We assume the reader to be familiar with the underlying notions and concepts From formal language theory, e.g., see [16], as well as from the area of P systems, e.g., see [13, 14, 15]; we also refer the reader to [18] for actual news. 1.1 Prerequisites The set of integers is denoted by Z, and the set of non-negative integers by N. Given an alphabet V, a finite non-empty set of abstract symbols, the free monoid generated by Vunder the operation of concatenation is denoted by V∗. The elements of V∗are called strings, the empty string is denoted by λ, and V∗\ {λ}is denoted by V+. For any string w∈V, by alph(w) we denote the set of symbols 26 Artiom Alhazov, Rudolf Freund, and Sergiu Ivanov results cannot be obtained without using external out or terminal extraction. In fact, all results in the P systems area should be carefully inspected with respect to these subtle details of complexity definitions. As we shall see in the following sections, the way how to obtain the results in many cases will have a significant influence on the computational power of several variants of P systems with toxic objects. Remark 4. As in this paper we will only consider P systems using the maximally parallel derivation mode, in the following the subscript maxpar will be omitted. Finally, P systems can also be considered as mechanisms for generating and accepting string languages as well as for computing any partial recursive function f:Σ∗→Γ∗on strings. Here the input string consists of the sequence of symbols taken in from the environment during a halting computation and the output string is formed by the sequence of symbols sent out to the environment; hence, the P system works like in the automaton style, but the input and output streams of symbols are interpreted as strings. In general, any number of symbols can be taken in and sent out in one computation step, and any possible sequence of those symbols has to be taken into account as a substring to be concatenated with the strings already computed by the preceding computation steps – thus, not only one input and one output string may result from a successful halting computation. The string relation computed by halting computations in a P system Πis denoted by Lcom (Π). If we only consider the symbols taken in from the environment, Lcom (Π) can be seen as an automaton accepting the strings computed by the sequences of symbols taken in during halting computations and we also write Laut (Π); if no symbols are taken from the environment, Lcom (Π) describes a string language generated by Πand we also write Lgen (Π). By LδOPm(X), δ∈ {gen, aut}, as well as by RelLcomOPm(X) and FunLcomOPm(X) we denote the families of string languages generated and accepted as well as the families of string relations and functions computed by P systems with at most mmembranes using rules of type X. With FunRE and RelRE denoting the class of partial recursive string functions and relations, respectively, the following results can be derived from the results proved in [5] (for the generating case, also see [15], Theorem 4.17): Theorem 1. For any δ∈ {gen, aut},Z∈ {Fun, Rel} RE =LδOP1(cat2) = LδOP1(pcat3) as well as ZRE =ZLcomOP1(cat2) = ZLcomOP1(pcat3). 3 Toxic Objects in P Systems We specify a specific subset Otox of Oas toxic objects. Toxic objects must not stay idle as otherwise the computation is abandoned without yielding a result. Variants of P Systems with Toxic Objects 27 In a successful computation, in any computation step continuing a derivation, we always have to apply multisets of rules evolving all toxic objects. On the other hand, if no rule can be applied any more and thus the system halts, toxic objects do no harm and we take out the results in the usual way depending on the specific definition for the systems under consideration. A P system with toxic objects is only allowed to continue a computation from a configuration Cby using an applicable multiset of rules covering all copies of objects from Otox occurring in C; moreover, if every non-empty multiset of applicable rules is not covering all toxic objects, the whole computation having yielded the configuration Cis abandoned, i.e., no results can be obtained from this computation. For any variant of P systems, we add the set of toxic objects Otox and in the specification of the families of sets of (vectors of) numbers generated/accepted by P systems with toxic objects using rules of type Xwe add the subscript tox to O, thus obtaining the families YγOtoxPm(X), for any Y∈ {N, Ps, L},γ∈ {gen, acc, aut}, and m≥1. 3.1 Variants of P Systems with Toxic Objects We may distinguish the following variants: •all symbols are toxic, i.e., we write YγOtoxallPm(X); •in catalytic P systems, exactly the catalysts are toxic, i.e., we write YγOtoxcatPm(X); •at least the catalysts are toxic, i.e., we write YγOtox⊇catPm(X); •all except the catalysts are toxic, i.e., we write YγOtox−catPm(X). In all these notations, we may add the superscript Tto indicate terminal extraction or the superscript −cat to indicate that the catalysts are not taken into account for the results; moreover, we replace Pmby Pm,ext or Pm,int in order to explicitly specify that the system uses external or internal output, respectively. Remark 5. The results established in the following implicitly may assume the P system to be flattened to one membrane, but in the sense of the previous remarks, we have to be very careful whether we have internal output, so that toxicity of symbols matters, or else we have external output, in which case we assume that the objects sent out do not affect the work of the system any more. 4 Purely Catalytic P Systems with All Objects Being Toxic We first consider the specific variants of P systems which in any step only allow for a bounded number kof rules to be applied, for example, purely catalytic P systems. Obviously, in this case, as until the end of a computation every symbol has to be affected by a rule, at most ksymbols can evolve in any computation 28 Artiom Alhazov, Rudolf Freund, and Sergiu Ivanov step, which of course bounds the number of possible configurations by a constant number, too. For the generative case with internal output, we show that we get precisely all finite sets, while for the accepting case (i.e., internal input), the power is also quite limited – everything which is not finite is arbitrary, and, moreover, only specific finite sets are accepted. Lemma 1. For all m≥1and all k≥1, PsgenOtoxallP−cat m,int (pcatk) = PsFIN. Proof. For the forward inclusion, we notice that the initial configuration is fixed, and the size of a vector we can generate by halting in any non-initial configuration is bounded by the maximal sum of the right-hand sides of rules over different catalysts. For the converse inclusion, it is enough to mention that for any finite set Fof d-dimensional vectors of non-negative integers, there exists a P system Πof type OtoxallP−cat 1,int (pcat1) such that Π=O={c1, a} ∪ T, C ={c1}, µ = [ ]1, w1=c1a, R1,1, where {c1, a} ∩ T=∅,|T|=dwith Tbeing written ha1,· · · , adias an ordered set, and R1consists of precisely one rule c1a→c1ak1 1· · · akd dfor every element (k1,· · · , kd)∈F, so each element of Fis generated in one step; for F=∅, we simply take the rule c1a→c1a, which causes an infinite computation. For both cases, we can define R1as follows: R1=nc1a→c1ak1 1· · · akd d|(k1,· · · , kd)∈Fo∪ {c1a→c1a}.  Lemma 2. For all m≥1and all k≥1, NaccOtoxallPm(pcatk) = {{d} | 0≤d≤k−1} ∪ {{0, k0} | 0≤k0≤k} ∪ {∅,N}. Proof. We proceed with the forward inclusion. Take an arbitrary P system Πof type OtoxallPm(pcatk), where Π= (O, C ={c1,· · · , ck0}, Σ ⊆O\C, µ, w1,· · · , wm, R1,· · · , Rm, i0), where k0≤k. Before the computation starts, input w0∈Σ∗is added to wi0. Only two cases are possible that do not lead to a computation which is not abandoned immediately: either the P system halts immediately, or all objects from w1,· · · , wm as well as all the objects from w0∈Σ∗additionally placed in region i0participate in catalytic rules in the first step, hence the number of catalysts must be equal to Variants of P Systems with Toxic Objects 29 the number of non-catalysts. In the second case, it follows that the size |w0|of the input w0must be equal to k0−Pm i=1 |wi|. In the first case, it is easy to see that if Πimmediately halts on some non-empty input, then it must also immediately halt on the empty input. If we have at least one rule for every input symbol in Σ, then immediate halting happens only on the empty input. If, however, there exists at least one symbol from Σthat does not appear in the left side of any rule from Ri0, then any number of these symbols (let us call them “passive”) would be accepted. We now put it all together. For the same system, having both immediate halting case and later halting case is only possible if besides the input, the initial system has only catalysts. This yields exactly {0, k0},k0≤kif there are no passive objects in Σ, or the entire set Notherwise. Only immediate halting yields {0}and N, depending on the presence of passive objects in Σ. Finally, only later halting yields {d}for 0 ≤d < k (the last inequality is strict since at least one non-catalyst is needed besides the input to reject 0). And of course, we may have a P system with no halting computations, accepting ∅. The family of all sets mentioned above is {{d} | 0≤d≤k−1} ∪ {{0, k0} | 0≤k0≤k} ∪ {∅,N}, which proves the forward inclusion of the claim of the lemma. For the converse inclusion, it is enough to exhibit P systems for each of these sets; in every case, the input alphabet is Σ={a}. Π∅=O={c1, a}, C ={c1}, Σ ={a}, µ = [ ]1, w1=c1a, R1, i0= 1, R1={c1a→c1a}; ΠN=O={c1, a}, C ={c1}, Σ ={a}, µ = [ ]1, w1=c1, R1, i0= 1, R1=∅; Πd,0=O=C∪ {a}, C ={c1,· · · , cd}, Σ ={a}, µ = [ ]1, w1, R1, i0= 1, w1=c1· · · cd, R1={cia→ci|1≤i≤d},0≤d≤k; Πd=O=C∪ {a}, C ={c1,· · · , cd+1}, Σ ={a}, µ = [ ]1, w1, R1, i0= 1, w1=c1· · · cd+1a, R1={cia→ci|1≤i≤d},0≤d≤k−1. Indeed, the only rule of Π∅forces an infinite loop on the empty input, while for a non-empty input the computation is blocked because more than one toxic object acannot be simultaneously taken by c1. On the other end of the spectrum, ΠN accepts any input by immediate halting, because the catalyst always stays idle as there is no rule in the system. P system Πd,0either halts immediately with no input, or halts after one step, erasing the input of exactly dobjects, d≤k. Finally, the P system Πdhalts after one step, erasing the input of exactly dobjects, d < k. These observations conclude the proof.  30 Artiom Alhazov, Rudolf Freund, and Sergiu Ivanov Note 1. Of course, characterizing sets of vectors in the accepting case would be more tedious for the following reason. Without passive objects, P system would accept some subset of Σ≤k−1, as well as a subset of Σ≤kcontaining some vectors of weight d≤kand a vector of zeros, and the empty set. With passive objects, any number of them is allowed for the case of immediate halting, while the projection of the accepted vectors onto the non-passive objects should form a set containing some vectors of weight d≤kand a vector of zeros. The meaning of the word some throughout this note can be made more precise by analyzing exactly which multisets of weight dcan be consumed by dcatalysts, depending on the rules of the system (whereas in the case of accepting numbers, only the total weight of such multisets was taken into consideration). While Lemma 1 characterized PsFIN by P systems with internal output, in the case of external output their power becomes exactly P sREG, as the following theorem shows: Lemma 3. For all m≥1and all k≥1, PsgenOtoxallPm,ext (pcatk) = PsREG. Proof. Let M= (Q, T, δ, q0, F) be a deterministic finite automaton. Then we construct the P system Πwhich generates Ps (L(M)): Π=O=C∪Q∪T, C ={c1}, µ = [ ]1, w1=c1q0, R1, i0= 0, R1={c1p→c1q(a, out)|(p, a, q)∈δ, p, q ∈Q, a ∈T} ∪ {c1p→c1|p∈F}. We conclude that P sREG ⊆PsgenOtoxallP1,ext (pcat1). The converse inclusion can be argued as follows: In any successful computation step with kcatalysts, there must be exactly knon-catalysts, and a computation stops with having yielded a result if all objects inside the system including the catalysts are idle; hence, this finite set of useful configurations is finite and constitutes the set of states of a finite automaton simulating the computations of the P system. Since every rule in such a system involves one catalyst and one non-catalyst, for a configuration Cto allow some derivation C⇒C0it is necessary (although not sufficient) that the number of catalysts equals the number of non-catalysts inside the system. Hence, for a P system Π= (O, C, µ, w1,· · · , wm0, R1,· · · Rm0, i0) having fixed the set of objects O, the membrane structure µof m0≤mmembranes, and the set of catalysts C, with the number k0≤kof catalysts, the set Qof configurations containing a total of exactly k0objects from O\Cin m0regions of the P system is bounded. Moreover, the set Q00 of all configurations reachable from Qin one step is also bounded. Finally, we define Q0=Q00 ∪ {q0}where q0is Variants of P Systems with Toxic Objects 31 the initial configuration, as well as Qh⊆Q0to be the set of halting configurations (in which no rule can be applied any more). Hence, a P system with external output generating vectors of natural numbers can be modeled by a finite automaton M= (Q0, T, δ, q0, Qh) having Q0as the set of states, Tcontains dsymbols for the generation of d-dimensional vectors, δcontains the triple (p, v, q) for any transition from a configuration p∈Q0to a configuration q∈Q0sending out v; the set of the final states is precisely Qh. In sum, with all objects being toxic, purely catalytic P systems with external output can exactly generate the regular sets of vectors.  The statement of Lemma 3 can be generalized to languages, as well as to P automata and P transducers. Indeed, in case of external input (P automaton case) and/or external output, the finite number of different configurations can serve as the finite state set of a finite automaton for the input specified by (a, come) in the rules and/or for the output specified by (a, out) in the rules. Lemma 4. For all m≥1and all k≥1, LgenOtoxallPm(pcatk) = REG. Proof. Using similar arguments as already pointed out in the previous proof, we can easily argue that purely catalytic P systems with all objects being toxic can generate any regular language L; the only difference now is that any sequence of symbols sent out during a successful computation is interpreted as string. Now we consider the converse, i.e., as in the previous proof, a P system with external output generating strings can be modeled by the finite automaton having Q0as the set of states and Qhas the set of the final states as constructed there, but now for any transition from a configuration p∈Q0to a configuration q∈Q0 sending out v,δcontains the triple (p, v0, q) for all v0∈P erm(v).  Lemma 5. For all m≥1and k≥2, LautOtoxallPm(pcatk) = REG, RelautOtoxallPm(pcatk) = RelREG. Proof. For a P automaton or a P transducer Π, again take Q0and Qhas constructed in the proof of Lemma 4. A P automaton can be modeled by a finite automaton having Q0as the set of states. A transition from configuration p∈Q0to a configuration q∈Q0while having ubrought from the environment is simulated by rules (p, u0, q) for all u0∈ Perm(u); clearly, |u| ≤ k0. The set of the final states is precisely Qh. A P automaton with external output can be modeled by a finite transducer having Q0as the set of states. A transition from configuration p∈Q0to a configuration q∈Q0while having ubrought in and vsent out is simulated by rules 32 Artiom Alhazov, Rudolf Freund, and Sergiu Ivanov (p, u0/v0, q), u0∈P erm(u), v0∈Perm(v); clearly, |u| ≤ k0and |v| ≤ k0. The set of the final states is precisely Qh. For proving the converse inclusion, take an arbitrary finite automaton M= (Q, T, δ, q0, F ); without loss of generality, we assume that Mhas at least one outgoing transition from any non-final state. A P automaton Π=O={c1, c2, b} ∪ T, C ={c1, c2}, Σ =T, µ = [ ]1, w1=c1c2b, R1, i0= 1 R1={c1p→c1q(a, come)|(p, a, q)∈δ, p, q ∈Q, a ∈T} ∪ {c2x→c2|x∈ {b} ∪ T}∪{c2q→c2|q∈F} can simulate M, using two catalysts c1, c2. Each transition (p, a, q)∈δcan be simulated by rule c1p→c1q(a, come), but also rule the c2a→c2is needed to erase the symbol previously brought in. The initial contents of a single membrane is c1c2q0b, where besides q0, one additional non-catalyst b /∈ {c1, c2} ∪ Tis used to keep c2busy in the first step. Halting can be simulated by rule c1q→c1for each final state q; in the same step c2deletes the last symbol brought in. A P automaton with external output can simulate a finite transducer in the same way as a P automaton without output simulates a finite automaton. The only difference is that now the simulated transitions have the form (p, a/u, q), and the corresponding simulating rules are c1p→c1q(a, come)(u, out), the rest of the construction being exactly the same as in the previous paragraph.  Two catalysts are needed for simulating an arbitrary finite automaton by a P automaton, since both the state symbol and the symbol brought in from the environment have to be processed in parallel. For the case of only one catalyst, the object brought in from the environment itself has to serve as a state. However, in this way, the last object brought inside completely determines the set of possible objects that can be brought inside in the next step, which considerably reduces the generality of finite automata. Having this in mind, we characterize input-driven finite automata: Lemma 6. For all m≥1, LautOtoxallPm(pcat1) = IDREG, RelautOtoxallPm(pcat1) = RelIDREG. Proof. The inclusion that at most IDREG/RelIDREG is generated/computed with one catalyst follows from the fact that exactly one non-catalyst may appear in any non-halting non-blocking configuration, and, except the initial configuration, this is precisely the symbol taken from the environment in the previous step. In any successful computation, the only rules applied in any step, possibly except in the last step, are erasing one non-catalyst while bringing in another one instead. For the inclusion that we can generate/compute the entire families IDREG/RelIDREG, we use a construction similar to that of the previous lemma, Variants of P Systems with Toxic Objects 33 except instead of erasing the object abrought in the previous step by c2, this object is used instead of the state object: each transition (qa, b, qb) now is simulated by the rule c1a→c1(b, come). The initial contents of a single membrane is c1q0, where the initial state q0is an additional symbol not in the input alphabet. Halting can be simulated by the rules c1a→c1for all final states qa. For the case of a P automaton with external output, the simulation is the same as above, except that now we also have an output: the transitions to be simulated have the form (qa, b/u, qb), and the corresponding simulating rules are c1a→c1(b, come)(u, out); the rest of the construction is exactly the same as in the previous paragraph.  Finally, the domain of relations computed with internal input (with either output region) corresponds to the sets accepted with internal input, see Lemma 2. Similarly, the range of relations computed with internal output and with internal input corresponds to the sets generated with internal output, see Lemma 1. The nature of these relations always results from a finite-state behavior, but we are not going into further details here; another question to be answered in the future is the exact characterization of P automata with internal output. 5 Non-Cooperative P Systems with All Objects Being Toxic In this section we consider P systems without catalysts and with only noncooperative rules, yet with all objects being toxic. 5.1 Connection to L Systems Example 1. Take the following P system with all objects being toxic. Πint =O={a, b}, µ = [ ]1, w1=a, R1={a→aa, a →b}, i0= 1. In ncomputation steps we obtain a2nand in a final step b2n. Only in this last step we may apply the rule a→bintroducing the toxic symbol bfor which no rule exists. Hence, the generated set is Ngen (Πint) = {2n|n≥0}. Example 2. The same set is accepted by the P automaton Πaut and generated by the P system Πext with external output: Naut (Πaut) = Ngen (Πext) = Ngen (Πint) = {2n|n≥0}where Πaut =O={a, b}, µ = [ ]1, w1=a, R1={a→aa, a →(b, come)}, i0= 1; Πext =O={a, b}, µ = [ ]1, w1=a, R1={a→aa, a →b(b, out), i0= 0). Indeed, the behavior of Πaut and Πext is the same as that of Πint, except producing binside the membrane is replaced by bringing in bfrom the environment, or accompanied by sending out bto the environment. Again, if both rules are simultaneously applied, then the toxic objects bwill block the computation, but still we will get a result if only symbols bare present in the final configuration. 34 Artiom Alhazov, Rudolf Freund, and Sergiu Ivanov We now compare non-cooperative P systems with all objects being toxic to L systems. Lemma 7. For (γ, α)∈ {(gen, int),(gen, ext),(aut, −)}, PsE0L⊆PsγOtoxallP1,α (ncoo). Proof. Let G= (V, T, P, w) be an E0Lsystem. We recall that for each symbol a∈V,Phas to contain some rule with aon the left side. For every a∈T, we replace aby Nathroughout all the rules of P. Moreover, we take Na→ainto Rfor every a∈T. These terminal rules are exactly applied in the last step of a derivation in the P system Π, whereas the other rules in Rsimulate the rules from P. As the final step with using the rules Na→ais an additional derivation step, instead of rules a→λerasing a symbol awe instead have to use the rules Na→Eand E→λwhere Eis a new symbol representing the erased symbol for one step. Hence, we construct the corresponding non-cooperative P system Πwith all symbols being toxic as follows (for the automaton case, we have to insert Σ=T): Π= (O=V∪ {Na|a∈T}∪{E}, µ = [ ]1, w1=w, R1, i0= 1), R1={h(a)→h(u)|a→u∈P, a ∈V}∪{Na→E|a→λ∈P, a ∈T} ∪ {Na→a|a∈T}∪{E→λ}, where h:V∪{E} → V\T∪{Na|a∈T}∪{E}is the morphism given by h(a) = a for X∈V\T∪ {E}and h(a) = Nafor a∈T. By construction, every object from {Na|a∈T} ∪ {V\T}can evolve by rules from R1, while objects in Tcannot. If a computation in Πends up with a configuration in which the skin contains both objects from Tand objects not from T, then the computation is blocked without yielding any result. Therefore, the only derivations of Πwhich will not be discarded are those in which Πsimulates a derivation of Gup to some configuration h(w), w∈(T∪ {E})∗, and then applies the rules Na→aand eventually the rule E→λ, and only those, to transform h(w) into w. To show the same result for external output, it suffices to set i0to 0 and replace every rule Na→aby Na→a(a, out). Alternatively, to show the same result for external input, it suffices to set i0to 0 and replace every rule Na→a by Na→a(a, come).  In the case of P systems with internal output (without terminal filtering) and only one membrane, we can directly show the converse inclusion. Lemma 8. PsgenOtoxallP1,int (ncoo)⊆P sE0L. Proof. Let Π= (O, µ = [ ]1, w1, R1, i0= 1) be a non-cooperative P system with all objects being toxic. We construct the corresponding E0Lsystem Gas follows: Variants of P Systems with Toxic Objects 35 G= (V=O∪ {#}, T, P, w =w1), T={a∈O|there exists no rule a→u∈Rwith u∈O∗}, P=R1∪ {a→#|a∈T∪ {#}} . We immediately observe that, whenever Gintroduces a terminal symbol, it will be rewritten into a trap symbol in the next step. Thus, the only way for Gto produce a terminal string is to move from a string over V\Tto a string over Tin a single step. But this exactly corresponds to the way in which Πevolves, because rewriting a terminal ainto # in Gcorresponds to discarding the derivation of Π in which ais produced alongside non-terminals.  Corollary 1. PsgenOtoxallP1,int (ncoo) = P sE0L. Proof. The result follows from Lemma 8 in combination with Lemma 7 for the case of P systems with internal output and only one membrane.  In case of multiple membranes or terminal filtering or both, however, there is a problem: symbols that represent objects in non-output regions do not contribute to the output. Yet, since E0Lis known to be closed under arbitrary morphisms (see, e.g., [16] volume 1 page 34), the result can be strengthened as follows: Theorem 2. For all m≥1, PsE0L=PsgenOtoxallPT m,int (ncoo) =PsgenOtoxallPm,int (ncoo) =PsgenOtoxallPm,ext (ncoo) =PsautOtoxallPm(ncoo). Proof. We only have to show that any P system with internal output, eventually even with terminal extraction, or else with external output (terminal extraction need not be considered in this case, as any non-wanted symbol need not be sent out) or external input can be simulated by an E0L-system. First, we can flatten the given P system Πwith internal output to only one membrane, yet keeping in mind that then we have to use terminal extraction to obtain the results in a clean form. Hence, in this case, we simply apply the construction from Lemma 8 to the flattened P system Π0thus obtaining an E0L-system G generating a set of strings which exactly represent the multisets generated by the P system Π0. In order to obtain the original results, we have to apply a projection hTerasing all non-terminals only yielding strings/multisets over T. As E0Lis closed under arbitrary morphisms (see, e.g., [16] volume 1 page 34), from Gwe can construct an E0L-system G0directly generating the desired results. If the original P system Πused terminal extraction to a terminal alphabet Σ, we can to apply another projection from Tto Σto obtain the desired results (by constructing a corresponding E0L-system G00). 42 Artiom Alhazov, Rudolf Freund, and Sergiu Ivanov Non-cooperative P systems with all objects being toxic have been shown to be quite versatile, for example, we can easily generate {anbncn|n≥1}. Multiple problems remain open. We find particularly interesting the following ones: •Characterize PsgenOtoxcatPm,int(cat∗) and all other possible variants of restricting the set of toxic objects not yet covered by the results obtained in this paper. •There still remains the open problem how to characterize the families of sets of (vectors of) natural numbers generated by [purely] catalytic P systems with only one [two] catalyst[s]. References 1. A. Alhazov, B. Aman, R. Freund: P systems with anti-matter. In: [9], 66–85. 2. A. Alhazov, C. Ciubotaru, Yu. Rogozhin, S. Ivanov: The family of languages generated by non-cooperative membrane systems. In: Gh. P˘aun, M.J. P´erez-Jim´enez, A. Riscos-N´u˜nez, G. Rozenberg, A. Salomaa: Membrane Computing, International Conference, CMC11, Jena, Lecture Notes in Computer Science 6501, 2011, 65–79. 3. R. Alur, P. Madhusudan: Visibly pushdown languages. In: L. Babai (Ed.): Proceedings of the 36th Annual ACM Symposium on Theory of Computing, Chicago, IL, USA, June 13-16, 2004, 202–211, ACM, 2004. 4. E. Csuhaj-Varj´u, Gy. Vaszil: P automata or purely communicating accepting P systems. In: Gh. P˘aun, G. Rozenberg, A. Salomaa, C. Zandron (Eds.): Membrane Computing, International Workshop, WMC-CdeA 2002, Curtea de Arge¸s, Romania, August 19–23, 2002, Revised Papers. Lecture Notes in Computer Science 2597, Springer, 2003, 219–233. 5. R. Freund, L. Kari, M. Oswald, P. Sos´ık: Computationally universal P systems without priorities: two catalysts are sufficient. Theoretical Computer Science 330 (2), 251–266 (2005). 6. R. Freund, A. Leporati, G. Mauri, A. E. Porreca, S. Verlan, C. Zandron: Flattening in (tissue) P systems. In: A. Alhazov, S. Cojocaru, M. Gheorghe, Yu. Rogozhin, G. Rozenberg, A. Salomaa (Eds.): Membrane Computing - 14th International Conference, CMC 2013, Chi¸sin˘au, Republic of Moldova, August 20-23, 2013, Revised Selected Papers, Lecture Notes in Computer Science 8340, Springer, 2014, 173–188. 7. R. Freund, I. P´erez-Hurtado, A. Riscos-N´u˜nez , S. Verlan: A formalization of membrane systems with dynamically evolving structures. International Journal of Computer Mathematics 90 (4) (2013), 801-815. 8. R. Freund, M. Oswald: A short note on analysing P systems. Bulletin of the EATCS 78, 2002, 231–236. 9. M. Gheorghe, G. Rozenberg, A. Salomaa, P. Sos´ık, C. Zandron: 15th International Conference, CMC 2014, Prague, Czech Republic, August 20-22, 2014, Revised Selected Papers. Lecture Notes in Computer Science 8961, Springer, 2014. 10. M. L. Minsky: Computation: Finite and Infinite Machines. Prentice Hall, Englewood Cliffs, New Jersey, USA, 1967. 11. A. Okhotin, K. Salomaa: Complexity of input-driven pushdown automata. SIGACT News 45 (2), 47–67 (2014). Variants of P Systems with Toxic Objects 43 12. Gh. P˘aun: Computing with Membranes. J. Comput. Syst. Sci. 61, 108–143 (2000); also see TUCS Report 208, 1998, www.tucs.fi. 13. Gh. P˘aun: Computing with Membranes. Journal of Computer and System Sciences 61 (1) (2000), 108–143 (and Turku Center for Computer Science-TUCS Report 208, November 1998, www.tucs.fi). 14. Gh. P˘aun: Membrane Computing. An Introduction. Springer, 2002. 15. Gh. P˘aun, G. Rozenberg, A. Salomaa (Eds.): The Oxford Handbook of Membrane Computing. Oxford University Press, 2010. 16. G. Rozenberg, A. Salomaa (Eds.): Handbook of Formal Languages, 3 volumes. Springer, 1997. 17. P. Sos´ık, J. Matyˇsek: Membrane computing: when communication is enough. In: C. Calude, M. Dinneen, F. Peper (Eds.): Unconventional Models of Computation 2002, Lecture Notes in Computer Science 2509, Springer, 2002, 264–275. 18. The P Systems Website: http://ppage.psystems.eu. Extended Spiking Neural P Systems with White Hole Rules Artiom Alhazov1, Rudolf Freund2, Sergiu Ivanov3, Marion Oswald2, and Sergey Verlan3 1Institute of Mathematics and Computer Science, Academy of Sciences of Moldova Str. Academiei 5, Chi¸sin˘au, MD 2028, Moldova E-mail: [email protected] 2Faculty of Informatics, Vienna University of Technology Favoritenstr. 9, A-1040 Wien, Austria E-mail: {rudi,marion}@emcc.at 3Universit´e Paris Est, France E-mail: {sergiu.ivanov,verlan}@u-pec.fr Summary. We consider extended spiking neural P systems with the additional possibility of so-called “white hole rules”, which send the complete contents of a neuron to other neurons, and we show how this extension of the original model allow for easy proofs of the computational completeness of this variant of extended spiking neural P systems using only one actor neuron. Using only such white hole rules, we can easily simulate special variants of Lindenmayer systems. 1 Introduction Based on the biological background of neurons sending electrical impulses along axons to other neurons, several models were developed in the area of neural computation, e.g., see [15], [16], and [10]. In the area of P systems, the model of spiking neural P systems was introduced in [14]. Whereas the basic model of membrane systems reflects hierarchical membrane structures, the model of tissue P systems considers cells to be placed in the nodes of a graph. This variant was first considered in [23] and then further elaborated, for example, in [9] and [17]. In spiking neural P systems, the cells are arranged as in tissue P systems, but the contents of a cell (neuron) consists of a number of so-called spikes, i.e., of a multiset over a single object. The rules assigned to a cell allow us to send information to other neurons in the form of electrical impulses (also called spikes) which are summed up at the target cell; the application of the rules depends on the contents of the neuron and in the general case is described by regular sets. As inspired from biology, the cell sending out spikes may be “closed” for a specific time period corresponding 46 A. Alhazov et al. to the refraction period of a neuron; during this refraction period, the neuron is closed for new input and cannot get excited (“fire”) for spiking again. The length of the axon may cause a time delay before a spike arrives at the target. Moreover, the spikes coming along different axons may cause effects of different magnitude. All these biologically motivated features were included in the model of extended spiking neural P systems considered in [1], the most important theoretical feature being that neurons can send spikes along the axons with different magnitudes at different moments of time. In this paper, we will further extend the model of extended spiking neural P systems by using so-called “white hole rules”, which allow us to use the whole contents of a neuron and send it to other cells, yet eventually multiplied by some constant rational number. In the literature, several variants how to obtain results from the computations of a spiking neural P system have been investigated. For example, in [14] the output of a spiking neural P system was considered to be the time between two spikes in a designated output cell. It was shown how spiking neural P systems in that way can generate any recursively enumerable set of natural numbers. Moreover, a characterization of semilinear sets was obtained by spiking neural P system with a bounded number of spikes in the neurons. These results can also be obtained with even more restricted forms of spiking neural P systems, e.g., no time delay (refraction period) is needed, as it was shown in [13]. In [4], the generation of strings (over the binary alphabet 0 and 1) by spiking neural P systems was investigated; due to the restrictions of the original model of spiking neural P systems, even specific finite languages cannot be generated, but on the other hand, regular languages can be represented as inverse-morphic images of languages generated by finite spiking neural P systems, and even recursively enumerable languages can be characterized as projections of inverse-morphic images of languages generated by spiking neural P systems. The problems occurring in the proofs are also caused by the quite restricted way the output is obtained from the output neuron as sequence of symbols 0 and 1. The strings of a regular or recursively enumerable language could be obtained directly by collecting the spikes sent by specific output neurons for each symbol. In the extended model considered in [1], a specific output neuron was used for each symbol. Computational completeness could be obtained by simulating register machines as in the proofs elaborated in the papers mentioned above, yet in an easier way using only a bounded number of neurons. Moreover, regular languages could be characterized by finite extended spiking neural P systems; again, only a bounded number of neurons was needed. In this paper, we now extend this model of extended spiking neural P systems by also using so-called “white hole rules”, which may send the whole contents of a neuron along its axons, eventually even multiplied by a (positive) rational number. In that way, the whole contents of a neuron can be multiplied by a rational number, in fact, multiplied with or divided by a natural number. Hence, even one single neuron is able to simulate the computations of an arbitrary register machine. Extended SN P Systems with White Hole Rules 47 The idea of consuming the whole contents of a neuron by white hole rules is closely related with concept of the exhaustive use of rules, i.e., an enabled rule is applied in the maximal way possible in one step; P systems with the exhaustive use of rules can be used in the usual maximally parallel way on the level of the whole system or in the sequential way, for example, see [27] and [26]. Yet all the approaches of spiking neural P systems with the exhaustive use of rules are mainly based on the classic definitions of spiking neural P systems, whereas the spiking neural P systems with white hole rules as investigated in this paper are based on the extended model as introduced in [1]. The rest of the paper is organized as follows: In the next section, we recall some preliminary notions and definitions from formal language theory, especially the definition and some well-known results for register machines. In section 3 we recall the definitions of the extended model of spiking neural P systems as considered in [1] as well as the most important results established there. Moreover, we show a new result for extended spiking neural P systems – such systems with only one actor neuron have exactly the same computational power as register machines with only one register that can be decremented. In section 4, we define the model of extended spiking neural P systems extended by the use of white hole rules. Besides giving some examples, for instance showing how Lindenmayer systems can be simulated by extended spiking neural P systems only using white hole rules, we prove that the computations of an arbitrary register machine can be simulated by only one single neuron equipped with the most powerful variant of white hole rules. In that way we can show that extended spiking neural P systems equipped with white hole rules are even more powerful than extended spiking neural P systems, which need (at least) two neurons to be able to simulate the computations of an arbitrary register machine. Finally, in section 5 we give a short summary of the results obtained in this paper and discuss some future research topics for extended spiking neural P systems with white hole rules, for example, variants with inhibiting neurons or axons. 2 Preliminaries In this section we recall the basic elements of formal language theory and especially the definitions and results for register machines; we here mainly follow the corresponding section from [1]. For the basic elements of formal language theory needed in the following, we refer to any monograph in this area, in particular, to [5] and [25]. We just list a few notions and notations: V∗is the free monoid generated by the alphabet V under the operation of concatenation and the empty string, denoted by λ, as unit element; for any w∈V∗,|w|denotes the number of symbols in w(the length of w). N+denotes the set of positive integers (natural numbers), Nis the set of non-negative integers, i.e., N=N+∪ {0}, and Zis the set of integers, i.e., Z=N+∪ {0} ∪ −N+. The interval of non-negative integers between kand mis 48 A. Alhazov et al. denoted by [k..m], and k·N+denotes the set of positive multiples of k. Observe that there is a one-to-one correspondence between a set M⊆Nand the oneletter language L(M) = {an|n∈M}; e.g., Mis a regular (semilinear) set of non-negative integers if and only if L(M) is a regular language. By FIN Nk, REG Nk, and RE Nk, for any k∈N, we denote the sets of subsets of Nkthat are finite, regular, and recursively enumerable, respectively. By REG (REG (V)) and RE (RE (V)) we denote the family of regular and recursively enumerable languages (over the alphabet V, respectively). By ΨT(L) we denote the Parikh image of the language L⊆T∗, and by PsFL we denote the set of Parikh images of languages from a given family FL. In that sense, P sRE (V) for a k-letter alphabet Vcorresponds with the family of recursively enumerable sets of k-dimensional vectors of non-negative integers. 2.1 Register Machines The proofs of the results establishing computational completeness in the area of P systems often are based on the simulation of register machines; we refer to [18] for original definitions, and to [7] for definitions like those we use in this paper: An n-register machine is a construct M= (n, P, l0, lh),where nis the number of registers, Pis a finite set of instructions injectively labelled with elements from a given set Lab (M), l0is the initial/start label, and lhis the final label. The instructions are of the following forms: –l1: (ADD (r), l2, l3) (ADD instruction) Add 1 to the contents of register rand proceed to one of the instructions (labelled with) l2and l3. –l1: (SUB (r), l2, l3) (SUB instruction) If register ris not empty, then subtract 1 from its contents and go to instruction l2, otherwise proceed to instruction l3. –lh:halt (HALT instruction) Stop the machine. The final label lhis only assigned to this instruction. A (non-deterministic) register machine Mis said to generate a vector (s1,· · · , sβ) of natural numbers if, starting with the instruction with label l0and all registers containing the number 0, the machine stops (it reaches the instruction lh:halt) with the first βregisters containing the numbers s1,· · · , sβ(and all other registers being empty). Without loss of generality, in the succeeding proofs we will assume that in each ADD instruction l1: (ADD (r), l2, l3) and in each SUB instruction l1: (SUB (r), l2, l3) the labels l1, l2, l3are mutually distinct (for a short proof see [9]). The register machines are known to be computationally complete, equal in power to (non-deterministic) Turing machines: they generate exactly the sets of vectors of non-negative integers which can be generated by Turing machines, i.e., the family PsRE. Extended SN P Systems with White Hole Rules 49 Based on the results established in [18], the results proved in [7] and [8] immediately lead to the following result: Proposition 1. For any recursively enumerable set L⊆Nβof vectors of nonnegative integers there exists a non-deterministic (β+ 2)-register machine Mgenerating Lin such a way that, when starting with all registers 1to β+2 being empty, Mnon-deterministically computes and halts with niin registers i, 1≤i≤β, and registers β+ 1 and β+ 2 being empty if and only if (n1, ..., nβ)∈L. Moreover, the registers 1to βare never decremented. When considering the generation of languages, we can use the model of a register machine with output tape, which also uses a tape operation: –l1: (write (a), l2) Write symbol aon the output tape and go to instruction l2. We then also specify the output alphabet Tin the description of the register machine with output tape, i.e., we write M= (n, T, P, l0, lh). The following result is folklore, too (e.g., see [18] and [6]): Proposition 2. Let L⊆T∗be a recursively enumerable language. Then Lcan be generated by a register machine with output tape with 2registers. Moreover, at the beginning and at the end of a successful computation generating a string w∈L both registers are empty, and finally, only successful computations halt. 3 Extended Spiking Neural P Systems The reader is supposed to be familiar with basic elements of membrane computing, e.g., from [21] and [24]; comprehensive information can be found on the P systems web page [28]. Moreover, for the motivation and the biological background of spiking neural P systems we refer the reader to [14]. The definition of an extended spiking neural P system is mainly taken from [1], with the number of spikes kstill be given in the “classical” way as ak; later on, we simple will use the number k itself only instead of ak. 3.1 The Definition of ESNP Systems The definitions given in the following are taken from [1]. Definition 1. An extended spiking neural P system (of degree m≥1) (in the following we shall simply speak of an ESNP system) is a construct Π= (m, S, R) where 50 A. Alhazov et al. •mis the number of cells (or neurons); the neurons are uniquely identified by a number between 1and m(obviously, we could instead use an alphabet with msymbols to identify the neurons); •Sdescribes the initial configuration by assigning an initial value (of spikes) to each neuron; for the sake of simplicity, we assume that at the beginning of a computation we have no pending packages along the axons between the neurons; •Ris a finite set of rules of the form i, E/ak→P;dsuch that i∈[1..m] (specifying that this rule is assigned to cell i), E⊆REG ({a})is the checking set (the current number of spikes in the neuron has to be from Eif this rule shall be executed), k∈Nis the “number of spikes” (the energy) consumed by this rule, dis the delay (the “refraction time” when neuron iperforms this rule), and Pis a (possibly empty) set of productions of the form (l, w, t)where l∈[1..m](thus specifying the target cell), w∈ {a}∗is the weight of the energy sent along the axon from neuron ito neuron l, and tis the time needed before the information sent from neuron iarrives at neuron l(i.e., the delay along the axon). If the checking sets in all rules are finite, then Πis called a finite ESNP system. Definition 2. Aconfiguration of the ESNP system is described as follows: •for each neuron, the actual number of spikes in the neuron is specified; •in each neuron i, we may find an “activated rule” i, E/ak→P;d0waiting to be executed where d0is the remaining time until the neuron spikes; •in each axon to a neuron l, we may find pending packages of the form (l, w, t0) where t0is the remaining time until |w|spikes have to be added to neuron l provided it is not closed for input at the time this package arrives. Atransition from one configuration to another one now works as follows: •for each neuron i, we first check whether we find an “activated rule” i, E/ak→P;d0waiting to be executed; if d0= 0, then neuron i“spikes”, i.e., for every production (l, w, t)occurring in the set Pwe put the corresponding package (l, w, t)on the axon from neuron ito neuron l, and after that, we eliminate this “activated rule” i, E/ak→P;d0; •for each neuron l, we now consider all packages (l, w, t0)on axons leading to neuron l; provided the neuron is not closed, i.e., if it does not carry an activated rule i, E/ak→P;d0with d0>0, we then sum up all weights win such packages where t0= 0 and add this sum of spikes to the corresponding number of spikes in neuron l; in any case, the packages with t0= 0 are eliminated from the axons, whereas for all packages with t0>0, we decrement t0by one; •for each neuron i, we now again check whether we find an “activated rule” i, E/ak→P;d0(with d0>0) or not; if we have not found an “activated rule”, we now may apply any rule i, E/ak→P;dfrom Rfor which the current number of spikes in the neuron is in Eand then put a copy of this rule as “activated rule” for this neuron into the description of the current configuration; on the other hand, if there still has been an “activated rule” i, E/ak→P;d0in the Extended SN P Systems with White Hole Rules 51 neuron with d0>0, then we replace d0by d0−1and keep i, E/ak→P;d0−1 as the “activated rule” in neuron iin the description of the configuration for the next step of the computation. After having executed all the substeps described above in the correct sequence, we obtain the description of the new configuration. A computation is a sequence of configurations starting with the initial configuration given by S. A computation is called successful if it halts, i.e., if no pending package can be found along any axon, no neuron contains an activated rule, and for no neuron, a rule can be activated. In the original model introduced in [14], in the productions (l, w, t) of a rule i, E/ak→ {(l, w, t)};d, only w=a(for spiking rules) or w=λ(for forgetting rules) as well as t= 0 was allowed (and for forgetting rules, the checking set E had to be finite and disjoint from all other sets Ein rules assigned to neuron i). Moreover, reflexive axons, i.e., leading from neuron ito neuron i, were not allowed, hence, for (l, w, t) being a production in a rule i, E/ak→P;dfor neuron i,l6=iwas required. Yet the most important extension is that different rules for neuron imay affect different axons leaving from it whereas in the original model the structure of the axons (called synapses there) was fixed. In [1], the sequence of substeps leading from one configuration to the next one together with the interpretation of the rules from Rwas taken in such a way that the original model can be interpreted in a consistent way within the extended model introduced in that paper. As mentioned in [1], from a mathematical point of view, another interpretation would have been even more suitable: whenever a rule i, E/ak→P;d is activated, the packages induced by the productions (l, w, t) in the set Pof a rule i, E/ak→P;dactivated in a computation step are immediately put on the axon from neuron ito neuron l, whereas the delay donly indicates the refraction time for neuron iitself, i.e., the time period this neuron will be closed. The delay t in productions (l, w, t) can be used to replace the delay in the neurons themselves in many of the constructions elaborated, for example, in [14], [23], and [4]. Yet as in (the proofs of computational completeness given in) [1], we shall not need any of the delay features in this paper, hence we need not go into the details of these variants of interpreting the delays in more details. Depending on the purpose the ESNP system is to be used, some more features have to be specified: for generating k-dimensional vectors of non-negative integers, we have to designate kneurons as output neurons; the other neurons then will also be called actor neurons. There are several possibilities to define how the output values are computed; according to [14], we can take the distance between the first two spikes in an output neuron to define its value. As in [1], also in this paper, we take the number of spikes at the end of a successful computation in the neuron as the output value. For generating strings, we do not interpret the spike train of a single output neuron as done, for example, in [4], but instead consider the sequence of spikes in the output neurons each of them corresponding to a specific terminal symbol; if more than one output neuron spikes, we take any permutation of the corresponding symbols as the next substring of the string to be generated. 58 A. Alhazov et al. is also bounded, i.e., even with allowing the use of white hole rules, the following lemma as a counterpart of Lemma 1 is still valid: Lemma 4. For any EESNP system where during any computation only a bounded number of spikes occurs in the actor neurons, the generated language is regular. Hence, in the following our main interest is in EESNPS which really make use of the whole power of white hole rules. 4.1 Examples for EESNPS EESNPS can also be used for computing functions, not only for generating sets of (vectors of) integer numbers. As a simple example, we show how the function n7→ 2n+1 can be computed by a deterministic EESPNS, which only has exactly one rule in each of its two neurons; the output neuron 2 in this case is not free of rules. Example 2. Computing n7→ 2n+1 (1,N+/1→ {(2,1)}) 1 (2,2·N++ 1/all → {(2,(all −1) ·2)}) 2 Initial value = nInitial value = 2 The rule (2,2·N++ 1/all → {(2,(all −1) ·2)}) could also be written as (2,2·N++ 1/all → {(2,(all)·2−2)}). In both cases, starting with the input number n(of spikes) in neuron 1, with each decrement in neuron 1, the contents of neuron 2 (not taking into account the enabling spike from neuron 1) is doubled. The computation stops with 2n+1 in neuron 1, as with 0 in neuron 1 no enabling spike is sent to neuron 2 any more, hence, the firing condition is not fulfilled any more. We finally remark that with the initial value 1 in neuron 2 we can compute the function n7→ 2n. Example 3. Pure White Hole Model of EESNPS for DT0L Systems Let G= ({a}, P, as) be a Lindenmayer system with the axiom asand the finite set of tables Peach containing a finite set of parallel productions of the form a→ak. Such a system is called a tabled Lindenmayer system, abbreviated T0Lsystem, and it is called deterministic, abbreviated DT0Lsystem, if each table contains exactly one rule. Now let G= ({a}, P, as) be a DT 0Lsystem with P=a→aki|1≤i≤n. Then the following EESNPS using only white hole rules computes the same set of natural numbers as are represented by the language generated by G, with the results being taken with unconditional halting, i.e., taking a result at every moment (see [2]). {(1,N+/all → {(1, all ·ki)})|1≤i≤n} 1 Initial value = s Extended SN P Systems with White Hole Rules 59 If we want to generate with normal halting, we have to add an additional output neuron 2 and an additional rule {(1,N+/all → {(2, all ·1)})}in neuron 1 which at the end moves the contents of neuron 1 to neuron 2. 4.2 Universality with EESNPS Lemma 5. The computation of any register machine can be simulated in only one single actor neuron of an EESPNS. Proof. Let M= (n, P, l0, lh) be an n-register machine, where nis the number of registers, Pis a finite set of instructions injectively labelled with elements from a set of labels Lab (M), l0is the initial label, and lhis the final label. Then we can effectively construct an EESNPS Π= (m, S, R) simulating the computations of Mby encoding the contents niof each register i, 1 ≤i≤n, as pni ifor different prime numbers pi. Moreover, for each instruction (label) jwe take a prime number qj, of course, also each of them being different from each other and from the pi. The instructions are simulated as follows: –l1: (ADD (r), l2, l3) (ADD instruction) This instruction can be simulated by the rules {(1, ql1·N+/all → {(1, all ·qlipr/ql1)})|2≤i≤3} in neuron 1. –l1: (SUB (r), l2, l3) (SUB instruction) This instruction can be simulated by the rules (1, ql1pr·N+/all → {(1, all ·ql2/(ql1pr))}) and (1, ql1·N+\ql1pr·N+/all → {(1, all ·ql2/ql1)}) in neuron 1; the first rule simulates the decrement case, the second one the zero test. –lh:halt (HALT instruction) This instruction can be simulated by the rule (1, qlh·N+/all → {(1, all ·1/qlh)}) in neuron 1. In fact, after the application of the last rule, we end up with pm1 1· · · pmn nin neuron 1, where (m1,· · · , mn) is the vector computed by Mand now, in the prime number encoding, by Πas well. All the checking sets we use are regular, and the productions in all the white hole rules even again yield integer numbers. ut Remark 2. As the productions in all the white hole rules of the EESNPS constructed in the preceding proof even again yield integer numbers, we could also interpret this EESNPS as an ESPNS with exhaustive use of rules: The white hole rules in the EESNPS constructed in the previous proof are of the general form 60 A. Alhazov et al. (1, q ·N+/all → {(1, all ·p/q)}) with pand qbeing natural numbers. Each of these rules can be simulated in a one-to-one manner by the rule (1, q ·N+/q →p) used in an ESNPS with one neuron in the exhaustive way. Theorem 3. Any recursively enumerable set of n-dimensional vectors can be generated by an ESNP system with n+ 1 neurons. Proof. We only have to show how to extract the results into the additional output neurons from the single actor neuron which can do the whole computational task as exhibited in Lemma 5. Yet this is pretty easy: When the actor neuron reaches the halting state, the desired result mifor output neuron i+ 1 is stored as factor in this one number stored in the actor neuron within the prime number encoding, i.e., as qmi i, for 1 ≤i≤n. Instead of using the final rule (1, qlh·N+/all → {(1, all ·1/qlh)}) in neuron 1 we now take the rule (1, qlh·N+/all → {(1, all ·r1/qlh)}). With the rules (1, riqiN+/all → {(1, all ·1/ki),(i+ 1,1)}),we can decode the factor qmi ito miinto output neuron i+ 1, with the instruction code (prime number) rifor 1 ≤i≤n. If the contents of the actor neuron is not dividable by qiany more, we switch to the next instruction code ri+1 by the rule (1, ri·N+\riqi·N+/all → {(1, all ·ri+1/ri)}). At the end, we can end up with 0 in the actor neuron after having used the rule (1, ri·N+\riqi·N+/all → ∅) and then stop with miin output neuron i+ 1, 1 ≤i≤n.ut Theorem 4. Any recursively enumerable language Lwith L⊆T∗for a terminal alphabet Twith card (T) = ncan be generated by an ESNP system with n+ 1 neurons. Proof. In the case of generating strings, we have to simulate a register machine with output tape; hence, in addition to the simulating rules already described in Lemma 5, we have to simulate the tape rule l1: (write (a), l2), which in the EESNPS means sending one spike to the output neuron N(a) representing the symbol a. This task is accomplished by the rule (1, l1·N+/all → {(1, all ·l2/l1),(N(a),1)}). The rest of the construction and of the proof is similar to that what we have done in the proof of Lemma 5. ut 5 Summary and Further Variants In this paper, we have extended the model of extended spiking neural P systems from [1] by white hole rules. With this new variant of extended spiking neural P systems, computational completeness can already be obtained with only one actor neuron, as the computations of any register machine can already be simulated in only one neuron equipped with the most general variant of white hole rules. Using Extended SN P Systems with White Hole Rules 61 this single actor neuron to also extract the final result of a computation, we even obtain weak universality with only one neuron. A quite natural feature found in biology and also already used in the area of spiking neural P systems is that of inhibiting neurons or axons between neurons, i.e., certain connections from one neuron to another one can be specified as inhibiting ones – the spikes coming along such inhibiting axons then close the target neuron for a time period given by the sum of all inhibiting spikes, e.g., see [3]. Such variants can also be considered for extended spiking neural P systems with white hole rules. References 1. A. Alhazov, R. Freund, M. Oswald, M. Slavkovik: Extended spiking neural P systems. In: [11], 123–134. 2. M. Beyreder, R. Freund: Membrane systems using noncooperative rules with unconditional halting. In: D. W. Corne, P. Frisco, Gh. P˘aun, G. Rozenberg, A. Salomaa (Eds.): Membrane Computing. 9th International Workshop, WMC 2008, Edinburgh, UK, July 28-31, 2008, Revised Selected and Invited Papers. Lecture Notes in Computer Science 5391, Springer, 2009, 129–136. 3. A. Binder, R. Freund, M. Oswald, L. Vock: Extended spiking neural P systems with excitatory and inhibitory astrocytes. In: M.A. Guti´errez-Naranjo, Gh. P˘aun, A. Romero-Jim´enez, A. Riscos-N´u˜nez (Eds.): Fifth Brainstorming Week on Membrane Computing, RGNC REPORT 01/2007, Research Group on Natural Computing, Sevilla University, F´enix Editora, 2007, 63–72. 4. H. Chen, R. Freund, M. Ionescu, Gh. P˘aun, M.J. P´erez-Jim´enez: On string languages generated by spiking neural P systems. In: [11], 169–194 5. J. Dassow, Gh. P˘aun: Regulated Rewriting in Formal Language Theory. Springer, 1989. 6. H. Fernau, R. Freund, M. Oswald, K. Reinhardt: Refining the nonterminal complexity of graph-controlled, programmed, and matrix grammars. Journal of Automata, Languages and Combinatorics,12 (1-2) (2007), 117–138. 7. R. Freund, M. Oswald: P systems with activated/prohibited membrane channels. In: Gh. P˘aun , G. Rozenberg, A. Salomaa, C. Zandron (Eds.): Membrane Computing. International Workshop WMC 2002, Curtea de Arge¸s, Romania. Lecture Notes in Computer Science 2597, Springer, Berlin, 2002, 261–268. 8. R. Freund, Gh. P˘aun: From regulated rewriting to computing with membranes: collapsing hierarchies. Theoretical Computer Science 312, 143–188. 9. R. Freund, Gh. P˘aun, M.J. P´erez-Jim´enez: Tissue-like P systems with channel states. Theoretical Computer Science 330 (2004), 101–116. 10. W. Gerstner, W. Kistler: Spiking Neuron Models. Single Neurons, Populations, Plasticity. Cambridge Univ. Press, 2002. 11. M.A. Guti´errez-Naranjo, Gh. P˘aun, A. Riscos-N´u˜nez, F.J. Romero-Campero (Eds.): Fourth Brainstorming Week on Membrane Computing, Vol. I RGNC REPORT 02/2006, Research Group on Natural Computing, Sevilla University, F´enix Editora, 2006. 62 A. Alhazov et al. 12. M.A. Guti´errez-Naranjo, Gh. P˘aun, A. Riscos-N´u˜nez, F.J. Romero-Campero (Eds.): Fourth Brainstorming Week on Membrane Computing, Vol. II RGNC REPORT 02/2006, Research Group on Natural Computing, Sevilla University, F´enix Editora, 2006. 13. O.H. Ibarra, A. P˘aun, Gh. P˘aun Gh, A. Rodr´ıguez-Pat´on, P. Sos´ık, S. Woodworth: Normal forms for spiking neural P systems. In: [12], 105–136, 2006. 14. M. Ionescu, Gh. P˘aun, T. Yokomori: Spiking neural P systems. Fundamenta Informaticae 71 (2 –3) (2006), 279–308. 15. W. Maass: Computing with spikes. Special Issue on Foundations of Information Processing of TELEMATIK 8(1) (2002), 32–36. 16. W. Maass, C. Bishop (Eds.): Pulsed Neural Networks. MIT Press, Cambridge, 1999. 17. Mart´ın-Vide C, Pazos J, P˘aun Gh, Rodr´ıguez-Pat´on A (2002) A new class of symbolic abstract neural nets: Tissue P systems. In: Proceedings of COCOON 2002, Singapore, Lecture Notes in Computer Science 2387, Springer-Verlag, Berlin, 290–299 18. M. L. Minsky: Computation: Finite and Infinite Machines. Prentice Hall, Englewood Cliffs, New Jersey, USA, 1967. 19. L. Pan, Gh. P˘aun: Spiking Neural P Systems with Anti-Matter. International Journal of Computers, Communications & Control 4(3), 273–282 (2009). 20. Gh. P˘aun: Computing with Membranes. Journal of Computer and System Sciences 61 (1) (2000), 108–143 (and Turku Center for Computer Science-TUCS Report 208, November 1998, www.tucs.fi). 21. Gh. P˘aun: Membrane Computing. An Introduction. Springer, 2002. 22. P˘aun Gh, M.J. P´erez-Jim´enez, G. Rozenberg: Spike trains in spiking neural P systems. Intern. J. Found. Computer Sci. 17 (2006), 975–1002. 23. Gh. P˘aun, Y. Sakakibara, T. Yokomori: P systems on graphs of restricted forms. Publicationes Mathematicae Debrecen 60 (2006), 635–660. 24. Gh. P˘aun, G. Rozenberg, A. Salomaa (Eds.): The Oxford Handbook of Membrane Computing. Oxford University Press, 2010. 25. G. Rozenberg, A. Salomaa (Eds.): Handbook of Formal Languages, 3 volumes. Springer, 1997. 26. X. Zhang, B. Luo, X. Fang, L. Pan: Sequential spiking neural P systems with exhaustive use of rules. BioSystems 108 (2012), 52–62. 27. X. Zhang, X. Zeng, L. Pan: On String Languages Generated by Spiking Neural P Systems with Exhaustive Use of Rules. Natural computing 7(4) (2002), 535–549. 28. The P Systems Website: www.ppage.psystems.eu. Simulating Membrane Systems and Dissolution in a Typed Chemical Calculus Bogdan Aman1, P´eter Batty´anyi2, Gabriel Ciobanu1, and Gy¨orgy Vaszil2 1Romanian Academy, Institute of Computer Science Blvd. Carol I no.8, 700505 Ia¸si, Romania [email protected] [email protected] 2Department of Computer Science, Faculty of Informatics University of Debrecen Kassai ´ut 26, 4028 Debrecen, Hungary [email protected] [email protected] Summary. We present a transformation of membrane systems, possibly with promoter/inhibitor rules, priority relations, and membrane dissolution, into formulas of the chemical calculus such that terminating computations of membranes correspond to terminating reduction sequences of formulas and vice versa. In the end, the same result can be extracted from the underlying computation of the membrane system as from the reduction sequence of the chemical term. The simulation takes place in a typed chemical calculus, but we also give a short account of the untyped case. 1 Introduction In the present paper we continue the investigations started in [2, 3] concerning the possibility of defining the semantics of membrane systems with rewriting logic [1, 2] in order to obtain a logical description of membrane system computations. The direct precedent of our work is [7] where a logical description of simple membrane systems was given using the γ-calculus of Banˆatre and Le M´etayer from [6] (see also [4] for more details). Their aim was to free the expression of algorithms from the sequentiality which is not inherently present in the problem to be solved, that is, the sequentiality which is implied by the structure of the computational model on which the given algorithm is to be performed. They called their calculus chemical calculus, and the underlying computational paradigm the chemical paradigm of computation while the execution model behind them closely resembles the way chemical reactions take place in chemical solutions. A chemical “machine” can be thought of as a symbolic chemical solution where data can be seen as molecules and operations as chemical reactions. If some molecules satisfy a reaction condition, they are replaced by the result of the reaction. If no reaction is possible, the program terminates. Chemical solutions are represented by multisets. Molecules interact freely according to reaction rules which results in an implicitly parallel, non-deterministic, distributed model. In what follows, using a slightly modified variant of the operational semantics of membrane systems presented in [3], we show how to transform a membrane system 64 B. Aman et al. with rules using promoters/inhibitors (see [8]), priorities, and also the possibility of membrane dissolution (introduced already in [9]), into formulas of the chemical calculus, such that terminating computations of the membrane system correspond to terminating reduction sequences of formulas and vice versa. 2 Preliminaries In this section we present the basic notions and notations we are going to use. For a comprehensive treatment of membrane systems ranging from the basic definitions to their computational power, see the the monographs [10, 11], for more information on the chemical calculus, we refer to [4, 5]. A finite multiset over an alphabet Vis a mapping m:V→Nwhere Ndenotes the set of non-negative integers, and m(a) for a∈Vis said to be the multiplicity of ain V. We say that m1⊆m2if for all a∈V,m1(a)≤m2(a). The union or sum of two multisets over Vis defined as (m1+m2)(a) = m1(a) + m2(a), the difference is defined for m2⊆m1as (m1−m2)(a) = m1(a)−m2(a) for all a∈V. The multiset mcan also be represented by any permutation of a string w=am(a1) 1am(a2) 2. . . am(an) n∈V∗, where if m(x)6= 0, then there exists j, 1≤j≤n, such that x=aj. The set of all finite multisets over an alphabet Vis denoted by M(V), the empty multiset is denoted by ∅as in the case of the empty set. 2.1 Membrane systems A membrane system, or P system is a structure of hierarchically embedded membranes, each having a label and enclosing a region containing a multiset of objects and possibly other membranes. The unique out-most membrane is called the skin membrane. The membrane structure is denoted by a sequence of matching parentheses where the matching pairs have the same label as the membranes they represent. We assume the membranes are labelled by natural numbers {1, . . . , n}, and we use the notation mifor the membrane with label i. Each membrane mi, except for the skin membrane, has its parent membrane, which we denote by µ(mi). As an abuse of notation µstands for both the membrane structure and both for the function determining the parent membrane of a membrane. To facilitate presentation we assume that µ(mj) = miimplies i < j. The evolution of the contents of the regions of a P system is described by rules associated to the regions. The system performs a computation by passing from one configuration to another one, applying the rules synchronously in each region. In the variant we consider in this paper, the rules are multiset rewriting rules given in the form of u→vwhere u, v are multisets, and they are applied in the maximal parallel manner, that is, as many rules are applied in each region as possible. The end of the computation is defined by the following halting condition: A P system halts when no more rules can be applied in any of the regions; the result is a number, the number of objects in a membrane labelled as output. AP system of degree n≥1 is a construct Π= (O, µ, w1, . . . , wn, R1, . . . , Rn, ρ1, . . . , ρn) where Simulating P Systems and Dissolution in a Typed Chemical Calculus 65 -Ois an alphabet of objects, -µis a membrane structure of nmembranes, -wi∈ M(O),1≤i≤n, are the initial contents of the nregions, -Ri,1≤i≤n, are the sets of evolution rules associated to the regions; they are of the form u→vwhere u∈ M(O) and v∈ M(O×tar) where tar = {here, out}∪{inj|1≤j≤n}, and -ρ1, . . . , ρnare the priority rules associated with membranes m1, . . . , mn. The evolution rules of the system are applied in the non-deterministic, maximally parallel manner to the n-tuple of multisets of objects constituting the configuration of the system. A configuration is the sequence C= (v1,...vn, µC) where vi∈O∗,1≤i≤nare the contents of the membranes, and µCis the current membrane structure. For two configurations C1= (u1, . . . , un, µC1) and C2= (v1, . . . , vn, µC2), we can obtain C2from C1, denoted as C1⇒C2, by applying the rules of R1, . . . , Rn. Let R=R1∪R2∪· · · ∪Rn, where Ri={ri1, . . . , riki} is the set of rules corresponding to membrane mi. The application of u→v∈Ri in the region imeans to remove the objects of ufrom uiand add the new objects specified by vto the system. The rule application in each region takes place in a non-deterministic and maximally parallel manner. This means that the rule application phase finishes, if no rule can be applied anymore in either region. As a result, each region where rule application took place, is possibly supplied with elements of the set O×tar. We call a configuration which is a multiset over O∪O×tar an intermediate configuration. If we want to emphasize that C= (w1, . . . , wn, µ) consists of multisets over O, we say that Cis a proper configuration. Rule applications can be preceded by priority check, if priority relations are present. Let ρi⊆Ri×Ri1≤i≤nbe the (possibly empty) priority relations. Then r∈Riis applicable only if no r0∈Rican be applied with (r0, r)∈ρi. We may also denote the relation (r0, r)∈ρiby r0> r. In the next phase the objects coming from vshould be added to the regions as specified by the target indicators associated to them. If vcontains a pair (a, here)∈ O×tar, then ais placed in region i, the region where the rule is applied. If v contains (a, out)∈O×tar, then ais added to the contents of the parent region of region i; if vcontains (a, inj)∈O×tar for some region jwhich is contained inside the region i(so region iis the parent region of region j), then ais added to the contents of region j. The symbol δmarks a region for dissolution. When it is introduced in the membrane by a rule, after having finished the maximal parallel and communication steps, the actual membrane disappears. Its objects move to the parent membrane and its rules can not be applied anymore. We can render promoter/inhibitor sets, prom/inhib, to each rule r= (u→ v)∈ Ri. The promoter/inhibitor sets belonging to rare subsets of O. When r is going to be applied they act as follows: rcan be applied to the content wiof membrane mionly if every element of prom is present in wand no element of inhib can be found in w. 2.2 The chemical calculus We give a brief summary of the chemical calculus following the presentation in [4] and [5]. Chemical programming is the formal equivalent of Gamma programming, which is a higher order multiset manipulating program language. Like Gamma 66 B. Aman et al. programming, the chemical calculus is also based on the chemical metaphor: data are represented by γ-terms, which are called molecules, and reactions between them are represented by rewrite rules. We begin with the basic definitions. The syntactical elements of molecules, reaction conditions, and patterns, denoted by M, C and P, respectively, are defined as follows. M:= x|(M1, M2)| hMi | γ(P)[C].M where xis a variable standing for any molecule, (M1, M2) is a compound molecule built with the commutative and associative “,” constructor operator, hMiis called a solution, and γ(P)[C].M is called a γ-abstraction with pattern P, reaction condition C, result M. The γ-abstraction encodes a rewriting rule: when the pattern Pis respected and the condition Cis met, a substituted variant of Mis created as a result. A pattern is P:= x|(P1, P2)| hPi, where xmatches any molecule, (P1, P2) matches a compound molecule, and hPi matches an inert solution, that is, a solution where no reaction can occur: it consists entirely of solutions or entirely of γ-abstractions. (The contained solutions can still be active, however.) The solution hMiencapsulates the molecule Mwhich is inside the solution, and thus, insulated from molecules outside the solution. The contents of solutions can only be changed by reactions which occur inside the solution. Now we define how patterns are matched, which requires the notion of substitution. A substitution is a mapping φfrom the set of variables to the set of molecules. We can define the application of a substitution to as follows: φx =φ(x) φ(M1, M2) = φM1, φM2 φhMi=hφMi φ(γ(P)[C].M) = γ(P)[C].φ0M, where φ0is obtained from φby removing from the domain all the variables which occur in P. The result of a match is an assignment of molecules to variables. The first argument of match is a pattern, the second one is a molecule, its value is a substitution. Let xdenote a variable, Pa pattern, and Ma molecule. Then we define match(x, M) = {x7→ M} match((P1, P2),(M1, M2)) = match(P1, M1)◦match(P2, M2) match(hPi,hMi) = match(P, M) provided inert(M) match(P, M) = fail in every other case, where ◦denotes the operation of function composition. The reaction rule is defined as γ(P)[C].M, N →φM, where match(P, N) = φassigns values to variables in such a way that φ(C) holds in the typed case or reduces to true in the untyped case. In this case true can be a special constant defined in advance, for example, true γhxi[x].x. Simulating P Systems and Dissolution in a Typed Chemical Calculus 67 We can define an operator replace (cf. [5]) which does not vanish in the course of the reduction: replace P by M if C let rec f =γ(P)[C].M, f in f. Then the new operator obeys the following reduction rule: replace P by M if C, N →replace P by M if C, φ(M), where match(P, N) = φand either φ(C) is true or it reduces to true. At this point we should mention that the simulation takes place in the typed γcalculus ([5]), because it is more convenient to talk about equality and comparison of integer values, than to check whether the conditional part of an untyped γexpression reduces to true (which is, in fact, undecidable in the general case). We could, however, restrict the γ-expressions taking part in the simulation in such a way that their conditional parts form a fragment of the γ-calculus that is decidable with respect to equality. (We can take, e. g., the γ-calculus equivalents of Church numerals and define Boolean operations on them.) 3 Results First we introduce molecules for the description of membrane system configurations. Notation 1 Let [x, y]=(hxi, y), and [x1, . . . , xn, xn+1] = [[x1, . . . , xn], xn+1]. Remark 1. Let P= [x1, x2, . . . , xl] be a pattern in the sense of the previous section, and M= [s1, s2, . . . , sl], where s1, . . . ,slare arithmetical expressions, i.e. expressions composed of natural numbers, variables and arithmetical operations. If we assume that none of the xiappears among the free variables of s1, . . . , sl, then match(P, M) = Φ6=fail implies Φ= [x1/s1, x2/s2, . . . , xl/sl], where Φis the simultaneous substitution formed by the substitutions [x1/s1],...,[xl/sl]. In other words, in this special case, the molecule [x1, x2, . . . , xl] behaves as an ordered tuple. If we use a,bas variables for elements of Oand ras a rule variable, respectively, then we say that a rule r=u→v∈Riis valid with respect to the configuration (w1, . . . , wn, µ) if the following conditions hold: 1. membrane structure µcontains membrane mi, 2. (∀a∈promr) (wi(a)≥1), 3. (∀a∈inhibr) (wi(a) = 0), and 4. (∀a∈O)(∀1≤j≤n) (v(a, inj)≥1) implies that µcontains the membrane mj(mjis not dissolved) and µ(mj) = mi, namely miis the parent membrane of mj. where promr⊆Oand inhibr⊆Odenotes the set of promoters and inhibitors associated to rule r, respectively. A description of a membrane system configuration as above is a molecule of the form 74 B. Aman et al. Lemma 2. (1) Let C0⇒∗ msg C00, and assume that C00 is msg-irreducible. Then M(C0,2) →Msg M(C00,2). (2) Conversely, assume M(C0,2) →Msg M00. Then there is C00 such that C0⇒msg C00,C00 is msg-irreducible, and M00 =M(C00,1). Proof. We prove by induction on the number of steps in C⇒msg C0that, for every 1 ≤i≤nand 1 ≤j≤k, Descrµ(C)cij +Descrµ(C)cij =Descrµ(C0)cij +Descrµ(C0)cij .(3) To this end, we show that, if C→msg C0and C= (µ, w1, . . . , wn) and C= (µ, w0 1, . . . , w0 n), then wi(aj) + wi(aj, here) + X p6=i wp(aj, ini) + X µ(p)=i wp(aj, out) = (4) w0 i(aj) + w0 i(aj, here) + X p6=i w0 p(aj, ini) + X µ(p)=i w0 p(aj, out). We treat Point 2 of Definition 5, the remaining cases can be handled similarly. Let C⇒msg C0by Point 2 of Definition 5. Assume wi(aj, inl)>0. Let us consider only the case i=lin Equation 4, since for all the other cases the equation trivially holds. But in this case the left hand side contains wl(aj)+wi(aj, inl), and the right hand side contains the corresponding w0 l(aj)+w0 i(aj, inl), which, by definition, are equal. (⇒)Let C⇒msg C0, assume that C0is msg-irreducible. A msg-irreducible P system with the Skin membrane as the outermost membrane contains no messages, thus, by Equation 3, M(C, 2) →Msg M(C0,2). (⇐)Let M(C, 2) →Msg N0. Then, by Claim 3, N0=M(D0,2) for some description D0. Let C⇒msg C0such that C0is msg-irreducible. Then C0is message free, which, by Equation 4, entails D0=Descrµ(C0).  Now, following [1], we define the skeleton of a configuration (µ, w1, . . . , wn) as U0= (u0 1, . . . , u0 n), where u0 i=∗, if membrane iis dissolved or under dissolution (that is, ui(δ) = 1 and i6=Skin) and u0 i= 0 otherwise. Let µ0(i) = i, µj(i) = µ(µj−1(i)) for j > 0. Let µU0(i) = min{j|µk(i) = j∧u0 j6=∗ ∧ u0(µl(i)) = ∗for 0 ≤l≤k−1}. That is, µU0(i) is the smallest membrane containing membrane iwhich exists or does not disappear. Let C0⇒δC00, assume w0 l(δ) = 1 for at least one membrane ml. We define the effect of the dissolution rule as follows: (µ0, w0 1, . . . , w0 n)⇒δ (µ00, w00 1, . . . , w00 n), where w00 i=∗provided u0 i=∗, and w00 i(aj) = w0 i(aj) + P{w0 l(aj)|µU0(l) = i, w0 l(δ)=1}, if u0(i) = 0. Lemma 3. (1) If C0⇒δC00, then M(C0,3) →∗ Dis M(C00,3). (2) Conversely, assume that M(C0,3) →∗ Dis M00, and M00 is Dis-irreducible. Then there exists a proper configuration C00 with C0⇒δC00 and M00 =M(C00,3). Simulating P Systems and Dissolution in a Typed Chemical Calculus 75 Proof. (1) Let C0= (µ, w0 1, . . . , w0 n)⇒δC00, and assume that w0 i(δ) = 1. Then bM(C0,3)cdi= 1. Let bM(C0,3)ccij >1 for some 1 ≤j≤k. Then M(C0,3) →Disi M([disi(Descrµ(C0)),3]). Let p=µU0(i), where U0is the skeleton of C0. Let D0= Descrµ(C0) and D00 =disi(Descrµ(C0)). Let us denote by D0 cij and D00 cij the values of the descriptions pertaining to the coordinates (i, j). It follows immediately, by Definition 3, that D0 cpj +X{D0 clj |µU0(l) = p, D0 dl= 1}= (5) D00 cpj +X{D00 clj |µU0(l) = p, D00 dl= 1}. In other words, for every 1 ≤j≤k, the sums of the occurrences of elements aj in the dissolved or to be dissolved descendants of membrane mpplus the multiplicity of ajin mpremain the same at a dissolution step in the chemical calculus. Let M(C0,3) →Dis M([D, 3]) such that M([D, 3]) is irreducible with respect to Dis. Then Ddi= 1 implies Dcij = 0, which, by Equation 5, involves that D=Descrµ(C00). (2) Let M(C0,3) →∗ Dis M00. By Claim 3, there exists a description D00 such that M00 =M([D00,3]). Since M00 is Dis irreducible, D00 di= 1 implies D00 cij = 0. This means, there is a proper configuration C00 such that Descrµ(C00) = D00. Assume w0 s(δ) = 1 holds in C0. Let D0=Descrµ(C0). Let U0be the skeleton of D0and p=µU0(s). Since M00 is Dis irreducible, Equation 5 simplifies to D0 cpj +X{D0 clj |µU0(l) = p, D0 dl= 1}=D00 cpj . Taking the corresponding configurations, this amounts to C0⇒δC00. Proof of Theorem 1. (⇒)Let Π= (O, µ, w1, . . . , wn, R1, . . . , Rn, ρ1, . . . , ρn) be a P system of order n with membrane dissolving, promoter/inhibitor sets for rules and priority relations. Assume C0⇒tC1. We prove by induction on tthat M(C0,0) →∗ M(C1,0). Let C⇒t−1C2⇒C1. Assume C2= (µ00, w00 n1, . . . , w00 ni), C1= (µ0, w0 n1, . . . , w0 ni). Assume there exists N00 such that M(C00,0) →V al N00. But V alρ(r) is applicable iff ris valid and no rule r0with (r0, r)∈ρis valid, this means N00 =M(C00,0) and M(C00,0) is V alρirreducible. In this case M(C00,0) →Sync M(C00,1). Putting Lemmas 1, 2 and 3 together, taking into account the fact that M(E, i)→Sync M(E, i + 1 mod 5) whenever M(E, i) is irreducible for the corresponding reduction, we obtain that there exists a configuration e Cand a description Dsuch that M(C00,0) →∗ RemV al M([D, 4]) →Sync M([D, 0]), where Dis the description Descrµ(e C) except for the values Dr= 0. A transition in V alρ(r) is applicable at most twice for every rule r. This means there is a description D0such that M([D, 0]) →∗ V alρM([D0,0]) and M([D0,0]) is V alρirreducible. But then D0=Descrµ(e C). 76 B. Aman et al. (⇐)Follows in a way similar to the above part from Lemmas 1, 2 and 3, but this time applying the other directions of the lemmas. Corollary 1. Let Π= (O, µ, w1, . . . , wn, R1, . . . , Rn, ρ1, . . . , ρn)and let C= (µ, w1, . . . , wn). Then Πis strongly (resp. weakly) normalizing iff M(C, 0) is strongly (resp. weakly) normalizing. Moreover, the halting computations starting from Cprovide the same results as those supplied by the terminating reduction sequences of M(C, 0). References 1. O. Agrigoroaiei, G. Ciobanu, Flattening the transition P systems with dissolution. In: M. Gheorghe, T. Hinze, Gh. P˘aun, G. Rozenberg, A. Salomaa (editors), Membrane Computing, 11th International Conference, CMC 2010, Jena, Germany, 2010, Revised Selected Papers. Volume 6501 of Lecture Notes in Computer Science, Springer Berlin Heidelberg (2011) 53–64. 2. O. Andrei, G. Ciobanu and D. Lucanu, Structural operational semantics of P systems. In: R. Freund, Gh. P˘aun, G. Rozenberg, A. Salomaa (editors), Membrane Computing, 6th International Workshop, WMC 2005, Vienna, Austria, 2005, Revised Selected and Invited Papers. Volume 3850 of Lecture Notes in Computer Science, Springer Berlin Heidelberg (2006) 32–49. 3. O. Andrei, G. Ciobanu and D. Lucanu, A rewriting logic framework for operational semantics of membrane systems. Theoretical Computer Science, 373 (2007) 163–181. 4. J.P. Banˆatre, P. Fradet, Y. Radenac, Principles of chemical computing. Electronic Notes in Theoretical Computer Science 124 (2005) 133–147. 5. J.P. Banˆatre, P. Fradet, Y. Radenac, Generalized multisets for chemical programming. Mathematical Structures in Computer Science 16 (2006) 557–580. 6. J.P. Banˆatre, D. Le M´etayer, A new computational model and its discipline of programming. Technical Report RR0566, INRIA (1986). 7. P. Batty´anyi, Gy. Vaszil, Describing membrane computations with a chemical calculus. Fundamenta Informaticae, 134 (2014) 39–50. 8. P. Bottoni, C. Mart´ın-Vide, G. P˘aun, G. Rozenberg, Membrane systems with promoters/inhibitors. Acta Informatica, 38 (2002) 695–720. 9. G. P˘aun, Computing with membranes. Journal of Computer and System Sciences, 61(1) (2000) 108–143. 10. G. P˘aun, Membrane Computing. An Introduction. Springer, 2002. 11. G. P˘aun, G. Rozenberg, A. Salomaa (eds), The Oxford Handbook of Membrane Computing. Oxford University Press, 2010. Notes on Spiking Neural P Systems and Finite Automata Francis George C. Cabarle1, Henry N. Adorna1, Mario J. P´erez-Jim´enez2 1Department of Computer Science University of the Philippines Diliman Diliman, 1101, Quezon city, Philippines; 2Department of Computer Science and AI Universidad de Sevilla Avda. Reina Mercedes s/n, 41012, Sevilla, Spain [email protected], [email protected], [email protected] Summary. Spiking neural P systems (in short, SNP systems) are membrane computing models inspired by the pulse coding of information in biological neurons. SNP systems with standard rules have neurons that emit at most one spike (the pulse) each step, and have either an input or output neuron connected to the environment. SNP transducers were introduced, where both input and output neurons were used. More recently, SNP modules were introduced which generalize SNP transducers: extended rules are used (more than one spike can be emitted each step) and a set of input and output neurons can be used. In this work we continue relating SNP modules and finite automata: (i) we amend previous constructions for DFA and DFST simulations, (ii) improve the construction from three neurons down to one neuron, (iii) DFA with output are simulated, and (iv) we generate automatic sequences using results from (iii). Key words: Membrane computing, Spiking neural P systems, Finite automata, Automatic sequences 1 Introduction Spiking neural P systems (in short, SNP systems) introduced in [7], incorporated into membrane computing the idea of pulse coding of information in computations using spiking neurons (see for example [10][11] and references therein for more information). In pulse coding from neuroscience, pulses known as spikes are not distinct, so information is instead encoded in their multiplicity or the time they are emitted. On the computing side, SNP systems have neurons processing only one object (the spike symbol a), and neurons are placed on nodes of a directed graph. Arcs between neurons are called synapses. SNP systems are known to be universal in 78 F.G.C. Cabarle, H.N. Adorna, M.J. P´erez-Jim´enez both generative (an output is given, but not an input) and accepting (an input is given, but not an output) modes. SNP systems can also solve hard problems in feasible (polynomial to constant) time. We do not go into such details, and we refer to [7][8][9][16] and references therein. SNP systems with standard rules (as introduced in their seminal paper) have neurons that can emit at most one pulse (the spike) each step, and either an input or output neuron connected to the environment, but not both. In [15], SNP systems were equipped with both an input and output neuron, and were known as SNP transducers. Furthermore, extended rules were introduced in [3] and [14], so that a neuron can produce more than one spike each step. The introduced SNP modules in [6] can then be seen as generalizations of SNP transducers: more than one spike can enter or leave the system, and more than one neuron can function as input or output neuron. In this work we continue investigations on SNP modules. In particular we amend the problem introduced in the construction of [6], where SNP modules were used to simulate deterministic finite automata and state transducers. Our constructions also reduce the neurons for such SNP modules: from three neurons down to one. Our reduction relies on more involved superscripts, similar to some of the constructions in [12]. We also provide constructions for SNP modules simulating DFA with output. Establishing simulations between DFA with output and SNP modules, we are then able to generate automatic sequences. Such class of sequences contain, for example, a common and useful automatic sequence known as the Thue-Morse sequence. The Thue-Morse sequence, among others, play important roles in many areas of mathematics (e.g. number theory) and computer science (e.g. automata theory). Aside from DFA with output, another way to generate automatic sequences is by iterating morphisms. We invite the interested reader to [1] for further theories and applications related to automatic sequences. This paper is organized as follows: Section 2 provides our preliminaries. Section 3 provides our results. Finally, section 4 provides our final remarks. 2 Preliminaries It is assumed that the readers are familiar with the basics of membrane computing (a good introduction is [13] with recent results and information in the P systems webpage1and a recent handbook [17] ) and formal language theory (available in many monographs). We only briefly mention notions and notations which will be useful throughout the paper. 2.1 Language theory and string notations We denote the set of natural (counting) numbers as N={0,1,2, . . .}. Let Vbe an alphabet, V∗is the set of all finite strings over Vwith respect to concatenation and 1http://ppage.psystems.eu/ Notes on Spiking Neural P Systems and Finite Automata 79 the identity element λ(the empty string). The set of all non-empty strings over V is denoted as V+so V+=V∗− {λ}. We call Va singleton if V={a}and simply write a∗and a+instead of {a}∗and {a}+. If ais a symbol in V, then a0=λ, A regular expression over an alphabet Vis constructed starting from λand the symbols of Vusing the operations union, concatenation, and +. Specifically, (i)λ and each a∈Vare regular expressions, (ii) if E1and E2are regular expressions over Vthen (E1∪E2), E1E2, and E+ 1are regular expressions over V, and (iii) nothing else is a regular expression over V. The length of a string w∈V∗is denoted by |w|. Unnecessary parentheses are omitted when writing regular expressions, and E+∪{λ}is written as E∗. We write the language generated by a regular expression Eas L(E). If Vhas ksymbols, then [w]k=nis the base-krepresentation of n∈N. 2.2 Deterministic finite automata Definition 1. A deterministic finite automaton (in short, a DFA) D, is defined by the 5-tuple D= (Q, Σ, q1, δ, F), where:  Q={q1, . . . , qn}is a finite set of states,  Σ={b1, . . . , bm}is the input alphabet,  δ:Q×Σ→Qis the transition function,  q1∈Qis the initial state,  F⊆Qis a set of final states. Definition 2. A deterministic finite state transducer (in short, a DFST) with accepting states T, is defined by the 6-tuple T= (Q, Σ, ∆, q1, δ0, F ), where:  Q={q1, . . . , qn}is a finite set of states,  Σ={b1, . . . , bm}is the input alphabet,  ∆={c1, . . . , ct}is the output alphabet,  δ0:Q×Σ→Q×∆is the transition function,  q1∈Qis the initial state,  F⊆Qis a set of final states. Definition 3. A deterministic finite automaton with output (in short, a DFAO) M, is defined by the 6-tuple M= (Q, Σ, δ00, q1, ∆, τ), where:  Q={q1, . . . , qn}is a finite set of states,  Σ={b1, . . . , bm}is the input alphabet,  δ00 :Q×Σ→Qis the transition function,  q1∈Qis the initial state,  ∆={c1, . . . , ct}is the output alphabet,  τ:Q→∆is the output function. A given DFAO Mdefines a function from Σ∗to ∆, denoted as fM(w) = τ(δ00(q1, w)) for w∈Σ∗. If Σ={1, ..., k}, denoted as Σk, then Mis a k-DFAO. 80 F.G.C. Cabarle, H.N. Adorna, M.J. P´erez-Jim´enez Definition 4. A sequence, denoted as a= (an)n≥0, is k-automatic if there exists ak-DFAO, M, such that given w∈Σ∗ k,an=τ(δ00(q1, w)), where [w]k=n. Example 1. (Thue-Morse sequence) The Thue-Morse sequence t= (tn)n≥0counts the number of 1’s (mod 2) in the base-2 representation of n. The 2-DFAO for t is given in Fig. 1. In order to generate t, the 2-DFAO is in state q1with output 0, if the input bits seen so far sum to 0 (mod 2). In state q2with output 1, the 2-DFAO has so far seen input bits that sum to 1 (mod 2). For example, we have t0= 0, t1=t2= 1, and t3= 0. - - ] ?W 00 1 1 start q1/0q2/1 Fig. 1. 2-DFAO generating the Thue-Morse sequence. 2.3 Spiking neural P systems Definition 5. A spiking neural P system (in short, an SNP system) of degree m≥1, is a construct of the form Π=({a}, σ1, . . . , σm, syn, in, out) where:  {a}is the singleton alphabet (ais called spike);  σ1, . . . , σmare neurons of the form σi= (ni, Ri),1≤i≤m, where: –ni≥0 is the initial number of spikes inside σi; –Riis a finite set of rules of the general form: E/ac→ap;d, where Eis a regular expression over {a},c≥1, with p, d ≥0, and c≥p; if p= 0, then d= 0 and L(E) = {ac};  syn ⊆ {1, . . . , m}×{1, . . . , m}, with (i, i)/∈syn for 1 ≤i≤m(synapses);  in, out ∈ {1, . . . , m}indicate the input and output neurons, respectively. A rule E/ac→ap;din neuron σi(we also say neuron ior simply σiif there is no confusion) is called a spiking rule if p≥1. If p= 0, then d= 0 and L(E) = {ac}, so that the rule is written simply as ac→λ, known as a forgetting rule. If a spiking rule has L(E) = {ac},we simply write it as ac→ap;d. The systems from the original paper [7], with rules of the form E/ac→a;dand ac→λ, are referred to Notes on Spiking Neural P Systems and Finite Automata 81 as standard systems with standard rules. The extended rules (i.e. p≥1) used in this work are referred to as SNP systems with extended rules in other literature, e.g. [6], [14], [16]. The rules are applied as follows: If σicontains kspikes, ak∈L(E) and k≥c, then the rule E/ac→ap;d∈Riwith p≥1,is enabled and can be applied. Rule application means consuming cspikes, so only k−cspikes remain in σi. The neuron produces pspikes (also referred to as spiking) after dtime units, to every σjwhere (i, j)∈syn. If d= 0 then the pspikes arrive at the same time as rule application. If d≥1 and the time of rule application is t, then during the time sequence t, t + 1, . . . , t +d−1 the neuron is closed. If a neuron is closed, it cannot receive spikes, and all spikes sent to it are lost. Starting at times t+dand t+d+ 1, the neuron becomes open (i.e., can receive spikes), and can apply rules again, respectively. Applying a forgetting rule means producing no spikes. Note that a forgetting rule is never delayed since d= 0. SNP systems operate under a global clock, i.e. they are synchronous. At every step, every neuron that can apply a rule must do so. It is possible that at least two rules E1/ac1→ap1;d1and E2/ac2→ap2;d2, with L(E1)∩L(E2)6=∅, can be applied at the same step. The system nondeterministically chooses exactly one rule to apply. The system is globally parallel (each neuron can apply a rule) but is locally sequential (a neuron can apply at most one rule). Aconfiguration or state of the system at time tcan be described by Ct= hr1/t1, . . . , rm/tmifor 1 ≤i≤m: Neuron icontains ri≥0 spikes and it will open after ti≥0 time steps. The initial configuration of the system is therefore C0= hn1/0, . . . , nm/0i, where all neurons are initially open. Rule application provides us a transition from one configuration to another. A computation is any (finite or infinite) sequence of transitions, starting from a C0. A halting computation is reached when all neurons are open and no rule can be applied. If σout produces ispikes in a step, we associate the symbol bito that step. In particular, the system (using rules in its output neuron) generates strings over Σ={p1, . . . , pm},for every rule r`=E`/aj`→ap`;d`,1≤`≤m, in σout. From [3] we can have two cases: associating b0(when no spikes are produced) with a symbol, or as λ. In this work and as in [6], we only consider the latter. Definition 6. A spiking neural P module (in short, an SNP module) of degree m≥1, is a construct of the form Π=({a}, σ1, . . . , σm, syn, Nin, Nout) where  {a}is the singleton alphabet (ais called spike);  σ1, . . . , σmare neurons of the form σi= (ni, Ri),1≤i≤m, where: –ni≥0 is the initial number of spikes inside σi; –Riis a finite set of rules of the general form: E/ac→ap,where Eis a regular expression over {a},c≥1, and p≥0, with c≥p; if p= 0, then L(E) = {ac}  syn ⊆ {1, . . . , m}×{1, . . . , m}, with (i, i)/∈syn for 1 ≤i≤m(synapses); 82 F.G.C. Cabarle, H.N. Adorna, M.J. P´erez-Jim´enez  Nin, Nout(⊆ {1,2, . . . , m}) indicate the sets of input and output neurons, respectively. In [15], SNP transducers operated on strings over a binary alphabet as well considering b0as a symbol. SNP modules, first introduced in [6], are a special type of SNP systems with extended rules, and generalize SNP transducers. SNP modules behave in the usual way as SNP systems, except that spiking and forgetting rules now both contain no delays. In contrast to SNP systems, SNP modules have the following distinguishing feature: at each step, each input neuron σi, i ∈Nin,takes as input multiple copies of afrom the environment (in short, Env); Each output neuron σo, o ∈Nout,produces pspikes to Env, if a rule E/ac→apis applied in σo; Note that Nin ∩Nout is not necessarily empty. 3 Main results In this section we amend and improve constructions given in [6] to simulate DFA and DFST using SNP modules. Then, k-DFAO are also simulated with SNP modules. Lastly, SNP modules are related to k-automatic sequences. 3.1 DFA and DFST simulations We briefly recall the constructions from theorem 8 and 9 of [6] for SNP modules simulating DFAs and DFSTs. The constructions for both DFAs and DFSTs have a similar structure, which is shown in Fig. 2. For neurons 1 and 2 in Fig. 2, the spikes and rules for DFA and DFST simulation are equal, so the constructions only differ for the contents of neuron 3. Let D= (Q, Σ, δ, q1, F ) be a DFA, where Σ={b1, . . . , bm},Q={q1, . . . , qn}. The construction for theorem 8 of [6] for an SNP Module ΠDsimulating Dis as follows: ΠD= ({a}, σ1, σ2, σ3, syn, {3},{3}), where  σ1=σ2= (n, {an→an}),  σ3= (n, {a2n+i+k/a2n+i+k−j→aj|δ(qi, bk) = qj}),  syn ={(1,2),(2,1),(1,3)}. The structure for ΠDis shown in Fig. 2. Note that n, m ∈N,are fixed numbers, and each state qi∈Qis represented as aispikes in σ3, for 1 ≤i≤n. For each symbol bk∈Σ, the representation is an+k. The operation of ΠDis as follows: σ1 and σ2interchange anspikes at every step, while σ1also sends anspikes to σ3. Suppose that Dis in state qiand will receive input bk, so that σ3of ΠDhas ai spikes and will receive an+kspikes. In the next step, σ3will collect anspikes from σ1,an+kspikes from Env, so that the total spikes in σ3is a2n+i+k. A rule in σ3 with L(E) = {a2n+i+k}is applied, and the rule consumes 2n+i+k−jspikes, Notes on Spiking Neural P Systems and Finite Automata 83 therefore leaving only ajspikes. A single state transition δ(qi, bk) = qjis therefore simulated. With a 1-step delay, ΠDreceives a given input w=bi1, . . . , birin Σ∗and produces a sequence of states z=qi1, . . . , qir(represented by ai1, .. . , air) such that δ(qi`, bi`) = qi`+1 ,for each `= 1, . . . , r where qi1=q1. Then, wis accepted by D(i.e. δ(q1, w)∈F) iff z= ΠD(w) ends with a state in F(i.e. qir∈F). Let the language accepted by ΠDbe defined as: L(ΠD) = {w∈Σ∗|ΠD(w)∈Q∗F}. Then, the following is theorem 8 from [6] Theorem 1. (Ibarra et al [6]) Any regular language Lcan be expressed as L= L(ΠD)for some SNP module ΠD. ' & $ % ' & $ %  - ? 12 ' & $ %  3 Fig. 2. Structure of SNP modules from [6] simulating DFAs and DFSTs. The simulation of DFSTs requires a slight modification of the DFA construction. Let T= (Q, Σ, ∆, δ0, q1, F) be a DFST, where Σ={b1, . . . , bk}, ∆={c1, . . . , ct},Q={q1, . . . , qn}. We construct the following SNP module simulating T: ΠT= ({a}, σ1, σ2, σ3, syn, {3},{3}), where:  σ1=σ2= (n, {an→an}),  σ3= (n, {a2n+i+k+t/a2n+i+k+t−j→an+s|δ0(qi, bk)=(qj, cs)}),  syn ={(1,2),(2,1),(1,3)}. The structure for ΠTis shown in Fig. 2. Note that n, m, t ∈Nare fixed numbers. For 1 ≤i≤n, 1≤s≤t, 1≤k≤m: each state qi∈Q, each input symbol bk∈Σ, and each output symbol cs∈∆, is represented by ai,an+t+k, and an+s, respectively. The operation of ΠTgiven an input w∈Σ∗is in parallel to the operation of ΠD; the difference is that the former produces a cs∈∆, while the latter produces Asynchronous Spiking Neural P Systems with Structural Plasticity? Francis George C. Cabarle1, Henry N. Adorna1, Mario J. P´erez-Jim´enez2 1Algorithms & Complexity Lab, Department of Computer Science University of the Philippines Diliman Diliman, 1101, Quezon City, Philippines; 2Department of Computer Science and AI Universidad de Sevilla Avda. Reina Mercedes s/n, 41012, Sevilla, Spain [email protected], [email protected], [email protected] Summary. Spiking neural P (in short, SNP) systems are computing devices inspired by biological spiking neurons. In this work we consider SNP systems with structural plasticity (in short, SNPSP systems) working in the asynchronous (in short, asyn mode). SNPSP systems represent a class of SNP systems that have dynamic synapses, i.e. neurons can use plasticity rules to create or remove synapses. We prove that for asyn mode, bounded SNPSP systems (where any neuron produces at most one spike each step) are not universal, while unbounded SNPSP systems with weighted synapses (a weight associated with each synapse allows a neuron to produce more than one spike each step) are universal. The latter systems are similar to SNP systems with extended rules in asyn mode (known to be universal) while the former are similar to SNP systems with standard rules only in asyn mode (conjectured not to be universal). Our results thus provide support to the conjecture of the still open problem. Key words: Membrane computing, Spiking neural P systems, Structural plasticity, Asynchronous systems, Turing universality 1 Introduction Spiking neural P systems (in short, SNP systems) are parallel, distributed, and nondeterministic devices introduced into the are of membrane computing in [7]. Neurons are often drawn as ovals, and they process only one type of object, the spike signal represented by a. Synapses between neurons are the arcs between ovals: neurons are then placed on the vertices of a directed graph. Since their introduction, several lines of investigations have been produced, e.g. (non)deterministic ?An improved version of this article will appear at the 14th Unconventional Computation and Natural Computation (2015), Auckland, New Zealand. 92 F.G.C. Cabarle, H.N. Adorna, M.J. P´erez-Jim´enez computing power in [7][14]; language generation in [4]; function computing devices in [11]; solving computationally hard problems in [9]. Many neuroscience inspirations have also been included for computing use, producing several variants (to which the previous investigation lines are also applied), e.g. use of weighted synapses [16], neuron division and budding [9], the use of astrocytes [10]. Furthermore, many restrictions have been applied to SNP systems (and variants), e.g. asynchronous SNP systems as in [6], [3], and [15], and sequential SNP systems as in [6]. In this work the variant we consider are SNP systems with structural plasticity, in short, SNPSP systems. SNPSP systems were first introduced in [1], then extended and improved in [2]. The biological motivation for SNPSP systems is structural plasticity, one form of neural plasticity, and distinct from the more common functional (Hebbian) plasticity. SNPSP systems represent a class of SNP systems using plasticity rules: synapses can be created or deleted so the synapse graph is dynamic. The restriction we apply to SNPSP systems is asynchronous operation: imposing synchronization on biological functions is sometimes “too much”, i.e. not alway realistic. Hence, the asynchronous mode of operation is interesting to consider. Such restriction is also interesting mathematically, and we refer the readers again to [6], [3], and [15] for further details. In this work we prove that (i) asynchronous bounded (i.e. there exists a bound on the number of stored spikes in any neuron) SNPSP systems are not universal, (ii) asynchronous weighted (i.e. a positive integer weight is associated with each synapse) SNPSP systems, even under a normal form (provided below), are universal. The open problem in [3] whether asynchronous bounded SNP systems with standard rules are universal is conjectured to be false. Also, asynchronous SNP systems with extended rules are known to be universal [5]. Our results provide some support to the conjecture, since neurons in SNPSP systems produce at most one spike each step (similar to standard rules) while synapses with weights function similar to extended rules (more than one spike can be produced each step). This work is organized as follows: Section 2 provides preliminaries for our results; syntax and semantics of SNPSP systems are given in Section 3; our (non)universality results are given in Section 4. Lastly, we provide final remarks and further directions in Section 5. 2 Preliminaries It is assumed that the readers are familiar with the basics of membrane computing (a good introduction is [13] with recent results and information in the P systems webpage (http://ppage.psystems.eu/) and a recent handbook [14] ) and formal language theory (available in many monographs). We only briefly mention notions and notations which will be useful throughout the paper. We denote the set of positive integers as N={1,2, . . .}. Let Vbe an alphabet, V∗is the set of all finite strings over Vwith respect to concatenation and the Asynchronous Spiking Neural P Systems with Structural Plasticity 93 identity element λ(the empty string). The set of all non-empty strings over Vis denoted as V+so V+=V∗− {λ}. If V={a}, we simply write a∗and a+instead of {a}∗and {a}+. If ais a symbol in V, we write a0=λand we write the language generated by a regular expression Eover Vas L(E). In proving computational universality, we use the notion of register machines. A register machine is a construct M= (m, I, l0, lh, R), where mis the number of registers, Iis the set of instruction labels, l0is the start label, lhis the halt label, and Ris the set of instructions. Every label li∈Iuniquely labels only one instruction in R. Register machine instructions have the following forms: •li: (ADD(r), lj, lk), increase nby 1, then nondeterministically go to ljor lk; •li: (SUB(r), lj, lk), if n≥1,then subtract 1 from nand go to lj, otherwise perform no operation on rand go to lk; •lh:HALT, the halt instruction. Given a register machine M, we say Mcomputes or generates a number nas follows: Mstarts with all its registers empty. The register machine then applies its instructions starting with the instruction labeled l0. Without loss of generality, we assume that l0labels an ADD instruction, and that the content of the output register is never decremented, only added to during computation, i.e. no SUB instruction is applied to it. If Mreaches the halt instruction lh, then the number nstored during this time in the first (also the output) register is said to be computed by M. We denote the set of all numbers computed by Mas N(M). It was proven that register machines compute all sets of numbers computed by a Turing machine, therefore characterizing NRE [8]. A strongly monotonic register machine is one restricted variant: it has only one register which is also the output register. The register initially stores zero, and can only be incremented by 1 at each step. Once the machine halts, the value stored in the register is said to be computed. It is known that strongly monotonic register machines characterize SLIN, the family of length sets of regular languages. 3 Spiking neural P systems with structural plasticity In this section we define SNP systems with structural plasticity. Initial motivations and results for SNP systems are included in the seminal paper in [7]. A spiking neural P system with structural plasticity (SNPSP system) of degree m≥1 is a construct of the form Π= (O, σ1, . . . , σm, syn, out), where: •O={a}is the singleton alphabet (ais called spike); •σ1, . . . , σmare neurons of the form (ni, Ri),1≤i≤m;ni≥0 indicates the initial number of spikes in σi;Riis a finite rule set of σiwith two forms: 1. Spiking rule: E/ac→a, where Eis a regular expression over O,c≥1; 2. Plasticity rule: E/ac→αk(i, N), where Eis a regular expression over O, c≥1, α∈ {+,−,±,∓},k≥1, and N⊆ {1, . . . , m}−{i}; 94 F.G.C. Cabarle, H.N. Adorna, M.J. P´erez-Jim´enez •syn ⊆ {1, . . . , m}×{1, . . . , m}, with (i, i)/∈syn for 1 ≤i≤m(synapses between neurons); •out ∈ {1, . . . , m}indicate the output neuron. Given neuron σi(we also say neuron ior simply σi) we denote the set of neuron labels with σias their presynaptic (postsynaptic, resp.) neuron as pres(i), i.e. pres(i) = {j|(i, j)∈syn}(as pos(i) = {j|(j, i)∈syn}, resp.). Spiking rule semantics in SNPSP systems are similar with SNP systems in [7]. In this work we do not use forgetting rules (rules of the form as→λ) or rules with delays of the form E/ac→a;dfor some d≥1. Spiking rules are applied as follows: If neuron σicontains bspikes and ab∈L(E), with b≥c, then a rule E/ac→a∈Rican be applied. Applying such a rule means consuming cspikes from σi, thus only b−c spikes remain in σi. Neuron isends one spike to every neuron with label in pres(i) at the same step as rule application. A nonzero delay dmeans that if σispikes at step t, then neurons receive the spike at t+d. Spikes sent to σifrom tto t+d−1 are lost (i.e. σiis closed), and σican receive spikes (i.e. σiis open) and apply a rule again at t+dand t+d+ 1, respectively. If a rule E/ac→ahas L(E) = {ac}, we simply write this as ac→a. Plasticity rules are applied as follows. If at step twe have that σihas b≥c spikes and ab∈L(E), a rule E/ac→αk(i, N)∈Rican be applied. The set Nis a collection of neurons to which σican connect to or disconnect from using the applied plasticity rule. The rule application consumes cspikes and performs one of the following, depending on α: •If α:= + and N−pres(i) = ∅, or if α:= −and pres(i) = ∅, then there is nothing more to do, i.e. cspikes are consumed but no synapses are created or removed. Notice that with these semantics, a plasticity rule functions similar to a forgetting rule, i.e. the former can be used to consume spikes without producing any spike. •for α:= +,if |N−pres(i)| ≤ k, deterministically create a synapse to every σl, l∈Nj−pres(i). If however |N−pres(i)|> k, nondeterministically select k neurons in N−pres(i), and create one synapse to each selected neuron. •for α:= −,if |pres(i)| ≤ k, deterministically delete all synapses in pres(i). If however |pres(i)|> k, nondeterministically select kneurons in pres(i), and delete each synapse to the selected neurons. If α∈ {±,∓} : create (respectively, delete) synapses at step tand then delete (respectively, create) synapses at step t+ 1. Only the priority of application of synapse creation or deletion is changed, but the application is similar to α∈ {+,−}. Neuron iis always open from tuntil t+ 1, but σican only apply another rule at time t+ 2. An important note is that for σiapplying a rule with α∈ {+,±,∓}, creating a synapse always involves an embedded sending of one spike when σiconnects to a neuron. This single spike is sent at the time the synapse creation is applied, i.e. whenever σiattaches to σjusing a synapse during synapse creation, we have σi immediately transferring one spike to σj. Asynchronous Spiking Neural P Systems with Structural Plasticity 95 Let tbe a step during a computation: we say a σiis activated at step tif there is at least one r∈Rithat can be applied; σiis simple if |Ri|= 1, with a nice biological and computing interpretation, i.e. some neurons do not need to be complex, but merely act as spike repositories or relays. We have the following nondeterminism levels: rule-level, if at least one neuron has at least two rules with regular expressions E1and E2such that E16=E2and L(E1)∩L(E2)6=∅;synapselevel, if initially Πhas at least one σiwith a plasticity rule where k < |N−pres(i)|; neuron-level, if at least one activated neuron with rule rcan choose to apply its rule ror not (i.e. asynchronous). By default SNP and SNPSP systems are locally sequential (at most one rule is applied per neuron) but globally parallel (all activated neurons must apply a rule). The application of rules in neurons are usually synchronized, i.e. a global clock is assumed. However, in the asynchronous (asyn, in short) mode we release this synchronization so that neuron-level nondeterminism is implied. A configuration of an SNPSP system is based on (a) distribution of spikes in neurons, and (b) neuron connections based on syn. For some step t, we can represent: (a) as hs1, . . . , smi where si,1≤i≤m, is the number of spikes contained in σi; for (b) we can derive pres(i) and pos(i) from syn, for a given σi. The initial configuration therefore is represented as hn1, . . . , nmi, with the possibility of a disconnected graph, or syn =∅. A computation is defined as a sequence of configuration transitions, from an initial configuration, and following rule application semantics. A computation halts if the system reaches a halting configuration, i.e. no rules can be applied and all neurons are open. A result of a computation can be defined in several ways in SNP systems literature. For SNP systems in asyn mode however, and as in [3] [5] [15], the output is obtained by counting the total spikes sent out by σout to the environment (in short, Env) upon reaching a halting configuration. We refer to Πas generator, if Πcomputes in this asynchronous manner. Πcan also work as an acceptor but this is not given in this work. For our universality results, the following simplifying features are used in our systems as the normal form: (i) plasticity rules can only be found in purely plastic neurons (i.e. neurons with plasticity rules only), (ii) neurons with standard rules are simple, and (iii) we do not use forgetting rules or rules with delays. We denote the family of sets computed by asynchronous SNPSP systems (under the mentioned normal form) as generators as NtotSNP SPasyn: subscript tot indicates the total number of spikes sent to Env as the result; Other parameters are as follows: +synk(−synj, respectively) where at most k(j, resp.) synapses are created (deleted, resp.) each step; ndβ, β ∈ {syn, rule, neur}indicate additional levels of nondeterminism source; rulemindicates at most mrules (either standard or plasticity) per neuron; Since our results for kand jfor +synkand −synjare equal, we write them instead in the compressed form ±synk, where ±in this sense is not the same as when α:= ±. A bound pon the number of spikes stored in any neuron of the system is denoted as boundp. We omit ndneur from writing since it is implied in asyn mode. 96 F.G.C. Cabarle, H.N. Adorna, M.J. P´erez-Jim´enez             j a→a k a→a la a→a ia a→ ±1(i, {j, k}) Fig. 1. An SNPSP system Πej . To illustrate the notions and semantics in SNPSP systems, we take as an example the SNPSP system Πej of degree 4 in Fig. 1, and describe its computations. The initial configuration is as follows: spike distribution is h1,0,0,1ifor the neuron order σi,σj,σk,σl, respectively; syn ={(j, k),(k, l)}; output neuron is σl, indicated by the outgoing synapse to Env. Given the initial configuration, σiand σlcan become activated. Due to asyn mode however, they can decide to apply their rules at a later step. If σlapplies its rule before it receives a spike from σi, then it will spike to Env twice so that Ntot(Πej ) = {2}. Since k= 1 <|{j, k}| and pres(i) = ∅,σinondeterministically selects whether to create synapse (i, j) or (i, k); if (i, j) ((i, k), resp.) is created; a spike is sent from σito σj(σk, resp.) due to the embedded sending of a spike during synapse creation. Let this be step t. If (i, j) is created then syn0:= syn ∪ {(i, j)}, otherwise syn00 := syn ∪ {(i, k)}. At t+ 1, σideletes the created synapse at t (since α:= ±), and we have syn again. Note that if σldoes not apply its rule and collects two spikes (one spike from σi), the computation is aborted or blocked, i.e. no output is produced since a2/∈L(a). 4 Main results In this section we use at most two nondeterminism sources: ndneur (in asyn mode), and ndsyn. Recall that in asyn mode, if σiis activated at step tso that an r∈Ri can be applied, σican choose to apply ror not. If σidid not choose to apply r, σican continue to receive spikes so that for some t0> t, it is possible that: rcan never be applied again, or some r0∈Ri, r06=r, is applied. For the next result, each neuron can store only a bounded number of spikes (see for example [3][6][7] and references therein). In [6], it is known that bounded SNP systems with extended rules in asyn mode characterize SLIN, but it is open whether such result holds for systems with standard rules only. In [3], a negative answer was conjectured for the following open problem: are asynchronous SNP systems with standard rules universal? First, we prove that bounded SNPSP systems in asyn mode characterize SLIN, hence they are not universal. Lemma 1 NtotSNPSPasyn(boundp, ndsyn)⊆SLIN, p ≥1. Proof. Taking any asynchronous SNPSP system Πwith a given bound pon the number of spikes stored in any neuron, we observe that the number of possible configurations is finite: Πhas a constant number of neurons, and that the number of spikes stored in each neuron are bounded. We then construct a right-linear Asynchronous Spiking Neural P Systems with Structural Plasticity 97 grammar G, such that Πgenerates the length set of the regular language L(G). Let us denote by Cthe set of all possible configurations of Π, with C0being the initial configuration. The right-linear grammar G= (C,{a}, C0, P), where the production rules in Pare as follows: (1) C→C0,for C, C0∈ C if Πhas a transition C⇒C0in which the output neuron does not spike; (2) C→aC0,for C, C0∈ C if Πhas a transition C⇒C0in which the output neuron spikes; (3) C→λ, for any C∈ C in which Πhalts. Due to the construction of G,Πgenerates the length set of L(G), hence the set is semilinear. ut Lemma 2 SLIN ⊆NtotSNP SPasyn(boundp, ndsyn), p ≥1. The proof is based on the following observation: A set Qis semilinear if and only if Qis generated by a strongly monotonic register machine M. It suffices to construct an SNPSP system Πwith restrictions given in the theorem statement, such that Πsimulates M. Recall that Mhas precisely register 1 only (it is also the output register) and addition instructions of the form li: (ADD(1), lj, lk). The ADD module for Πis given in Fig. 2. Next, we describe the computations in Π.               HHH Hj ?- lia→a1 aq/a →a for 1 ≤q≤p l1 i a→ ±1(l1 i,{lj, lk}) ljlk Fig. 2. Module ADD simulating li: (ADD(1) : lj, lk) in the proof of Lemma 2. Once ADD instruction liof Mis applied, σliis activated and it sends one spike each to σ1and σl1 i. At this point we have two possible cases due to asyn mode, i.e. either σ1spikes to Env before σl1 ispikes, or after. If σ1spikes before σl1 i, then the number of spikes in Env is immediately incremented by 1. After some time, the computation will proceed if σl1 iapplies its only (plasticity) rule. Once σl1 iapplies its rule, either σljor σlkbecomes nondeterministically activated. However, if σ1spikes after σl1 ispikes, then the number of spikes in Env is not immediately incremented by 1 since σ1does not consume a spike and fire to Env. The next instruction, either ljor lk, is then simulated by Π. Furthermore, due to asyn mode, the following “worst case” computation is possible: σlhbecomes activated (corresponding to lhin Mbeing applied, thus halting M) before σ1 spikes. In this computation, Mhas halted and has applied an mnumber of ADD instructions since the application of li. Without loss of generality we can have the 98 F.G.C. Cabarle, H.N. Adorna, M.J. P´erez-Jim´enez arbitrary bound p>m, for some positive integer p. We then have the output neuron σ1storing mspikes. Since the rules in σ1are of the form aq/a →a, 1≤q≤p,σ1consumes one spike at each step it decides to apply a rule, starting with rule am/a →a, until rule a→a. Thus, Πwill only halt once σ1has emptied all spikes it stores, sending mspikes to Env in the process. The FIN module is not necessary, and we add σlhwithout any rule (or maintain pres(lh) = ∅). Once Mhalts by reaching instruction lh, a spike in Πis sent to neuron lh.Πis clearly bounded: every neuron in Πcan only store at most pspikes, at any step. We then have Πcorrectly simulating the strongly monotonic register machine M. This completes the proof. ut From Lemma 1 and 2, we can have the next result. Theorem 1 SLIN =NtotSNP SPasyn(boundp, ndsyn), p ≥1. Next, in order to achieve universality, we add an additional ingredient to asynchronous SNPSP systems: weighted synapses. The ingredient of weighted synapses has already been introduced in SNP systems literature, and we refer the reader to [16] (and references therein) for computing and biological motivations. In particular, if σiapplies a rule E/ac→ap, and the weighted synapse (i, j, r) exists (i.e. the weight of synapse (i, j) is r) then σjreceives p×rspikes. It seems natural to consider weighted synapses for asynchronous SNPSP systems: since asynchronous SNPSP systems are not universal, we look for other ways to improve their power. SNPSP systems with weighted synapses (in short, WSNPSP systems) are defined in a similar way as SNPSP systems, except for the plasticity rules and the synapse set. Plasticity rules in σiare now of the form E/ac→αk(i, N, r), where r≥1, and E, c, α, k, N are as previously defined. Every synapse created by σiusing a plasticity rule with weight rreceives the weight r. Instead of one spike sent from σito a σjduring synapse creation, j∈N,rspikes are sent to σj. The synapse set is now of the form syn ⊆ {1,2, . . . , m}×{1,2, . . . , m} × N. We note that SNPSP systems are special cases of SNPSP systems with weighted synapses where r= 1, and when r= 1 we omit it from writing. In weighted SNP systems with standard rules, the weights can allow neurons to produce more than one spike each step, similar to having extended rules. In this way, our next result parallels the result that asynchronous SNP systems with extended rules are universal in [5]. However, our next result uses ndsyn with asyn mode, while in [5] their systems use ndrule with asyn mode. We also add the additional parameter lin our universality result, where the synapse weight in the system is at most l. Our universality result also makes use of the normal form given in Section 3. Theorem 2 NtotW SNPSPasyn(rulem,±synk, weightl, ndsyn) = NRE, m ≥9, k ≥ 1, l ≥3. Asynchronous Spiking Neural P Systems with Structural Plasticity 99 Proof. We construct an asynchronous SNPSP system with weighted synapses Π, with restrictions given in the theorem statement, to simulate a register machine M. The general description of the simulation is as follows: each register rof Mcorresponds to σrin Π. If register rstores the value n,σrstores 2nspikes. Simulating instruction li: (OP(r) : lj, lk) of Min Πcorresponds to σlibecoming activated. After σliis activated, the operation OP is performed on σr, and σljor σlkbecomes activated. We make use of modules in Πto perform addition, subtraction, and halting of the computation. Module ADD: The module is shown in Fig. 3. At some step t,σlisends a spike to σl1 i. At some t0> t,σl1 isends a spike: the spike sent to σris multiplied by two, while 1 spike is received by σl2 i. For now we omit further details for σr, since it is never activated with an even number of spikes. At some t00 > t0,σl2 inondeterministically creates (then deletes) either (l2 i, lj) or (l2 i, lk). The chosen synapse then allows either σljor σlkto become activated. The ADD module thus increments the contents of σrby 2, simulating the increment by 1 of register r. Next, only one among σljor σlkbecomes nondeterministically activated. The addition operation is correctly simulated.                  - - ? l1 i a→a r 2 li a→a l2 i a→ ±1(l2 i,{lj, lk},1) ljlk Fig. 3. Module ADD simulating li: (ADD(r) : lj, lk) in the proof of Theorem 2. Module SUB: The module is shown in Fig. 4. Let |Sr|be the number of instructions with form li: (SUB(r), lj, lk), and 1 ≤s≤ |Sr|.|Sr|is the number of SUB instructions operating on register r, and we explain in a moment why we use a size of a set for this number. Clearly, when no SUB operation is performed on r, then |Sr|= 0, as in the case of register 1. At some step t,σlispikes, sending 1 spike to σr, and 4|Sr| − sspikes to σl1 i(the weight of synapse (li, l1 i)). σl1 ihas rules of the form ap→ −1(l1 i,{r},1), for 3|Sr| ≤ p < 8|Sr|. When one of these rules is applied, it performs similar to a forgetting rule: pspikes are consumed and deletes a nonexisting synapse (l1 i, r). Since σl1 ireceived 4|Sr| − s spikes from σli, and 3|Sr| ≤ 4|Sr| − s < 8|Sr|, then one of these rules can be applied. If σl1 iapplies one of these rules at t0> t, no spike remains. Otherwise, the 4|Sr| − sspikes can combine with the spikes from σrat a later step. In the case where register rstores n= 0 (respectively, n≥1), then instruction lk(respectively, lj) is applied next. This case corresponds to σrapplying the 106 L. Cienciala, L. Ciencialov´a, E. Csuhaj-Varj´u devices even with very restricted size parameters and with other (syntactic or functioning) restrictions [1, 3, 5, 6, 7, 8, 11, 12]. According to the the basic model, the impact of the environment on the behaviour of the P colony is indirect. To describe the situation when the behaviour of the components of the P colony is influenced by direct impulses coming from the environment step-by-step, the model was augmented with a string put on an input tape to be processed by the P colony [4]. These strings correspond to the impulse sequence coming from the environment. In addition to their rewriting rules and the rules for communicating with the environment, the agents have so-called tape rules which are used for reading the next symbol on the input tape. The model, called a P colony automaton or a PCol automaton, combines properties of standard finite automata and standard P colonies. It was shown that these variants of P colonies are able to describe the class of recursively enumerable languages, taking various working mode into account. In [2] one step further was made in combining properties of P colonies and automata. While in the case of PCol automata the behaviour of the system is influenced both by the string to be processed and the environment consisting of multisets of symbols, in the case of automaton-like P colonies or APCol systems the environment is given as a string. The interaction between the agents in the P colony and the environment is realized by exchanging symbols between the objects of the agents and the environment (communication rules), and the states of the agents may change both via communication and evolution; the latter one is an application of a rewriting rule to an object. The distinguished symbol, e(in the previous models the environmental symbol) has a special role: whenever it is introduced in the string by communication, the corresponding input symbol is erased. The computation in APCol systems starts with an input string, representing the environment, and with each agent having only symbols ein its state. Every computational step means a maximally parallel action of the active agents: an agent is active if it is able to perform at least one of its programs, and the joint action of the agents is maximally parallel if no more active agent can be added to the synchronously acting agents. The computation ends if the input string is reduced to the empty word, there are no more applicable programs in the system, and meantime at least one of the agents is in so-called final state. In this paper, after recalling the model and its accepting working mode, we introduce its generating working mode. The result of computation depends on the mode in which the APCol system works. In the case of accepting mode, a computation is called accepting if and only if at least one agent is in final state and the string obtained after the computation is ε, the empty word. When the APCol system works in the generating mode, then a computation is called successful if only if it is halting and at least one agent is in final state. A string wis generated by the APCol system if starting with the empty string Automaton-like P Colonies 107 in the environment, after finishing the computation the obtained string is w, the computation is halting and at least one agent is in final state. After introducing the notion of the generating working mode, we compared the power of APCol systems working in the generating mode and that of register machines and context-free matrix grammars with and without appearance checking. 2 Definitions Throughout the paper the reader is assumed to be familiar with the basics of formal language theory and membrane computing. For further details we refer to [14] and [20]. For an alphabet Σ, the set of all words over Σ(including the empty word, ε), is denoted by Σ∗. We denote the length of a word w∈Σ∗by |w|and the number of occurrences of the symbol a∈Σin wby |w|a. For a language L⊆Σ∗, the set length(L) = {|w| | w∈L}is called the length set of L. For a family of languages FL, the family of length sets of languages in FL is denoted by NFL. A multiset of objects Mis a pair M= (V, f), where Vis an arbitrary (not necessarily finite) set of objects and fis a mapping f:V→N;fassigns to each object in Vits multiplicity in M. The set of all multisets with the set of objects V is denoted by V◦. The set V0is called the support of Mand denoted by supp(M). The cardinality of M, denoted by |M|, is defined by |M|=Pa∈Vf(a). Any multiset of objects Mwith the set of objects V0={a1,...an}can be represented as a string wover alphabet V0with |w|ai=f(ai); 1 ≤i≤n. Obviously, all words obtained from wby permuting the letters can also represent the same multiset M, and εrepresents the empty multiset. 2.1 Register machines and matrix grammars Definition 1. [19] A register machine is the construct M= (m, H, l0, lh, P )where: •mis the number of registers, •His the set of instruction labels, •l0is the start label, •lhis the final label, •Pis a finite set of instructions injectively labelled with the elements from the set H. The instructions of the register machine are of the following forms: l1: (ADD(r), l2, l3) Add 1 to the content of the register rand proceed to the instruction (labelled with) l2or l3. l1: (SUB(r), l2, l3) If the register rstores a value different from zero, then subtract 1 from its content and go to instruction l2, otherwise proceed to instruction l3. lh:HALT Halt the machine. The final label lhis only assigned to this instruction. 108 L. Cienciala, L. Ciencialov´a, E. Csuhaj-Varj´u Without loss of generality, we may assume that in each ADD-instruction l1: (ADD(r), l2, l3) and in each SUB-instruction l1: (SUB(r), l2, l3) the labels l1, l2, l3 are pairwise different. The register machine Mcomputes a set N(M) of numbers in the following way: it starts with all registers empty (hence storing the number zero) with the instruction labelled by l0and it proceeds to apply the instructions as indicated by the labels (and made possible by the contents of registers). If it reaches the halt instruction, then the number stored at that time in the register 1 is said to be computed by Mand hence it is introduced in N(M). (Because of the non-determinism in choosing the continuation of the computation in the case of ADD-instructions, N(M) can be an infinite set.) It is known (see e.g.[19]) that in this way we compute all Turing computable sets. Moreover, we call a register machine partially blind [13], if we interpret a subtract instruction in the following way: l1: (SUB(r); l2;l3) - if in register rthere is value different from zero, then subtract one from its contents and go to instruction l2or to instruction l3; if in register rthere is stored zero when attempting to decrement register r, then the program ends without yielding a result. When the partially blind register machine reaches the final state, the result obtained in the first register is only taken into account if the remaining registers store value zero. The family of sets of non-negative integers generated by partially blind register machines is denoted by NRMpb. Partially blind register machines accept a proper subset of NRE, the family of recursively enumerable sets of numbers. Definition 2. A context-free matrix grammar is a construct G= (N, T, S, M, F ),where •Nand Tare sets of non-terminal and terminal symbols, respectively, with N∩T=∅, •S∈Nis the start symbol, •Mis a finite set of matrices, M={mi|1≤i≤n}, where matrices miare sequences of the form mi= (mi,1, . . . , mi,ni), ni≥1,1≤i≤n, and mi,j,1≤ j≤ni,1≤i≤n, are context-free rules over (N∪T), •Fis a subset of all productions occurring in the elements of M, i.e. F∈ {mij|1≤i≤n, 1≤j≤ni}. We say that x∈(N∪T)+directly derives y∈(N∪T)∗in the appearance checking mode by application of mi,j =A→w∈mi– denoted by x⇒ac y, – if one of the following conditions hold: x=x1Ax2and y=x1wx2or Adoes not appear in x, mi,j ∈Fand x=y. For mi= (mi,1, . . . , mi,ni) and v, w ∈(N∪T)∗we define v⇒miwif and only if there are w0, w1, . . . , wni∈(N∪T)∗such that v=w0⇒ac mi,1w1⇒ac mi,2w2⇒ac mi,3. . . ⇒ac mi,niwni=w Automaton-like P Colonies 109 The language generated by Gis L(G) = {w∈T∗|S⇒mi1w1· · · ⇒mikwk, wk=w, wj∈(N∪T)∗, mij∈Mfor 1 ≤j≤k, k ≥1,1≤i≤n} The family of languages generated by matrix grammars with appearance checking is denoted by MATλ ac. The superscript λindicates that erasing rules (λ-rules) are allowed. We say that Mis a matrix grammar without appearance checking if and only if F=∅. The family of languages generated by matrix grammars without appearance checking is denoted by MATλ. The following results are known about matrix languages: •CF ⊂MAT ⊆MATλ⊂RE •MAT ⊂MATac ⊂CS •MATλ⊂MATλ ac =CS, where CF,CS,RE are the context-free, contextsensitive, and recursively enumerable language classes, respectively •NRMpb =NMATλ,where NMATλis class of the length sets associated with matrix languages without appearance checking (in [11]). Further details about matrix grammars can be found in [9]. 2.2 Automaton-like P colony In the following we recall the concept of an automaton-like P colony (an APCol system, for short) where the environment of the agents is given in the form of a string [2]. As in the case of standard P colonies, agents of APCol systems contain objects, each being an element of a finite alphabet. With every agent, a set of programs is associated. There are two types of rules in the programs. The first one, called an evolution rule, is of the form a→b. It means that object ainside of the agent is rewritten (evolved) to the object b. The second type of rules, called a communication rule, is in the form c↔d. When this rule is performed, the object cinside the agent and a symbol din the string are exchanged, so, we can say that the agent rewrites symbol dto symbol cin the input string. If c=e, then the agent erases dfrom the input string and if d=e, symbol cis inserted into the string. An automaton-like P colony works successfully, if it is able to reduce the given string to ε, i.e., to enter a configuration where at least one agent is in accepting state and the processed string is the empty word. 110 L. Cienciala, L. Ciencialov´a, E. Csuhaj-Varj´u Definition 3. [2] An automaton-like P colony (an APCol system, for short) is a construct Π= (O, e, A1, . . . , An), where •Ois an alphabet; its elements are called the objects, •e∈O, called the basic object, •Ai,1≤i≤n, are agents. Each agent is a triplet Ai= (ωi, Pi, Fi), where –ωiis a multiset over O, describing the initial state (content) of the agent, |ωi|= 2, –Pi={pi,1, . . . , pi,ki}is a finite set of programs associated with the agent, where each program is a pair of rules. Each rule is in one of the following forms: ·a→b, where a, b ∈O, called an evolution rule, ·c↔d, where c, d ∈O, called a communication rule, –Fi⊆O∗is a finite set of final states (contents) of agent Ai. During the work of the APCol system, the agents perform programs. Since both rules in a program can be communication rules, an agent can work with two objects in the string in one step of the computation. In the case of program ha↔b;c↔di, a sub-string bd of the input string is replaced by string ac. If the program is of the form hc↔d;a↔bi, then a sub-string db of the input string is replaced by string ca. That is, the agent can act only in one place in a computation step and the change of the string depends both on the order of the rules in the program and on the interacting objects. In particular, we have the following types of programs with two communication rules: • ha↔b;c↔ei-bin the string is replaced by ac, • hc↔e;a↔bi-bin the string is replaced by ca, • ha↔e;c↔ei-ac is inserted in a non-deterministically chosen place in the string, • he↔b;e↔di-bd is erased from the string, • he↔d;e↔bi-db is erased from the string, • he↔e;e↔di;he↔e;c↔di, . . . - these programs can be replaced by programs of type he→e;c↔di. The program is said to be restricted if it is formed from one rewriting and one communication rule. The APCol system is restricted if all the programs the agents have are restricted. At the beginning of the work of the APCol system (at the beginning of the computation), there is an input string placed in the environment, more precisely, the environment is given by a string ωof objects which are different from e. This string represents the initial state of the environment. Consequently, an initial configuration of the automaton-like P colony is an (n+1)-tuple c= (ω;ω1, . . . , ωn) where ωis the initial state of the environment and the other ncomponents are multisets of strings of objects, given in the form of strings, the initial states of the agents. Automaton-like P Colonies 111 A configuration of an APCoL system Πis given by (w;w1, . . . , wn), where |wi|= 2,1≤i≤n,wirepresents all the objects placed inside the i-th agent and w∈(O− {e})∗is the string to be processed. At each step of the computation every agent attempts to find one of its programs to use. If the number of applicable programs is higher than one, the agent non-deterministically chooses one of them. At every step of computation, the maximal possible number of agents have to perform a program. By applying programs, the automaton-like P colony passes from one configuration to another configuration. A sequence of configurations starting from the initial configuration is called a computation. A configuration is halting if the AP- Col system has no applicable program. 3 Accepting and generating mode of computation The result of a computation depends on the mode in which the APCol system works. In the case of accepting mode, a computation is called accepting if and only if at least one agent is in final state and the string obtained is ε. Hence, the string ωis accepted by the automaton-like P colony Πif there exists a computation by Π such that it starts in the initial configuration (ω;ω1, . . . , ωn) and the computation ends by halting in the configuration (ε;w1, . . . , wn), where at least one of wi∈Fi for 1 ≤i≤n. The situation is different when the APCol system works in the generating mode. A computation is called successful if only if it is halting and at least one agent is in final state. The string wFis generated by Πiff there exists computation starting in an initial configuration (ε;ω1, . . . , ωn) and the computation ends by halting in the configuration (wF;w1, . . . , wn), where at least one of wi∈Fifor 1 ≤i≤n. We denote by APColaccR(n) (or APColacc(n)) the family of languages accepted by APCol system having at most nagents with restricted programs only (or without this restriction). Similarly we denote by APColgenR(n) the family of languages generated by APCol systems having at most nagents with restricted programs only. APCol system Πcan generate or accept a set of numbers |L(Π)|. By NAPColxR(n), x ∈ {acc, gen}, is denoted the family of sets of natural numbers accepted or generated by APCol systems with at most nagents. In [2] the authors proved that the family of languages accepted by jumping finite automata (introduced in [18]) is properly included in the family of languages accepted by APCol systems with one agent, and it is proved that any recursively enumerable language can be obtained as a projection of a language accepted by an automaton-like P colony with two agents. Theorem 1. [2] The family of languages accepted by automaton-like P colonies with one agent properly includes the family of languages accepted by jumping finite automata. 112 L. Cienciala, L. Ciencialov´a, E. Csuhaj-Varj´u Theorem 2. [2] Any recursively enumerable language can be obtained as a projection of a language accepted by an automaton-like P colony with two agents. 4 The power of restricted generating APCol systems In this section we compare the computational power of automaton-like P colonies working in generating mode with one and two agents and that of register machine and matrix grammars with erasing rules. We start with the comparison of APCol systems and register machines. Theorem 3. NAPColgenR(2) = NRE Proof. Let us consider a register machine Mwith mregisters. We construct an APCol system Π= (O, e, A1, A2) simulating the computations of register machine M. To help the easier understanding of the simulation, we provide the components together with some explanations of their role. Let -O={G}∪{li, lI i, lII i, lIII i, lIV i, lV i, lV I i, li, li, Li, L0 i, L00 i, Fi|li∈H}∪ ∪ {r|1≤r≤m}, -A1= (ee, P1,{eG}) -A2= (ee, P2,{ee}) At the beginning of the computation the first agent generates object l0(the label of starting instruction of M). Then it starts to simulate instruction labelled by l0and it generates the label of the next instruction. The number stored at the register rcorresponds to the number of symbols rplaced on the input string. The set of programs is as follows: (1) For initializing the simulation there is one program in P1: P1 1 : he→l0;e↔ei The initial configuration of Πis (ε;ee, ee). After the first step of computation (only the program 1 is applicable) the system enters configuration (ε;l0e, ee). (2) For every ADD-instruction l1: (ADD(r), l2, l3) we add to P1the next programs: P1 2 : he→r;l1↔ei,3 : he→a;r↔l1i, 4 : hl1→l2;a↔ei,5 : hl1→l3;a↔ei When there is object l1inside the agent, it generates one copy of r, puts it to the environment and generates the label of the next instruction (it non-deterministically chooses one of the last two programs 4 and 5) configuration of Πlabels of applicable programs A1A2string P1P2 1. l1e ee rx2− 2. re ee l1rx3− 3. al1ee rx+1 4or 5− 4. l2e ee rx+1a Automaton-like P Colonies 113 (3) For every SUB-instruction l1: (SUB(r), l2, l3), the next programs are added to sets P1and P2: P1:P2: 6 : l1→lI 1;e↔e12 : lV I 1→l2;e↔L00 119 : e→L1;e↔lI 1 7 : e→lII 1;lI 1↔e13 : L00 1→l2;l2↔e20 : lI 1→L0 1;L1↔lII 1 8 : e→lIII 1;lII 1↔e14 : lV I 1→l3;e↔L121 : lII 1→L00 1;L0 1↔r 9 : lIII 1→lIV 1;e↔e15 : L1→F3;l3↔e22 : hr→e;L00 1↔L1i 10 : lIV 1→lV 1;e↔e16 : De→l3;F3↔l3E23 : hL1→e;e↔ei 11 : lV 1→lV I 1;e↔e17 : Dl3→F0 3;l3↔eE24 : lII 1→e;L0 1↔F3 18 : hF0 3→l3;e↔ei25 : hF3→e;e↔ei At the first phase of the simulation of the SUB instruction the first agent generates object l0 1, which is consumed by the second agent. The agent A2generates symbol L1and tries to consume one copy of symbol r. If there is any r, the agent sends to the environment object L00 1and consumes L1. After this step the first agent consumes L00 1or L1and rewrites it to l2or l3. Instruction l1: (SUB(r), l2, l3) is simulated by the following sequence of steps. If the register rstores non-zero value: configuration of Π labels of applicable programs A1A2string P1P2 1. l1e ee rx6− 2. lI 1e ee rx7− 3. lII 1e ee lI 1rx8 19 4. lIII 1e L1lI 1lII 1rx9 20 5. lIV 1e L0 1lII 1L1rx10 21 6. lV 1e L00 1r L1L0 1rx−111 22 7. lV I 1e eL1L00 1rx−112 23 8. l2L00 1ee rx−114 − 9. l2e ee rx−1l2 If the register rstores value zero : configuration of Π labels of applicable programs A1A2string P1P2 1. l1e ee 6− 2. lI 1e ee 7− 3. lII 1e ee lI 18 19 4. lIII 1e L1lI 1lII 19 20 5. lIV 1e L0 1lII 1L110 − 6. lV 1e L0 1lII 1L111 − 7. lV I 1e L0 1lII 1L113 − 8. l3L1L0 1lII 115 − 9. F3e L0 1lII 1l316 − 10. l3l3L0 1lII 1F317 24 11. F 0 3e F3e l3L0 118 25 12. l3e ee l3L0 1 (4) For halting instruction lhthere are programs belonging to the sets P1and P2. After that agent A1generates the object lh, it writes the symbol Gto the tape. After consuming it, the second agent erases all the symbols from the tape except these ones which correspond to the first register of the register machine. 114 L. Cienciala, L. Ciencialov´a, E. Csuhaj-Varj´u P1:P2: 26 : he→G;lh↔ei27 : he→e;e↔lhi28 : he→e;lh↔Xi 29 : hX→e;e↔lhi X∈ {a}∪{L0 i, li, li|0≤i≤p, where |H|=p}∪{r|1< r ≤m} The APCol system Πstarts computation in the initial configuration with empty tape. It starts the simulation of register machine Mwith instruction labelled by l0and it proceeds the simulation according to the instructions of the register machine. After Mreaches the halting instruction, then agent A2in the APCol system Πerases from the tape all the symbols except symbols 1 and then APCol systems halts. So the length of the word placed on the tape in the last configuration corresponds to the number stored in the first register of Mat the end of its computation. We proved that the family of length sets of languages generated by restricted APCol systems with two agents equals to NRE. If the APCol system is formed from only one agent, there are some limitation for generated languages. In the following we show the limits of the computational power of restricted APCol systems with only one agent. Theorem 4. NRMP B ⊆NAPColgenR(1) Proof. Let us consider a partially blind register machine Mwith mregisters. We construct an APCol system Π= (O, e, A) simulating the computations of register machine Mwith: -O={G}∪{li, lI i, lII i, lIII i, lIV i, lV i, lV I i, li, li, Li, L0 i, L00 i, Fi|li∈H}∪ ∪ {r|1≤r≤m}, -A= (ee, P, {eG}) The functioning of the constructed APCol system is very similar to the one from the proof of previous theorem. At the beginning of the computation, the agent generates the object l0(the label of starting instruction of M). Then it starts to simulate instruction labelled by l0and generates the label of the next instruction. The number stored at register rcorresponds to the number of symbols rplaced on the input string. The set of programs is given as follows: (1) For initializing the simulation there is one program in P1: P: 1 : he→l0;e↔ei The initial configuration of Πis (ε;ee). After the first step of computation (only the program 1 is applicable) the system enters configuration (ε;l0e). (2) For every ADD-instruction l1: (ADD(r), l2, l3) we add to Pthe next programs: P 2 : he→r;l1↔ei,3 : he→a;r↔l1i, 4 : hl1→l2;a↔ei,5 : hl1→l3;a↔ei Automaton-like P Colonies 115 When there is object l1inside the agent, it generates one copy of r, puts it to the environment and generates the label of the next instruction (it non-deterministically chooses one of two programs 4 and 5) configuration of Πlabels of applicable programs Astring P 1. l1e rx2 2. re l1rx3 3. al1rx+1 4or 5 4. l2e rx+1a (3) For every SUB-instruction l1: (SUB(r), l2, l3), the next programs are added to set P: P: 6 : l1→lI 1;e↔r7 : r→l2;lI 1↔e8 : r→l3;lI 1↔e The agent generates object l0 1even if there is at least one object rin the environment. Then it rewrites rto l2or l3. If there is no rin the environment, the computation halts and the agent is in non-final state. (4) For halting instruction lhthere are programs belonging to the set P: P: 9 : hlh→G;e↔ei10 : he→e;G↔Xi11 : hX→e;e↔Gi X∈ {a}∪{lI i|0≤i≤p, where |H|=p}∪{r|1< r ≤m} After the object lhappears inside agent A, it generates the symbol G. Using G, the agent erases all the symbols from the tape except those ones which correspond to the first register of the register machine. The APCol system Πstarts computation in the initial configuration with empty tape. It starts the simulation of the partially blind register machine M with instruction labelled by l0and it proceeds the simulation according to the instructions of register machine. After Mreaches the halting instruction, the agent Ain the APCol system Πerases from the tape all the symbols except symbols 1 and then the APCol system halts. So the length of the word placed on the tape in the last configuration corresponds to the number stored in the first register of M at the end of its computation. In the following we will examine the language generating power of restricted APCoL systems. Theorem 5. AP ColgenR(1) ⊆MATλ Proof. Let Π= (O, e, A) be a restricted APCol system with one agent. We construct a matrix grammar G= (N, T, S, M) simulating Πas follows: The symbol on the tape a6=eis represented by a∈Nand at the end of simulation it can be rewritten to a∈T. The content of the agent is represented 122 D. D´ıaz-Pernil et al. The Subset Sum problem belongs to the so-called weakly NP-complete problems, since its intractability strongly depends on the fact that extremely large input numbers are allowed [8]. The reason for this weakness is based on the encoding scheme of the input, since every integer in the input denoting a weight wi should be encoded by a string of length only O(log wi). On the other hand, strongly NP-complete problems are those which remain NP-complete even if the data are encoded in a unary way. The best-known one of these problems is the satisfiability problem (SAT for short). SAT was the first problem shown to be NP-complete, as proved by Stephen Cook at the University of Toronto in 1971 [5], and it has been widely used in Membrane Computing to prove the ability of a P system model to solve NP-problems (e.g. [9, 11, 12, 14, 16, 17]). In this paper, we provide a solution to the SAT problem in the polynomial complexity class of recognizer P systems with active membranes without polarizations, without dissolution and with division for elementary membranes endowed with antimatter and matter/antimatter annihilation rules. To the best of our knowledge, this is the first time that a strongly NP-complete problem is solved in this P system model. The details of the implementation can provide new tools for a better understanding of the problem of searching new frontiers of tractability in Membrane Computing. The paper is organized as follows. In Section 2, we present a general discussion about the relationship of model ingredients used in different solutions for solving computationally difficult problems by P systems with active membranes, and the emerging computational power. In Section 3, we recall the P systems model used in this paper. The main novelty is the use of antimatter and matter/antimatter annihilation rules as well as their semantics. In Section 4, some basics on recognizer P systems are recalled, and in Section 5 our solution for the SAT problem is provided. The paper finishes with some conclusions and hints for future work. 2 Computation Theory Remarks A configuration consists of symbols (which, in the general sense, may include instances of objects, instances of membranes, or any other entities bearing information). A computation consists of transformations of symbols. Clearly, the computations without cooperation of symbols are quite limited in power (e.g., it is known that E0L-behavior with standard halting yields PsREG, and accepting P systems are considerably more degenerate). In this sense, interaction of symbols is a fundamental part of Membrane Computing, or of Theoretical Computer Science in general. Various ways of interaction of symbols have been studied in membrane computing. For the models with active membranes, the most commonly studied ways are various rules changing polarizations (or even sometimes labels), and membrane dissolution rules. One object may engage such a rule, which would affect the context (polarization or label) of other objects in the same membrane, thus affecting the behavior of the latter, e.g., in Solving SAT with Antimatter in Membrane Computing 123 case of dissolution, such objects find themselves in the parent membrane, which usually has a different label. In the literature on P systems with active membranes, normally only the rules with at most one object on the left side were studied. Since recently, the model with matter/antimatter annihilation rules, e.g. see [1] and [2], attracted the attention of researchers. Clearly, it provides a form of direct object-object interaction, albeit in a rather restricted way (i.e., by erasing a pair of objects that are in a bijective relation). Although it is known that non-cooperative P systems with antimatter are already universal, studying their efficiency turned out to be an interesting line of research. So how does matter/antimatter annihilation compare to other ways of organizing interaction of objects? First, all known solutions of NP-complete (or more difficult) problems in membrane computing rely on the possibility of P systems to obtain exponential space in polynomial time (note that object replication alone does not count as building exponential space, since an exponential number can be written, e.g. in binary, in polynomial space). Such possibility is provided by either of membrane division rules, membrane separation rules, membrane creation rules (or string replication rules, but string-objects lie outside of the scope of the current paper); in tissue P systems, one could apply similar approach to cells instead of membranes. Note that in case of cell-like P systems, membrane creation alone (unlike the other types of rules mentioned above) makes it also possible to construct a hierarchy of membranes, let us refer to it as structured workspace, which is used to solve PSPACE-complete problems. The structured workspace can be alternatively created by elementary membrane division plus non-elementary membrane division (plus membrane dissolution if we have no polarizations). Besides creating workspace, to solve NP-complete problems, we need to be able to effectively use that workspace, by making objects interact. For instance, it is known that, even with membrane division, without polarizations and without dissolution only problems in Pmay be solved. However, already with two polarizations (the smallest non-degenerate value) P systems can solve NP-complete problems. What can be done without polarizations? One solution is to use the power of switching the context by membrane dissolution. Coupled with non-elementary division, a suitable membrane structure can be constructed so that the needed interactions can be performed solving NP- complete or even PSPACE-complete problems, [4]. It is not difficult to realize that elementary and non-elementary division rules can be replaced by membrane creation rules, or elementary division rules can be replaced by separation rules. Finally, an alternative way of interaction of objects considered in this paper following [7] is matter/antimatter annihilation. What are the strengths and the weaknesses of these three possibilities (the weaker is an ingredient, the stronger is the result, while sometimes a weaker ingredient does not let us do what a stronger one can)? The power of matter/antimatter annihilation makes it possible to carry out multiple simultaneous interactions (for example, the checking phase is constant- 124 D. D´ıaz-Pernil et al. time instead of linear with respect to the number of clauses), and it is a direct object-object interaction. The power of polarizations is the possibility of mass action (not critical for studying computational efficiency within PSPACE as all multiplicities are bounded with respect to the problem size) by changing context. The power of non-elementary division lets us build structured workspace (probably necessary for PSPACE if membrane creation is not used instead of membrane division, unless PPP=PSPACE), see [13], and change non-local context (e.g., the label of the parent membrane). The power of dissolution provides mass action (not critical for studying computational efficiency within PSPACE as all multiplicities are bounded with respect to the problem size) by changing context. 3 The P System Model In this paper, we use the common rules of evolution, communication and division of elementary membranes which are usual in P systems with active membranes. The main novelty in the model is the use of antimatter and matter/antimatter annihilation rules. The concept of antimatter was introduced in the framework of Membrane Computing as a control tool for the flow of spikes in spiking neural P systems [15, 18, 22, 23]. In this context, when one spike and one anti-spike appear in the same neuron, the annihilation occurs and both, spike and antispike, disappear. Antimatter and matter/antimatter annihilation rules later were adapted to other contexts in Membrane Computing, and currently this an active research area [1, 2, 7]. Inspired by physics, we consider the annihilation of two objects aand bfrom the alphabet Γin a membrane with label h, with the annihilation rule for aand bwritten as [ ab →λ]h. The meaning of the rule follows the idea of annihilation: If aand boccur simultaneously in the same membrane, then both are consumed (disappear) and nothing is produced (denoted by the empty string λ). The object bis called the antiparticle of aand it is usually written ainstead of b. With respect to the semantics, let us recall that this rule must be applied as many times as possible in each membrane, according to the maximal parallelism. Following the intuition from physics, if aand aoccur simultaneously in the same membrane hand the annihilation rule [ aa →λ]his defined, then it has to be applied, regardless any other option. In this sense, any annihilation rule has priority over all rules of the other types of rules (see [7]). A P system with active membranes without polarizations, without dissolution and with division of elementary membranes and with annihilation rules is a celllike P system with rules of the following kinds (following [3], we use subscript 0 for the rule type to represent a restriction that such rule does not depend on polarization and is now allowed to change it; if all rules have this subscript, this is equivalent to saying that the P system is without polarizations): Solving SAT with Antimatter in Membrane Computing 125 (a0) [ a→u]hfor h∈H,a∈Γ,u∈Γ∗. This is an object evolution rule, associated with a membrane labeled by h: an object a∈Γbelonging to that membrane evolves to a string u∈Γ∗. (b0)a[ ]h→[b]hfor h∈H,a, b ∈Γ. An object from the region immediately outside a membrane labeled by his taken into this membrane, possibly being transformed into another object. (c0) [ a]h→b[ ]hfor h∈H,a, b ∈Γ. An object is sent out from a membrane labeled by hto the region immediately outside, possibly being transformed into another object. (e0) [ a]h→[b]h[c]hfor h∈H,a, b, c ∈Γ. An elementary membrane can be divided into two membranes with the same label, possibly transforming one original object into a different one in each of the new membranes. (g0) [ aa →λ]hfor h∈H,a, a ∈O. This is an annihilation rule, associated with a membrane labeled by h: the pair of objects a, a ∈Obelonging simultaneously to this membrane disappears. Let us remark that dissolution rules - type (d0) - and rules for non-elementary division - type (f0) - are not considered in this model. These rules are applied according to the following principles (with the special restrictions for annihilation rules specified above): •All the rules are applied in parallel and in a maximal manner. In one step, one object of a membrane can be used by at most one rule (chosen in a non– deterministic way), and each membrane can be the subject of at most one rule of types (b0), (c0) and (e0). •If at the same time a membrane labeled with his divided by a rule of type (e0) triggered by some object aand there are other objects in this membrane to which rules of type (a0) or (g0) can be applied, then we suppose that first the rules of type (g0) and only then those of type (a0) are used, before finally the division is executed. Of course, this process in total takes only one step. •The rules associated with membranes labeled by hare used for all copies of membranes with label h. 4 Recognizer P Systems Recognizer P systems are a well-known model of P systems which are basic for the study of complexity aspects in Membrane Computing. Next, we briefly recall some basic ideas related to them. For a detailed description, for example, see [19, 20]. In recognizer P systems all computations halt; there are two distinguished objects traditionally called yes and no (used to signal the result of the computation), and exactly one of these objects is sent out to the environment (only) in the last computation step. Let us recall that a decision problem Xis a pair (IX, θX) where IXis a language over a finite alphabet (the elements are called instances) and θXis a predicate 126 D. D´ıaz-Pernil et al. (a total Boolean function) over IX. Let X= (IX, θX) be a decision problem. A polynomial encoding of Xis a pair (cod, s) of polynomial time computable functions over IXsuch that for each instance w∈IX,s(w) is a natural number representing the size of the instance and cod(w) is a multiset representing an encoding of the instance. Polynomial encodings are stable under polynomial time reductions. Let Rbe a class of recognizer P systems with input membrane. A decision problem X= (IX, θX) is solvable in a uniform way and polynomial time by a family Π= (Π(n))n∈Nof P systems from R– we denote this by X∈PMCR – if the family Πis polynomially uniform by Turing machines, i.e., there exists a polynomial encoding (cod, s) from IXto Πsuch that the family Πis polynomially bounded with regard to (X, cod, s); this means that there exists a polynomial function psuch that for each u∈IXevery computation of Π(s(u)) with input cod(u) is halting and, moreover, it performs at most p(|u|) steps; the family Πis sound and complete with regard to (X, cod, s). 5 Solving SAT Propositional Satisfiability is the problem of determining, for a formula of the propositional calculus, if there is an assignment of truth values to its variables for which that formula evaluates to true. By SAT we mean the problem of propositional satisfiability for formulas in conjunctive normal form (CNF). In this section we describe a family of P systems which solves it. As usual, we will address the resolution via a brute force algorithm, which consists of the following stages (some of the ideas for the design are taken from [6] and [21]): •Generation and Evaluation Stage: All possible assignments associated with the formula are created and evaluated (in this paper we have subdivided this group into Generation and Input processing groups of rules, which take place in parallel). •Checking Stage: In each membrane we check whether or not the formula evaluates to true for the assignment associated with it. •Output Stage: The systems sends out the correct answer to the environment. Let us consider the pair function h,idefined by hn, mi= ((n+m)(n+m+ 1)/2) + n. This function is polynomial-time computable (it is primitive recursive and bijective from N2onto N). For any given formula in CNF, ϕ=C1∧ · · · ∧ Cm, with mclauses and nvariables V ar(ϕ) = {x1, . . . , xn}we construct a P system Π(hn, mi) solving it, where the multiset encoding of the problem to be the input of Π(hn, mi) (for the sake of simplicity, in the following we will omit mand n) is cod(ϕ) = {xi,j :xj∈Ci}∪{yi,j :¬xj∈Ci}. For solving SAT by a uniform family of deterministic recognizer P systems with active membranes, without polarizations, without non-elementary membrane Solving SAT with Antimatter in Membrane Computing 127 division and without dissolution, yet with matter/antimatter annihilation rules, we now construct the members of this family as follows: Π= (O, Σ, H ={0,1}, µ = [ [ ]2]1, w1, w2, R, iin = 2),where Σ={xi,j, yi,j |1≤i≤m, 1≤j≤n}, O={d, t, f, F, F , T, non+5, Fn+5, yesn+6, yesn+6, non+6, yes, no} ∪ {xi,j, yi,j |1≤i≤m, −1≤j≤n}∪{xi,−1, yi,−1|1≤i≤m} ∪ {ci, ci|1≤i≤m}∪{ej|1≤j≤n+ 3} ∪ {yesj, noj, Fj|1≤j≤n+ 5}, w1=no0yes0F0, w2=dne1, and the rules of set Rare given below, presented in groups Generation, Input processing, Checking and Output, together with explanations how the rules in the groups work. Generation G1. [ d]2→[t]2[f]2; G2. [ t→y1,−1· · · ym,−1]2; G3. [ f→x1,−1· · · xm,−1]2; G4. [ xi,−1→λ]2, 1 ≤i≤m; G5. [ yi,−1→λ]2, 1 ≤i≤m. In each step j, 1 ≤j≤n, every elementary membrane is divided, one child membrane corresponding with assigning true to variable jand the other one with assigning false to it. One step later, proper objects are produced to annihilate the input objects associated to variable j: in the true case, we introduce the antimatter object for the negated variable, i.e., it will annihilate the corresponding negated variable, and in the false case, we introduce the antimatter object for the variable itself, i.e., it will annihilate the corresponding variable. Remaining barred (antimatter) objects not having been annihilated with the input objects, are erased in the next step. Input processing I1. [ xi,j →xi,j−1]2, 1 ≤i≤m, 0 ≤j≤n; I2. [ yi,j →yi,j−1]2, 1 ≤i≤m, 0 ≤j≤n; I3. [ xi,−1xi,−1→λ]2, 1 ≤i≤m; I4. [ yi,−1yi,−1→λ]2, 1 ≤i≤m; I5. [ xi,−1→ci]2, 1 ≤i≤m; I6. [ yi,−1→ci]2, 1 ≤i≤m. Input objects associated with variable jdecrement their second subscript during j+ 1 steps to −1. The variables not representing the desired truth value are eliminated by the corresponding antimatter object generated by the rules G2 and G3, whereas any of the input variables not annihilated then, shows that the associated clause iis satisfied, which situation is represented by the introduction of the object ci. 128 D. D´ıaz-Pernil et al. Checking C1. [ ej→ej+1 ]2, 1 ≤j≤n+ 1; C2. [ en+2 →c1· · · cmen+3 ]2; C3. [ cici→λ]2, 1 ≤i≤m; C4. [ ci→F]2, 1 ≤i≤m; C5. [ en+3 →F]2; C6. [ F F →λ]2, 1 ≤i≤m; C7. [ F]2→[ ]2T. It took n+2 steps to produce objects cifor every satisfied clause, possibly multiple times. Starting from object e1, we have obtained the object en+2 until then; from this object en+2, at step n+ 2 one anti-object is produced for each clause. Any of these clause anti-objects that is not annihilated, is transformed into F, showing that the chosen variable assignment did not satisfy the corresponding clause. It remains to notice that object Tis sent to the skin (at step n+ 4) if and only if an object Fdid not get annihilated, i.e., no clause failed to be satisfied. Output O1. [ yesj→yesj+1 ]1, 1 ≤j≤n+ 5; O2. [ noj→noj+1 ]1, 1 ≤j≤n+ 5; O3. [ Fj→Fj+1 ]1, 1 ≤j≤n+ 4; O4. [ T→non+5Fn+5 ]1; O5. [ non+5 non+5 →λ]1; O6. [ non+6 ]1→[ ]1no; O7. [ Fn+5 Fn+5 →λ]1; O8. [ Fn+5 →yesn+6 ]1; O9. [ yesn+6 yesn+6 →λ]1; O10.[ yesn+6 ]1→[ ]1yes. If no object Thas been sent to the skin, then the initial no-object can count up to n+ 6 and then sends out the negative answer no, while the initial F-object counts up to n+ 5, generates the antimatter object for the yes-object at stage n+ 6 and annihilates with the corresponding yes-object at stage n+ 6. On the other hand, if (at least one) object Tarrives in the skin, then the no-object is annihilated at stage n+ 5 before it would be sent out in the next step, and the F-object is annihilated before it could annihilate with the yes-object, so that the positive answer yes can be sent out in step n+ 6. Finally, we notice that the solution is uniform, deterministic, and uses only rules of types (a0), (c0), (e0) as well as matter/antimatter annihilation rules. The result is produced in n+ 6 steps. 6 Conclusions Although the ability of the model for solving NP problems was proved in [7], to the best of our knowledge, this is the first solution to a strongly NP problem by using Solving SAT with Antimatter in Membrane Computing 129 annihilation rules in Membrane Computing. Let us remark the important role of the definition for recognizer P systems we have used in this paper. This definition is quite restrictive, since only one object yes or no is sent to the environment in any computation. In the literature one can find other definitions of recognizer P systems and therefore other definitions of what it means to solve a problem in the framework of Membrane Computing. The study of the complexity classes in Membrane Computing deserves a deep revision under these new definitions. Acknowledgements M.A. Guti´errez-Naranjo acknowledges the support of the project TIN2012-37434 of the Ministerio de Econom´ıa y Competitividad of Spain. References 1. Artiom Alhazov, Bogdan Aman, and Rudolf Freund. P systems with anti-matter. In Marian Gheorghe, Grzegorz Rozenberg, Arto Salomaa, Petr Sos´ık, and Claudio Zandron, editors, Membrane Computing - 15th International Conference, CMC 2014, Prague, Czech Republic, August 20-22, 2014, Revised Selected Papers, volume 8961 of Lecture Notes in Computer Science, pages 66–85, Springer, 2014. 2. Artiom Alhazov, Bogdan Aman, Rudolf Freund, and Gheorghe P˘aun. Matter and anti-matter in membrane systems. In DCFS 2014, volume 8614 of Lecture Notes in Computer Science, pages 65–76, Springer, 2014. 3. Artiom Alhazov, Linqiang Pan, and Gheorghe P˘aun. Trading polarizations for labels in P systems with active membranes. Acta Informatica, 41(2-3): 111–144, 2004. 4. Artiom Alhazov and Mario J. P´erez-Jim´enez. Uniform solution of QSAT using polarizationless active membranes. In MCU 2007, volume 4664 of Lecture Notes in Computer Science, pages 122–133, Springer, 2007. 5. Stephen A. Cook. The complexity of theorem-proving procedures. In Proceedings of the Third Annual ACM Symposium on Theory of Computing, STOC ’71, pages 151–158, ACM, New York, NY, USA, 1971. 6. Andr´es Cord´on-Franco, Miguel A. Guti´errez-Naranjo, Mario J. P´erez-Jim´enez, and Fernando Sancho-Caparrini. A Prolog simulator for deterministic P systems with active membranes. New Generation Computing, 22(4): 349–363, 2004. 7. Daniel D´ıaz-Pernil, Francisco Pe˜na-Cantillana, Artiom Alhazov, Rudolf Freund, and Miguel A. Guti´errez-Naranjo. Antimatter as a frontier of tractability in membrane computing. Fundamenta Informaticae, 134: 83–96, 2014. 8. Michael R. Garey and David S. Johnson. Computers and Intractability, A Guide to the Theory of NP-Completeness. W.H. Freeman and Company, New York, 1979. 9. Zsolt Gazdag and G´abor Kolonits. A new approach for solving SAT by P systems with active membranes. In Erzs´ebet Csuhaj-Varj´u, Marian Gheorghe, Grzegorz Rozenberg, Arto Salomaa, and Gy¨orgy Vaszil, editors, International Conference on Membrane Computing, volume 7762 of Lecture Notes in Computer Science, pages 195–207, Springer, 2012. 130 D. D´ıaz-Pernil et al. 10. Miguel A. Guti´errez-Naranjo, Mario J. P´erez-Jim´enez, Agustin Riscos-N´u˜nez, and Francisco Jos´e Romero-Campero. On the power of dissolution in P systems with active membranes. In Rudolf Freund, Gheorghe P˘aun, Grzegorz Rozenberg, and Arto Salomaa, editors, Workshop on Membrane Computing, volume 3850 of Lecture Notes in Computer Science, pages 224–240, Springer, 2005. 11. Miguel A. Guti´errez-Naranjo, Mario J. P´erez-Jim´enez, and Francisco Jos´e Romero- Campero. A uniform solution to SAT using membrane creation. Theoretical Computer Science, 371(1-2): 54–61, 2007. 12. Tseren-Onolt Ishdorj and Alberto Leporati. Uniform solutions to SAT and 3-SAT by spiking neural P systems with pre-computed resources. Natural Computing, 7(4): 519–534, 2008. 13. Alberto Leporati, Luca Manzoni, Giancarlo Mauri, Antonio E. Porreca, Claudio Zandron. Simulating elementary active membranes - with an application to the P conjecture. In Marian Gheorghe, Grzegorz Rozenberg, Arto Salomaa, Petr Sos´ık, Claudio Zandron, editors, Conference on Membrane Computing, volume 8961 of Lecture Notes in Computer Science, pages 284–299, Springer, 2014. 14. Alberto Leporati, Giancarlo Mauri, Claudio Zandron, Gheorghe P˘aun, and Mario J. P´erez-Jim´enez. Uniform solutions to SAT and subset sum by spiking neural P systems. Natural Computing, 8(4): 681–702, 2009. 15. Venkata Padmavati Metta, Kamala Krithivasan, and Deepak Garg. Computability of spiking neural P systems with anti-spikes. New Mathematics and Natural Computation (NMNC), 08(03): 283–295, 2012. 16. Adam Obtulowicz. Deterministic P-systems for solving SAT-problem. Romanian Journal of Information Science and Technology, 4(1-2): 195–201, 2001. 17. Linqiang Pan and Artiom Alhazov. Solving HPP and SAT by P systems with active membranes and separation rules. Acta Informatica, 43(2): 131–145, 2006. 18. Linqiang Pan and Gheorghe P˘aun. Spiking neural P systems with anti-spikes. International Journal of Computers, Communications & Control, IV(3): 273–282, September 2009. 19. Mario J. P´erez-Jim´enez. An approach to computational complexity in membrane computing. In Giancarlo Mauri, Gheorghe P˘aun, Mario J. P´erez-Jim´enez, Grzegorz Rozenberg, and Arto Salomaa, editors, Workshop on Membrane Computing, volume 3365 of Lecture Notes in Computer Science, pages 85–109, Springer, 2004. 20. Mario J. P´erez-Jim´enez, Agustin Riscos-N´u˜nez, ´ Alvaro Romero-Jim´enez, and Damien Woods. Complexity - membrane division, membrane creation. In Gheorghe P˘aun, Grzegorz Rozenberg, and Arto Salomaa, editors, The Oxford Handbook of Membrane Computing, pages 302 – 336. Oxford University Press, Oxford, England, 2010. 21. Mario J. P´erez-Jim´enez, ´ Alvaro Romero-Jim´enez, and Fernando Sancho-Caparrini. Complexity classes in models of cellular computing with membranes. Natural Computing, 2(3): 265–285, 2003. 22. Tao Song, Yun Jiang, Xiaolong Shi, and Xiangxiang Zeng. Small universal spiking neural P systems with anti-spikes. Journal of Computational and Theoretical Nanoscience, 10(4): 999–1006, 2013. 23. Gangjun Tan, Tao Song, Zhihua Chen, and Xiangxiang Zeng. Spiking neural P systems with anti-spikes and without annihilating priority working in a ’flip-flop’ way. International Journal of Computing Science and Mathematics, 4(2): 152–162, July 2013. On The Semantics of Annihilation Rules in Membrane Computing Daniel D´ıaz-Pernil1, Rudolf Freund2, Miguel A. Guti´errez-Naranjo3, Alberto Leporati4 1Research Group on Computational Topology and Applied Mathematics Department of Applied Mathematics - University of Sevilla, Spain [email protected] 2Faculty of Informatics Vienna University of Technology, Austria [email protected] 3Research Group on Natural Computing Department of Computer Science and Artificial Intelligence University of Sevilla, Spain [email protected] 4Dipartimento di Informatica, Sistemistica e Comunicazione Universit`a degli Studi di Milano-Bicocca, Italy [email protected] Summary. It is well known that polarizationless recognizer P systems with active membranes, without dissolution, with division of elementary and non-elementary membranes, with antimatter and matter/antimatter annihilation rules can solve all problems in NP when the annihilation rules have (weak) priority over all the other rules. Until now, it was an open problem whether these systems can still solve all NP problems if the priority of the matter/antimatter annihilation rules is removed. In this paper we provide a negative answer to this question: we prove that the class of problems solvable by this model of P systems without priority of the matter/antimatter annihilation rules is exactly P. To the best of our knowledge, this is the first paper in the literature of P systems where the semantics of applying the rules constitutes a frontier of tractability. 1 Introduction The concept of antimatter was first introduced in the framework of membrane computing as a control tool for the flow of spikes in spiking neural P systems [6, 5, 10, 11]). In this context, when one spike and one anti-spike appear in the same neuron, the annihilation occurs and both, spike and anti-spike, disappear. The concept of antimatter and matter/antimatter annihilation rules later was 138 D´ıaz-Pernil et al. reasoning, either a2appears in the membrane with label h2since the beginning of the computation, or it is produced or moved there by the application of a rule r3, and so on. Finally we have a chain (yes, env)r1 ←− (a1, skin)r2 ←− (a2, h2)r3 ←− · · · rk ←− (ak, hk) where k≤nand akappears in a membrane with label hkin the initial configuration (possibly as part of the input multiset). The key idea here is two-folded. On the one hand, annihilation rules do not produce any object; the objects that trigger an annihilation rule disappear and nothing is produced. On the other hand, for any halting configuration there must exist a finite sequence of rules (rk, rk−1, . . . , r2, r1) where rkis triggered by an object from the initial configuration, r1produces yes and each riproduces an object that triggers ri−1. Therefore, none of rules r1, . . . , rk is an annihilation rule. To formally prove the result we have to check that the amount of resources for finding the sequence of rules is polynomially bounded. With this aim, we will start by considering the dependency graph associated with Π(s(u)) , but considering only evolution, communication and division rules2(i.e., only rules which can produce new occurrences of objects). Namely, if Ris the set of rules associated with Π(s(u)), we will consider the corresponding directed graph G= (V, E) defined as follows, where the function f:H→Hreturns the label of the parent membrane: V=V L ∪V R, V L ={(a, h)∈Γ×H:∃u∈Γ∗([a→u]h∈R)∨ ∃b∈Γ([a]h→[ ]hb∈R)∨ ∃b∈Γ∃h0∈H(h=f(h0)∧a[ ]h0→[b]h0∈R)∨ ∃b, c ∈Γ([a]h→[b]h[c]h∈R)}, V R ={(b, h)∈Γ×H:∃a∈Γ∃u∈Γ∗([a→u]h∈R∧b∈u)∨ ∃a∈Γ∃h0∈H(h=f(h0)∧[a]h0→[ ]h0b∈R)∨ ∃a∈Γ(a[ ]h→[b]h∈R)∨ ∃a, c ∈Γ([a]h→[b]h[c]h∈R)}, E={((a, h),(b, h0)) : ∃u∈Γ∗([a→u]h∈R∧b∈u∧h=h0)∨ ([a]h→[ ]hb∈R∧h0=f(h)) ∨ (a[ ]h0→[b]h0∈R∧h=f(h0)) ∨ ∃c∈Γ([a]h→[b]h[c]h∈R∧h=h0)}. Such a dependency graph can be constructed by a Turing machine working in polynomial time with respect to the instance size. Finally, let us consider the set 2See [4] for the details about polynomial resources. On The Semantics of Annihilation Rules in Membrane Computing 139 ∆Π={(a, h)∈Γ×H: there exists a path (within the dependency graph) from (a, h) to (yes, env)}. It has also been proved that there exists a Turing machine that constructs ∆Π in polynomial time; the proof uses the Reachability Problem in order to prove the polynomially bounded construction. From this construction we directly obtain that the set of rules used in the chain (yes, env)r1 ←− (a1, skin)r2 ←− (a2, h2)r3 ←− · · · rk ←− (ak, hk) described above can be found in polynomial time. Finally, for the instance u∈IX, let us consider the P system Π(u0) with only one membrane with label sand only one object (ak, hk) in the initial configuration. The set of rules is •[(ai, hi)→(ai−1, hi−1)]sfor each i∈ {3, . . . , k −1} •[(a2, h2)→(a1, skin)]s •[(a1, skin)]s→yes [ ]s The system Π(u0) can be built in polynomial time by a deterministic Turing machine. A direct inspection of the rules shows that Π(u0)∈ AM0 −d,+ne. The behavior of the system is deterministic, and it computes the correct answer for the instance u∈IX, sending out the object yes to the environment in the last step of computation. We finally observe that a similar construction can be carried out for the answer no. Hence, we conclude that X∈PMC? AM0 −d,+ne =P.ut Remark 1. Let us finally explain the idea how to even get a uniform family of recognizer P systems from the family constructed in the preceding proof by making some preprocessing: For any input of length n, we include all possible input symbols in the dependency graph. If there is a path from some symbol to yes and from another symbol to no, then by the definition of confluence, an input containing both of these symbols simultaneously cannot be a valid input. So, once we get an input of length n, we first check if it has symbols deriving yes and symbols deriving no. This certainly is possible within polynomial time. 4 Conclusions We have proved that by removing priority in polarizationless recognizer P systems with antimatter and annihilation rules, without dissolution, and with division of elementary and non-elementary membranes, we obtain a new characterization of the standard complexity class P. Since it was previously known that the same model of P systems can solve the NP-complete problem Subset Sum when the priority of annihilation rules is used [3], we have shown that this priority plays an important role in the computational power of these P systems. 140 D´ıaz-Pernil et al. Indeed, the most interesting aspect of our result is the fact that if the rules of these P systems are applied in different ways, a different computational power is obtained. We have thus proved that the semantics of a model can be a useful tool for studying problems of tractability. To the best of our knowledge, this is the first time where it is proved that two models of P systems syntactically identical correspond to two (presumably) different complexity classes simply because they use different semantics. This opens a new research area in the study of tractability in membrane computing. Not only new ingredients or new models must be studied in order to find new frontiers: classical results can also be revisited in order to explore the consequences of considering alternative semantics. Acknowledgements Miguel A. Guti´errez-Naranjo acknowledges the support of the project TIN2012- 37434 of the Ministerio de Econom´ıa y Competitividad of Spain. The authors are very grateful to Artiom Alhazov for carefully reading the paper and for also pointing out Remark 1. References 1. Alhazov, A., Aman, B., Freund, R.: P systems with anti-matter. In: Gheorghe, M., Rozenberg, G., Salomaa, A., Sos´ık, P., Zandron, C. (eds.) Membrane Computing - 15th International Conference, CMC 2014, Prague, Czech Republic, August 20-22, 2014, Revised Selected Papers. Lecture Notes in Computer Science, vol. 8961, pp. 66–85. Springer (2014) 2. Alhazov, A., Aman, B., Freund, R., P˘aun, Gh.: Matter and anti-matter in membrane systems. In: DCFS 2014. Lecture Notes in Computer Science, vol. 8614, pp. 65–76. Springer (2014) 3. D´ıaz-Pernil, D., Pe˜na-Cantillana, F., Alhazov, A., Freund, R., Guti´errez-Naranjo, M.A.: Antimatter as a frontier of tractability in membrane computing. Fundamenta Informaticae 134, 83–96 (2014) 4. Guti´errez-Naranjo, M.A., P´erez-Jim´enez, M.J., Riscos-N´u˜nez, A., Romero-Campero, F.J.: On the power of dissolution in P systems with active membranes. In: Freund, R., P˘aun, Gh., Rozenberg, G., Salomaa, A. (eds.) Workshop on Membrane Computing. Lecture Notes in Computer Science, vol. 3850, pp. 224–240. Springer, Berlin Heidelberg (2005) 5. Metta, V.P., Krithivasan, K., Garg, D.: Computability of spiking neural P systems with anti-spikes. New Mathematics and Natural Computation (NMNC) 08(03), 283– 295 (2012) 6. Pan, L., P˘aun, Gh.: Spiking neural P systems with anti-spikes. International Journal of Computers, Communications & Control IV(3), 273–282 (2009) 7. P´erez-Jim´enez, M.J.: An approach to computational complexity in membrane computing. In: Mauri, G., P˘aun, Gh., P´erez-Jim´enez, M.J., Rozenberg, G., Salomaa, A. On The Semantics of Annihilation Rules in Membrane Computing 141 (eds.) Workshop on Membrane Computing. Lecture Notes in Computer Science, vol. 3365, pp. 85–109. Springer (2004) 8. P´erez-Jim´enez, M.J., Riscos-N´u˜nez, A., Romero-Jim´enez, A., Woods, D.: Complexity - membrane division, membrane creation. In: P˘aun, Gh., Rozenberg, G., Salomaa, A. (eds.) The Oxford Handbook of Membrane Computing, pp. 302 – 336. Oxford University Press, Oxford, England (2010) 9. P˘aun, Gh.: Some quick research topics., In these proceedings. 10. Song, T., Jiang, Y., Shi, X., Zeng, X.: Small universal spiking neural P systems with anti-spikes. Journal of Computational and Theoretical Nanoscience 10(4), 999–1006 (2013) 11. Tan, G., Song, T., Chen, Z., Zeng, X.: Spiking neural P systems with anti-spikes and without annihilating priority working in a ’flip-flop’ way. International Journal of Computing Science and Mathematics 4(2), 152–162 (2013) How to Go Beyond Turing with P Automata: Time Travels, Regular Observer ω-Languages, and Partial Adult Halting Rudolf Freund1, Sergiu Ivanov2, and Ludwig Staiger3 1Technische Universit¨at Wien, Austria Email: [email protected] 2Universit´e Paris Est, France Email: [email protected] 3Martin-Luther-Universit¨at Halle-Wittenberg, Germany Email: [email protected] Summary. In this paper we investigate several variants of P automata having infinite runs on finite inputs. By imposing specific conditions on the infinite evolution of the systems, it is easy to find ways for going beyond Turing if we are watching the behavior of the systems on infinite runs. As specific variants we introduce a new halting variant for P automata which we call partial adult halting with the meaning that a specific predefined part of the P automaton does not change any more from some moment on during the infinite run. In a more general way, we can assign ω-languages as observer languages to the infinite runs of a P automaton. Specific variants of regular ω-languages then, for example, characterize the red-green P automata. 1 Introduction Various possibilities how one can “go beyond Turing” are discussed in [11], for example, the definitions and results for red-green Turing machines can be found there. In [2] the notion of red-green automata for register machines with input strings given on an input tape (often also called counter automata) was introduced and the concept of red-green P automata for several specific models of membrane systems was explained. Via red-green counter automata, the results for acceptance and recognizability of finite strings by red-green Turing machines were carried over to red-green P automata. The basic idea of red-green automata is to distinguish between two different sets of states (red and green states) and to consider infinite runs of the automaton on finite input objects (strings, multisets); allowed to change between red and green states more than once, red-green automata can recognize more than the recursively enumerable sets (of strings, multisets), i.e., in that way we can “go beyond Turing”. In the area of P systems, first attempts to do that can 144 R. Freund, S. Ivanov, L. Staiger be found in [4] and [18]. Computations with infinite words by P automata were investigated in [9]. In this paper, we also consider infinite runs of P automata, but in a more general way take into account the existence/non-existence of a recursive feature of the current sequence of configurations. In that way, we obtain infinite sequences over {0,1}which we call “observer languages” where 1 indicates that the specific feature is fulfilled by the current configuration and 0 indicates that this specific feature is not fulfilled. The recognizing runs of red-green automata then correspond with ω-regular languages over {0,1}of a specific form ending with 1ωas observer languages. A very special observer language is {0,1}∗{1}ωwhich corresponds with a very special acceptance condition for P automata which we call “partial adult halting”. This special acceptance variant for P automata with infinite runs on finite multisets is motivated by an observation we make for the evolution of time lines described by P systems – at some moment, a specific part of the evolving time lines, for example, the part describing time 0, shall not change any more. 2 Definitions We assume the reader to be familiar with the underlying notions and concepts from formal language theory, e.g., see [17], as well as from the area of P systems, e.g., see [13, 14, 15]; we also refer the reader to [25] for actual news. 2.1 Prerequisites The set of integers is denoted by Z, and the set of non-negative integers by N. Given an alphabet V, a finite non-empty set of abstract symbols, the free monoid generated by Vunder the operation of concatenation is denoted by V∗. The elements of V∗are called strings, the empty string is denoted by λ, and V∗\{λ}is denoted by V+. For an arbitrary alphabet V={a1, . . . , an}, the number of occurrences of a symbol aiin a string xis denoted by |x|ai, while the length of a string xis denoted by |x|=Pai∈V|x|ai. A (finite) multiset over a (finite) alphabet V={a1, . . . , an} is a mapping f:V→Nand can be represented by Daf(a1) 1, . . . , af(an) nEor by any string xfor which (|x|a1,...,|x|an) = (f(a1), . . . , f(an)). The families of regular and recursively enumerable string languages are denoted by REG and RE, respectively. 2.2 Register Machines Aregister machine is a tuple M= (m, B, l0, lh, P ), where mis the number of registers, Bis a set of labels, l0∈Bis the initial label, lh∈Bis the final label, and Pis the set of instructions bijectively labeled by elements of B. The instructions of Mcan be of the following forms: How to Go Beyond Turing with P Automata 145 •l1: (ADD (r), l2, l3), with l1∈B\ {lh},l2, l3∈B, 1 ≤j≤m. Increases the value of register rby one, followed by a non-deterministic jump to instruction l2or l3. This instruction is usually called increment. •l1: (SUB (r), l2, l3), with l1∈B\ {lh},l2, l3∈B, 1 ≤j≤m. If the value of register ris zero then jump to instruction l3; otherwise, the value of register ris decreased by one, followed by a jump to instruction l2. The two cases of this instruction are usually called zero-test and decrement, respectively. •lh:HALT . Stops the execution of the register machine. Aconfiguration of a register machine is described by the contents (i.e., by the number stored in the register) of each register and by the current label, which indicates the next instruction to be executed. Computations start by executing the instruction l0of P, and terminate with reaching the HALT-instruction lh. In order to deal with strings, this basic model of register machines can be extended by instructions for reading from an input tape and writing to an output tape containing strings over an input alphabet Tin and an output alphabet Tout, respectively: •l1: (read (a), l2), with l1∈B\ {lh},l2∈B,a∈Tin. Reads the symbol afrom the input tape and jumps to instruction l2. •l1: (write (a), l2), with l1∈B\ {lh},l2∈B,a∈Tout. Writes the symbol aon the output tape and jumps to instruction l2. Such a register machine working on strings often is also called a counter automaton, and we write M= (m, B, l0, lh, P, Tin, Tout). If no output is written, we omit Tout. As is well known (e.g., see [12]), for any recursively enumerable set of natural numbers there exists a register machine with (at most) three registers accepting the numbers in this set. Counter automata, i.e., register machines with an input tape, with two registers can simulate the computations of Turing machines and thus characterize RE. All these results are obtained with deterministic register machines, where the ADD-instructions are of the form l1: (ADD (r), l2), with l1∈B\ {lh},l2∈B, 1 ≤j≤m. 2.3 The Arithmetical Hierarchy The Arithmetical Hierarchy (e.g., see [3]) is usually developed with the universal (∀) and existential (∃) quantifiers restricted to the integers. Levels in the Arithmetical Hierarchy are labeled as Σnif they can be defined by expressions beginning with a sequence of nalternating quantifiers starting with ∃; levels are labeled as Πnif they can be defined by such expressions of nalternating quantifiers that start with ∀.Σ0and Π0are defined as having no quantifiers and are equivalent. Σ1and Π1only have the single quantifier ∃and ∀, respectively. We only need to consider alternating pairs of the quantifiers ∀and ∃because two quantifiers of the same type occurring together are equivalent to a single quantifier. 146 R. Freund, S. Ivanov, L. Staiger 3 Time Travel P Systems In the most general case, we can think of P systems as devices manipulating multisets in a hierarchical membrane structure. The membranes can have labels and polarizations both eventually changing with the application of rules. Membranes may be divided, generated or deleted. Together with the division or the generation of a new membrane the whole contents of another membrane may be copied. For a general framework of P systems we refer to [7]. Usually, configurations in P systems (and other systems like Turing machines) evolve step by step through time, see Figure 1. 0 1 2 30 1 2 3 Time configurations Time axis Fig. 1. Standard time line evolution. Without time travel option, we need only consider the evolution of the system on one time axis from time nto time n+ 1. The situation becomes more difficult if we follow the idea of parallel worlds (time axes), which means that we have another time dimension, described by the vertical evolution in Figure 2, i.e., the time configurations at time nmay be altered depending on future evolutions. −1 0 1 2 ⇓ −1 0 1 2 ⇓ Time configurations Time axis Evolution of time axes Fig. 2. Time lines evolution. How to Go Beyond Turing with P Automata 147 anY es -1 an−1Y es -1 · · · a Y es -1 ⇓ ⇓ ⇓ Y es 0 ⇓ Fig. 3. Sending back an answer from time nto time 0. For example, we can consider membrane systems with polarizations assigned to the membranes. The usual polarization of the whole time configuration in the normal case is +1, indicating that the evolution of the membrane(s) goes from time configuration nto time configuration n+ 1. Now assume we allow polarization −1 indicating that the corresponding membrane evolves from time configuration nto time configuration n−1. Having kept trace of the number of computation steps, e.g., by the multiplicity of a specific object a, we are able to send back information – like the answer yes to a question we have posed at time 0 which then is sent back to time configuration 0, i.e., to the time we have posed the question. In that way, on a specific time line we can have answers to questions in zero time, see Figure 3. During its travel through the time back, the time capsule with polarization −1 can be assumed not to be affected by the other membranes in the intermediate time configurations. Obviously, this restriction can be alleviated for even more complex systems. Putting a new skin membrane around all the current time configurations of one time axis, we again obtain a conventional evolution model, yet now with a vertical time evolution as depicted in Figure 4. The only assumption we have to do for making this variant possible is that at the beginning only a finite number of time configurations exists (in fact, we usually will start with the time configuration at time 0). 3.1 Partial Adult Halting Going back to the time travel model of Figure 2 the question that arises is what kind of results we may obtain and how. For example, given a specific input in time configuration 0, we may request that from some moment on this time configuration becomes stable, i.e., it is not changed any more (by time capsules arriving there). Looking for Computers in the Biological Cell. After Twenty Years? Gheorghe P˘aun Institute of Mathematics of the Romanian Academy PO Box 1-764, 014700 Bucure¸sti, Romania [email protected] 1 Preliminary Cautious and Explanations The previous title needs some explanations which I would like to bring from the very beginning. On the one hand, it promises too much, at least with respect to my scientific preoccupations in the last two decades and with respect to the discussion which follows. It is true that there are attempts to use the cell as it is (bacteria, for instance) or parts of it (especially DNA molecules) to compute, but a research direction which looks more realistic, at least for a while, and which has interested me, is to look in the cell for ideas useful to computer science, for computability models which, passing from biological structures and processes to mathematical models, of a computational type, can not only ensure a better use of the existing computers, the electronic ones, but they can also return to the starting point, as tools for biological investigations. Looking to the cell through the mathematician-computer scientist glasses, this is the short description of the present approach, and in this area it is placed the personal research experience which the present text is based on. On the other hand, the title announces already the autobiographical intention. Because a Reception Speech is a synthesis moment, if not also a career summarizing moment, it cannot be less autobiographical than it is, one uses to say, any novel or poetry volume. And, let us not forget, the life in the purity and signs world (a syntagma of Dan Barbilian-Ion Barbu, a Romanian mathematician and poet) ?This is the English version of the Reception Speech I have delivered on October 24, 2014, at the Romanian Academy, Bucharest, and printed by the Publishing House of the Romanian Academy in December 2014. The answer to this speech was given by acad. Solomon Marcus. Some ideas and some paragraphs of the text have appeared, in a preliminary version, in the paper Gh. P˘aun ”From cells to (silicon) computers, and back”, published in the volume New Computational Paradigms. Changing Conceptions of what is Computable (B.S. Cooper, B. Lowe, A. Sorbi, eds.), Springer, New York, 2008, 343–371. 252 Gh. P˘aun of mathematics assumes/imposes a great degree of loneliness, as acad. Solomon Marcus reminded us in his Reception Speech (2008), while the loneliness (it is supposed to) make(s) us wiser, but it also moves us farther from the ”world-as-it- is”, so that at some stage you no longer know how much from a mathematician belongs to the ”world” and how much belongs to mathematics. That is why we can consider that a mathematician is autobiographical both in his/her theorems and in the proofs of his/her theorems, as well as in the models (s)he proposes. Looking back in time, I find that I am now at the end of two periods of two decades each, the second one completely devoted to ”searching computers in the cell”, while the first period was almost systematically devoted to preparing the tools needed/useful to this search. The present text describes mainly the latter of these two periods. 2 Another Possible Title For a while, I had in mind also another title, much more general, namely, From bioinformatics to infobiology. It was at the same time a proposal and a forecast, and the pages which follow try to bring consistency to this forecast. Actually, the idea does not belong to me, in several places there were discussions about a new age of biology – the same was predicted also for physics – based on using the informational-computational paradigms, if not also based on further chapters of mathematics, not developed yet. The idea is not to apply computer science, be it theoretical or practical, to biology, but to pass to a higher level, to a systematic approach to biological phenomena in terms of computability, with the key role of information being understood. Attempts which illustrate this possibility, also advocating for its necessity, can be found in many places, going back in time to Erwin Schr¨odinger and John von Neumann. In a recent book, Infobiotics. Information in Biotic Systems (Springer-Verlag, 2013), Vincenzo Manca also pleads for ”a new biology”, which he calls infobiotics, starting from the observation that the life is too important to be investigated only by biologists. I would reformulate in more general terms: the life is too important and too complex to be investigated only by the traditional biology – with the important emphasis that exactly the biologists are called to not only benefit, but also to provide consistency to infobiology. Together with the computer scientists and, more plausibly and more efficient, borrowing from the computer scientists ideas, models, techniques, making them their own ideas, models and techniques and developing them. There is here also a plead for multi-trans-inter-disciplinarity (starting with the higher education), but also a warning: this is not only possible, but, it seems, this is also at the right time, on the verge to become urgent. Looking for Computer in the Biological Cell 253 3 The Framework Having in mind the title before and looking for an ”official” enveloping area, the first syntagma which appears is natural computing – with the mentioning, however, that it covers a very large variety of research areas, including the bioinformatics and also moving towards infobiology. For an authoritative description, let us consider the Handbook of Natural Computing, edited by Grzegorz Rozenberg, Thomas B¨ack and Joost N. Kok, published, in four large volumes, by Springer-Verlag, in 2012. From the beginning of the Preface, we learn that Natural Computing is the field of research that investigates human-designed computing inspired by nature as well as computing taking place in nature, that is, it investigates models and computational techniques inspired by nature, and also it investigates, in terms of information processing, phenomena taking place in nature. The generality is obvious, adding to the desire to identify in nature (important: not only in biology) ideas useful to computer science, a position which, as I have already said, although it is not completely new, if it is systematically applied, it can lead to a new paradigm in biological research and in other frameworks too: the informational approach, hence surpassing the traditional approach, the chemical-physical one. The idea was formulated also in other contexts: the computational point of view (to the information processing one adds the essential aspect of computability) can also lead to a new physics – among others, this is the forecast of Jozef Gruska, an active promoter of quantum computing and a pioneer of computer science, rewarded with a diploma of this kind by the Computer Science Section of IEEE (let us remind the fact that also Grigore C. Moisil has been awarded such a diploma and title). On the same idea is grounded also the collective volume A Computable Universe. Understanding and Exploring Nature as Computation, edited by Hector Zenil and published by World Scientific in 2013. Many chapters have exciting-enthusiastic titles: Life as Evolving Software, The Computable Universe Hypothesis, The Universe as Quantum Computer, etc. There also is a chapter-long Preface, by sir Roger Penrose, not always fully agreeing with the hypotheses from the book. Actually, also the Handbook of Natural Computing mentioned before includes the quantum computing among the covered domains. Here is its contents (the main sections, without specifying the chapters): Cellular Automata, Neural Computation, Evolutionary Computation, Molecular Computation, Quantum Computation, Broader Perspective – Nature-Inspired Algorithms, Broader Perspective – Alternative Models of Computation. There is some degree of ”annexationism” here (for instance, cellular automata are not too much related to the biological cells), but let us mention that the section devoted to the molecular computation covers DNA computing, membrane computing, and gene assembly in ciliates, the former two areas being exactly what we are interested in here. 254 Gh. P˘aun 4 The Popularity of a Domain Even remaining only at the editorial level and at the level of conferences (without considering also the research projects, hence the financial support), one can say that there is a real fashion of natural computing – more general, of unconventional computing, more restricted, of bioinformatics. Here are only a few illustrations. Springer-Verlag has a separate series of books dedicated to natural computing monographs, named exactly in this way, it also has a journal, Natural Computing. There is an international conference, Unconventional Computing, which became, in the last year, slightly pleonastic, International Conference on Unconventional Computation and Natural Computation.BIC-TA, that is, Bio-Inspired Computing – Theory and Applications, is another conference of a real success, at least in what concerns the number of participants, a meeting whose format I has established, together with colleagues from Spain and China, in 2005, and which is organized since then each year, in China or in the neighboring countries – this can explain the massive participation, as the Chinese researchers are very active in this area. We have reached the closest upper envelope of the area discussed here: the computability inspired from biology. It is important to note that the term ”bioinformatics” (bio-computer science) has a double meaning, with, one can say, a geographical determination. In the ”pragmatic West”, it mainly covers the computer science applications to biology (in the ”standard” scenario, one goes from problems towards tools, without too much theory). In Europe, both directions of influence are taken into consideration, from biology towards computer science and conversely. Although it is just natural that both these two research directions should be developed together, in collaboration, the reality is not always so. In search of solutions for current questions, some of them really urgent, for instance from the biomedical area, mathematics and computer science often provide tools prepared and developed in other areas. The typical example is that of differential equations, with a glorious history in physics, astronomy, mechanics, meteorology, and which are ”borrowed” to biology, not always checking their adequacy. I will return to this issue, of a great importance for promoting new tools for biology. ”The European strategy”, of constructing a mathematical theory which looks for applications after it is developed, has its appeal and advantages – but also its traps. Being an European, being a mathematician, I have been especially attracted by this strategy, but, in time, I became more and more interested by ”reality”, by applications. 5 What Means to Compute? Let us come back to the title, with the fundamental question concerning the definition of the notions of computation and computer. This is a question of the same type as ”what is mathematics?”, with many different answers, none of them Looking for Computer in the Biological Cell 255 complete, none of them fully agreed. If information processing is a computation, then we can see computations everywhere. With a very important detail, hidden in the previous formulation: we can see. We, the human beings. Otherwise stated, an observer, which interprets a process as being a computation. I do not want to push the discussion as far as asking questions of the form ”does a tree which falls in the water of a lake, in the middle of an uninhabited forest, produce any noise, taking into account that there is nobody there to hear it?” – I mention the fact that this question was the topic of a paper accepted some years ago by a conference on unconventional computing, that is why I recall it – and, on the other hand, I also do not want to involve God in this issue, the omnipresent, omniscient, omnipotent God, considered as an universal observer (at least, not for observing computations, maybe only for noticing noises in desert forests...). A somewhat exaggerated but rather suggestive example is that of a drop of liquid which falls freely in the air. During its falling down, the drop instantaneously ”solves” on its surface, by the form it takes, complex differential equations. Is this a computation? I would not go so far. Similarly with what happens continuously in the cells of a leaf or of the human body, at the biochemical or even at the informational level. The idea of a computation as a process considered so by an observer is not at all new. One of the conclusions of the John Searle book The Rediscovery of the Mind (MIT Press, 1992), is exactly this – a computation is not an intrinsic property of a process, but it is observer-relative. A very suggestive formulation of the role of the observer in considering a process as being a computation belongs to Tommaso Toffoli. The quotation which follows appears in a paper with a statement-title: ”Nothing makes sense in computing except in the light of evolution” (Journal of Unconventional Computing, vol. 1, 2005, pages 3–29). “We’we just seen that it is not useful to call computation just any nontrivial yet somewhat disciplined coupling between state variables. We also want this coupling to have been intentionally set up for the purpose of predicting or manipulating – in other words, for knowing or doing something. This is what shall distinguish bona–fide computation from other intriguing function–composition phenomena such as weather patterns or stock–exchange cycles. But now we have new questions, namely, ‘Set up by whom or what?’, ‘What is it good for?’, and ‘How do we recognize intention?’ Far from me to want to sneak animistic, spiritualistic, or even simply anthropic considerations into the makeup of computation! The concept of computation must emerge as a natural, well–characterized, objective construct, recognizable by and useful to humans, Martians and robots alike” (my emphasis, Gh.P.). Toffoli’s questions should be remembered and discussed, but they move us far from our subject. Let us return to John Searle, namely, to a more technical reading of the idea of implying an observer in the definition of a computation. This was the approach of Matteo Cavaliere and Peter Leupold, both of them my students in the PhD school in Tarragona, Spain, the former one being my first PhD student 256 Gh. P˘aun there. They have published a series of papers with this subject, I cite here only a recent one, by Peter Leupold, ”Is computation observer-relative?”, presented at the Sixth Workshop on Non-Classical Models of Automata and Applications, Kassel, Germany, July 2014. Actually, in the Cavaliere-Leupold approach there appear two observers, one of them – we can call it observer of the first order – following a simple process and ”translating” the steps of the process in an external language, and the second observer, closer to the Searle-Toffoli observer, interpreting as a computation the results of the activity of the first observer. Cavaliere and Leupold consider a series of process-observer (of the first order) pairs which, separately, have a reduced (computing) power, but which, together, lead to the computing power of Turing machines from the point of view of the external observer. 6 The Turing Machine Let us start also from another direction, from the meaning given by mathematics to the notion of computation. Already from the thirties of the previous century we have a definition of what is computable, the answer Alan Turing gave to the question ”what is mechanically computable?”, formulated by David Hilbert at the beginning of the twentieth century. ”Mechanically”, i.e., ”algorithmically” in our today reformulation. There were many proposed answers (I recall only the recursive functions and the lambda-calculus), given by great names of mathematicscomputer science (I recall here only Alonzo Church, Stephen Kleene, Emil Post), but the solution given by Turing, what we call now Turing machine, has been accepted as the most convincing one (a fact certified even by the highly exigent G¨odel). This is now in computer science the standard model of an algorithm (I have not said definition, because we have only an intuitive understanding of the idea of an algorithm, but we can say that in this way we have a definition of what is computable). Without entering into details, I mention only that Hilbert’s problem was more general. It started from the algorithmic resolution of diophantine equations, those with integer coefficients (the tenth problem in Hilbert’s 1990 list), but in its later (in 1928) formulation Hilbert was saying that ”the Entscheidungsproblem [the decision problem in the first order logic] would be solved if we would have a procedure which, for any logical expression we would decide through a finite number of operations whether it is satisfiable... Entscheidungsproblem should be considered the main problem of the mathematical logic”. At this general level, G¨odel theorems answer negatively Hilbert’s program. Negative answers gave also Church and Turing, while Hilbert tenth problem was solved – also negatively – in 1970, by Yurii Matijasevich (after many efforts of several mathematicians: Julia Robinson, Hilary Putnam, Martin Davis). Turing not only gives a negative answer, moreover, he not only defines ”the frontiers of computability”, but he also produces an example of a problem placed behind these frontiers, a problem which is not algorithmically solvable, the halting problem (there is no algorithm, hence a Turing machine, which, taking as input an arbitrary Turing machine, can tell us, in a finite number of Looking for Computer in the Biological Cell 257 steps, whether the given input machine halts or not when starting from an arbitrarily given initial data). To the halting problems reduce, directly or indirectly, most if not all undecidability results obtained after that. The Turing machine is so important for computer science, including the natural/unconventional computability, that it is worth discussing it a little bit more. 7 Some More Technical Details It is interesting to note that when he defined his ”machine”, Turing explicitly started – he states this at the beginning of the paper – from the attempt to abstract the way a human being computes, reducing to the minimum the resources used and the operations made. In this way, in the end one obtains a ”computer” which consists of a potentially infinite tape, bounded to the left, divided in cells where one can write symbols from a given finite alphabet; these symbols can be read and rewritten by a read-write head, which can ”see” only one cell, can read the symbol written there, can change it, then it can move to the neighboring left or right cell or it can stay in the same place; the activity of the read-write head is controlled by the finitely many states of a memory. Thus, we get instructions of the form s1a→s2bD with the following meaning: in state s1, with the head reading symbol a, the machine passes to state s2, modifies ato b(in particular, aand bcan be identical), and moves the read-write head as indicated by D. One starts with the tape empty, with the machine in a special initial state s0; one writes the initial data on the tape (for instance, two numbers which have to be multiplied), one places the head on the first cell of the tape (the leftmost one), and one follows the instructions of the (e.g., multiplication) ”program” until one reaches a final state and the machine halts, no further instruction can be applied. The contents of the tape at that moment is the result of the computation. Extremely reductionistic, but this is the most general model of an algorithmic computation – because no previous definition of what is computable is known, this assertion is only a hypothesis, called the Turing-Church thesis. However, what made Turing machine so attractive were not only the simplicity of its definition and its power (it was proved that the Turing machine can simulate any other computing model), but also its robustness (the computing power is not changed if we add further ingredients to the architecture or to the functioning, such as further tapes, if we infinitely prolong the tape also to the left, if we consider non-deterministic computations, etc.), and, mainly, the existence of universal Turing machines: there exists a fixed Turing machine T MU which can simulate any particular Turing machine T U, in the following sense. If a code of the machine T M (let us denote it by code(T M)) is placed on the tape of T MU together with an input xof T U, then T MU will provide the same result as that provided by T U when starting from input x. A little bit more formally (but still omitting some details – e.g., codifications), we can write T MU(code(T M), x) = T M(x). And Turing proved that there are universal Turing machines. This was done in 1936, in the paper ”On 258 Gh. P˘aun computable numbers, with an application to the Entscheidungsproblem”, published in Proceedings of the London Mathematical Society, Ser. 2, vol. 42, 1936, 230–265, with an erratum in vol. 43, 1936, pages 544–546. This is the ”birth certificate” of the today computers, consequently called of Turing-von Neumann type (in forties, when he has participate in the designing of the first programmable electronic computers, von Neumann was influenced by Turing ideas). A couple of things deserve to be mentioned: the code of machine T M is the program to be executed/simulated on T MU, starting from the data x; the instructions of T MU form the ”operating system” of our ”computer”; the data and the programs are written in the same place, on the tape of the universal Turing machines (in the ”computer memory”) – from here it follows the possibility to process programs in the same way as we process data, hence the vulnerability of programs to computer viruses. Several details are important from the point of view of natural computing. The work of the Turing machine is sequential, in each time unit one performs only one instruction. In many places in nature, if not in most of them, in particular, in biology, the processes develop in parallel, which is a very appealing feature for computer science, but these processes are not necessarily synchronized, which, in turn, raises difficulties for computer science. There also are further differences between Turing machines, the ”biological computers”, and the electronic computers, but we will discuss these differences later. For the time being we keep in mind that in what follows to compute has the meaning suggested by Turing machines: there are an input and an output, between them there is an algorithm which bridges inputs and outputs, and the result of a computation is obtained in the moment when the machine halts. Very restricted, but precise. With such a framework at hand, we can look around for computations, moreover, we can investigate them in a well developed context, the computability theory – actually, a set of several theories, such as automata theory, formal language (grammar) theory, complexity theory and others. 8 Computer Science and Mathematics This is maybe the place to remind a debate which motivated many discussions and points of view, often biased, concerning the relation between computer science and mathematics. Discussions of this kind have appeared also in the Romanian Academy, they appeared in the higher education (in the sixties-seventies of the last century, at the time of sputniks and hydroelectrical plants, we had many faculties of ”mathematics-mechanics”, now mechanics was replaced by computer science), the issue is often debated in mass media. Actually, the context is larger, sometimes it is put in question the relation of mathematics with other sciences, with school education, with the society. There are persons who are proud of the fact that they Looking for Computer in the Biological Cell 259 ”were not good in math”. It was even expressed the opinion that mathematics is a luxury, a ”national fetish” (this expression has recently appeared in the title of a Romanian newspaper article), in short, that one makes too much fuss of mathematics and one teaches too much mathematics. This opinion is getting more and more popular, supported also by the ubiquitous penetration of computers (”we no longer need to know the multiplication table, the computer knows it for us”). Of course, there is a problem with the mathematical education. What, how much, and, mainly, how? – and there also are further questions; we can find them, often also together with solutions, in the papers dedicated in the last years by professor Solomon Marcus to education. The problem cannot be solved from bottom up, the mathematicians involved in research and in higher education should consider it – this is, for instance, the opinion of Juraj Hromkovic, from ETH Z¨urich, formulated in an article published in the Curtea de la Arge¸s journal (www.curteadelaarges.ro, August 2014), based on the practical activity in this respect carried out in the institute where J. Hromkovic works (among others, this activity was materialized in mathematical school books of a new type). In general, the mathematicians should enter public debates and plead for their discipline, mainly they are guilty if the domain loses its popularity. It is true that for a mathematician mathematics is a great game, which, like any game, has an intrinsic rewarding, in the very development of the game, therefore it is natural that the interest for ”popularization” is low among mathematicians, but the persons who are proud of their mathematical infirmity, be it real or only claimed, are always much more visible, more vocal, and the danger which comes from this is obvious. Having in mind only the relation between mathematics and computer science, let us mention that the theoretical computer science, placed at the intersection of the two domains, is often considered by computer scientists as a part of mathematics, and by mathematicians as a part of computer science. Sometimes, theoretical computer science has problems even inside computer science – as it happens also with other theoretical branches of science with a strong practical dimension. Of course, all these are false problems by themselves, but they can have unpleasant practical consequences. Being of the same opinion, I cite here an authoritative voice, that of Edsger W. Dijkstra, one of the classics of computer science, in fact, of the practical computer science: it is sufficient to remind that during sixties he has worked for implementing the Algol language in the Amsterdam Mathematical Center, and, furthermore, he was the promoter of structured programming, well-known among the software practitioners. (Maybe it is good to add here that the first four years after graduation I have intensively written computer programs, in Cobol and Fortran, realizing even the programs for computing the salaries of the workers in a large Bucharest factory – I remember, therefore, what practical computer science means...) ”The end of computer science?”, asks Dijkstra, ironically-rhetorically, already in the title of a note published in Communications of the ACM (vol. 44, March 2001, page 92), which starts with the following phrase: ”In academia, in industry, and in the commercial world, there is a widespread belief that computing science as 266 Gh. P˘aun A beautiful theory, which, however, in its basic version has three weaknesses: (1) it cannot tell us yet whether or not P=NP, whether or not polynomial solutions can be found also for the problems which are now supposed to be of an exponential complexity, (2) the theory does not take into account such ”details” as the coefficients and the degree of the polynomials and which, at the practical level, can have a crucial influence on the computation time, and (3) the theory takes into consideration the extreme cases, it is of the worst case type, it counts the steps of computations which solve the most difficult instances of a problem, while the reality is placed in most cases in the middle, near the ”average”. Here is an example with a practical relevance: the linear programming problem is in P, because the ellipsoid algorithm of Leonid Khachiyan (1979) solves the problem in a polynomial time, but this algorithm is so complex that practically, in most cases, it is less efficient than the old simplex algorithm, proposed during the Second World War, considered one of the most important ten algorithms ever imagined, but which is, theoretically, of an exponential complexity. For these reasons, the complexity theory was refined and diversified (average complexity, approximate algorithms – these algorithms have a direct connection with natural computing), while the definition of tractability was carefully redefined. Anyway, the general feeling was transformed in a slogan: the Turing-von Neumann computers cannot solve in a reasonable time problems of an exponential complexity. The interest for the P=NP problem is enormous. On the one hand, most of the (no-trivial) practical problems are in the class NP and are not known to be in P, hence they are (considered) intractable, cannot be efficiently solved, on the other hand, most of the cryptographic systems in use are based on problems of an exponential complexity, hence solving them in a polynomial time would lead to breaking these systems. The problem whether Pis or not equal to NP was already formulated in 1971 (by Stephen Cook), and in the year 2000 it was included by Clay Mathematical Institute, Cambridge, Massachusetts, in the list of the seven ”millennium problems”, with a prize of one million dollars for a solution. While the importance of this problem for the theoretical computer science cannot be overestimated, it is not clear which would be the practical consequences of a solution, whichever this will be. There were many discussions on this topic – see, for instance, S. Cook, ”The importance of the Pversus NP question”, Journal of the ACM, vol. 50, 2003, pages 27–29. If a proof of the strict inclusion of Pin NP will be obtained, as most computer scientists (but not all of them!) believe, then almost nothing will be changed at the level of the practical computer science. If the equality will be proved in a non-constructive manner, or the proof will be a constructive one, but in a non-feasible manner (polynomial solutions to problems in NP will be found, but with polynomials of very high degrees or with very large coefficients), then the practical consequences will not be significant (but a race will start for ad-hoc solutions, having the time estimated by polynomials with reasonable degrees and coefficients). If, however, a ”cheap” passage from NP Looking for Computer in the Biological Cell 267 to Pwould be found, then the consequences for the practical computer science will be spectacular – in the good sense, excepting the cryptography, where the consequences will be dramatic. At the level of the software there is one further problem, which I recall here in the formulation of Edsger W. Dijkstra (from ”The end of computer science?”, the above mentioned paper): ”Most of our systems are much more complicated than can be considered healthy, and are too messy and chaotic to be used in comfort and confidence. The average customer of the computing industry has been served so poorly that he expects his system to crash all the time.” The lack of robustness of the complex software systems is today a concern of the same interest as it was in the year 2000. In order to illustrate the fact that not by means of technological progresses one can face the exponential complexity, let us examine a simple case: let us consider a problem of exponential complexity of the range of 2n, for instance, a graph problem, which can be solved on a usual computer, say, for graphs with 500 nodes, in approximately one quarter of hour; let us suppose that the technology provides us a computer which is 1000 times faster than the ones we have, which is a totally nontrivial advance, not very frequently met. Using the new computer, we will solve the same problems as before in about one second (around 15 minutes means approximately 1000 seconds), but if we try to address the same problem for graphs with more than 500 nodes, the progresses are negligible: with the new computer we will solve in a quarter of hour only problems for graphs with at most 510 nodes. The simple reason for that is the fact that 210 is already bigger than 1000. If the problem were of complexity 3n, then we will stop around 506 nodes... 14 Promises of Natural Computing In order to cope with the exponential complexity, but also for other reasons which I will mention later, computer science has imagined several research directions, most of them also related to the natural computing, even to bio-inspired computing: (1) looking for massively parallel computers, (2) looking for non-deterministic computers/computations, (3) looking for approximate/probabilistic solutions to computationally hard problems. All these three research directions were explored already in the framework of the ”standard” computer science, both at the theoretical level and at the technology level, the electronic one. Multiprocessor computers are available since several years – but without reaching the massive parallelism which is supposed to solve complex problems. If a large number of processors are put together, there appear other problems, some of them technological (e.g., high temperature dissipation), others, maybe more important, theoretical, concerning the synchronization of the processors. A distinct research area deals with the synchronization complexity – see, for instance, Juraj Hromkovic monograph Communication Complexity and Parallel Computing, Springer-Verlag, 1997. One of the conclusions of this theory 268 Gh. P˘aun says that, for a large number of processors, the synchronization cost (measured by the number of bits necessary to this aim) becomes larger than the cost of the computation itself, which suggests to get rid of synchronization, but then other problems appear, as we are not accustomed to use asynchronous computers. Even less used we are to construct and utilize ”non-deterministic computers”. In exchange, the last of the three ideas mentioned above is rather attractive, and in this respect of a great help is the ”brute force” of existing computers. The approach is useful especially in addressing complex optimization problems: exploring randomly the candidate solutions space, for a large enough time, with a sufficiently high probability we will reach optimal or nearly optimal solutions. Approximate solutions, possibly found with a known probability of being optimal. Here it enters the stage, with great promises, the natural computing. From now on I will only refer to the one having a biological inspiration. In a cell, a huge number of ”chemical objects” (ions, simple molecules, macromolecules, DNA and RNA molecules, proteins) evolve together, in an aqueous solutions, at a high degree of parallelism, and, at the same time, of non-determinism, in a robust manner, controlled in an intricate way, successfully facing the influences coming from the environment, and getting in time very attractive characteristics, such as adaptation, learning, self-healing, reproduction. Many other details are of interest, such as the reversibility of certain processes or the energy efficiency, with the number of operations per Joule much bigger than in the case of the electronic processing of information (erasing consumes energy, that is why the reversible computers are of interest; see, e.g., R. Landauer, ”Irreversibility and heat generation in the computing process”, IBM Journal of Research and Development, vol. 5, 1961, pages 183–191, and C.H. Bennett, ”Logical reversibility of computation”, Idem, vol. 17, 1973, pages 525–532). It seems, therefore, that during millions of years of evolution nature has polished many processes (and material supports for them) which wait to be identified and understood by the computer scientists, in order to learn new computability methods and paradigms, maybe for constructing computers of a new kind. And, the computer scientists have started to work singe a long time... Here are a few steps on this road, very shortly: Genetic algorithms, as a way to organize the search through the space of candidate solutions, imitating the Darwinian evolution, in order to solve optimization problems. Generalization to evolutionary computing and evolutionary programming.Neural networks, trying to imitate the functioning of the human brain, also used for finding approximate solutions, especially for pattern recognition problems. A little bit later, DNA computing, which has proposed a new hardware, massively parallel, based on using the DNA molecules as a support for computations. Even younger, membrane computing, taking as the starting point the biological cell itself and cell populations. In turn, the evolutionary computing, in general, the area of approximative algorithms inspired from biology, is spectacularly ramified, in the most diverse (in certain cases, also picturesque) directions: immune computing, ant colony algorithm, bee colony algorithm, swarm computing, water flowing computing, cultural Looking for Computer in the Biological Cell 269 algorithm, cuckoo algorithm, strawberry algorithm – and it is highly probable that in the meantime further algorithms have been proposed... It is important to note that all the above mentioned branches of natural computing, with the exception of DNA computing, are meant to be implemented on the usual computer, in the aim of having a better use of it; one proposes new types of software/algorithms, not to change the computers architecture or new types of hardware. 15 Everything Goes Back to Turing In a certain sense and in a certain extent, the whole history of theoretical computer science is related to biology, it has searched and has found inspiration in biology. I have already mentioned that, in 1935-1936, when he has defined the machine which bears now his name, Turing tried to imitate the way the humans are computing. After one decade, McCullock, Pitts, Kleene have founded the theory of finite automata starting from the modeling of neurons and of neural networks. Later, the same starting point led to what is called today neural computing. It is interesting to note that the beginnings of this research area can be identified in unpublished papers of the same Allan Turing. We have here an interesting case which can illustrate the influence of psychology and sociology on the development of science, telling about uninspired group leaders and about researchers interested more in their research than in the publication of the obtained results. Specifically, in 1948, Turing has written a short paper, called ”Intelligent machinery”, which has remained unpublished until 1968, because his boss from the London National Physical Laboratory, ironically, named sir Charles Darwin, the grandson of the famous biologist with the same name, has written on the corner of the first page of the paper ”schoolboy essay”, thus preventing the publication. ”In reality, this farsighted paper was a manifesto of the field of artificial intelligence. In the work (...) the British mathematician not only set out the fundamentals of connectionism but also brilliantly introduced many of the concepts that were later to become central to AI, in some cases after reinvention by others.” – I have cited from B.J. Copeland, D. Proudfoot, ”Alan Turing’s forgotten ideas in computer science”, Scientific American, April 1999, pages 77–81. Among others, Turing paper introduces two types of ”neural networks”, with the neurons randomly connected. This was proposed as a first step towards an intelligent machine, one of the key features of these networks being that of learning, of getting trained for solving problems. This is neural computing avant la lettre, with the main ideas rediscovered later, without referring to Turing. Details about Turing ”unorganized machines” can also be found in C. Teuscher, ed., Alan Turing. Life and Legacy of a Great Thinker, Springer-Verlag, 2003, and in C. Teuscher, E. S´anchez, ”A revival of Turing’s forgotten connectionist ideas: exploring unorganized machines”, from Proc. Connectionist Models of Learning, Development and Evolution Conf., Li´ege, Belgium, 2000 (R.M. French, J.J. Sougne, eds.), Springer-Verlag, 2001, pages 270 Gh. P˘aun 153–162. Furthermore, at the address http://www.AlanTuring.net one can find details about Turing unpublished manuscripts and about the recent efforts to reintroduce them in circulation. The same Turing, in the same year 1948, has proposed the ”genetic or evolutionary search”, the first ideas of the evolutionary computing developed later, a domain which contains now several powerful branches, (re)launched during the years: evolutionary programming (L.J. Fogel, A.J. Owens, M.J. Walsh), genetic algorithms (J.H. Holland), evolutionary strategies (I. Rechenberg, H.P. Schwefel), all three initiated in the sixties, genetic programming (J.R. Koza, the years 1990). The first experiment of computer ”optimization through evolution and recombination” was carried out in 1962, by Bremermann. Details can be found in A.E. Eiben, J.E. Smith, Introduction to Evolutionary Computing, Springer-Verlag, 2003. It would not be completely surprisingly if among Turing manuscripts we would discover also ideas related to DNA computing – let us remember that Turing died in June 1654, and the Nature paper where J.D. Watson and F.H.C. Crick described the double helix structure of the DNA molecule was published one year before (”A structure for deoxyribose nucleic acid”, vol. 171, April 25, pages 737–738). It is worth mentioning that two other concepts with a high career in computer science come from Turing, thus supporting the assertion that ”everything starts with Turing”. First, Turing himself raised the question whether or not one can compute... more than the Turing machine, imagining Turing machines with oracles, which is a much investigated topic in the current computer science. Then, Turing can be considered not only a founder of artificial intelligence, but also a forerunner of what is called now artificial life: in the last years of his life, Turing was interested in morphogenesis, in modeling the evolution from the genes of a fertilized egg to the structure of the resulting animal. 16 An Encouraging Example: The Genetic Algorithms Before passing to the DNA and membrane computing, topics which I will describe in more details, let us spend some time discussing a branch of natural computing inspired from biology which is, at the first sight, surprisingly efficient. This is the genetic algorithms area, used for solving complex optimization problems for which there do not exist deterministic optimal algorithms or these algorithms are not efficient. The implicit slogan can look confusing: if you do not know where to go, then go randomly – with the mentioning that the ”randomness” here is directed, the ”random walk” is done ”like in nature, in species evolution”. Everything is a metaphorical imitation of some elements from the Darwinian evolution. Let us assume we have a two variables function (we can suggestively represent it as a ground surface, with valleys and hills) for which we need to find the maximum (one of them, if there are several). If we cannot analytically address the problem, then we can choose to walk randomly through the definition domain, looking for the greatest value of the function. To this aim, we represent the Looking for Computer in the Biological Cell 271 domain points as ”chromosomes”, binary strings of a constant length, we choose (randomly or through other methods) a given number of starting points, and we compute the function value for all of them. Then we pass to ”evolution”: we take two by two the ”chromosomes” and we recombine them (by crossover), that is, we cut them at a specified position and then we recombine the fragments, the prefix of one ”chromosome” with the suffix of the other one and conversely. In this way, we obtain two new ”chromosomes”, describing two new individuals of the next ”generation”. We repeat this procedure for a specified number of times, we select the best solution obtained so far, and we stop. Nothing guarantees that in this way we reach the solution of the problem, that, for instance, we do not get stuck in a local maximum, without being able to escape, but, and this is the (pleasant) surprise, in a large number of practical applications, this strategy works. Sure, there are a lot of variations of the previous scenario, it is even said that the monographs in this area are a sort of ”cooking books”, collections of recipes, lists of ingredients and suggestions of improvements of the algorithms: besides recombination, similar to the biological evolution, one also uses the local mutation operation, the passing from a generation to another one can be done in many ways, the ”chromosomes” population can be distributed, we can evolve it locally, communicating in a way or another among regions, there are several halting criteria, and so on and so forth. We have here at work the brute force of the computers and the evolutionary metaphor – with results, I repeat and stress it, unexpectedly good: non-intuitive solutions, rapid initial convergence, in many cases succeeding to avoid local maxima. The only ”explanation” for these good results is the ”bio-mystical” one: genetic algorithms are so good because they involve ingredients which nature has polished for many millions of years in the species evolution. All these induce, at the same speculative level, a rather optimistic conclusion: if the genetic algorithms are so useful, in spite of the lack of any mathematical argument for their usefulness, let us try to imitate biology also in other aspects, with a great probability that, if we are similarly inspired to extract the right ideas, to obtain other fruitful suggestions for improving the use of the existing computers and, maybe, for imagining computers of other kinds, more efficient. However, this optimism should be cooled down by the observation that a famous result in the area of evolutionary computing, in the area of approximate optimization algorithms in general, is the so-called no free lunch theorem of David Wolpert and William Macready (1997), which, informally, says that any two methods of approximate optimization are equally good, in average, over all optimization problems. ”Equally good” can be also read ”equally bad”, for each method there are problems for which the method does not provide satisfactory solutions. 17 A Coincidence Before passing to DNA computing, an autobiographical intermezzo. In April 1994 I was in Graz, Austria, attending a conference, and there I got a copy of the paper 272 Gh. P˘aun by Tom Head, from State University of New York at Binghamton, USA, soon after that a friend and collaborator, ”Formal language theory and DNA: An analysis of the generative capacity of specific recombinant behaviors”, published in Bulletin of Mathematical Biology, vol. 49, 1987, pages 737–759. It was a revelation. I was then after twenty years of formal language theory research and I immediately felt that it is open there a large area of application of what I have done before. It is true, I should had a similar revelation earlier, namely when I have read professor Solomon Marcus paper ”Linguistic structures and generative devices in molecular genetics”, from Cahiers de Linguistique Th`eorique et Appliqu´ee, vol. 11, 1974, pages 77–104, but probably it was too early, at that time I had not passed yet through the twenty years of preparation for natural computing which will be shortly described in a forthcoming section. In his paper, Tom Head introduces a formal operation with strings which formalizes the operation of recombination of DNA molecules. He calls it splicing, and I will call it in the same way, thus distinguishing it from the recombination operation from the genetic algorithms. The two operations are related, but they are not identical. Still being in Graz, I have imagined a sort of grammar based on the splicing operation, in fact, a variant simpler than that of Tom Head and closer to the string operations in language theory. The paper emerged in this way was published in Discrete Applied Mathematics and it consecrated the splicing version I have proposed. After a few weeks, I was in Leiden, The Netherlands, where I have written a paper together with Grzegorz Rozenberg and Arto Salomaa, the latter one from Turku, Finland, the place where I have spent after that several years, initially devoted to DNA computing and then to membrane computing. As usually well inspired, G. Rozenberg gave to our paper the title ”Computing by splicing”. Because, starting then, we have named H systems the computing devices based on splicing, thus reminding the name of the one who has introduced (invented of discovered?...) the respective operation, we have sent the paper, in manuscript, to Tom Head. He has immediately replied, by phone, asking us rather excited: have you known that right now it was carried out a successful experiment of computing with DNA?! No, we did not know – this was only a coincidence, which I place in the category of significant coincidences. 18 The First Computation in a Test Tube Tom Head was talking about Leonard Adleman experiment, published in the autumn of 1994 in Science, nr. 226, November 1994, pages 1021–1024: ”Molecular computation of solutions to combinatorial problems”. Speculations about the possibility of using DNA molecules for computing were made already in seventies of the last century (Ch. Bennett, M. Conrad, even R. Feynman, with his much invoked phrase ”there is plenty of space at the bottom”, referring to physics but also extended to biology). Adleman has confirmed these expectations, solving in a laboratory the problem whether a Hamiltonian path exists or not in a given graph (I have mentioned it in a previous section). The problem is known to be NP- complete, hence among the most difficult intractable problems, of an exponential Looking for Computer in the Biological Cell 273 complexity (we assume that Pis not equal to NP), but Adleman solved it in a number of steps which is linear with respect to the size of the graph. It is true, these steps are biochemical operations, performed by making use of a massive parallelism, even of non-determinism, all these made possible by the characteristics of the DNA molecules and the related biochemistry. In short, millions of copies of one stranded sequences of nucleotides, codifying the nodes and the edges of the graph, were placed in an aqueous solution. Then, by decreasing the temperature of the solution, these sequences annealed, forming double stranded molecules, corresponding to the paths in the graph. Because there were used sufficiently many copies of the initial sequences, with a high probability we obtain in this way all paths in the graph. From them, the paths were selected which pass through all nodes, and this was done by usual laboratory procedures: gel electrophoresis for separating the molecules according to their length, then selection through denaturation and amplification by PCR of the paths passing through all nodes (hence Hamiltonian). This procedure assumes a number of biochemical operations which is linear with respect to the number of the nodes in the graph. The problem is NP-complete, hence this is an extraordinary achievement – and the consequences were accordingly sound. Already in the next year, 1995, it was organized in Princeton a meeting with the title ”DNA Computing”, which became an international conference which is still continuing. However... 19 Pro and Against Arguments Adleman experiment was a historical achievement, the proof that it is possible. However, the experiment has considered a graph with only 7 nodes, for which the problem can be solved by a simple visual inspection. In comparison, at the beginning of the nineties, the computers were already able to solve the Hamiltonian path problem for graphs with several hundred nodes, sufficient for current practical applications (in the meantime, the progresses continued). Moreover, the solution was obtained by means of a space-time trade-off, the number of molecules used was exponential with respect to the number of nodes. Juris Hartmanis, an authoritative name in computer science, after expressing his enthusiasm (Hartmanis compares computer science with physics: while the latter progresses by means of crucial experiments, the former progresses by means of proofs that something can be done, by demos; Adleman has produced such a demo!), has computed the quantity of ADN which is necessary in order to apply Adleman’s procedure for a graph with 200 nodes and he has found that the weight of the ADN would be greater than the weight of the Earth... From a practical point of view, DNA computing is, in a certain extent, in the same point even now. Numerous experiments, but all of them always dealing with ”toy problems”, a lot of theory, a lot of lab experience gained in dealing with DNA molecules, with results of interest for the general lab technology (just one example: 274 Gh. P˘aun an improved version of PCR, the Polymerase Chain Reaction, called XPCR, was proposed; one of the inventors is a mathematician, Vincenzo Manca, mentioned already in the first pages of this text), but the domain has moved towards nanotechnology, no computability practical applications were reported (unless if, and this is plausible, there were applications in cryptography which are still classified). However, the list of possible advantages of using DNA molecules for computing is large: a very good efficiency as a data support, with one bit at the level of a nucleotide; energy efficiency; parallel and non-deterministic behavior, two dreams of computer science (with the mentioning that the non-determinism also brings problems, for instance, providing false solutions); a very developed laboratory technology; robustness, predictability, reversibility of certain processes. 20 The Marvelous Double Helix The DNA molecule has surprising properties at the informational and computational level. Let us remind that, formulated in ”syntactic” terms, we have two strings of letters A, C, G, T, the four nucleotides, placed face to face, in Watson- Crick complementary pairs, always A being paired with T and C with G. The two strings are oriented, in opposite directions with respect to each other; the biochemists indicate the directionality by marking one end of a string with 30and the other end with 50. There already appear here a surprise, first pointed out by G. Rozenberg and A. Salomaa in Technical Report 96-28 of Leiden University, The Netherlands (October 1996), ”Watson-Crick complementarity, universal computations, and genetic engineering”: the structure of the DNA molecule ”hides”, in a codified manner, the computing power of Turing machines! The formulation above is not precise, it however corresponds to the following observation. Already in 1980, it was proved (J. Engelfriet and G. Rozenberg) that any language whose strings can be recognized by a Turing machine can be written as the image of a specified fixed language, let us denote it with T S(0,1), by means of a sequential transducer. The previous language is the so-called ”twin-shuffle” over 0, 1 (hence the used notation). Shuffle is the operation of mixing the letters of the two words, without changing their ordering (exactly as in the case of shuffling two decks of playing cards of different back colors). Here we shuffle the letters of two ”twin” words, one string of symbols 0, 1 and the second string identical with this one, but changing the ”color” of each symbol (for instance, we can add an upper bar or a prime to each symbol in order to get the twin string). In turn, the sequential transducers are the simplest transducers, with a finite memory and with a head which scans the string from left to right. Let us note that we work with four symbols, let us say 0, 1 and their pairs 00,10. Exactly the number of the nucleotides, four. Let us also note that T S(0,1) is a fixed language. Given an arbitrary language, if it is recognized by a Turing machine, then it can be obtained from this unique language T S(0,1), only the transducer depends on the language. Looking for Computer in the Biological Cell 275 The nice and significant surprise is that the language T S(0,1) can be obtained by means of ”reading” the DNA molecules, in the following way: let us walk along the two Watson-Crick complementary sequences, from the left to the right, advancing randomly along the two strands, and associating with the four nucleotides A, C, G, T symbols 0, 1 according to the following rule: A= 0, G = 1, T = 00, C = 10. Collecting all these strings over 0,1,00,10, for all readings of all DNA molecules, we get a set which is exactly T S(0,1)! Consequently, any language which can be defined by a Turing machine can be obtained by translating these readings of the DNA molecules by means of the simplest transducer, the sequential one, with a finite memory. The transducer depends on the language, it ”extract” from T S(0,1) the result of the computations of a Turing machine. The power is there, what we have to do is only to make it visible. (In a certain sense, we have again the coupling of a simple process, the ”reading” of the DNA molecule, and an observer of the first order, a simple one, the sequential transducer, like in the papers of M. Cavaliere and P. Leupold mentioned before, with the result reaching the highest level of computability, the power of Turing machines.) Two questions arise in this framework. For instance, we mentioned the different orientation of the two strands of the DNA molecule, but in the previous reading we pass along the two strands in the same direction, from the left to the right. There is no problem, the reading of the double stranded DNA molecules can proceed in opposite directions and the result is the same. Second: nature is redundant, are all the four nucleotides (the four symbols 0,1,00,10) necessary in order to cover, in the sense discussed above, the power of Turing machines? No, three symbols are sufficient – but not two! Proofs for all these results can be found in the monograph (translated in Japanese, Chinese, and Russian) Gh. P˘aun, G. Rozenberg, A. Salomaa, DNA Computing. New Computing Paradigms, Springer- Verlag, 1998. Speaking about computations and redundancy, let us remember that a large part of the DNA molecule is ”residual”, it does not codify genes and we do not exactly know what it is used for. We can then speculate: if in the cell, at the genetic level, one performs computations (the viruses are strings of nucleotides, hence their identification is a parsing operation, hence a computation), and these computations are supposed to be complex, why not?, even of the level of Turing machines, then we need a ”workspace”, a ”tape” which in the end remains empty in most of its length, with the result placed in a finite part of it (at the beginning in the case of the Turing machine tape). Can then the DNA without an apparent usefulness be the workspace for complex computations, which we cannot yet understand? 21 Computing by Splicing In his experiment, Adleman has not used the splicing operation, but the biochemical ingredients specific to the splicing have been used in many other cases: 282 Gh. P˘aun Avan¸cado de Comunica¸cao e Semi´otica. Biossemi´otica e Semi´otica Cognitiva, Sao Paolo, Brasil, 1998. In this context we can also remember the essential role of the water in the life of the cell, as well as the processes of moving water molecules across membranes through the dedicated channels, the aquaporines, in whose discovery our colleague Gheorghe Benga had pioneering contributions. 27 A Terminology-History Parenthesis Before passing to a quick description of membrane computing, let me point out a few preliminary things. First, about the name of the domain. I have called it membrane computing, starting from the position of the membrane in the life of the cell, in its architecture and functioning, but the choice was not the best one. ”Cellular computing” was probably the most ”marketable” choice, but I have discarded it as being too comprehensive. Then, the name of the models: in the first papers, I used ”membrane systems”, but soon those who started to investigate these models have called them ”P systems”, continuing the line of other computing devices having a name (H systems are the closest ones). In the beginning this induced to me some public discomfort, for instance, during conferences, but the letter P soon became autonomous, completely neutral to me. What is interesting is that there are papers which use the syntagma ”P system”, sometimes even in the title, without citing any paper of mine. Of course, it would be a great success if this syntagma will became largely folkloric... The domain has grown very rapidly and it is still active after more than sixteen years since its initiation. I have sometimes asked myself which were the explanations, and what I can do for enhancing the growth. Several aspects concurred to the interest for the membrane computing: the favorable context (the natural computing ”fashion” mentioned in the beginning); the right moment, on the one hand, with respect to the DNA computing (which, in some sense, is covered and generalized by membrane computing), on the other hand, with respect to the theoretical computer science in general and the formal language theory in particular. There are several things to be mentioned here. After four decades since the introduction of Chomsky grammars, the formal language theory became ”classical” enough and got somewhat retired from the front research (almost completely in USA), even if there still exist specialized conferences (for instance, about finite automata and their applications) or more general conferences (DLT – Developments in Language Theory). Membrane computing appeared as a continuation and an extension of formal language theory: the main investigation objects are no longer the strings of symbols and the languages, but (I anticipate) the multisets of symbols and the sets of multisets. Strings, without taking into account the ordering of the symbols, more technically speaking, strings ”seen” through the Parikh application, Looking for Computer in the Biological Cell 283 the one which tells us the number of occurrences of each symbol in a given string. The consequence was that a large number of researchers in formal language theory became interested in the new research area. Among them, since the very beginning, important names, such as Arto Salomaa (Finland) and Grzegorz Rozenberg (The Netherlands), Oscar H. Ibarra (USA), Sheng Yu (Canada), Kamala Krithivasan (India), Takashi Yokomori (Japan), Mario J. P´erez-Jim´enez (Spain), as well as very active researchers from my generation, such as J¨urgen Dassow (Germany), Erzs´ebet Csuhaj-Varj´u (Hungary), Jozef Kelemen (The Czech Republic), Rudolf Freund (Austria), Gheorghe Marian and Gabriel Ciobanu (Romania), Yurii Rogozhin (Republic of Moldova), Linqiang Pan (China), many of them coagulating around them research groups dedicated to membrane computing. Somewhat surprising was the rapidly growing number of PhD students – now doctors – who have presented theses in membrane computing. There are over 50 at this moment. I mention only the first two, Shankara Narayanan Krishna (India) and Claudio Zandron (Italy), with the theses presented in 2001, respectively, in 2002. Starting with the summer of 2014, C. Zandron is the chairman of the steering committee of membrane computing. A comprehensive information about the membrane computing area can be found at the domain website from the address http://ppage.psystems.eu, hosted in Vienna (it is the successor of a page which has functioned for many years in Milan, Italy, at the address http://psystems.disco.unimib.it). Of course, it has counted very much the ”sociology” of the domain. A community was soon created, and this is very important, not only in science, but in culture in general. They have contributed to that the seniors mentioned above, the yearly conferences (started in 2000, with the first three editions organized in Curtea de Arge¸s, Romania, where the meeting returned for the tenth edition and where I intend to also organize the twentieth edition) as well as a series of meetings which I would like to specially emphasize, one of a unusual format, which I have organized for the first time in Tarragona, Spain, in 2003. After that, it took place every year in Seville, also in Spain. Because it had to have a name, I called it ”Brainstorming Week on Membrane Computing”. One week when researchers interested in membrane computing work together, far from the current preoccupations, teaching or bureaucratic tasks. A very fruitful idea was to collect in advance open problems and research topics and to circulate them among the participants before the meeting in Seville, then addressed, in collaboration, during the Brainstorming. Very useful meetings – in the website of membrane computing one can find the yearly volumes, with the papers written or only started during the Brainstorming. Very useful was, of course, the Internet. The first paper, ”Computing with membranes”, has waited more than one year before it was published in Journal of Computer and System Sciences (vol. 61, 2000, pages 108–143), but, because I was in Turku, Finland, in the autumn of 1998, I made the paper available on Internet, in the form of an internal report of TUCS, Turku Center for Computer Science (Report No. 208, 1998, www.tucs.fi). Until 2000, when the journal paper 284 Gh. P˘aun has appeared, there were written some dozens of papers, making possible the organization of the first meeting dedicated to this topic, in Curtea de Arge¸s. 28 A Quick View on Membrane Computing Let us not forget: we want to start from the cell and to construct a computing model. The result (the one proposed in the fall of 1988) is something of the following form. We look to the cell and we abstract it until we only see the structure of the hierarchically arranged membranes, defining compartments where multisets of objects are placed (I am using a generic term, abstract, free of any biochemical interpretation); these objects evolve according to given reactions. A multiset is a set with multiplicities associated with its elements, hence it can be described by a string; for instance, aabcab describes the multiset which contains three copies of a, two of b, and one of c. All permutations of the string aabcab describe the same multiset. The reactions, in their turn, are described by multiset ”rewriting” rules, of the form u→v, where uand vare strings which identify multisets. Initially (in the beginning of a computation), in the compartments of our system we have given multisets of objects. The evolution rules start to be applied, like biochemical reactions, in parallel, simultaneously, making evolve all objects which can evolve – and thus the multisets change. Using a rule u→vas above means to ”consume” the objects indicated by uand to introduce the objects indicated by v. We have to notice that the objects and the rules are localized, placed in compartments, the rules in a given compartment are applied only to objects from that compartment. Certain objects can also pass through membranes. We proceed by applying rules until (like in the case of a Turing machine) we get stuck, no rule can be applied, and then the computation halts. The result of a halting computation is ”read”, for instance, in the form of the number of objects placed in a compartment specified in advance. Processing of multisets (of symbols), in parallel, in the compartments defined by a hierarchical structure of membranes – this is the short description of a ”P system”. A distributed grammar, working with multisets of symbols – this is the direct connection with the formal language theory. The working site starting here looks endless. First, one can introduce a large number of variations of P systems, with a mathematical, computer science, biological motivation, or motivated by applications. From the point of view of mathematics, the models should be minimalistic, they have to contain the smallest number of ingredients. For computer science, a computing model is good to be as powerful as possible, in the best case universal, equivalent with the Turing machine, and as efficient as possible, in the best case able to solve NP-complete problems in polynomial time. Biology and applications provide a long list of alternatives, starting with the way of arranging the membranes (hierarchical, as in a cell, or placed in the nodes Looking for Computer in the Biological Cell 285 of an arbitrary graph, as in tissues and other populations of cells), the types of objects (symbols as before, strings or even more complex data structures, such as graphs or bidimensional arrays), the form of the evolution rules (also dependent on the type of objects), the strategies of applying them, the way of defining the result of a computation. I have mentioned before the multiset rewriting rules. They can be arbitrary, non-cooperative (with the left hand multiset consisting of a single object, which corresponds to context-free rules in Chomsky grammars), or, an intermediate case, catalytic (of the form ca →cv, where cis a catalyst, an object which assists object ain its transformation to the multiset v). Then, we have the symport and antiport rules, which move objects from a compartment into another one (example: the antiport rule (u, out;v, in), associated with a membrane, moves the objects indicated by ufrom this membrane to the surrounding compartment and the objects indicated by vin the opposite direction). Very important are the rules which divide membranes, because they increase, even exponentially, the number of membranes in the system. Many other types of rules were investigated (for instance, with a control on their application – with promoters, inhibitors, etc.), but I do not mention them here, the presentation would become too technical for the intentions of this text. If the objects in the compartments of a system are strings, then they evolve by means of operations specific to strings: rewriting, insertion and deletion, or, in order to make the model more uniform from a biological point of view, by the splicing operation from the DNA computing. An interesting situation is that when we work with symbol objects, hence with numbers, but the result of a computation is ”read” outside the system, in the form of the string of the objects which are expelled from the system. It is worth noticing the qualitative difference between the internal data structure, the multiset, and the external one, the string, which carries out positional information. In turn, the applications need a completely different strategy of constructing the models – far from minimalistic, but adequate to the modeled piece of reality; this time not the computing power is of interest, but the evolution in time of the system. I will come back to applications. Over this small jungle of models one superposes the investigation program of the classic computer science: computing power, normal forms, descriptional complexity, computational complexity, simulation programs, etc., etc. 29 Classes of Results (and Problems) Of course, I will not recall precise theorems, but I will only mention the two main classes of results in membrane computing and their general form. Computational completeness/universality: most of the classes of P systems considered so far are equivalent with Turing machines, they are computationally complete. Because the proofs are constructive, in this way one also brings to membrane 286 Gh. P˘aun computing the universality property in the sense of Turing (that is why we speak about computational completeness and universality as they would be synonymous). In most cases, this result is obtained for systems of a reduced, particular form, with a small number of membranes. For instance, cell-like P systems with only two membranes, using catalytic rules (hence not of the general form) can compute whatever the Turing machines can compute. An important detail: two catalysts are sufficient. It is an open problem whether the P systems with only one catalyst are universal. The conjecture is that the answer is negative, but the proof still fails to appear. This is one of the most interesting types of open problems in membrane computing (many of them still open): identifying the precise borderline between universality and non-universality. Efficiency: the classes of P systems which can grow (exponentially) the number of membranes can solve NP-complete problems in a polynomial time. The idea is to generate, in a polynomial time, an exponential working space and then to use it, in parallel, for examining the possible solutions to a problem. Membrane division helps, similarly the membrane creation, similarly other operations. Like in the case of the Adleman experiment, we have again a space-time trade-off, but in our case the space is not provided in advance, but it is created during the computation, through ”mitosis” or by means of other ”realistic” biological operations. There are also in this area open problems concerning the borderline between efficiency and non-efficiency, but more difficult to be stated in plain words. Interesting is a somewhat unexpected fact. Using rules of the form a→aa, applied in parallel, we can produce an exponential number of copies of ain a linear number of steps. (In nsteps, we get 2ncopies of a.) However, such an exponential working space is not of any help in solving high complexity problems in a feasible time– this is what the so-called Milan theorem, from Claudio Zandron PhD thesis, says. If these objects are localized, placed in an exponentially large number of membranes, then the situation is different. Otherwise stated, not only the size of the working space matters, but also its structure, the possibility to apply different rules in different compartments. This is a subtle aspect, which I do not know whether it has been met also in other frameworks. For details, the reader is refereed to the monograph Membrane Computing. An Introduction, published by Springer-Verlag in 2002 (and recently translated in Chinese) and, especially, to The Oxford Handbook of Membrane Computing, edited by Gh. P˘aun, G. Rozenberg, and A. Salomaa and published by Oxford University Press, in 2010. 30 Significations for Computer Science and for Biology A computing model which has the same power as the Turing machine is a good thing, such a computer is universal not only in the intuitive sense, but it is also programmable. Moreover we have here a distributed, parallel computer, with a great degree of non-determinism, controlled in various biologically inspired ways. Looking for Computer in the Biological Cell 287 Let us, however, observe the similarities and the differences between a usual computer program, a set of instructions of a Turing machine, and a set of evolution rules of a P system. In the programming languages, the programs consist of precisely ordered instructions, perhaps labeled and addressed by means of these labels. In the case of the Turing machine, the sequence of instructions to be applied is determined by the states of the machine and by the contents of the tape. In the cell case, the reactions are potential, their set is completely unstructured, and their application depends on the available molecules. The evolution rules are just waiting for the data to which they can be applied, there is a competition between rules with respect to the objects to process. The differences are visible and they suggest once again the question what means to compute in a natural way?, adding now the question whether we can work with programs in the form of completely unstructured sets of instructions. On the other hand, in the first moment, it is expected that the biologist reaction to results of the type of the equivalence with the Turing machine is indifference, a raising of the shoulders. Another domain, another language, another book... But: if the cell is so powerful from a computational point of view, then, according to an old result, the Rice theorem (”all nontrivial problems – having both instances with a positive answer and instances with a negative answer – about a computing model equivalent with Turing machines are algorithmically undecidable”), no nontrivial question about the cell can be solved in an algorithmic way, by means of a program. The biologists formulate every day such questions: How a cell, a cell population, an organ or an organism evolves in time? Is there a substance which gets accumulated over a given threshold, in a given compartment? What happens if we add a multiset of molecules (a medicine), does the state of an organ improves (from specified points of view)? – and so on. If a model of the cell would be decidable, then we could find the answer to such questions by (algorithmically) examining the model, at a given initial state. But, because this is not possible (cannot be done in principle, not only we cannot do it now, here), what remains to do are the laboratory experiment (expensive and time consuming), the computer experiment (cheap, fast, but with the relevance depending on the quality of the model), and, theoretically, the non-algorithmic, ad-hoc, approach. The previous paragraphs can be seen also as a plead for biology to learn new languages, in particular, the language of theoretical computer science, thus having the possibility of raising problems and of finding solutions which cannot appear, cannot be even formulated in the previous language. This would be an essential step towards infobiology. 31 Three Novel Computer Science Problems In the continuation of the discussion about the significance for computer science, let us point out a remarkable fact: natural computing in general and membrane computing in particular raise theoretical questions which were not considered in [Document text truncated for crawler view.]