Small Universal Spiking Neural P Systems

Small Universal Spiking Neural P Systems Andrei P˘aun1, Gheorghe P˘aun2 1Department of Computer Science Louisiana Tech University, Ruston PO Box 10348, Louisiana, LA-71272 USA [email protected] 2Institute of Mathematics of the Romanian Academy PO Box 1-764, 014700 Bucharest, Romania and Research Group on Natural Computing Department of Computer Science and Artificial Intelligence University of Sevilla Avda Reina Mercedes s/n, 41012 Sevilla, Spain [email protected], [email protected] Summary. In search for small universal computing devices of various types, we consider here the case of spiking neural P systems (SN P systems), in two versions: as devices computing functions and as devices generating sets of numbers. We start with the first case and we produce a universal spiking neural P system with 84 neurons. If a slight generalization of the used rules is adopted, namely, we allow rules for producing simultaneously several spikes, then a considerable improvement, to 49 neurons, is obtained. For SN P systems used as generators of sets of numbers, we find a universal system with restricted rules having 76 neurons, and one with extended rules having 50 neurons. 1 Introduction Looking for small universal computing devices is a natural and well investigated topic in computer science, see, e.g., [4], [11], and the references therein. Recently, this issue started to be considered also in membrane computing; first contributions of this kind can be found in [13] (for tissue P systems with string objects processed by splicing operations) and [1] (for symport/antiport P systems). In the present paper, we address the case of the recently introduced (see [3], [9], [10]) spiking neural P systems (in short, SN P systems), computing models which bring into membrane computing (see [8] for an introduction and [15] for updated information) ingredients from neural computing by spiking (see, e.g., [5], [6]). In short, an SN P system consists of a set of neurons placed in the nodes of a directed graph (representing synapses) and sending to each other spikes, identical electrical impulses; the distance between consecutive spikes is the main way to 214 A. P˘aun, Gh. P˘aun encode information; the neurons contain rules for emitting spikes and for forgetting spikes; one neuron is distinguished as the output neuron and its spikes also exit into the environment, thus producing a spike train. Such systems can be used as computing devices in various ways; generating sets of numbers (encoded in the number of steps between consecutive spikes sent into the environment by the output neuron), generating strings (the spike train itself is such a string over the binary alphabet), or computing functions (an input neuron “reads” the arguments of the function from the environment and the output neuron “writes” the function value, in all cases with the numbers being encoded in the distance between consecutive spikes). More precise definitions will be given in Subsection 2.2. Here we deal with the first and the third cases, of SN P systems generating numbers and computing functions. Already in [3], the SN P systems used for computing sets of numbers were proved to be computationally complete (able to compute all Turing computable sets of numbers), but no bound on the number of used neurons was found. The proof from [3] is based on simulating register machines with SN P systems, hence the same strategy as that followed in [1] in search of small universal P systems is useful also here: starting from a small universal register machine as those constructed in [4], we can get a small universal SN P system, with the important mentioning that in [4] one works with register machines computing functions. That is why we also start here with this case. We work with the so-called strong universality (without encodings of the input and output) and we use the standard type of register machines (using ADD and SUB instructions). For this case, a universal register machine with 8 registers and 23 instructions (the halting one included) was constructed in [4]. (The “code” of the particular partial recursive function and the argument of the function are introduced in registers 1 and 2 of the universal machine and the value of the function for that argument, if defined, is found in register 0 when/if the machine halts.) Following then the construction of an SN P system simulating a register machine from [3], with some improvements inspired from [2] and some additional “code optimization”, as well as a suitable input module, we get an SN P system with 84 neurons simulating the register machine from [4]. We may formulate this result as follows: there is a universal “brain” (in the form of an SN P system) with only 84 neurons. Of course, this number needs to be checked for optimality, but it is our expectation that in the framework used here (with the type of SN P systems considered, i.e., with standard rules) it is not possible to significantly decrease the number of neurons. However, if we allow rules which produce two or more spikes, then a considerable improvement of the previous result is obtained: 49 neurons are sufficient for universality. We pass then to the case when SN P systems are used for generating sets of numbers, starting from the observation that a set Q⊆Nis recursively enumer- Small Universal Spiking Neural P Systems 215 able if and only if the characteristic function of Q(equal to 1 for elements of Q and undefined otherwise) is a partial recursive function. Similar results as for the previous case are obtained: 76 neurons are sufficient for universality when using restricted rules and 50 when using extended rules. In the next section we introduce all necessary prerequisites related to register machines, universality, and standard SN P systems. Section 3 gives the first universal SN P system, and in Section 4 we introduce the extended spiking rules and we produce the universal computing SN P system with 49 rules. In Section 5 we consider the case of universal SN P systems working as generators of sets of numbers. 2 Prerequisites The reader is assumed to have some elementary knowledge in theoretical computer science as available from the many monographs in the field (e.g., from [12], [14]), so that we specify here only some notations and basic definitions. For an alphabet V,V∗denotes the set of all strings over V, with the empty string denoted by λ. Aregular expression over an alphabet Vis defined as follows: (i) λand each a∈Vis a regular expression, (ii) if E1, E2are regular expressions over V, then (E1)(E2), (E1)∪(E2), and (E1)+are regular expressions over V, and (iii) nothing else is a regular expression over V. Clearly, we assume that the parentheses are not in V; as a matter of fact, we will often omit “unnecessary parentheses”. Also, E+ 1∪λcan be written as E∗ 1. With each expression Ewe associate its language L(E) as follows: (i) L(λ) = {λ}, L(a) = {a},for a∈V, (ii) L((E1)(E2)) = L(E1)L(E2), L((E1)∪(E2)) = L(E1)∪L(E2),and L((E1)+) = L(E1)+, for all regular expressions E1, E2. The operations used here are the standard union, concatenation, and Kleene +. We also need below the operation of right derivative of a language L⊆V∗with respect to a string x∈V∗, which is defined by L/x ={y∈V∗|yx ∈L}. We pass now to introducing the necessary notions related register machines and universality, then the spiking neural P systems. 2.1 Universal Register Machines We use here register machines given in the form M= (m, H, l0, lh, I), where mis the number of registers, His the set of instruction labels, l0is the start label, lh is the halt label (assigned to instruction HALT), and Iis the set of instructions; each label from His associated with only one instruction from I, thus precisely identifying it (therefore, there are as many labels as instructions). The instructions are of the following forms: 216 A. P˘aun, Gh. P˘aun •li: (ADD(r), lj, lk) (add 1 to register rand then go to one the instructions with labels ljand lk, non-deterministically chosen), •li: (SUB(r), lj, lk) (if register ris non-empty, then subtract 1 from it and go to the instruction with label lj, otherwise go to the instruction with label lk), •lh:HALT (the halt instruction). A register machine Mgenerates a set of numbers in the following way: we start with all registers empty (i.e., storing the number zero), we apply the instruction with label l0and we proceed to apply instructions as indicated by the labels (and made possible by the contents of registers); if we reach the halt instruction, then the number nstored at that moment in a specified register r0is said to be computed by M; if the computation does not halt, then no number is generated. The set of all numbers generated by Mis denoted by N(M). It is known (see, e.g., [7]) that register machines generate all sets of numbers which are Turing computable. A register machine can also compute any Turing computable function: we introduce the arguments in specified registers r1, . . . , rk(without loss of the generality, we may assume that we use the first kregisters), we start with the instruction with label l0, and if we stop (with the instruction with label lh), then the value of the function is placed in another specified register, rt, with all registers different from rtbeing empty. The partial function computed in this way is denoted by M(n1, n2, . . . , nk). In the computing form, the register machines can be considered deterministic, without losing the Turing completeness; then, the ADD instructions li: (ADD(r), lj, lk) have lj=lk(and the instruction is written in the form li: (ADD(r), lj)). In [4], the register machines are used for computing functions, with the universality defined as follows. Let (ϕ0, ϕ1, . . .) be a fixed admissible enumeration of the unary partial recursive functions. A register machine Muis said to be universal if there is a recursive function gsuch that for all natural numbers x, y we have ϕx(y) = Mu(g(x), y). In [4], several universal register machines are constructed, with the input (the couple of numbers g(x) and y) introduced in registers 1 and 2, and the result obtained in register 0, so that, from now on we also assume that the registers are always numbered from 0 to m−1. In general, we directly continue here the results from [4], using one of the universal register machines constructed there, implicitly also the recursive function gwhich encodes the partial recursive function ϕxin the form of the number g(x) as used in the universal register machine. We give now in the notation introduced above the specific universal register machine from [4] which will be used in Section 3 below: we have Mu= (8, H, l0, lh, I), with the instructions (their labels constitute the set H) presented in Figure 1. (The machine from [4] contains a separate check for zero of register 6, of the form “l8: if register(6) = 0, then go to l0, else go to l10”; this instruction was replaced in our setup by l8: (SUB(6), l9, l0), l9: (ADD(6), l10).) Therefore, there are 8 registers (numbered from 0 to 7) and 23 instructions (hence 23 labels), the last instruction being the halting one. The input numbers (the “code” of the partial Small Universal Spiking Neural P Systems 217 recursive function to simulate and the argument for this function) are introduced in registers 1 and 2, and the result is obtained in register 0. l0: (SUB(1), l1, l2), l1: (ADD(7), l0), l2: (ADD(6), l3), l3: (SUB(5), l2, l4), l4: (SUB(6), l5, l3), l5: (ADD(5), l6), l6: (SUB(7), l7, l8), l7: (ADD(1), l4), l8: (SUB(6), l9, l0), l9: (ADD(6), l10), l10 : (SUB(4), l0, l11), l11 : (SUB(5), l12, l13), l12 : (SUB(5), l14, l15), l13 : (SUB(2), l18, l19), l14 : (SUB(5), l16, l17), l15 : (SUB(3), l18, l20), l16 : (ADD(4), l11), l17 : (ADD(2), l21), l18 : (SUB(4), l0, lh), l19 : (SUB(0), l0, l18), l20 : (ADD(0), l0), l21 : (ADD(3), l18), lh:HALT. Fig. 1. The universal register machine from [4] 2.2 Spiking Neural P Systems We introduce now the SN P systems in the form necessary for universality considerations, hence computing functions. A computing spiking neural P system (abbreviated SN P system), of degree m≥1, is a construct of the form Π= (O, σ1, . . . , σm, syn, in, out), where: 1. O={a}is the singleton alphabet (ais called spike); 2. σ1, . . . , σmare neurons, of the form σi= (ni, Ri),1≤i≤m, where: a) ni≥0 is the initial number of spikes contained in σi; b) Riis a finite set of rules of the following two forms: (1) E/ac→a;d, where Eis a regular expression over aand c≥1, d≥0; (2) as→λ, for s≥1, with the restriction that for each rule E/ac→a;d of type (1) from Ri, we have as/∈L(E); 3. syn ⊆ {1,2, . . . , m} × {1,2, . . . , m}with i6=jfor all (i, j)∈syn, 1 ≤i, j ≤m (synapses between neurons); 4. in, out ∈ {1,2, . . . , m}indicate the input and the output neurons, respectively. 218 A. P˘aun, Gh. P˘aun An SN P system with rules as above is said to be of the standard type. The rules of type (1) are firing (we also say spiking)rules, and they are applied as follows. If the neuron σicontains kspikes, and ak∈L(E), k ≥c, then the rule E/ac→a;d∈Rican be applied. This means consuming (removing) cspikes (thus only k−cremain in σi; this corresponds to the right derivative operation L(E)/ac), the neuron is fired, and it produces a spike after dtime units (as usual in membrane computing, a global clock is assumed, marking the time for the whole system, hence the functioning of the system is synchronized). If d= 0, then the spike is emitted immediately, if d= 1, then the spike is emitted in the next step, etc. If the rule is used in step tand d≥1, then in steps t, t + 1, t + 2, . . . , t +d−1 the neuron is closed (this corresponds to the refractory period from neurobiology), so that it cannot receive new spikes (if a neuron has a synapse to a closed neuron and tries to send a spike along it, then that particular spike is lost). In the step t+d, the neuron spikes and becomes again open, so that it can receive spikes (which can be used starting with the step t+d+ 1, when the neuron can again apply rules). The rules of type (2) are forgetting rules; they are applied as follows: if the neuron σicontains exactly sspikes, then the rule as→λfrom Rican be used, meaning that all sspikes are removed from σi. If a rule E/ac→a;dof type (1) has E=ac, then we write it in the simplified form ac→a;d. In each time unit, if a neuron σican use one of its rules, then a rule from Rimust be used. Since two firing rules, E1/ac1→a;d1and E2/ac2→a;d2, can have L(E1)∩L(E2)6=∅, it is possible that two or more rules can be applied in a neuron, and in that case, only one of them is chosen non-deterministically. Note however that, by definition, if a firing rule is applicable, then no forgetting rule is applicable, and vice versa. Thus, the rules are used in the sequential manner in each neuron, at most one in each step, but neurons function in parallel with each other. It is important to notice that the applicability of a rule is established based on the total number of spikes contained in the neuron. The initial configuration of the system is described by the numbers n1, n2, . . . , nm, of spikes present in each neuron, with all neurons being open. During the computation, a configuration is described by both the number of spikes present in each neuron and by the state of the neuron, more precisely, by the number of steps to count down until it becomes open (this number is zero if the neuron is already open). Thus, hr1/t1, . . . , rm/tmiis the configuration where neuron σicontains ri≥0 spikes and it will be open after ti≥0 steps, i= 1,2, . . . , m; with this notation, the initial configuration is C0=hn1/0, . . . , nm/0i. A computation in a system as above starts in the initial configuration. In order to compute a function f:Nk−→ N, we introduce knatural numbers n1, . . . , nkin the system by “reading” from the environment a binary sequence z= 10n1−110n2−11. . . 10nk−11. This means that the input neuron of Πreceives a spike in each step corresponding to a digit 1 from the string zand no spike Small Universal Spiking Neural P Systems 219 otherwise. Note that we input exactly k+ 1 spikes, i.e., after the last spike we assume that no further spike is coming to the input neuron. The result of the computation is also encoded in the distance between two spikes: we impose the restriction that the system outputs exactly two spikes and halt (immediately after the second spike), hence producing a train spike of the form 0b10r−11, for some b≥0 and with r=f(n1, . . . , nk) ( the system outputs no spike a non-specified number of steps from the beginning of the computation until the first spike). In Section 5 the SN P systems are used as number generators – in a way which will be specified there. An SN P system can be represented graphically in a very natural way: the neurons are placed in the nodes of a graph representing the synapses, with the rules and the initial spikes mentioned in each neuron; the input neuron has an incoming arrow and the output neuron has an outgoing arrow, suggesting their communication with the environment. In the next sections we will always present the systems we construct in this way, which is much more transparent (easy to understand) than the symbolic one. 3 A Small Universal SN P System We pass now to constructing the first of the four announced universal SN P systems, namely the one for computing functions and using rules of the standard type. To this aim, we follow the way used in [3] to simulate a deterministic register machine by an SN P system. This is done as follows: neurons are associated with each register and with each label of an instruction of the machine; if a register contains a number n, then the associated neuron will contain 2nspikes; modules as in Figures 2 and 3 are associated with the ADD and the SUB instructions (each of these modules contains two neurons which do not correspond to registers or to labels of instructions, namely the neurons with labels l0 i, l00 i). The work of the system is triggered by introducing two spikes in the neuron σl0(associated with the starting instruction of the register machine). In general, the simulation of an ADD or SUB instruction starts by introducing two spikes in the neuron with the instruction label (we say that this neuron is activated). We do not describe here in detail the (pretty transparent) way the modules from Figures 2 and 3 work (if necessary, the reader can consult [3] in this respect), but we only remark that after incrementing, respectively decrementing (if possible) the value of register r(the number of spikes in neuron σr), we activate exactly one neuron, σljor σlk, as requested by the instruction. Starting with neurons σ1and σ2already loaded with g(x) and yspikes, respectively, and introducing two spikes in neuron σl0, we can compute in our system in the same way as the universal register machine Mufrom Figure 1; if the computation halts, then neuron σ0will contain the double of ϕx(y) spikes. There are two additional tasks to solve: to introduce the mentioned spikes in the neurons σl0,σ1, σ2, and to output the computed number. The first task is 220 A. P˘aun, Gh. P˘aun  Á¿ À Á¿ À ¾ ½» ¼ ¾ ½» ¼  Á¿ À   À SS Sw ¡ ¡ ¡ª HHHH Hj © © © © © ©¼ ZZZ Z~ li a2→a; 0 a→λ l0 il00 i a→a; 0 a→a; 0 r lj a2→a; 0 a→λ Fig. 2. Module ADD (simulating li: (ADD(r), lj)) ' & $ % ¶ µ³ ´ ¶ µ³ ´ ' & $ % ' & $ % ' & $ % ¶ ¶ ¶ ¶ ¶/ AAAAA AU QQQQ Qs ? ¶ ¶ ¶/ HHHH Hj JJ^ lia2→a; 0 a→λ r (a2)+a/a3→a; 0 a→a; 1 l0 i l00 i a→a; 0 a→a; 1 lj a2→a; 0 a→λ a2→a; 0 a→λ lk Fig. 3. Module SUB (simulating li: (SUB(r), lj, lk)) covered by module INPUT presented in Figure 4. The neurons σc1, σc2fire only after receiving the third spike, and then they send two spikes to neuron σl0, thus starting the simulation of Mu. At that moment, neurons σ1and σ2are already loaded: neurons σc3and σc4send to neuron σ1as many pairs of spikes as the number of steps between the first two input spikes, and after that they get “over flooded” by the second input spike and are blocked; in turn, neurons σc5, σc6start working only after collecting two spikes and stop working after receiving the third spike. Small Universal Spiking Neural P Systems 221 ¾ ½» ¼¾ ½» ¼ ¾ ½» ¼ ² ±¯ ° ² ±¯ ° ² ±¯ ° ² ±¯ ° ² ±¯ ° ² ±¯ ° ² ±¯ ° ¡ ¡ ¡ ¡ ¡ ¡ ¡ª © © © © © © © © ©¼ JJJJJJJ J^ QQQQQQ Qs CCCCCCCCW ¢ ¢ ¢ ¢® @@ @R@ @I ¡ ¡µ ¡ ¡ ¡ª ¤ ¤ ¤ ¤ ¤ ¤ ¤² AA AU ¢ ¢ ¢® AAAAAA AU CCCCCCW ¢ ¢ ¢ ¢® ? in a→a; 0 c1 a3→a; 0 c2 a3→a; 0 l0 a2→a; 0 a→λ c3 a→a; 0 a→a; 0 c4 12 a2/a →a; 0 c5 c6 a2/a →a; 0 Fig. 4. Module INPUT The second task needs a modification in the universal register machine: the construction from [3] does not allow subtraction operations on the neuron where we place the result, but register 0 of Muis subject of such operations. That is why we have to add a further register – we label it with 8 – and we replace the halt instruction of Muwith the following instructions: lh: (SUB(0), l22, l0 h), l22 : (ADD(8), lh), l0 h:HALT. In this way, we have 9 registers, 24 ADD and SUB instructions, and 25 labels. We denote by M0 uthe obtained register machine. Having the result of the computation in register 8, which is never decremented during the computation, we can output the result by means of the module OUTPUT from Figure 5. When neuron σl0 hreceives two spikes, it fires and sends a spike to neuron σ8; in this way, the number of spikes of this neuron becomes odd, hence its rule can be applied. A spike arrives in the output neuron, which spikes. From the next step on until exhausting the spikes from neuron σ8, the output neuron receives two spikes (one from σ8and one from σd1), hence neuron σout collects an even number of spikes and cannot fire. When neuron σ8has only one spike, it cannot fire anymore, but one further spike comes in neuron σout from neuron σd1, and thus the output neuron spikes for the second (and last) time. The overall design of the system is given in Figure 6. Thus, we have 228 A. P˘aun, Gh. P˘aun to produce six spikes, in the latter case four. In Figures 9 and 10 we have indicated this by writing the respective rules in the form a11 →aδ(lj),a10 →aδ(lj), and a6→aδ(lj), where δ(l) = ½6 if lis the label of an ADD instruction, 4 if lis the label of a SUB instruction. The simulation of instructions of Muis achieved in this way. The computation in our SN P system halts if and only if the computation in Muhalts, which means that the halting instruction is reached. We have now to see how the INPUT and the OUTPUT modules look like in the case of extended rules. Figures 11 and 12 present these modules. We leave to the reader the task of checking the functioning of the INPUT module (note that l0is the label of a SUB instruction of Mu), and we only briefly describe here the work of the OUTPUT module. We start by activating neuron σlhassociated with the halt label of Mu. (From Figure 1 we know that lhis present only in a SUB instruction of Muas an output label, that is why we do not need a rule a6→a3in this neuron.) When firing, σlh produces 3 spikes, which are sent to neuron σ0. The number of spikes from σ0is of the form 6m+ 3, m ≥0, hence (i) the rules mentioned in Figure 12 for σ0can fire, but (ii) no rule used for SUB instructions (like in Figure 10) can fire (they need 6m+ 4 spikes). This way to avoid the conflict in using the same neuron in two types of operations is the basis for avoiding the two additional instructions of M0 uin comparison with Mu, as well as the additional register 8. Now, if register 0 is empty, then we use the rule a3→a3of R0immediately after activating neuron σlh; the system spikes only once, hence it outputs the number 0. If register 0 is not empty, then for each unit (for each six spikes from σ0) we use once the rule a3(a6)+/a6→a2. This rule does not change the arity of the number of spikes, hence it is used until only 3 spikes remain in σ0. When the first two spikes arrive in σout, this neuron spikes. All subsequent pairs of spikes sent from σ0to σout are forgotten. The last time when σ0spikes, it uses the rule a3→a3, hence again σout spikes – and then the system halts. In this way, we get the spike train 10n−11, encoding the number nas the result of the computation. From Figures 11 and 12 one sees that, in comparison with Figures 4 and 5, we save two neurons in the first case and one in the second. The same happens with both intermediate neurons in the ADD + ADD module from Figure 7 (using the ADD + ADD module instead of two ADD modules, a label-neuron is saved): we directly send 6 spikes to each neuron σl18 , σ2, σ3from Figure 7. In this way, our system will contain Small Universal Spiking Neural P Systems 229 ' & $ % ' & $ % ' & $ % ? ? ? lh a10 →a3 a11 →a3 a7→λ a8→λ a9→λ a13 →λ 0 a3(a6)+/a6→a2 a3→a3 out a a3→a a4→a a2→λ Fig. 12. The OUTPUT module in the case of extended rules. 8 neurons for the 8 registers, 22 neurons for the 22 labels (one is saved in the ADD + ADD module), 13 neurons for the 13 SUB instructions, 5 neurons in the INPUT module, 1 neuron in the OUTPUT module, which means in total 49 neurons. It is also worth noting that all spiking rules from our system have no delay from firing to spiking. Theorem 2. There is a universal computing SN P system with extended rules (without delay) which has 49 neurons. 5 Universal SN P Systems as Number Generators Let us now consider the case when with an SN P system Πwe associate a set N(Π) of numbers as in [3]: the system starts working in its initial configuration; 230 A. P˘aun, Gh. P˘aun because of the non-determinism in using the spiking rules, several computations are possible; any halting computation provides a result, in the form of the number of time units between the first two steps when any spike exits the system. Note that this definition covers both the case of restricted rules, with only one spike emitted in a time unit by the output neuron, and the case of extended rules, where it is possible that several spikes are emitted at the same time (they are perceived in the environment of the system as a single spike; however, in order to avoid any complication, in the constructions below we make sure that the output neuron produces always only one spike). In this framework, an SN P system Πuis universal if, given a fixed admissible enumeration of the unary partial recursive functions, (ϕ0, ϕ1, . . .), there is a recursive function gsuch that for each natural number x, if we input the number g(x) in Πu, by “reading” the sequence 10g(x)−11 from the environment, the set of numbers generated by the system is equal to {n∈N|ϕx(n) is defined}. Otherwise stated, after introducing the “code” g(x) of the partial recursive function ϕxin a specified neuron, the system generates (hence halts sometimes after sending two spikes out) all numbers nfor which ϕx(n) is defined. This time, the strategy followed by the universal system is the following: 1. Read the string 10g(x)−11 from the environment and load 2g(x) spikes in neuron σ1. 2. Load neuron σ2non-deterministically with an arbitrary natural number n(in the case of using restricted rules this means to introduce 2nspikes in neuron σ2and in the case of extended rules means to introduce 6nspikes); at the same time, output the spike train 10n−11 (hence the number n). 3. Check whether the function ϕxis defined for n. To this aim, start the register machine Mufrom Figure 1, with g(x) in register 1 and nin register 2. If the computation in Muhalts, then also the computation in our SN P system halts, hence nis introduced in the set of generated numbers. It is worth noting that there is an essential difference between number generating and function computing: we no longer need to output a result after halting the computation, but we have to randomly generate a number at the beginning of the computation. In this way, we have two important consequences for our construction, a simplification and a supplementary task. First, no separate output module is necessary, the additional register 8 can be omitted, and the simulation of the last SUB instruction used in a halting computation, l18 : (SUB(4), l0, lh), can be simplified, just ignoring lhand halting. On the other hand, the input module should be combined with the output one, at the same time non-deterministically producing the number n. The combined INPUT–OUTPUT module for the case of restricted rules is presented in Figure 13. After loading neuron σ1with 2g(x) spikes, we start loading neuron σ2with an arbitrary number of spikes, by means of neurons σc4and σc5, at the same time sending out the respective number as the distance between two spikes emitted by Small Universal Spiking Neural P Systems 231 ' &$ % ¶ µ³ ´ ¶ µ³ ´ ¶ µ³ ´ ² ±¯ ° ' & $ % ' & $ % ¶ µ³ ´ ? ½ ½ ½ ½ ½ ½= - ¾ ? ZZZZ Z~ ´ ´ ´ ´+ ¶ ¶ ¶/ SS Sw ½ ½= Z Z~ ¾ ¶ µ³ ´¶ µ³ ´ º ¹· ¸ ¶ µ³ ´# "à ! - ? ¢ ¢ ¢ ¢ ¢ ¢® ´ ´ ´ ´ ´ ´ ´ ´ ´+ - ¾ JJ J^ ¶ ¶ ¶/ JJJJ J^ HHHHHHHHHj ½ ½ ½ ½ ½ ½= 6 ? in a→a; 0 c1 a→a; 0 c2 a→a; 0 1 2 c3 a2/a →a; 0 a2→a; 1 c4 a3 a5→a; 0 a2→a; 0 a→λ c5 a3 a5→a; 0 a2→a; 0 a→λ c6 a→a; 0 out a(a2)∗/a →a; 0 c7 a2→a; 0 c8 a2→a; 0 l0 a2→a; 0 a→λ Fig. 13. The INPUT–OUTPUT module for the number generating universal SN P systems neuron σout. The work of neurons σc4, σc5stops when neuron σc3uses the rule a2→a; 1, and only after that (after having two spikes emitted by σout) we load neuron σl0with two spikes (via neurons σc7, σc8) and in this way we start the work of the register machine Mu. In turn, the simplified module for simulating the instruction l18 : (SUB(4), l0, lh) is given in Figure 14: when the subtraction is no longer possible, we just halt. Consequently, the obtained system contains 232 A. P˘aun, Gh. P˘aun  Á¿ À  Á¿ À ² ±¯ °  Á¿ À ¡ ¡ ¡ª @@@ @R ½ ½ ½ ½= ZZ Z~ l18 a2→a; 0 a→λ 4 (a2)+a/a3→a; 0 a→a; 1 l0 18 a→a; 0 l0 a2→a; 0 a→λ Fig. 14. The simplified module for simulating l18 : (SUB(4), l0, lh) 8 neurons for the 8 registers, 22 neurons for the 22 labels (lhis saved), 42 neurons for the 21 ADD and SUB instructions, 1 neuron for the special SUB instruction (Figure 14), 10 neurons in the INPUT–OUTPUT module, which means in total 83 neurons. From them, 7 neurons can be saved in the way we have proceeded in the end of Section 3, hence we can conclude with the following result: Theorem 3. There is a universal number generating SN P system with standard rules having 76 neurons. Passing now to extended rules, we can have the INPUT–OUTPUT module as shown in Figure 15. This time the system contains 8 neurons for registers, 21 neurons for labels (besides the label saved in the ADD + ADD module, we also save lh), 13 for SUB instructions, and 8 neurons in the INPUT–OUTPUT module, in total 50 neurons. Again, the rules use no delay between firing and spiking. Theorem 4. There is a universal number generating SN P system with extended rules (without delay) having 50 neurons. 6 Closing Remarks It remains as an open problem to decrease the number of neurons from our universal SN P systems. Is this possible in the setups used here? As said in the Introduction, we conjecture that significant improvements are not possible. Small Universal Spiking Neural P Systems 233 ' & $ % ¶ µ³ ´  Á¿ À ¶ µ³ ´  Á¿ À º ¹· ¸ ? © © © © ©¼ - ¾ ? ? QQ Qs ½ ½ ½= ¾  Á¿ À  Á¿ À º ¹· ¸ ¶ µ³ ´Â Á¿ À ? 6 - ? ¡ ¡ ¡ ¡ ¡ª HHHHHHHHH Hj @@@@R £ £ £ £ £° © © © © © © © © ©¼ @ @R ¡ ¡ª - ¾ in a→a; 0 c1 a3 a4/a3→a3; 0 a3 a4/a3→a3; 0 12 c2c3 c4 a3 a5/a3→a3; 0 c5 a3 a5/a3→a3; 0 c3 a2/a →a; 0 a2→a2; 0 c6 a3→a3; 0 out a3(a6)/a3→a; 0 l0 a4 a6→a6; 0 etc. Fig. 15. The INPUT–OUTPUT module in the extended case Another direction of research is to look for the borderline between universality and non-universality also starting from below: what is the number of neurons for which we can prove that an SN P system is not universal? Besides trivial observations (at least three neurons are necessary, one input, one output, and one “working” neuron) we do not have any better estimation at this moment. Of course, some neurons can be saved if the input to the universal SN P system and its output are not introduced/emitted by means of input or output neurons as above, but simply placed in the necessary neurons. Input–output modules are then saved, but we do not find such a definition “fair”, because a “brain” should have interfaces with its environment. Anyway, the results above look rather optimistic: there exist pretty small universal “brains” (it would be of interest to see where on the evolution scale there are animals with the brain of comparable sizes. . . ). Note. Useful discussions with Rudi Freund and Takashi Yokomori are gratefully acknowledged. 234 A. P˘aun, Gh. P˘aun References 1. E. Csuhaj-Varju, M. Margenstern, G. Vaszil, S. Verlan: Small computationally complete symport/antiport P systems. In volume I of the present proceedings. 2. O.H. Ibarra, A. P˘aun, Gh. P˘aun, A. Rodr´ıguez-Pat´on, P. Sosik, S. Woodworth: Normal forms for spiking neural P systems. In the present volume. 3. M. Ionescu, Gh. P˘aun, T. Yokomori: Spiking neural P systems. Fundamenta Informaticae, 71, 2-3 (2006), 279–308. 4. I. Korec: Small universal register machines. Theoretical Computer Science, 168 (1996), 267–301. 5. W. Maass: Computing with spikes. Special Issue on Foundations of Information Processing of TELEMATIK, 8, 1 (2002), 32–36. 6. W. Maass, C. Bishop, eds.: Pulsed Neural Networks. MIT Press, Cambridge, 1999. 7. M. Minsky: Computation – Finite and Infinite Machines. Prentice Hall, Englewood Cliffs, New Jersey, 1967. 8. Gh. P˘aun: Membrane Computing – An Introduction. Springer-Verlag, Berlin, 2002. 9. Gh. P˘aun, M.J. P´erez-Jim´enez, G. Rozenberg: Spike trains in spiking neural P systems. International Journal of Foundations of Computer Science, to appear (also available at [15]). 10. Gh. P˘aun, M.J. P´erez-Jim´enez, G. Rozenberg: Infinite spike trains in spiking neural P systems. Submitted, 2006. 11. Y. Rogozhin: Small universal Turing machines. Theoretical Computer Science, 168 (1996), 215–240. 12. J. van Leeuwen, ed.: Handbook of Theoretical Computer Science. Elsevier, Amsterdam, 1990. 13. Y. Rogozhin, S. Verlan: On the rule complexity of universal tissue P systems. In Membrane Computing, International Workshop, WMC6, Vienna, Austria, 2005, Selected and Invited Papers (R. Freund, Gh. P˘aun, G. Rozenberg, A. Salomaa, eds.), LNCS 3850, Springer-Verlag, Berlin, 2006, 356–363. 14. D. Wood: Theory of Computation. Harper and Row, New York, 1987. 15. The P Systems Web Page: http://psystems.disco.unimib.it.