Computing with Spiking Neural P Systems: Traces and Small Universal Systems

Computing with Spiking Neural P Systems: Traces and Small Universal Systems Mihai Ionescu1, Andrei P˘aun2, Gheorghe P˘aun3,4,andMarioJ.P´erez-Jim´enez4 1Research Group on Mathematical Linguistics Universitat Rovira i Virgili Pl. Imperial T`arraco 1, 43005 Tarragona, Spain [email protected] 2Department of Computer Science, Louisiana Tech University Ruston, PO Box 10348, Louisiana, LA-71272 USA, and Universidad Polit´ecnica de Madrid – UPM, Faculdad de Informat´ıca Campus de Montegancedo s/n, Boadilla del Monte 28660 Madrid, Spain [email protected] 3Institute of Mathematics of the Romanian Academy PO Box 1-764, 014700 Bucharest, Romania [email protected] 4Department of Computer Science and AI, University of Sevilla Avda Reina Mercedes s/n, 41012 Sevilla, Spain [email protected], [email protected] Abstract. Recently, the idea of spiking neurons and thus of computing by spiking was incorporated into membrane computing, and so-called spiking neural P systems (abbreviated SN P systems) were introduced. Very shortly, in these systems neurons linked by synapses communicate by exchanging identical signals (spikes), with the information encoded in the distance between consecutive spikes. Several ways of using such devices for computing were considered in a series of papers, with universality results obtained in the case of computing numbers, both in the generating and the accepting mode; generating, accepting, or processing strings or infinite sequences was also proved to be of interest. In the present paper, after a short survey of central notions and results related to spiking neural P systems (including the case when SN P systems are used as string generators), we contribute to this area with two (types of) results: (i) we produce small universal spiking neural P systems (84 neurons are sufficient in the basic definition, but this number is decreased to 49 neurons if a slight generalization of spiking rules is adopted), and (ii) we investigate the possibility of generating a language by following the trace of a designated spike in its way through the neurons. 1 Introduction Spiking neural P systems (in short, SN P systems) were introduced in [6], with the motivation coming from two directions: the attempt of membrane computing to pass from cell-like architectures to tissue-like or neural-like architectures (see [15], [12]), and the intriguing possibility of encoding information in the duration of events, or in the interval of time elapsed between events, as vividly investigated in recent research in neural computing (of “third generation”) [8], [9]. This double challenge led to a class of P systems based on the following simple ideas: let us use only one object, the symbol denoting a spike, and one-membrane cells (called neurons) which can hold any number of spikes; each neuron fires in specified conditions (after collecting a specified number of spikes) and then sends one spike along its axon; this spike passes to all neurons connected by a synapse to the spiking neuron (hence it is replicated into as many copies as many target neurons exist); between the moment when a neuron fires and the moment when it spikes, each neuron needs a time interval, and this time interval is the essential ingredient of the system functioning (the basic information carrier – with the mentioning that also the number of spikes accumulated in each moment in the neurons provides an important information for controlling the functioning of the system); one of the neurons is considered the output one, and its spikes provide the output of the computation. The sequence of time moments when spikes are sent out of the system is called a spike train. The rules for spiking take into account all spikes present in a neuron not only part of them, but not all spikes present in a neuron are consumed in this way; after getting fired and before sending the spike to its synapses, the neuron is idle (biology calls this the refractory period) and cannot receive spikes. There are also rules used for “forgetting” some spikes, rules which just remove a specified number of spikes from a neuron. In the spirit of spiking neurons, as the result of a computation (not necessarily a halting one) in [6] one considers the number of steps elapsed between the first two spikes of the output neuron. Even in this restrictive framework, SN P systems turned out to be Turing complete, able to compute all Turing computable sets of natural numbers. This holds both in the generative mode (as sketched above, a number is computed if it represents the interval between the two consecutive spikes of the output neuron) and in the accepting mode (a number is introduced in the system in the form of the interval of time between the first two spikes entering a designated neuron, and this number is accepted if the computation halts). If a bound is imposed on the number of spikes present in any neuron during a computation, then a characterization of semilinear sets of numbers is obtained. These results were extended in [13] to several other ways of associating a set of numbers with an SN P system: taking into account the interval between the first kspikes of each spike train, or all spikes, taking only alternately the intervals, or all of them, considering halting computations. Then, the spike train itself (the sequences of symbols 0, 1 describing the activity of the output neuron: we write 0 if no spike exits the system in a time unit and 1 if a spike is emitted) was considered as the result of a computation; the infinite case is investigated in [14], the finite one in [2]. A series of possibilities of handling infinite sequences of bits are discussed in [14], while morphic representations of regular and of recursively enumerable languages are found in [2]. The results from [2] are briefly recalled in Section 5 below. In this paper we directly continue these investigations, contributing in two natural directions. First, the above mentioned universality results (the possibility to compute all Turing computable sets of numbers) do not give an estimation on the number of neurons sufficient for obtaining the universality. Which is the size of the smallest universal “brain” (of the form of an SN P system)? This is both a natural and important (from computer science and, also, from neuro-science point of view) problem, reminding the extensive efforts paid for finding small universal Turing machines – see, e.g., [16] and the references therein. Our answer is rather surprising/encouraging: 84 neurons ensure the universality in the basic setup of SN P systems, as they were defined in [6], while this number is decreased to 49 if slightly more general spiking rules are used (rules with the possibility to produce not only one spike, but also two or more spikes at the same time – such rules are called extended).Theproofisbasedonsimulating a small universal register machine from [7]. (The full details for the proof of these results about small universal SN P systems will be provided elsewhere – see [11].) Extended rules are also useful when generating strings: we associate a symbol biwith a step when the system outputs ispikes and in this way we obtain a string over an arbitrary alphabet, not only on the binary one, as in the case of standard rules. Especially flexible is the case when we associate the empty string with a step when no spike is sent out of the system we associate (that is, b0is interpreted as λ). Results from [3], concerning the power of extended SN P systems as language generators, are also recalled in Section 5. Then, another natural issue is to bring to the SN P systems area a notion introduced for symport/antiport P systems in [5]: mark a spike and follow its path through the system, recording the labels of the visited neurons until either the marking disappears or the computation halts. Because of the very restrictive way of generating strings in this way, there are simple languages which cannot be computed, but, on the other hand, there are rather complex languages which can be obtained in this framework. Due to space restrictions, we do not give full formal details in definitions and proofs (we refer to the above mentioned papers for that); such details are or will be available in separate papers to be circulated/announced through [19]. 2 Formal Language Theory Prerequisites We assume the reader to be familiar with basic language and automata theory, e.g., from [17] and [18], so that we introduce here only some notations and notions used later in the paper. For an alphabet V,V∗denotes the set of all finite strings of symbols from V; the empty string is denoted by λ, and the set of all nonempty strings over V is denoted by V+.WhenV={a}is a singleton, then we write simply a∗and a+instead of {a}∗,{a}+.Ifx=a1a2...a n,a i∈V, 1≤i≤n, then the mirror image of xis mi(x)=an...a 2a1. A morphism h:V∗ 1−→ V∗ 1such that h(a)∈{a, λ}for each a∈V1is called a projection, and a morphism h:V∗ 1−→ V∗ 2such that h(a)∈V2∪{λ}for each a∈V1is called a weak coding. If L1,L 2⊆V∗are two languages, the left and right quotients of L1with respect to L2are defined by L2\L1={w∈V∗|xw ∈L1for some x∈L2}, and respectively L1/L2={w∈V∗|wx ∈L1for some x∈L2}. When the language L2is a singleton, these operations are called left and right derivatives, and denoted by ∂l x(L)={x}\Land ∂r x(L)=L/{x}, respectively. A Chomsky grammar is given in the form G=(N,T,S,P), where Nis the nonterminal alphabet, Tis the terminal alphabet, S∈Nis the axiom, and Pis the finite set of rules. For regular grammars, the rules are of the form A→aB, A →a,forsomeA, B ∈N,a ∈T. We denote by FIN, REG, CF, CS, RE the families of finite, regular, contextfree, context-sensitive, and recursively enumerable languages; by MAT we denote the family of languages generated by matrix grammars without appearance checking. The family of Turing computable sets of numbers is denoted by NRE (these sets are length sets of RE languages, hence the notation). Let V={b1,b 2,...,b m},forsomem≥1. For a string x∈V∗, let us denote by valm(x)thevalueinbasem+1ofx(we use base m+ 1 in order to consider the symbols b1,...,b mas digits 1,2,...,m, thus avoiding the digit 0 in the left hand of the string). We extend this notation in the natural way to sets of strings. All universality results of the paper are based on the notion of a register machine. Such a device – in the non-deterministic version – is a construct M= (m, H, l0,l h,I), where mis the number of registers, His the set of instruction labels, l0is the start label (labeling an ADD instruction), lhis the halt label (assigned to instruction HALT), and Iis the set of instructions; each label from H labels only one instruction from I, thus precisely identifying it. The instructions are of the following forms: –li:(ADD(r),l j,l k) (add 1 to register rand then go to one of the instructions with labels lj,l knon-deterministically chosen), –li:(SUB(r),l j,l k)(ifregisterris 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 N(M) 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 continue 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 npresent in register 1 at that time is said to be generated by M. (Without loss of generality we may assume that in the halting configuration all other registers are empty; also, we may assume that register 1 is never subject of SUB instructions, but only of ADD instructions.) It is known (see, e.g., [10]) that register machines generate all sets of numbers which are Turing computable. A register machine can also be used as a number accepting device: we introduce a number nin some register r0, we start working with the instruction with label l0, and if the machine eventually halts, then nis accepted (we may also assume that all registers are empty in the halting configuration). Again, accepting register machines characterize NRE. Furthermore, register machines can compute all Turing computable functions: we introduce the numbers n1,...,n kin some specified registers r1,...,r k,we start with the instruction with label l0, and when we stop (with the instruction with label lh) the value of the function is placed in another specified register, rt, with all registers different from rtbeing empty. Without loss of generality we may assume that r1,...,r kare the first kregisters of M, and then the result of the computation is denoted by M(n1,...,n k). In both the accepting and the computing case, the register machines can be deterministic, i.e., with the ADD instructions of the form li:(ADD(r),l j)(add1 to register rand then go to the instruction with label lj). In the following sections, when comparing the power of two language generating/accepting devices the empty string λis ignored. 3 Spiking Neural P Systems We give here the basic definition we work with, introducing SN P systems in the form considered in the small universal SN P systems, hence computing functions (which, actually, covers both the generative and accepting cases). A computing spiking neural membrane 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,oftheform σi=(ni,R i),1≤i≤m, where: a) ni≥0istheinitial number of spikes contained in σi; b) Riis a finite set of rules of the following two forms: (1) E/ac→a;d,whereEis a regular expression1over a,c≥1, and d≥0; (2) as→λ,fors≥1, with the restriction that for each rule E/ac→a;d of type (1) from Ri,wehaveas/∈L(E); 3. syn ⊆{1,2,...,m}×{1,2,...,m}with (i, i)/∈syn for 1 ≤i≤m(synapses between neurons); 4. in, out ∈{1,2,...,m}indicate the input and the output neurons of Π. 1The regular language defined by Eis denoted by L(E). 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) c spikes (thus only k−cremain in σi), 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). 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 will write it in the following simplified form: ac→a;d. If all spiking rules are of this form, then the system is said to be finite (it can handle only a bounded number of spikes in each of its neurons). In each time unit, if a neuron σican use one of its rules, then a rule from Ri must be used. Since two firing rules, E1/ac1→a;d1and E2/ac2→a;d2,can have L(E1)∩L(E2)=∅, 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, but neurons function in parallel with each other (the system is synchronized). The initial configuration of the system is described by the numbers n1,n 2,..., 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). 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,...,n kin the system by “reading” from the environment a binary sequence z=0 b10n1−110n2−11...10nk−110f,forsomeb, f ≥0; this means that the input neuron of Πreceives a spike in each step corresponding to a digit 1 from the string z. Note that we input exactly k+ 1 spikes. The result of the computation is also encoded in the distance between two spikes: we impose to the system to output exactly two spikes and halt (sometimes after the second spike), hence producing a train spike of the form 0b10r−110f,forsomeb,f≥0andwith r=f(n1,...,n k). If we use an SN P system in the generative mode, then no input neuron is considered, hence no input is taken from the environment; we start from the initial configuration and the distance between the first two spikes of the output neuron (or other numbers, see the discussion in the Introduction) is the result of the computation. Dually, we can ignore the output neuron, we input a number in the system as the distance between two spikes entering the input neuron, and if the computation halts, then the number is accepted. We do not give here examples, because in the next section we show the four basic modules of our small universal SN P system. 4 Two Small Universal SN P Systems In both the generating and the accepting case, SN P systems are universal, they compute the Turing computable sets of numbers. The proofs from [6], [13] are based on simulating register machines, which are known to be equivalent to Turing machines when computing (generating or accepting) sets of numbers, [10]. In [7], the register machines are used for computing functions, with the universality defined as follows. Let (ϕ0,ϕ 1,...) be a fixed admissible enumeration of the set of 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 [7], the input is introduced in registers 1 and 2, and the result is obtained in register 0 of the machine. l0:(SUB(1),l 1,l 2),l 1:(ADD(7),l 0), l2:(ADD(6),l 3),l 3:(SUB(5),l 2,l 4), l4:(SUB(6),l 5,l 3),l 5:(ADD(5),l 6), l6:(SUB(7),l 7,l 8),l 7:(ADD(1),l 4), l8:(SUB(6),l 9,l 0),l 9:(ADD(6),l 10), l10 :(SUB(4),l 0,l 11),l 11 :(SUB(5),l 12,l 13), l12 :(SUB(5),l 14,l 15),l 13 :(SUB(2),l 18,l 19), l14 :(SUB(5),l 16,l 17),l 15 :(SUB(3),l 18,l 20), l16 :(ADD(4),l 11),l 17 :(ADD(2),l 21), l18 :(SUB(4),l 0,l h),l 19 :(SUB(0),l 0,l 18), l20 :(ADD(0),l 0),l 21 :(ADD(3),l 18), lh:HALT. Fig. 1. The universal register machine from [7] The constructions from [6] do not provide a bound on the number of neurons, but such a bound can be found if we start from a specific universal register machine. We will use here the one with 8 registers and 23 instructions from [7] – for the reader convenience, this machine is recalled in Figure 1, in the notation and the setup introduced in the previous section. Theorem 1. There is a universal SN P system with 84 neurons. Proof. (Outline) We follow the way used in [6] to simulate a register machine by an SN P system. This is done as follows: neurons are associated with each register (r)andwitheachlabel(li) 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 – with primed labels – which do not correspond to registers and labels of the simulated machine). # " !# " !      # " !    SSS Sw    HHHHH Hj        ZZZ Z~ li a2→a;0 a→λ l il i a→a;0 a→a;0 r lj a2→a;0 a→λ Fig. 2. Module ADD (simulating li:(ADD(r),l j)) 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 do not describe here in detail the (pretty transparent) way the modules from Figures 2 and 3 work – the reader can consult [6] in this respect. Starting with neurons σ1and σ2already loaded with 2g(x)and2yspikes, respectively, and introducing two spikes in neuron σl0, we can compute in our system in the same way as Mu; if the computation halts, then neuron σ0will contain 2ϕx(y) spikes. What remains to do is to construct input and output modules, for reading a sequence of bits and introducing the right number of spikes in the neurons corresponding to registers 1 and 2, and, in the end of the computation, to output the contents of register 0. Modules of these types are given in Figures 4, 5, having seven and two additional neurons, respectively. After this direct construction, we get a system with 91 neurons (9 for the registers of the starting register machine – one further register is necessary for technical reasons, 25 for its labels, 24 ×2 for the ADD and SUB instructions, 7 in the input module, and 2 in the output module). However, some “code optimization” is possible, based on certain properties of the register machine from & $ %       & & & %     / AAAAAA AU QQQQ Qs ?    / HHHHH Hj JJ J^ lia2→a;0 a→λ r (a2)+a/a3→a;0 a→a;1 l i l 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),l j,l k)) [7] (for instance, consecutive ADD instructions can be simulated by a specific module, smaller than two separate ADD modules); we skip the technical details and we only mention that the final SN P system will contain 84 neurons. This is a small number (a small “brain”, compared to the human one; it would be nice to know where in the evolution scale there are animals with about 84 neurons in their brain), but we do not know whether it is optimal or not. Anyway, we believe that in the previous setup, we cannot significantly decrease the number of neurons from a universal SN P system. However, we can do better starting from the following observation. In many modules mentioned above we need pairs of intermediate neurons for duplicating the spike to be transmitted further (this is the case for neurons σl i,σ l iin Figure 2), and this suggests to consider a slight extension of the rules of SN P systems: to allow spiking rules of the form E/ac→ap;d, where all components are as usual, and p≥1. The meaning is that cspikes are consumed and pspikes are produced. To be “realistic”, we impose the restriction c≥p(the number of produced spikes is not larger than the number of consumed spikes). Theorem 2. There is a universal SN P system with 49 neurons, using rules of the form E/ac→ap;0,withp≥1. (Note that the delay is zero in the rules of the extended form used in the theorem.) As above, we do not know whether this result is optimal, but we again believe that it cannot be significantly improved (without, maybe, changing the definition of SN P systems in an essential way). 2. 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 Proc. of Fourth. Brainstorming Week on Membrane Computing, Sevilla, 2006, vol. I, 169–193 (also available at [19]). 3. H. Chen, T.-O. Ishdorj, Gh. P˘aun, M.J. P´erez-Jim´enez: Spiking neural P systems with extended rules. In Proc. of Fourth. Brainstorming Week on Membrane Computing, Sevilla, 2006, vol. I, 241–266 (also available at [19]). 4. 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 Fourth Brainstorming Week on Membrane Computing, Febr. 2006, Fenix Editora, Sevilla, 2006, vol. II, 105–136 (also available at [19]). 5. M. Ionescu, C. Martin-Vide, A. P˘aun, Gh. P˘aun: Membrane systems with symport/antiport: (unexpected) universality results. In Proc. 8th International Meeting of DNA Based Computing (M. Hagiya, A. Ohuchi, eds.), Japan, 2002, 151–160. 6. M. Ionescu, Gh. P˘aun, T. Yokomori: Spiking neural P systems. Fundamenta Informaticae, 71, 2-3 (2006), 279–308. 7. I. Korec: Small universal register machines. Theoretical Computer Science, 168 (1996), 267–301. 8. W. Maass: Computing with spikes. Special Issue on Foundations of Information Processing of TELEMATIK, 8, 1 (2002), 32–36. 9. W. Maass, C. Bishop, eds.: Pulsed Neural Networks, MIT Press, Cambridge, 1999. 10. M. Minsky: Computation – Finite and Infinite Machines. Prentice Hall, Englewood Cliffs, NJ, 1967. 11. A. P˘aun, Gh. P˘aun: Small universal spiking neural P systems. BioSystems,to appear. 12. Gh. P˘aun: Membrane Computing – An Introduction. Springer-Verlag, Berlin, 2002. 13. Gh. P˘aun, M.J. P´erez-Jim´enez, G. Rozenberg: Spike trains in spiking neural P systems. Intern. J. Found. Computer Sci., to appear (also available at [19]). 14. Gh. P˘aun, M.J. P´erez-Jim´enez, G. Rozenberg: Infinite spike trains in spiking neural P systems. Submitted, 2006. 15. Gh. P˘aun, Y. Sakakibara, T. Yokomori: P systems on graphs of restricted forms. Publicationes Mathematicae Debrecen, 60 (2002), 635–660. 16. Y. Rogozhin: Small universal Turing machines. Theoretical Computer Science, 168 (1996), 215–240. 17. G. Rozenberg, A. Salomaa, eds.: Handbook of Formal Languages,3volumes. Springer-Verlag, Berlin, 1997. 18. A. Salomaa: Formal Languages. Academic Press, New York, 1973. 19. The P Systems Web Page: http://psystems.disco.unimib.it.