Wireless spiking neural P systems

Vol.:(0123456789) Journal of Membrane Computing https://doi.org/10.1007/s41965-025-00199-8 RESEARCH PAPER Wireless spiking neural P systems DavidOrellana‑Martín1 · FrancisGeorgeC.Cabarle1,2 · PrithwineelPaul3 · XiangxiangZeng4 · RudolfFreund5 Received: 30 September 2024 / Accepted: 26 May 2025 © The Author(s) 2025 Abstract Spiking neural P systems (SN P systems) are computing models based on the third generation of neuron models known as spiking neurons. Recent results in neuroscience highlight the importance of extrasynaptic activities of neurons, that is, features and functioning of neurons outside their synapses. Previously it was thought that signals such as neuropeptides only assist neurons, but recently such signals have been given additional importance. Inspired by recent results, we define wireless SN P systems (WSN P systems). In WSN P systems, no synapses exist: regular expressions associated with each neuron are used to decide which spikes it receives. We provide two semantics of how to “interpret” the spikes released by neurons. A specific register machine is simulated to show the different style of programming WSN P systems compared to programming standard SN P systems and other variants. This style emphasizes a trade-off: WSN P systems can be more “flexible” since they are not limited by their synapses for sending spikes; however, losing the useful directed graph structure requires careful design of rules and expressions associated with each neuron. We use linear prime number encodings in constructing the expressions and rules of the neurons to prove that WSN P systems are Turing-complete in both spike semantics. Keywords Natural computing· Membrane computing· Spiking neural P systems· Extrasynaptic signaling· Neuropeptides 1 Introduction The present work introduces a variant of spiking neural P systems, in short SN P systems, in a formal way. SN P systems as introduced in Ref.[24] are inspired by spiking neurons and their network: the processors are neurons which are the nodes in a directed graph; the edges are synapses which allow for the communication between neurons using a single object a referred to as a spike; the neurons are spike processors which consume and produce spikes. Some recent survey papers of SN P systems and variants include Refs. citeleporatispssnpsurv2022,fanspssnps urv2020 and more recently Ref. [9]. Since their introduction, it is known that SN P systems are Turing-complete [24]. Much literature is dedicated to computational completeness (Turing-completeness) of SN P systems, also investigating how small the system can be [41], restrictions on their syntax or semantics [22, 32]. SN P systems are also shown to solve NP-complete problems, trading time for space [30] such as with the use of arbitrarily large resources (e.g., neurons and synapses) [25] or creation of new resources [55]. In the past 2 decades, many variants of SN P systems have been introduced depending on specific ingredients or * David Orellana-Martín [email protected] Francis George C. Cabarle [email protected] Prithwineel Paul prit[email protected] Xiangxiang Zeng [email protected] Rudolf Freund r[email protected] 1 Research Group onNatural Computing, Department ofComputer Science andArtificial Intelligence, SCORE lab, I3US, Universidad de Sevilla, Avda. Reina Mercedes s/n, 41012Sevilla, Spain 2 Department ofComputer Science, University of the Philippines Diliman, 1101QuezonCity, Philippines 3 Department ofComputer Science andEngineering, Institute ofEngineering andManagement, University ofEngineering andManagement, New Town Rd., Kolkata700091, India 4 Department ofComputer Science, Hunan University, Changsha, China 5 Faculty ofInformatics, TU Wien, Favoritenstraße 9-11, 1040Vienna, Austria D.Orellana-Martín et al. features, mostly from biology, for instance, the introduction of autapses [51], synaptic plasticity [10], polarisations [56], synaptic schedules [6], neurogenesis [55], dynamic threshold [26], colored spikes [40], and astrocytes [5, 7, 8, 27, 39], among others. Applications of SN P systems and their variants include image processing [50], evolutionary optimisation [18, 59], pattern recognition [49], cybersecurity [44], migration strategies in membrane algorithms [14], among others. Simulators of SN P systems and variants are used to support research or pedagogy, such as interactive and visual software in Refs. [15, 17]. SN P systems are also investigated for their implementation in parallel hardware such as in Refs. [20, 33] with recent and some state-of-the-art results in Ref. [19]. Wireless SN P systems, or WSN P systems in short, are a SN P system variant defined in a formal way in the present work, previously introduced in an informal way in a recent report [38]. One general reference for the bio-inspiration of WSN P systems is from Ref. [31] with recent and detailed results from Refs. [47, 48]. Briefly, such recent results emphasize the crucial and important role of neuronal activities outside their synapses, hence their wireless features and functions. Such recent works focus their attention on a specific animal known as C. elegans. The worm C. elegans is a model organism, i.e., much is known about its biology including its nervous system due to its “simplicity” of several hundred neurons only. Despite the small size of this worm, its nervous system has interesting biochemical complexity with structural features shared by larger animals [48]. Due to better techniques and technology, more recently there are improved works to show how a wireless network (that is, without synaptic wiring) among nerve cells or neurons is able to operate [47, 48]. These recent works challenge the idea that neurons communicate only or mainly through anatomical connections, that is, through their synapses [31]. Such recent works reveal new details of a connectome or wiring diagram among neurons, the neuropeptidergic connectome: a connectome which is equally important and perhaps more diverse than the synaptic connectome. Furthermore, these recent works identify neuropeptides, the chemical messages released by neurons, as the basis for such wireless network among neurons. Neurons in the C. elegans worms can release neuropeptides, or have receptors for such neuropeptides. The wireless network formed from these pairs of releasing and receiving neurons is dense and decentralized, compared to the less dense and more centralized network of synapses [48]. Such pairs are responsible for the existence of the wireless network, which means that neuropeptides are not random chemicals floating between neurons. Neuropeptides affect the neural system over larger scales of time and space, unlike synaptic signals restricted only to both sides of the synapse [48]. Previously it was thought that neuropeptides only assisted in synaptic communication. However, these recent works indicate the ubiquitous, important, and direct role to neuron activation of neuropeptides and the corresponding wireless network [31]. Neuropeptides are conserved and ancient chemicals in brains of many organisms, including the human brain, suggesting that the pioneering work with C. elegans can at least reveal useful structures or principles for brain function [47, 48]. For instance, a recent technique allows for detecting neuropeptides, which can assist in better understanding of both wired and wireless networks of neurons including those of humans [54]. We use such recent results as inspirations for extrasynaptic functions of neurons, that is, functioning without or outside the usual synapses. Contributions of the present work include the formal introduction of wireless SN P systems and proofs for their Turing-completeness. No synapses are present in the neurons, while still using rules to consume and produce spikes. For each neuron, we associate a finite filter to decide what “forms” of spikes the neuron can receive. We introduce two semantics for WSN P systems, based on the interpretation of the spikes released in each step by the neurons: (i) the spike package semantics considers the spikes as individual packages as released by each neuron; (ii) the spike total semantics considers the sum of spikes released by all neurons. We show how to program a specific WSN P system through the simulation of specific register machine instructions. Such a simulation emphasizes the rather different way how to program WSN P systems compared with SN P systems and their variants, due to the associated finite filter for each neuron and the lack of synapses. Although the directed graph structure of SN P systems and their many variants is a very useful feature, in WSN P systems, some “flexibility” is gained in the sense that the neurons are not limited to sending spikes only to neurons to which their synapses connect. On the other hand, losing the directed graph structure makes the programming of the system more “involved” in the sense that more effort can be required to design the rules and neurons. The present work is organized as follows: In Sect.2, we recall some preliminaries needed to understand WSN P systems and their computations; the definition of WSN P systems is given in Sect.3. An example of a WSN P system, considered under two semantics, is used to illustrate two kinds of computations in Sect.4. In Sect.5, we highlight the interesting way how to program WSN P systems by implementing the simulation of a specific small register machine. This simulation also gives us an idea of the computing power and the way how to program WSN P systems in a general purpose way. The proofs for computational completeness are given in Sect.6. Finally, conclusions and directions for future work are discussed in Sect.7. Wireless spiking neural P systems 2 Preliminaries In this section, we only briefly mention some notions required for our definitions and results. For more details on automata and language theory, we refer to Ref. [34], for their applications to membrane computing to Refs. [45, 46]. Given a finite and nonempty alphabet V, by V∗ , we denote the set of all finite strings over V; V+=V∗⧵{𝜆} . The set of all multisets over V is denoted by V◦ . The family of finite and regular string languages is denoted by FIN and REG, respectively, the corresponding family of finite and regular multiset languages by PsFIN and PsREG, respectively (as it contains the Parikh images of the finite and regular string languages, respectively). NFIN(a) and NREG(a) denote the family of finite and regular multiset languages over the oneletter alphabet {a} . Definition 1 A register machine is a construct where – m is the number of registers, – B is the set of labels for the instructions in P, – P is the set of instructions bijectively labeled by elements of B, – l0∈B is the initial label, and – lh∈B is the final label. The instructions of M can be of the following forms: – p:(ADD(r),q(p),s(p)); p∈B⧵ { l h} , q(p),s(p)∈B , 1≤r≤m . Increase the value of register r by one, and non-deterministically jump to instruction q(p) or s(p). – p:(SUB(r),q(p),s(p)) ; p ∈B⧵ { l h} , q(p),s(p)∈B , 1≤r≤m . If the value of register r is not zero, then decrease the value of registerr by one (decrement case) and jump to instruction q(p), otherwise jump to instructions(p) (zero-test case). – lh∶HALT .Stop the execution of the register machine. A configuration of a register machine is described by the contents of each register and by the value of the current label, which indicates the next instruction to be executed. M is called deterministic if the ADD instructions all are of the form p:(ADD(r),q(p)) . Throughout the paper, BADD(r) denotes the set of labels of ADD instructions p:(ADD(r),q(p),s(p)) of an arbitrary register r, and BSUB(r) denotes the set of labels of all SUB instructions p:(SUB(r),q(p),s(p)) of a decrementable register r. Moreover, for any p∈B⧵{lh} , Reg(p) denotes the register M = ( m,B,l 0 ,l h ,P ) affected by the ADD or SUB instruction labeled byp; for the sake of completeness, in addition Reg(lh)=1 is taken. In the generating case, a computation starts with all registers being empty and by executing the first instruction of P (labeled by l0 ); it terminates with reaching the HALT instruction and the output of a k vector of natural numbers in its last k registers. Without loss of generality, we may assume all registers except the last k output registers to be empty at the end of the computation, and, moreover, on the output registers, i.e., the last k registers, no SUB instruction is ever used, i.e., they are never decremented. The set of vectors of natural numbers generated by M is denoted by Ps(M); if only sets of numbers are computed, we write N(M). It is known that register machines are Turing-complete, e.g., see Ref. [35], i.e., register machines characterize NRE (PsRE), the family recursively enumerable sets of (vectors of) natural numbers. Hence, register machines are a convenient model to be compared with models dealing with (sets of) numbers directly instead of strings. 3 Definition ofWSN P systems In this section, we define both the syntax and semantics of WSN P systems. In fact, two different semantics can arise from the way the spikes are treated when they are fired from a neuron. The syntax and the semantics of WSN P systems share similarities with SN P systems and their variants, for instance, we refer to Refs.[24, 42, 46] and more recently to Ref. [29] for further details. 3.1 Syntax Definition 2 A WSN P system of degree m≥1 is a construct where: 1. O={a} is the singleton alphabet (a is called spike); 2. 𝜎i=(ni,Ei,Ri),1≤i≤m , is a neuron such that: (a) ni∈ℕ is the initial number of spikes in neuron 𝜎i ; (b) Ei⊆NFIN(a) , the input filter of neuron 𝜎i ; (c) Ri is a finite set of rules of two possible forms: i. E∕ac → as where E⊆NREG(a) is a regular set of numbers over O and c,s∈ℕ,c,s≥1 (spiking rules); ii. as→𝜆 where s∈ℕ,s≥1 (forgetting rules); 𝛱=(O,𝜎1,…,𝜎m) D.Orellana-Martín et al. A WSN P system 𝛱=(O,𝜎1,…,𝜎m) of degree m≥1 can be seen as a a set of m neurons labeled by 1, …,m such that: 1. n1,…,nm represent the initial multisets of objects a (spikes) situated at the beginning in the m neurons of the system; 2. E1,…,Em are finite sets over O assigned to the m neurons of the system, working as input filters for the spike packages allowed to enter the neuron; 3. R1,…,Rm are finite sets of rules governing the dynamics of the system. Remark 1 We mention that in this paper, we do not consider delays, as they are not needed in the following and only make definitions much more complicated. 3.2 Applicability ofrules inaWSN P system A configuration of a WSN P system 𝛱 at some moment of time t is described as with the number of spikes ni,t in each neuron i. The initial configuration of 𝛱 is C0=⟨( n 1) , … , ( n m)⟩ . A spiking rule E∕ac → as∈Ri is applicable in the neuroni given a configuration Ct in step t+1 if, in the configuration Ct , in the neuron labeled by i, the number of spikes ani , t is in E. The application of such a rule in that neuron i produces the following effects: c spikes are removed from the neuron i, and it produces (we also say fires) s spikes to the environment. A forgetting rule as → 𝜆∈Ri is applicable to a configuration Ct in step t+1 if, in configuration Ct , the neuron labeled by i contains exactly s spikes. The application of such a rule in that neuron i removes all the s spikes contained in the neuron without generating any spike. 3.3 Semantics Two possibilities arise regarding how the produced spikes of some neurons are received by the same or other neurons: 1. spike packages semantics: Each package of spikes is treated separately in the following way: Let {ac 1 ,…,ac k } be the multiset of packages of spikes produced by neurons that have applied a spiking rule in the current step. Thus, for each acj , only all the neurons 𝜎i such that ac j ∈ E i receive cj spikes. 2. Total spikes semantics: We take the sum of all the spikes produced by the neurons of the system in the following way: Let {ac 1 ,…,ac k } be the multiset of packages of Ct=⟨(n1,t),…,(nm,t)⟩ spikes produced by neurons that have applied a spiking rule in the current step, and let c = ∑k j=1 c j . Then only the neurons 𝜎i such that ac∈Ei receive c spikes. These two semantics in the following will be abbreviated by pac and tot, respectively. 3.4 Computations inaWSN P system At some time instance t, we say the configuration Ct of the WSN P system 𝛱 produces a configuration Ct+1 in one step—we denote that by Ct ⇒ 𝛱Ct+1 —by executing the following two substeps: – All neurons apply one rule (if possible) – Each neuron 𝜎i according to the underlying semantics 𝛼∈{pac,tot} takes the (packages of) spikes produced in the first substep from the environment if they can pass the input filter Ei of 𝜎i . We assume a global clock to synchronize the computations in 𝛱 , that is, if a neuron can apply a rule, then it must do so. In every step, 𝛱 is locally sequential since at most one rule in each neuron can be applied, but globally parallel as more than one neuron can apply a rule. If more than one rule in a neuron is applicable, then the rule to be applied is chosen in a nondeterministic way. A computation of a WSN P system 𝛱 is defined as a (finite or infinite) sequence of configurations C=(C0 , C1 , … , Cn , …) , where C0 is the initial configuration of 𝛱 and Ct ⇒ 𝛱Ct+1 for all t. If, after n steps, no more rules as described above can be applied, we say that 𝛱 halts after n steps, and C=(C0 , C1 , … , Cn) is called a halting computation. Remark 2 We assume the spikes present in the environment to be available for all the neurons only for one computation step, i.e., these spikes can be interpreted as decaying after one step (decaying spikes, for example, were considered in Ref. [16]). 3.5 Output Let be a WSN P system working in the semantics 𝛼∈{pac,tot} . There are several ways how at the end of a halting computation the output of the system can be obtained: – The output consists of a k-vector of natural numbers given by the number of spikes in some designated out𝛱=(O,𝜎1,…,𝜎m) Wireless spiking neural P systems put neurons 𝜎j1,…,𝜎jk ; in that case, the whole WSN P system is given as and we may also distinguish the following subcases: – We write Ps 𝛼 ,k−out(𝛱) , if the numbers in the k-vector are directly given by the number of spikes contained in the output neurons. – If the numbers for the output vector are encoded in the number of spikes contained in the output neurons by a specific function f like an exponential function, we write Ps 𝛼,k−out f(𝛱) ; as a special case, we consider f to be a linear function, in which case we also write Ps 𝛼, k−outl(𝛱) . – The output is obtained from a designated output neuron 𝜎 i 0 , 1≤i0≤m ; in that case, the whole WSN P system is given as and we may also distinguish the following subcases: – The output vector with k components is given by k+1 spikes sent to the environment by the output neuron 𝜎i0 , and we write Ps𝛼,kWSNP ; given the sequence of time instances ⟨t1,…,tk+1⟩ when the k+1 spikes have been sent out by the output neuron 𝜎i0 , the k components of the output vector are obtained as the time intervals ⟨t2−t1 , … , tk+1−tk⟩ ; in this case, we write Ps 𝛼, k−int(𝛱) . – The output vector with k components is given by k sequences of consecutive spikes sent to the environment by the output neuron 𝜎i0 , and we write Ps 𝛼, k−sequ(𝛱) . In all the variants described above, we replace Ps by N, if only one natural number is to be obtained as output. The families of sets of k vector of natural numbers obtained by WSN P systems as described above are denoted by Ps 𝛼, k−outWSNP , Ps 𝛼,k−out fWSNP , Ps 𝛼, k−intWSNP , and Ps𝛼,k−sequWSNP . If only sets of natural numbers are considered, we denote the corresponding families of sets of natural numbers by N𝛼,outWSNP , N 𝛼,out fWSNP , N𝛼,intWSNP , and N 𝛼, sequWSNP . Remark 3 In the second case described above with the designated output neuron 𝜎 i 0 , we can think of 𝜎 i 0 as the interface of 𝛱 to the environment. As a technical detail, we mention that in contrast to SN P systems and other variants, the firing of 𝜎i0 should only send spikes to the environment, but none of the neurons in 𝛱 including 𝜎 i 0 itself should receive the 𝛱=(O,𝜎1,…,𝜎m;j1,…,jk), 𝛱=(O, 𝜎 1,…, 𝜎 m;i0), spikes produced by 𝜎i0 . This may be accomplished by avoiding a to be contained in any of the input filters Ei , 1≤i≤m . 4 An example withthetwo semantics In this section, as an example, we consider the WSN P system 𝛱1 shown in Fig.1. We use 𝛱1 to explain the definitions and the two semantics from Sect.3. For short, 𝛱1 has three neurons, each labeled by a pair (i,Ei) for 1≤i≤3 . Each neuron has associated the finite input filter Ei to check which number(s) of spikes it can receive. For instance, neurons 𝜎1 and 𝜎2 have E1=E2={a} , which means they can only receive spikes of the form a1=a fired from other neurons or for 𝜎2 even including spikes sent from itself. We note that the rule set of 𝜎1 is empty, so it can never spike, and the number of spikes inside can only either remain the same or increase. 4.1 Semantics 1: spike packages We first consider semantics 1, which we refer to as spike packages semantics. It only considers spikes arriving in “packages” sent by neurons to the environment, not the total number of spikes in the environment. To illustrate the computation of 𝛱1 using the spike packages semantics, we refer to the configuration tree in Fig.2. The initial configuration of 𝛱1 , assuming the (contents of the) neurons to be listed according to the total ordering 1,2,3, is C0=⟨1, 1, 2⟩ , i.e., neurons 1, 2, and 3 contain 1, 1, and 2 spikes, respectively. To C0 , the rule r2 can be applied in 𝜎2 , and in neuron 𝜎3 , there is a nondeterministic choice between rule r3 and rule r4 . If rule r2 is applied, one spike is consumed in neuron 𝜎2 and sent to both neuron 𝜎1 and neuron 𝜎2 due to their input filters E1=E2={a} . Applying rule r3 means that 𝜎3 consumes two spikes but fires only one spike. Again this single spike from 𝜎3 arrives in 𝜎1 and 𝜎2 due to their input filters. Hence, in total, we have got the transition C 0 r 2 r 3 ⟹C1,1 = ⟨ 3, 2, 0 ⟩ , i.e., by applying r2 and r3 , we obtain configuration C1,1 from configuration C0 . Now we consider the case when we apply rule r4 together with rule r2 instead. The effect of applying rule r2 is still to return a spike to 𝜎2 and to increment the number of spikes in 𝜎1 . The effect of r4 is reflexive, i.e., in Fig. 1 𝛱1 is an example of a wireless SN P system D.Orellana-Martín et al. neuron 𝜎3 two spikes are consumed and then returned to itself, since E3={a2} . Hence, we have the transition C0 r 2 r 4 ⟹C 1,2 = ⟨ 2, 1, 2 ⟩ , i.e., by applying r2 and r4 , we obtain configuration C1,2 from configuration C0 . Hence, in total, from the initial configuration C0 , we get the two successor configurations C1,1 =⟨ 3, 2, 0 ⟩ and C1,2 =⟨2, 1, 2⟩ as depicted in the tree of Fig.2. As can be seen in the configuration tree in Fig.2, each branch of computations in 𝛱1 is non-halting, i.e., 𝛱1 always arrives at a configuration where some rule can still be applied. The number of spikes in neuron 𝜎1 continues to increase. More precisely, for all b≥1 , we have the following transitions: – ⟨b ,2,0 ⟩ r 1 ⟹ ⟨b ,1,2 ⟩ , – ⟨b ,1,2 ⟩ r 2 r 3 ⟹ ⟨b+ 2, 2, 0 ⟩ , – ⟨b ,1,2 ⟩ r 2 r 4 ⟹ ⟨b+ 1, 1, 2 ⟩ . 4.2 Semantics 2: total spikes We now consider the WSN P system 𝛱1 from Fig.1 together with the total spikes semantics. The corresponding configuration tree of 𝛱1 is now given by Fig.3. Fig. 2 The tree of configurations of 𝛱1 in Fig.1 using semantics 1 (spike packages semantics). The initial configuration is ⟨1, 1, 2⟩ . Except for ⟨1, 1, 2⟩ , each node in the tree is a successor configuration obtained by applying the rules labeling the connecting edge. Nodes (configurations) in bold are nodes repeated elsewhere in the portion of the tree depicted here Fig. 3 Configuration tree for 𝛱1 in Fig.1 using semantics 2 (total spikes semantics). As in Fig.2, edges between nodes (configurations) are labeled by the rules applied from the source to destination nodes. Moreover, configuration ⟨ 1, 0, 2 ⟩ in bold means it is repeated with all its branches infinitely often Wireless spiking neural P systems From the same initial configuration C0=⟨ 1, 1, 2 ⟩ , the computation proceeds in a different way: The transition C0 r 2 r 4 ⟹C 1,2 = ⟨ 1, 0, 0 ⟩ is a halting configuration, i.e., no more rules can be applied in 𝛱1 . We note that the effect of applying rules r2 and r4 from C0 is to release a total number of 3 spikes followed by the halting of 𝛱1 , because the three spikes cannot enter any of the neurons, since none of them has a3 in its input filter. Only the subtree with transition C0 r 2 r 3 ⟹C 1,1 = ⟨ 1, 0, 2 ⟩ continues to infinitely grow the number of spikes in neuron 𝜎1 . In fact, for all b≥1 , applying rule r4 to the configuration ⟨b,1,0⟩ yields the configuration ⟨b,1,0⟩ again, whereas applying rule r2 to the configuration ⟨b ,1,0 ⟩ yields the configuration ⟨b+1, 1, 0⟩ . In both cases, we see that every branch leads to a non-halting computation. 5 Programming WSN P systems To give an idea how to program WSN P systems, including their similarities and differences with SN P systems and their other variants, we consider the following very small register machine M which simply copies the contents of register 1 into register 2: with the following instructions in P: For “addressing” the neuron i which encodes the contents of registeri, we use the (odd) prime number P(i), where we assume P(1)<P(2) . The contents xi of register i then are represented by 2P(i) spikes in neuron i, i.e., it contains a2P(i)xi ; hence, the number xi is encoded by the linear function 2P(i)xi . In addition, for the simulation of the ADD and SUB instructions on this register regi of M, 𝜎regi may contain an additional odd number of spikes, which is less than the number representing the lowest non-zero value 2P(i). The main idea of our construction of the WSN P system is that each register r, r∈{1, 2} , does its job itself when an ADD or SUB instruction labeled by p∈{1, 2, 3} on r is to be simulated, activated by 2(3+p)−1 additional spikes, which make the contents of 𝜎regr an odd instead of an even number of spikes. Hence, we have to fulfill the additional condition 2∗(3+3)<2P(1) , assuming that P(1) is the smallest odd prime number used for the encodings in the neurons, because for the l=3 instructions p∈{1, 2, 3} , we have at most 2(l+p)−1=4∗l−1 . In total, these additional odd “remainders” are 2∗l+1, …,4∗l−1 . When subtracting 2l=6 , the resulting odd “remainders” are 1, …,2l−1 , so, M = ( m,B={1, 2, 3},l 0 =1, l h =3, P ) 1∶(SUB(1),2,3),2∶(ADD(2),1,1), and 3 ∶HALT. in total, we have the odd numbers between 1 and 4l−1 . Thus, we require 4∗3<2P(1) , i.e., P(1)>6 . Hence, we take P(1)=7 and P(2)=11 . The WSN P system 𝛱 now is defined as follows: With the following defintion of the neurons 𝜎i , 1≤i≤2 : 𝜎i=(Initiali,Ri,Ei) . Initiali =a 2P(i)ni where ni is the initial value in register i; as register 2 is the output register, we have to take Initial2 =a 0 (= 𝜆 ). E1={a7 , a14} , E2 ={a 9 ,a 22} . The filters a14 and a22 allow the number of spikes to pass which are necessary to increase the number of spikes in neurons 1 and 2, respectively, when an ADD instruction has to be executed on these neurons, which coresponds to an increment of the contents of the simulated register. On the other hand, a7 activates the SUB instruction 1∶(SUB(1),2,3) on register 1 and a9 activates the ADD instruction 2∶(ADD(2),1,1) on register 2. R1= { {a14j + 7∣1≤j}∕a14 + 7→a9,a7→a11 } , R 2 = { {a22j+9∣0≤j}∕a6→a22,{a22j+3∣0≤j}∕a3→a7 }. The number of spikes yi in each neuron i at time t of a computation in 𝛱 can be described by the configuration C(t)=⟨y1 , y2⟩ . At the beginning, we have the configuration C(0)=⟨14 ∗x0+7, 0⟩ , where x0 describes the initial value in register 1 of the register machine M and the additional 7 spikes in neuron 1 activate the initial instruction to be simulated. Simulation of the SUB instruction The simulation of the SUB instruction 1∶(SUB(1),2,3) only takes one step; the action taken depends on the number n encoded in the neuron 𝜎1 as 14 ∗n : n>0 : In this case, neuron 𝜎1 contains at least 14 spikes in addition to the 7 spikes which have activated the neuron; hence, the rule { a 14j+7∣ 1≤j }∕ a 14+7 →a 9 is to be applied. Thus, we have got the computation n=0 : In this case, neuron 𝜎1 contains exactly the 7 spikes which have activated the neuron; hence, the rule a7→a11 is to be applied. Thus, we have got the computation 𝛱= ({a},𝜎1,𝜎2) C(t)=⟨14x 1 +7, 22x 2 ⟩⟹ C(t+ 1 )=⟨ 14 (x1− 1 ) , 22 x2+ 9 ⟩. C( t )=⟨ 7, 22x2 ⟩⟹ C(t+ 1 )=⟨ 0, 22 x2⟩. D.Orellana-Martín et al. Observe that, in this case, the 11 spikes sent out to the environment cannot enter any of the two neurons 1 or 2 as the 11 spikes have “activated" the HALT instruction, i.e., the computation stops. Finally, we observe that the final configuration is ⟨0, 22x0⟩ , i.e., the initial contents of register 1 represented by 14x0 in neuron 1 have successfully been copied to register 2 represented by 22x0 in neuron 2. Simulation of the ADD instruction The simulation of the ADD instruction 2∶(ADD(2),1,1) takes two steps: – In the first step, the register itself is incremented by sending 22 spikes to neuron 𝜎2 using the rule {a22j+9∣ 0≤ j}∕a6 → a22 . The 22 spikes can only enter neuron 𝜎2 . – The remaining 3 spikes in neuron 𝜎2 now activate the rule {a22j+3∣ 0≤ j}∕a3 → a7 ; the 7 spikes can only enter neuron 𝜎1 , thus activating neuron 𝜎1 to simulate the corresponding register machine instruction labeled by 1 for the next step. In sum, we have got the computation C(t)=⟨14x1, 22x2+9⟩⟹ C(t+ 1 )=⟨ 14 x1 , 22 (x2+ 1 )+ 3 ⟩⟹ C(t+2)=⟨14x1+7, 22(x2+1)⟩ . The whole system is constructed in such a way that it works sequentially, i.e., only one neuron is activated; hence, only this one may spike, which also means that the constructed system not only works with using the spike packages semantics, but also with using the total spikes semantics. Simulation of the HALT instruction At the end, starting the simulation of the HALT instruction 3:HALT means that 11 spikes have been sent to the environment, but no input filter Ei , i∈{1, 2} , let this number of spikes enter the corresponding neuron 𝜎i . Hence, none of the neurons is activated; the computation in 𝛱 stops. Using prime numbers as “addresses” for each neuron and the odd numbers for choosing the corresponding rules allows for correct simulations. We use such addressing not only in the input filters associated with each neuron, but also in the number of spikes released by the neurons. In sum, the WSN P system 𝛱 correctly simulates the actions of the given register machine M, for both semantics 1 and 2. 6 Computational completeness ofWSN P systems In this section, we prove that WSN P systems are computationally complete by simulating an arbitrary register machine. This also shows that the power of addressing neurons using the input filters for the (packages of) spikes in WSN P systems even exceeds the power of an underlying directed graph for the communication of spikes in SN P systems. The proof not only works with using the spike packages semantics, but also with using the total spikes semantics. Both the input and the output are encoded in a linear way. The following result is even already optimal with respect to the number of neurons: Theorem1 The computations of any register machine with mregisters can be simulated by a WSN P system with m neurons, with the input and output being encoded in a linear way, and either using the spike packages semantics or even the total spikes semantics. Proof Consider an arbitrary register machine with m registers with |B|=l=|P| . We now construct a WSN P system 𝛱 to simulate M and its instructions. Without loss of generality, we assume a total order for the instructions as well as for the registers of M, i.e., we list instructions and registers as ⟨l0 , l1 , … , lh⟩ and ⟨reg1,…,regm⟩ . For the first list of (labels of) instructions, without loss of generality, we assume that the list simply describes the natural numbers from 1 to l, with l0=1 and lh=l . Now we assign an odd prime number P(regj) , 1 ≤ j ≤ m , to the elements of the second list ⟨reg1 , … , regm⟩ , in such a way that P(reg1)<P(reg2)<…<P(regm) , but, in addition, we require 4l<2P(reg1) ; the reason for this requirement will become clear soon below. If a register regi contains the number n, then the corresponding neuron 𝜎regi contains a2P(reg i )n , i.e., 2P(regi)n spikes; hence, the number n is encoded by the linear function 2P(regi)n . In addition, for the simulation of the ADD and SUB instructions on this register regi of M, 𝜎regi may contain an additional odd number of spikes, which is less than the number representing the lowest non-zero value 2P(regi) . The WSN P system 𝛱 now is defined as with the following defintion of the neurons 𝜎 reg i , 1≤i≤m : 𝜎regi=(Initialregi,Rregi,Eregi) . With ni denoting the initial value in register i, we have Initialregi =a 2P(reg i )ni for i>1 and Initial reg 1 =a 2P(reg 1 )n 1+2(l+1)− 1 , with the additional 2(l+1)−1 additional spikes “activating" the simulation of the initial instruction labeled by l0=1 . E reg i ={a 2P(reg i ) }∪{a 2(l+p)−1 ∣p∈BADD ( i ) ∪BSUB ( i )} M = ( m,B,l 0 ,l h ,P ) 𝛱= ({a},𝜎 reg 1,…,𝜎 reg m ) Wireless spiking neural P systems R regi= { {a2jP(regr)+2(l+p)−1∣0≤j}∕a2l→a2P(regr)) ∣p∈BADD(r) } ∪{a2jP(regr)+2p−1∣0≤j}∕a2p−1→a2(l+q(p))−1∣p∈BADD(r) } ∪{a2jP(regr)+2p−1∣0≤j}∕a2p−1→a2(l+s(p))−1∣p∈BADD(r) } ∪{{a2jP(regr)+2(l+p)−1∣1≤j}∕a2(l+p)−1+2P(regr)→a2(l+q(p))−1 ∣p∈BSUB(r)} ∪ { a2(l+p)−1→a2(l+s(p))−1∣p∈B SUB(r)} Let us denote the unit vector having m components with the i-th component being 1 and all the other components being 0 by em , i . Moreover, the number of spikes yi in each neuron i at time t of a computation in 𝛱 can be described by the configuration C(t)=⟨y1 , … , yn⟩ . At the beginning, we have the configuration C(0)=⟨2P(reg1)x1+2(l+1)−1, 2P(reg2)x2…, 2P ( regn ) xn⟩ , where ⟨x1 , … , xn⟩ describes the initial values in the registers of the register machine M. The main idea of our construction is that each register r does its job itself when an ADD or SUB instruction on r is to be simulated, activated by 2(l+p)−1 additional spikes, which make the contents of 𝜎regr an odd instead of an even number of spikes. Here we immediately see why we made the condition 4l<2P(reg1) , assuming that P(reg1) is the smallest odd prime number used for the encodings in the neurons, because for p=l we have 2(l+p)−1=4l−1 . In total, these additional odd “remainders” are 2l+1, …,4l−1 . When subtracting 2l, the resulting odd “remainders” are 1, …,2l−1 , so, in total, we have the odd numbers between 1 and 4l−1 . The whole system is constructed in such a way that it works sequentially, i.e., only one neuron is activated; hence, only this one may spike, which also means that the constructed system not only works with using the spike packages semantics, but also with using the total spikes semantics. Now let us assume that, at time t, we have the configuration C ( t )= ⟨ 2 P ( reg1 ) x1 ,…,2 P ( regn ) xn⟩ +(2( l + p )−1 ) em , Reg ( p) , where the simulation of the instruction labeled by p working on register r is initiated by the (2(l+p)−1) additional spikes in neuron Reg(p)=r . Simulation of an ADD instruction The simulation of an ADD instruction takes two steps: – In the first step, the register itself is incremented by sending 2P(regr) spikes to neuron 𝜎regr using the rule a2l→a2P(reg r )) . The 2P(regr) spikes can only enter neuron 𝜎regr . – The remainder of 2p−1 spikes in neuron 𝜎regr now activates one of the rules a2p−1→a2(l+q(p))−1 or a2p−1→a2(l+s(p))−1 ; the 2(l+q(p)) − 1 spikes can only enter neuron 𝜎 reg Reg(q(p)) , the 2(l+s(p)) − 1 spikes can only enter neuron 𝜎 reg Reg(s(p)) , thus activating 𝜎 reg Reg(q(p)) or 𝜎 reg Reg(s(p)) to simulate the corresponding register machine instructions q(p) or s(p), respectively. In sum, we have got the computation or Simulation of a SUB instruction The simulation of a SUB instruction only takes one step; the action taken depends on the number n encoded in the neuron 𝜎regr as 2P(regr)n : n>0 : In this case, neuron 𝜎regr contains at least 2P(regr) spikes in addition to the 2(l+p)−1 spikes which have activated the neuron; hence, the rule a2(l+p)−1+2P(reg r )→a2(l+q(p))−1 is to be applied. Thus, we have got the computation n=0 : In this case, neuron 𝜎regr contains exactly the 2(l+p)−1 spikes which have activated the neuron; hence, the rule a2(l+p)−1→a2(l+s(p))−1 is to be applied. Thus, we have got the computation C(t)=⟨2P(reg1)x1,…,2P(regm)xm⟩+ (2(l+p)−1)em,r⟹ C (t+1)= ⟨ 2P(reg 1 )x 1 ,…,2P(reg n )x n⟩+ (2(l+s(p)) − 1)em,Reg(s(p)) . Simulation of the HALT instruction C ( t )=⟨ 2P ( reg1 ) x1, … ,2P ( regm ) xm ⟩+( 2 ( l + p )− 1 ) em,r ⟹ C (t+1)=⟨2P(reg1)x1,…,2P(regn)xn⟩ +(2p−1+2P(regr))em,r⟹ C (t+2)=⟨2P(reg1)x1,…,2P(regn)xn⟩ +2P(reg r )e m , r +(2(l+q(p)) − 1)e m , Reg(q(p)) C(t+2)=⟨2P(reg 1 )x 1 ,…,2P(reg n )x n ⟩ +2P(reg r )e m,r +(2(l+q(p)) − 1)e m,Reg(s(p)). C(t)=⟨2P(reg 1 )x 1 ,…,2P(reg m )x m ⟩ +(2(l+p)−1)em,r⟹ C (t+1)=⟨2P(reg1)x1,…,2P(regn)xn⟩ −2P(reg r )e m,r +(2(l+q(p)) − 1)e m,Reg(q(p)).