Wireless spiking neural P systems

Vol.:(0123456789) Jou nal o Memb ane Compu ing h ps://doi.o g/10.1007/s41965-025-00199-8 RESEARCH PAPER Wi eless spiking neu al P sys ems Da idO ellana‑Ma ín1 · F ancisGeo geC.Caba le1,2 · P i hwineelPaul3 · XiangxiangZeng4 · Rudol F eund5 Recei ed: 30 Sep embe 2024 / Accep ed: 26 May 2025 © The Au ho (s) 2025 Abs ac Spiking neu al P sys ems (SN P sys ems) a e compu ing models based on he hi d gene a ion o neu on models known as spiking neu ons. Recen esul s in neu oscience highligh he impo ance o ex asynap ic ac i i ies o neu ons, ha is, ea u es and unc ioning o neu ons ou side hei synapses. P e iously i was hough ha signals such as neu opep ides only assis neu ons, bu ecen ly such signals ha e been gi en addi ional impo ance. Inspi ed by ecen esul s, we de ine wi e- less SN P sys ems (WSN P sys ems). In WSN P sys ems, no synapses exis : egula exp essions associa ed wi h each neu on a e used o decide which spikes i ecei es. We p o ide wo seman ics o how o “in e p e ” he spikes eleased by neu ons. A speci ic egis e machine is simula ed o show he di e en s yle o p og amming WSN P sys ems compa ed o p og am- ming s anda d SN P sys ems and o he a ian s. This s yle emphasizes a ade-o : WSN P sys ems can be mo e “ lexible” since hey a e no limi ed by hei synapses o sending spikes; howe e , losing he use ul di ec ed g aph s uc u e equi es ca e ul design o ules and exp essions associa ed wi h each neu on. We use linea p ime numbe encodings in cons uc ing he exp essions and ules o he neu ons o p o e ha WSN P sys ems a e Tu ing-comple e in bo h spike seman ics. Keywo ds Na u al compu ing· Memb ane compu ing· Spiking neu al P sys ems· Ex asynap ic signaling· Neu opep ides 1 In oduc ion The p esen wo k in oduces a a ian o spiking neu al P sys ems, in sho SN P sys ems, in a o mal way. SN P sys ems as in oduced in Re .[24] a e inspi ed by spiking neu ons and hei ne wo k: he p ocesso s a e neu ons which a e he nodes in a di ec ed g aph; he edges a e synapses which allow o he communica ion be ween neu ons using a single objec a e e ed o as a spike; he neu ons a e spike p ocesso s which consume and p oduce spikes. Some ecen su ey pape s o SN P sys ems and a i- an s include Re s. ci elepo a ispssnpsu 2022, anspssnps u 2020 and mo e ecen ly Re . [9]. Since hei in oduc ion, i is known ha SN P sys ems a e Tu ing-comple e [24]. Much li e a u e is dedica ed o compu a ional comple eness (Tu ing-comple eness) o SN P sys ems, also in es iga ing how small he sys em can be [41], es ic ions on hei syn- ax o seman ics [22, 32]. SN P sys ems a e also shown o sol e NP-comple e p oblems, ading ime o space [30] such as wi h he use o a bi a ily la ge esou ces (e.g., neu- ons and synapses) [25] o c ea ion o new esou ces [55]. In he pas 2 decades, many a ian s o SN P sys ems ha e been in oduced depending on speci ic ing edien s o * Da id O ellana-Ma ín [email p o ec ed] F ancis Geo ge C. Caba le [email p o ec ed] P i hwineel Paul p i [email p o ec ed] Xiangxiang Zeng [email p o ec ed] Rudol F eund [email p o ec ed] 1 Resea ch G oup onNa u al Compu ing, Depa men o Compu e Science andA i icial In elligence, SCORE lab, I3US, Uni e sidad de Se illa, A da. Reina Me cedes s/n, 41012Se illa, Spain 2 Depa men o Compu e Science, Uni e si y o he Philippines Diliman, 1101QuezonCi y, Philippines 3 Depa men o Compu e Science andEnginee ing, Ins i u e o Enginee ing andManagemen , Uni e si y o Enginee ing andManagemen , New Town Rd., Kolka a700091, India 4 Depa men o Compu e Science, Hunan Uni e si y, Changsha, China 5 Facul y o In o ma ics, TU Wien, Fa o i ens aße 9-11, 1040Vienna, Aus ia D.O ellana-Ma ín e al. ea u es, mos ly om biology, o ins ance, he in oduc- ion o au apses [51], synap ic plas ici y [10], pola isa ions [56], synap ic schedules [6], neu ogenesis [55], dynamic h eshold [26], colo ed spikes [40], and as ocy es [5, 7, 8, 27, 39], among o he s. Applica ions o SN P sys ems and hei a ian s include image p ocessing [50], e olu iona y op imisa ion [18, 59], pa e n ecogni ion [49], cybe se- cu i y [44], mig a ion s a egies in memb ane algo i hms [14], among o he s. Simula o s o SN P sys ems and a i- an s a e used o suppo esea ch o pedagogy, such as in e ac i e and isual so wa e in Re s. [15, 17]. SN P sys ems a e also in es iga ed o hei implemen a ion in pa allel ha dwa e such as in Re s. [20, 33] wi h ecen and some s a e-o - he-a esul s in Re . [19]. Wi eless SN P sys ems, o WSN P sys ems in sho , a e a SN P sys em a ian de ined in a o mal way in he p esen wo k, p e iously in oduced in an in o mal way in a ecen epo [38]. One gene al e e ence o he bio-inspi a ion o WSN P sys ems is om Re . [31] wi h ecen and de ailed esul s om Re s. [47, 48]. B ie ly, such ecen esul s emphasize he c ucial and impo an ole o neu onal ac i i- ies ou side hei synapses, hence hei wi eless ea u es and unc ions. Such ecen wo ks ocus hei a en ion on a spe- ci ic animal known as C. elegans. The wo m C. elegans is a model o ganism, i.e., much is known abou i s biology including i s ne ous sys em due o i s “simplici y” o se e al hund ed neu ons only. Despi e he small size o his wo m, i s ne ous sys em has in e es ing biochemical complexi y wi h s uc u al ea u es sha ed by la ge animals [48]. Due o be e echniques and echnol- ogy, mo e ecen ly he e a e imp o ed wo ks o show how a wi eless ne wo k ( ha is, wi hou synap ic wi ing) among ne e cells o neu ons is able o ope a e [47, 48]. These ecen wo ks challenge he idea ha neu ons communica e only o mainly h ough ana omical connec ions, ha is, h ough hei synapses [31]. Such ecen wo ks e eal new de ails o a connec ome o wi ing diag am among neu ons, he neu opep ide gic connec ome: a connec ome which is equally impo an and pe haps mo e di e se han he syn- ap ic connec ome. Fu he mo e, hese ecen wo ks iden i y neu opep ides, he chemical messages eleased by neu ons, as he basis o such wi eless ne wo k among neu ons. Neu ons in he C. elegans wo ms can elease neu opep ides, o ha e ecep o s o such neu opep ides. The wi eless ne wo k o med om hese pai s o eleasing and ecei ing neu ons is dense and decen alized, compa ed o he less dense and mo e cen al- ized ne wo k o synapses [48]. Such pai s a e esponsible o he exis ence o he wi eless ne wo k, which means ha neu opep ides a e no andom chemicals loa ing be ween neu ons. Neu opep ides a ec he neu al sys em o e la ge scales o ime and space, unlike synap ic signals es ic ed only o bo h sides o he synapse [48]. P e iously i was hough ha neu opep ides only assis ed in synap ic communica ion. Howe e , hese ecen wo ks indica e he ubiqui ous, impo an , and di ec ole o neu on ac i a ion o neu opep ides and he co esponding wi eless ne wo k [31]. Neu opep ides a e conse ed and ancien chemicals in b ains o many o ganisms, including he human b ain, sugges ing ha he pionee ing wo k wi h C. elegans can a leas e eal use ul s uc u es o p inciples o b ain unc ion [47, 48]. Fo ins ance, a ecen echnique allows o de ec ing neu opep ides, which can assis in be e unde - s anding o bo h wi ed and wi eless ne wo ks o neu ons including hose o humans [54]. We use such ecen esul s as inspi a ions o ex asynap- ic unc ions o neu ons, ha is, unc ioning wi hou o ou - side he usual synapses. Con ibu ions o he p esen wo k include he o mal in oduc ion o wi eless SN P sys ems and p oo s o hei Tu ing-comple eness. No synapses a e p esen in he neu ons, while s ill using ules o consume and p oduce spikes. Fo each neu on, we associa e a ini e il e o decide wha “ o ms” o spikes he neu on can ecei e. We in oduce wo seman ics o WSN P sys ems, based on he in e p e a ion o he spikes eleased in each s ep by he neu ons: (i) he spike package seman ics conside s he spikes as indi idual packages as eleased by each neu on; (ii) he spike o al seman ics conside s he sum o spikes eleased by all neu ons. We show how o p og am a speci ic WSN P sys em h ough he simula ion o speci ic egis e machine ins uc- ions. Such a simula ion emphasizes he a he di e en way how o p og am WSN P sys ems compa ed wi h SN P sys- ems and hei a ian s, due o he associa ed ini e il e o each neu on and he lack o synapses. Al hough he di ec ed g aph s uc u e o SN P sys ems and hei many a ian s is a e y use ul ea u e, in WSN P sys ems, some “ lexibili y” is gained in he sense ha he neu ons a e no limi ed o sending spikes only o neu ons o which hei synapses con- nec . On he o he hand, losing he di ec ed g aph s uc u e makes he p og amming o he sys em mo e “in ol ed” in he sense ha mo e e o can be equi ed o design he ules and neu ons. The p esen wo k is o ganized as ollows: In Sec .2, we ecall some p elimina ies needed o unde s and WSN P sys ems and hei compu a ions; he de ini ion o WSN P sys ems is gi en in Sec .3. An example o a WSN P sys em, conside ed unde wo seman ics, is used o illus a e wo kinds o compu a ions in Sec .4. In Sec .5, we highligh he in e es ing way how o p og am WSN P sys ems by imple- men ing he simula ion o a speci ic small egis e machine. This simula ion also gi es us an idea o he compu ing powe and he way how o p og am WSN P sys ems in a gene al pu pose way. The p oo s o compu a ional comple eness a e gi en in Sec .6. Finally, conclusions and di ec ions o u u e wo k a e discussed in Sec .7. Wi eless spiking neu al P sys ems 2 P elimina ies In his sec ion, we only b ie ly men ion some no ions equi ed o ou de ini ions and esul s. Fo mo e de ails on au oma a and language heo y, we e e o Re . [34], o hei applica ions o memb ane compu ing o Re s. [45, 46]. Gi en a ini e and nonemp y alphabe V, by V∗ , we deno e he se o all ini e s ings o e V; V+=V∗⧵{𝜆} . The se o all mul ise s o e V is deno ed by V◦ . The amily o ini e and egula s ing languages is deno ed by FIN and REG, espec i ely, he co esponding amily o ini e and egula mul ise languages by PsFIN and PsREG, espec i ely (as i con ains he Pa ikh images o he ini e and egula s ing languages, espec i ely). NFIN(a) and NREG(a) deno e he amily o ini e and egula mul ise languages o e he one- le e alphabe {a} . De ini ion 1 A egis e machine is a cons uc whe e – m is he numbe o egis e s, – B is he se o labels o he ins uc ions in P, – P is he se o ins uc ions bijec i ely labeled by elemen s o B, – l0∈B is he ini ial label, and – lh∈B is he inal label. The ins uc ions o M can be o he ollowing o ms: – p:(ADD( ),q(p),s(p)); p∈B⧵ { l h} , q(p),s(p)∈B , 1≤ ≤m . Inc ease he alue o egis e by one, and non-de e minis ically jump o ins uc ion q(p) o s(p). – p:(SUB( ),q(p),s(p)) ; p ∈B⧵ { l h} , q(p),s(p)∈B , 1≤ ≤m . I he alue o egis e is no ze o, hen dec ease he alue o egis e  by one (dec emen case) and jump o ins uc ion q(p), o he wise jump o ins uc- ions(p) (ze o- es case). – lh∶HALT .S op he execu ion o he egis e machine. A con igu a ion o a egis e machine is desc ibed by he con en s o each egis e and by he alue o he cu en label, which indica es he nex ins uc ion o be execu ed. M is called de e minis ic i he ADD ins uc ions all a e o he o m p:(ADD( ),q(p)) . Th oughou he pape , BADD( ) deno es he se o labels o ADD ins uc ions p:(ADD( ),q(p),s(p)) o an a bi a y eg- is e , and BSUB( ) deno es he se o labels o all SUB ins uc- ions p:(SUB( ),q(p),s(p)) o a dec emen able egis e . Mo eo e , o any p∈B⧵{lh} , Reg(p) deno es he egis e M = ( m,B,l 0 ,l h ,P ) a ec ed by he ADD o SUB ins uc ion labeled byp; o he sake o comple eness, in addi ion Reg(lh)=1 is aken. In he gene a ing case, a compu a ion s a s wi h all eg- is e s being emp y and by execu ing he i s ins uc ion o P (labeled by l0 ); i e mina es wi h eaching he HALT ins uc- ion and he ou pu o a k ec o o na u al numbe s in i s las k egis e s. Wi hou loss o gene ali y, we may assume all egis e s excep he las k ou pu egis e s o be emp y a he end o he compu a ion, and, mo eo e , on he ou pu egis e s, i.e., he las k egis e s, no SUB ins uc ion is e e used, i.e., hey a e ne e dec emen ed. The se o ec o s o na u al numbe s gene a ed by M is deno ed by Ps(M); i only se s o numbe s a e compu ed, we w i e N(M). I is known ha egis e machines a e Tu ing-comple e, e.g., see Re . [35], i.e., egis e machines cha ac e ize NRE (PsRE), he amily ecu si ely enume able se s o ( ec o s o ) na u al numbe s. Hence, egis e machines a e a con eni- en model o be compa ed wi h models dealing wi h (se s o ) numbe s di ec ly ins ead o s ings. 3 De ini ion o WSN P sys ems In his sec ion, we de ine bo h he syn ax and seman ics o WSN P sys ems. In ac , wo di e en seman ics can a ise om he way he spikes a e ea ed when hey a e i ed om a neu on. The syn ax and he seman ics o WSN P sys ems sha e simila i ies wi h SN P sys ems and hei a ian s, o ins ance, we e e o Re s.[24, 42, 46] and mo e ecen ly o Re . [29] o u he de ails. 3.1 Syn ax De ini ion 2 A WSN P sys em o deg ee m≥1 is a cons uc whe e: 1. O={a} is he single on alphabe (a is called spike); 2. 𝜎i=(ni,Ei,Ri),1≤i≤m , is a neu on such ha : (a) ni∈ℕ is he ini ial numbe o spikes in neu on 𝜎i ; (b) Ei⊆NFIN(a) , he inpu il e o neu on 𝜎i ; (c) Ri is a ini e se o ules o wo possible o ms: i. E∕ac → as whe e E⊆NREG(a) is a egula se o numbe s o e O and c,s∈ℕ,c,s≥1 (spiking ules); ii. as→𝜆 whe e s∈ℕ,s≥1 ( o ge ing ules); 𝛱=(O,𝜎1,…,𝜎m) D.O ellana-Ma ín e al. A WSN P sys em 𝛱=(O,𝜎1,…,𝜎m) o deg ee m≥1 can be seen as a a se o m neu ons labeled by 1, …,m such ha : 1. n1,…,nm ep esen he ini ial mul ise s o objec s a (spikes) si ua ed a he beginning in he m neu ons o he sys em; 2. E1,…,Em a e ini e se s o e O assigned o he m neu- ons o he sys em, wo king as inpu il e s o he spike packages allowed o en e he neu on; 3. R1,…,Rm a e ini e se s o ules go e ning he dynamics o he sys em. Rema k 1 We men ion ha in his pape , we do no conside delays, as hey a e no needed in he ollowing and only make de ini ions much mo e complica ed. 3.2 Applicabili y o  ules inaWSN P sys em A con igu a ion o a WSN P sys em 𝛱 a some momen o ime is desc ibed as wi h he numbe o spikes ni, in each neu on i. The ini ial con igu a ion o 𝛱 is C0=⟨( n 1) , … , ( n m)⟩ . A spiking ule E∕ac → as∈Ri is applicable in he neu- oni gi en a con igu a ion C in s ep +1 i , in he con igu- a ion C , in he neu on labeled by i, he numbe o spikes ani , is in E. The applica ion o such a ule in ha neu on i p oduces he ollowing e ec s: c spikes a e emo ed om he neu on i, and i p oduces (we also say i es) s spikes o he en i onmen . A o ge ing ule as → 𝜆∈Ri is applicable o a con igu a- ion C in s ep +1 i , in con igu a ion C , he neu on labeled by i con ains exac ly s spikes. The applica ion o such a ule in ha neu on i emo es all he s spikes con ained in he neu on wi hou gene a ing any spike. 3.3 Seman ics Two possibili ies a ise ega ding how he p oduced spikes o some neu ons a e ecei ed by he same o o he neu ons: 1. spike packages seman ics: Each package o spikes is ea ed sepa a ely in he ollowing way: Le {ac 1 ,…,ac k } be he mul ise o packages o spikes p oduced by neu- ons ha ha e applied a spiking ule in he cu en s ep. Thus, o each acj , only all he neu ons 𝜎i such ha ac j ∈ E i ecei e cj spikes. 2. To al spikes seman ics: We ake he sum o all he spikes p oduced by he neu ons o he sys em in he ollowing way: Le {ac 1 ,…,ac k } be he mul ise o packages o C =⟨(n1, ),…,(nm, )⟩ spikes p oduced by neu ons ha ha e applied a spiking ule in he cu en s ep, and le c = ∑k j=1 c j . Then only he neu ons 𝜎i such ha ac∈Ei ecei e c spikes. These wo seman ics in he ollowing will be abb e ia ed by pac and o , espec i ely. 3.4 Compu a ions inaWSN P sys em A some ime ins ance , we say he con igu a ion C o he WSN P sys em 𝛱 p oduces a con igu a ion C +1 in one s ep—we deno e ha by C ⇒ 𝛱C +1 —by execu ing he ol- lowing wo subs eps: – All neu ons apply one ule (i possible) – Each neu on 𝜎i acco ding o he unde lying seman ics 𝛼∈{pac, o } akes he (packages o ) spikes p oduced in he i s subs ep om he en i onmen i hey can pass he inpu il e Ei o 𝜎i . We assume a global clock o synch onize he compu a ions in 𝛱 , ha is, i a neu on can apply a ule, hen i mus do so. In e e y s ep, 𝛱 is locally sequen ial since a mos one ule in each neu on can be applied, bu globally pa allel as mo e han one neu on can apply a ule. I mo e han one ule in a neu on is applicable, hen he ule o be applied is chosen in a nonde e minis ic way. A compu a ion o a WSN P sys em 𝛱 is de ined as a ( ini e o in ini e) sequence o con igu a ions C=(C0 , C1 , … , Cn , …) , whe e C0 is he ini ial con igu a- ion o 𝛱 and C ⇒ 𝛱C +1 o all . I , a e n s eps, no mo e ules as desc ibed abo e can be applied, we say ha 𝛱 hal s a e n s eps, and C=(C0 , C1 , … , Cn) is called a hal ing compu a ion. Rema k 2 We assume he spikes p esen in he en i onmen o be a ailable o all he neu ons only o one compu a ion s ep, i.e., hese spikes can be in e p e ed as decaying a e one s ep (decaying spikes, o example, we e conside ed in Re . [16]). 3.5 Ou pu Le be a WSN P sys em wo king in he seman ics 𝛼∈{pac, o } . The e a e se e al ways how a he end o a hal ing com- pu a ion he ou pu o he sys em can be ob ained: – The ou pu consis s o a k- ec o o na u al numbe s gi en by he numbe o spikes in some designa ed ou - 𝛱=(O,𝜎1,…,𝜎m) Wi eless spiking neu al P sys ems pu neu ons 𝜎j1,…,𝜎jk ; in ha case, he whole WSN P sys em is gi en as and we may also dis inguish he ollowing subcases: – We w i e Ps 𝛼 ,k−ou (𝛱) , i he numbe s in he k- ec o a e di ec ly gi en by he numbe o spikes con ained in he ou pu neu ons. – I he numbe s o he ou pu ec o a e encoded in he numbe o spikes con ained in he ou pu neu ons by a speci ic unc ion like an exponen ial unc ion, we w i e Ps 𝛼,k−ou (𝛱) ; as a special case, we conside o be a linea unc ion, in which case we also w i e Ps 𝛼, k−ou l(𝛱) . – The ou pu is ob ained om a designa ed ou pu neu on 𝜎 i 0 , 1≤i0≤m ; in ha case, he whole WSN P sys em is gi en as and we may also dis inguish he ollowing subcases: – The ou pu ec o wi h k componen s is gi en by k+1 spikes sen o he en i onmen by he ou pu neu on 𝜎i0 , and we w i e Ps𝛼,kWSNP ; gi en he sequence o ime ins ances ⟨ 1,…, k+1⟩ when he k+1 spikes ha e been sen ou by he ou pu neu- on 𝜎i0 , he k componen s o he ou pu ec o a e ob ained as he ime in e als ⟨ 2− 1 , … , k+1− k⟩ ; in his case, we w i e Ps 𝛼, k−in (𝛱) . – The ou pu ec o wi h k componen s is gi en by k sequences o consecu i e spikes sen o he en i- onmen by he ou pu neu on 𝜎i0 , and we w i e Ps 𝛼, k−sequ(𝛱) . In all he a ian s desc ibed abo e, we eplace Ps by N, i only one na u al numbe is o be ob ained as ou pu . The amilies o se s o k ec o o na u al numbe s ob ained by WSN P sys ems as desc ibed abo e a e deno ed by Ps 𝛼, k−ou WSNP , Ps 𝛼,k−ou WSNP , Ps 𝛼, k−in WSNP , and Ps𝛼,k−sequWSNP . I only se s o na u al numbe s a e consid- e ed, we deno e he co esponding amilies o se s o na u al numbe s by N𝛼,ou WSNP , N 𝛼,ou WSNP , N𝛼,in WSNP , and N 𝛼, sequWSNP . Rema k 3 In he second case desc ibed abo e wi h he des- igna ed ou pu neu on 𝜎 i 0 , we can hink o 𝜎 i 0 as he in e ace o 𝛱 o he en i onmen . As a echnical de ail, we men ion ha in con as o SN P sys ems and o he a ian s, he i ing o 𝜎i0 should only send spikes o he en i onmen , bu none o he neu ons in 𝛱 including 𝜎 i 0 i sel should ecei e he 𝛱=(O,𝜎1,…,𝜎m;j1,…,jk), 𝛱=(O, 𝜎 1,…, 𝜎 m;i0), spikes p oduced by 𝜎i0 . This may be accomplished by a oid- ing a o be con ained in any o he inpu il e s Ei , 1≤i≤m . 4 An example wi h he wo seman ics In his sec ion, as an example, we conside he WSN P sys- em 𝛱1 shown in Fig.1. We use 𝛱1 o explain he de ini ions and he wo seman ics om Sec .3. Fo sho , 𝛱1 has h ee neu ons, each labeled by a pai (i,Ei) o 1≤i≤3 . Each neu on has associa ed he ini e inpu il e Ei o check which numbe (s) o spikes i can ecei e. Fo ins ance, neu ons 𝜎1 and 𝜎2 ha e E1=E2={a} , which means hey can only ecei e spikes o he o m a1=a i ed om o he neu ons o o 𝜎2 e en including spikes sen om i sel . We no e ha he ule se o 𝜎1 is emp y, so i can ne e spike, and he numbe o spikes inside can only ei he emain he same o inc ease. 4.1 Seman ics 1: spike packages We i s conside seman ics 1, which we e e o as spike packages seman ics. I only conside s spikes a i ing in “packages” sen by neu ons o he en i onmen , no he o al numbe o spikes in he en i onmen . To illus a e he com- pu a ion o 𝛱1 using he spike packages seman ics, we e e o he con igu a ion ee in Fig.2. The ini ial con igu a ion o 𝛱1 , assuming he (con en s o he) neu ons o be lis ed acco ding o he o al o de ing 1,2,3, is C0=⟨1, 1, 2⟩ , i.e., neu ons 1, 2, and 3 con ain 1, 1, and 2 spikes, espec i ely. To C0 , he ule 2 can be applied in 𝜎2 , and in neu on 𝜎3 , he e is a nonde e minis ic choice be ween ule 3 and ule 4 . I ule 2 is applied, one spike is consumed in neu on 𝜎2 and sen o bo h neu on 𝜎1 and neu on 𝜎2 due o hei inpu il e s E1=E2={a} . Applying ule 3 means ha 𝜎3 consumes wo spikes bu i es only one spike. Again his single spike om 𝜎3 a i es in 𝜎1 and 𝜎2 due o hei inpu il e s. Hence, in o al, we ha e go he ansi ion C 0 2 3 ⟹C1,1 = ⟨ 3, 2, 0 ⟩ , i.e., by applying 2 and 3 , we ob ain con igu a ion C1,1 om con igu a ion C0 . Now we conside he case when we apply ule 4 oge he wi h ule 2 ins ead. The e ec o applying ule 2 is s ill o e u n a spike o 𝜎2 and o inc emen he num- be o spikes in 𝜎1 . The e ec o 4 is e lexi e, i.e., in Fig. 1 𝛱1 is an example o a wi eless SN P sys em D.O ellana-Ma ín e al. neu on 𝜎3 wo spikes a e consumed and hen e u ned o i sel , since E3={a2} . Hence, we ha e he ansi ion C0 2 4 ⟹C 1,2 = ⟨ 2, 1, 2 ⟩ , i.e., by applying 2 and 4 , we ob ain con igu a ion C1,2 om con igu a ion C0 . Hence, in o al, om he ini ial con igu a ion C0 , we ge he wo successo con igu a ions C1,1 =⟨ 3, 2, 0 ⟩ and C1,2 =⟨2, 1, 2⟩ as depic ed in he ee o Fig.2. As can be seen in he con igu a ion ee in Fig.2, each b anch o compu a ions in 𝛱1 is non-hal ing, i.e., 𝛱1 always a i es a a con igu a ion whe e some ule can s ill be applied. The numbe o spikes in neu on 𝜎1 con inues o inc ease. Mo e p ecisely, o all b≥1 , we ha e he ol- lowing ansi ions: – ⟨b ,2,0 ⟩ 1 ⟹ ⟨b ,1,2 ⟩ , – ⟨b ,1,2 ⟩ 2 3 ⟹ ⟨b+ 2, 2, 0 ⟩ , – ⟨b ,1,2 ⟩ 2 4 ⟹ ⟨b+ 1, 1, 2 ⟩ . 4.2 Seman ics 2: o al spikes We now conside he WSN P sys em 𝛱1 om Fig.1 oge he wi h he o al spikes seman ics. The co esponding con igu- a ion ee o 𝛱1 is now gi en by Fig.3. Fig. 2 The ee o con igu a- ions o 𝛱1 in Fig.1 using seman ics 1 (spike packages seman ics). The ini ial con- igu a ion is ⟨1, 1, 2⟩ . Excep o ⟨1, 1, 2⟩ , each node in he ee is a successo con igu a ion ob ained by applying he ules labeling he connec ing edge. Nodes (con igu a ions) in bold a e nodes epea ed elsewhe e in he po ion o he ee depic ed he e Fig. 3 Con igu a ion ee o 𝛱1 in Fig.1 using seman ics 2 ( o al spikes seman ics). As in Fig.2, edges be ween nodes (con igu a ions) a e labeled by he ules applied om he sou ce o des ina ion nodes. Mo eo e , con igu a ion ⟨ 1, 0, 2 ⟩ in bold means i is epea ed wi h all i s b anches in ini ely o en Wi eless spiking neu al P sys ems F om he same ini ial con igu a ion C0=⟨ 1, 1, 2 ⟩ , he compu a ion p oceeds in a di e en way: The ansi ion C0 2 4 ⟹C 1,2 = ⟨ 1, 0, 0 ⟩ is a hal ing con igu- a ion, i.e., no mo e ules can be applied in 𝛱1 . We no e ha he e ec o applying ules 2 and 4 om C0 is o elease a o al numbe o 3 spikes ollowed by he hal ing o 𝛱1 , because he h ee spikes canno en e any o he neu ons, since none o hem has a3 in i s inpu il e . Only he sub ee wi h ansi ion C0 2 3 ⟹C 1,1 = ⟨ 1, 0, 2 ⟩ con inues o in ini ely g ow he numbe o spikes in neu on 𝜎1 . In ac , o all b≥1 , applying ule 4 o he con igu a- ion ⟨b,1,0⟩ yields he con igu a ion ⟨b,1,0⟩ again, whe eas applying ule 2 o he con igu a ion ⟨b ,1,0 ⟩ yields he con igu a ion ⟨b+1, 1, 0⟩ . In bo h cases, we see ha e e y b anch leads o a non-hal ing compu a ion. 5 P og amming WSN P sys ems To gi e an idea how o p og am WSN P sys ems, including hei simila i ies and di e ences wi h SN P sys ems and hei o he a ian s, we conside he ollowing e y small egis e machine M which simply copies he con en s o egis e 1 in o egis e 2: wi h he ollowing ins uc ions in P: Fo “add essing” he neu on i which encodes he con en s o egis e i, we use he (odd) p ime numbe P(i), whe e we assume P(1)<P(2) . The con en s xi o egis e i hen a e ep esen ed by 2P(i) spikes in neu on i, i.e., i con ains a2P(i)xi ; hence, he numbe xi is encoded by he linea unc- ion 2P(i)xi . In addi ion, o he simula ion o he ADD and SUB ins uc ions on his egis e egi o M, 𝜎 egi may con ain an addi ional odd numbe o spikes, which is less han he num- be ep esen ing he lowes non-ze o alue 2P(i). The main idea o ou cons uc ion o he WSN P sys em is ha each egis e , ∈{1, 2} , does i s job i sel when an ADD o SUB ins uc ion labeled by p∈{1, 2, 3} on is o be simula ed, ac i a ed by 2(3+p)−1 addi ional spikes, which make he con en s o 𝜎 eg an odd ins ead o an e en numbe o spikes. Hence, we ha e o ul ill he addi ional condi- ion 2∗(3+3)<2P(1) , assuming ha P(1) is he smalles odd p ime numbe used o he encodings in he neu ons, because o he l=3 ins uc ions p∈{1, 2, 3} , we ha e a mos 2(l+p)−1=4∗l−1 . In o al, hese addi ional odd “ emainde s” a e 2∗l+1, …,4∗l−1 . When sub ac ing 2l=6 , he esul ing odd “ emainde s” a e 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 o al, we ha e he odd numbe s be ween 1 and 4l−1 . Thus, we equi e 4∗3<2P(1) , i.e., P(1)>6 . Hence, we ake P(1)=7 and P(2)=11 . The WSN P sys em 𝛱 now is de ined as ollows: Wi h he ollowing de in ion o he neu ons 𝜎i , 1≤i≤2 : 𝜎i=(Ini iali,Ri,Ei) . Ini iali =a 2P(i)ni whe e ni is he ini ial alue in egis- e i; as egis e 2 is he ou pu egis e , we ha e o ake Ini ial2 =a 0 (= 𝜆 ). E1={a7 , a14} , E2 ={a 9 ,a 22} . The il e s a14 and a22 allow he numbe o spikes o pass which a e necessa y o inc ease he numbe o spikes in neu ons 1 and 2, espec i ely, when an ADD ins uc ion has o be execu ed on hese neu ons, which co esponds o an inc emen o he con en s o he simula ed egis- e . On he o he hand, a7 ac i a es he SUB ins uc ion 1∶(SUB(1),2,3) on egis e 1 and a9 ac i a es he ADD ins uc ion 2∶(ADD(2),1,1) on egis e 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 numbe o spikes yi in each neu on i a ime o a compu a ion in 𝛱 can be desc ibed by he con igu a ion C( )=⟨y1 , y2⟩ . A he beginning, we ha e he con igu a ion C(0)=⟨14 ∗x0+7, 0⟩ , whe e x0 desc ibes he ini ial alue in egis e 1 o he egis e machine M and he addi ional 7 spikes in neu on 1 ac i a e he ini ial ins uc ion o be simula ed. Simula ion o he SUB ins uc ion The simula ion o he SUB ins uc ion 1∶(SUB(1),2,3) only akes one s ep; he ac ion aken depends on he numbe n encoded in he neu on 𝜎1 as 14 ∗n : n>0 : In his case, neu on 𝜎1 con ains a leas 14 spikes in addi ion o he 7 spikes which ha e ac i a ed he neu on; hence, he ule { a 14j+7∣ 1≤j }∕ a 14+7 →a 9 is o be applied. Thus, we ha e go he compu a ion n=0 : In his case, neu on 𝜎1 con ains exac ly he 7 spikes which ha e ac i a ed he neu on; hence, he ule a7→a11 is o be applied. Thus, we ha e go he compu a ion 𝛱= ({a},𝜎1,𝜎2) C( )=⟨14x 1 +7, 22x 2 ⟩⟹ C( + 1 )=⟨ 14 (x1− 1 ) , 22 x2+ 9 ⟩. C( )=⟨ 7, 22x2 ⟩⟹ C( + 1 )=⟨ 0, 22 x2⟩. D.O ellana-Ma ín e al. Obse e ha , in his case, he 11 spikes sen ou o he en i onmen canno en e any o he wo neu ons 1 o 2 as he 11 spikes ha e “ac i a ed" he HALT ins uc ion, i.e., he compu a ion s ops. Finally, we obse e ha he inal con igu a ion is ⟨0, 22x0⟩ , i.e., he ini ial con en s o egis e 1 ep esen ed by 14x0 in neu on 1 ha e success ully been copied o egis e 2 ep esen ed by 22x0 in neu on 2. Simula ion o he ADD ins uc ion The simula ion o he ADD ins uc ion 2∶(ADD(2),1,1) akes wo s eps: – In he i s s ep, he egis e i sel is inc emen ed by sending 22 spikes o neu on 𝜎2 using he ule {a22j+9∣ 0≤ j}∕a6 → a22 . The 22 spikes can only en e neu on 𝜎2 . – The emaining 3 spikes in neu on 𝜎2 now ac i a e he ule {a22j+3∣ 0≤ j}∕a3 → a7 ; he 7 spikes can only en e neu on 𝜎1 , hus ac i a ing neu on 𝜎1 o simula e he co - esponding egis e machine ins uc ion labeled by 1 o he nex s ep. In sum, we ha e go he compu a ion C( )=⟨14x1, 22x2+9⟩⟹ C( + 1 )=⟨ 14 x1 , 22 (x2+ 1 )+ 3 ⟩⟹ C( +2)=⟨14x1+7, 22(x2+1)⟩ . The whole sys em is cons uc ed in such a way ha i wo ks sequen ially, i.e., only one neu on is ac i a ed; hence, only his one may spike, which also means ha he con- s uc ed sys em no only wo ks wi h using he spike packages seman ics, bu also wi h using he o al spikes seman ics. Simula ion o he HALT ins uc ion A he end, s a ing he simula ion o he HALT ins uc- ion 3:HALT means ha 11 spikes ha e been sen o he en i onmen , bu no inpu il e Ei , i∈{1, 2} , le his numbe o spikes en e he co esponding neu on 𝜎i . Hence, none o he neu ons is ac i a ed; he compu a ion in 𝛱 s ops. Using p ime numbe s as “add esses” o each neu on and he odd numbe s o choosing he co esponding ules allows o co ec simula ions. We use such add essing no only in he inpu il e s associa ed wi h each neu on, bu also in he numbe o spikes eleased by he neu ons. In sum, he WSN P sys em 𝛱 co ec ly simula es he ac ions o he gi en egis e machine M, o bo h seman ics 1 and 2. 6 Compu a ional comple eness o WSN P sys ems In his sec ion, we p o e ha WSN P sys ems a e compu a- ionally comple e by simula ing an a bi a y egis e machine. This also shows ha he powe o add essing neu ons using he inpu il e s o he (packages o ) spikes in WSN P sys ems e en exceeds he powe o an unde lying di ec ed g aph o he communica ion o spikes in SN P sys ems. The p oo no only wo ks wi h using he spike packages seman- ics, bu also wi h using he o al spikes seman ics. Bo h he inpu and he ou pu a e encoded in a linea way. The ollowing esul is e en al eady op imal wi h espec o he numbe o neu ons: Theo em1 The compu a ions o any egis e machine wi h m egis e s can be simula ed by a WSN P sys em wi h m neu ons, wi h he inpu and ou pu being encoded in a linea way, and ei he using he spike packages seman ics o e en he o al spikes seman ics. P oo Conside an a bi a y egis e machine wi h m egis e s wi h |B|=l=|P| . We now cons uc a WSN P sys em 𝛱 o simula e M and i s ins uc ions. Wi hou loss o gene ali y, we assume a o al o de o he ins uc ions as well as o he egis e s o M, i.e., we lis ins uc ions and egis e s as ⟨l0 , l1 , … , lh⟩ and ⟨ eg1,…, egm⟩ . Fo he i s lis o (labels o ) ins uc ions, wi hou loss o gene ali y, we assume ha he lis simply desc ibes he na u al numbe s om 1 o l, wi h l0=1 and lh=l . Now we assign an odd p ime numbe P( egj) , 1 ≤ j ≤ m , o he elemen s o he second lis ⟨ eg1 , … , egm⟩ , in such a way ha P( eg1)<P( eg2)<…<P( egm) , bu , in addi ion, we equi e 4l<2P( eg1) ; he eason o his equi emen will become clea soon below. I a egis e egi con ains he numbe n, hen he co - esponding neu on 𝜎 egi con ains a2P( eg i )n , i.e., 2P( egi)n spikes; hence, he numbe n is encoded by he linea unc- ion 2P( egi)n . In addi ion, o he simula ion o he ADD and SUB ins uc ions on his egis e egi o M, 𝜎 egi may con ain an addi ional odd numbe o spikes, which is less han he numbe ep esen ing he lowes non-ze o alue 2P( egi) . The WSN P sys em 𝛱 now is de ined as wi h he ollowing de in ion o he neu ons 𝜎 eg i , 1≤i≤m : 𝜎 egi=(Ini ial egi,R egi,E egi) . Wi h ni deno ing he ini ial alue in egis e i, we ha e Ini ial egi =a 2P( eg i )ni o i>1 and Ini ial eg 1 =a 2P( eg 1 )n 1+2(l+1)− 1 , wi h he addi ional 2(l+1)−1 addi ional spikes “ac i- a ing" he simula ion o he ini ial ins uc ion labeled by l0=1 . E eg i ={a 2P( eg i ) }∪{a 2(l+p)−1 ∣p∈BADD ( i ) ∪BSUB ( i )} M = ( m,B,l 0 ,l h ,P ) 𝛱= ({a},𝜎 eg 1,…,𝜎 eg m ) Wi eless spiking neu al P sys ems R egi= { {a2jP( eg )+2(l+p)−1∣0≤j}∕a2l→a2P( eg )) ∣p∈BADD( ) } ∪{a2jP( eg )+2p−1∣0≤j}∕a2p−1→a2(l+q(p))−1∣p∈BADD( ) } ∪{a2jP( eg )+2p−1∣0≤j}∕a2p−1→a2(l+s(p))−1∣p∈BADD( ) } ∪{{a2jP( eg )+2(l+p)−1∣1≤j}∕a2(l+p)−1+2P( eg )→a2(l+q(p))−1 ∣p∈BSUB( )} ∪ { a2(l+p)−1→a2(l+s(p))−1∣p∈B SUB( )} Le us deno e he uni ec o ha ing m compo- nen s wi h he i- h componen being 1 and all he o he componen s being 0 by em , i . Mo eo e , he num- be o spikes yi in each neu on i a ime o a com- pu a ion in 𝛱 can be desc ibed by he con igu a ion C( )=⟨y1 , … , yn⟩ . A he beginning, we ha e he con igu- a ion C(0)=⟨2P( eg1)x1+2(l+1)−1, 2P( eg2)x2…, 2P ( egn ) xn⟩ , whe e ⟨x1 , … , xn⟩ desc ibes he ini ial alues in he egis e s o he egis e machine M. The main idea o ou cons uc ion is ha each egis e does i s job i sel when an ADD o SUB ins uc ion on is o be simula ed, ac i a ed by 2(l+p)−1 addi ional spikes, which make he con en s o 𝜎 eg an odd ins ead o an e en numbe o spikes. He e we immedia ely see why we made he condi ion 4l<2P( eg1) , assuming ha P( eg1) is he smalles odd p ime numbe used o he encodings in he neu ons, because o p=l we ha e 2(l+p)−1=4l−1 . In o al, hese addi ional odd “ emain- de s” a e 2l+1, …,4l−1 . When sub ac ing 2l, he esul - ing odd “ emainde s” a e 1, …,2l−1 , so, in o al, we ha e he odd numbe s be ween 1 and 4l−1 . The whole sys em is cons uc ed in such a way ha i wo ks sequen ially, i.e., only one neu on is ac i a ed; hence, only his one may spike, which also means ha he cons uc ed sys em no only wo ks wi h using he spike packages seman ics, bu also wi h using he o al spikes seman ics. Now le us assume ha , a ime , we ha e he con igu a ion C ( )= ⟨ 2 P ( eg1 ) x1 ,…,2 P ( egn ) xn⟩ +(2( l + p )−1 ) em , Reg ( p) , whe e he simula ion o he ins uc ion labeled by p wo k- ing on egis e is ini ia ed by he (2(l+p)−1) addi ional spikes in neu on Reg(p)= . Simula ion o an ADD ins uc ion The simula ion o an ADD ins uc ion akes wo s eps: – In he i s s ep, he egis e i sel is inc emen ed by sending 2P( eg ) spikes o neu on 𝜎 eg using he ule a2l→a2P( eg )) . The 2P( eg ) spikes can only en e neu- on 𝜎 eg . – The emainde o 2p−1 spikes in neu on 𝜎 eg now ac i- a es one o he ules a2p−1→a2(l+q(p))−1 o a2p−1→a2(l+s(p))−1 ; he 2(l+q(p)) − 1 spikes can only en e neu on 𝜎 eg Reg(q(p)) , he 2(l+s(p)) − 1 spikes can only en e neu on 𝜎 eg Reg(s(p)) , hus ac i a ing 𝜎 eg Reg(q(p)) o 𝜎 eg Reg(s(p)) o simula e he co esponding egis e machine ins uc- ions q(p) o s(p), espec i ely. In sum, we ha e go he compu a ion o Simula ion o a SUB ins uc ion The simula ion o a SUB ins uc ion only akes one s ep; he ac ion aken depends on he numbe n encoded in he neu on 𝜎 eg as 2P( eg )n : n>0 : In his case, neu on 𝜎 eg con ains a leas 2P( eg ) spikes in addi ion o he 2(l+p)−1 spikes which ha e ac i a ed he neu on; hence, he ule a2(l+p)−1+2P( eg )→a2(l+q(p))−1 is o be applied. Thus, we ha e go he compu a ion n=0 : In his case, neu on 𝜎 eg con ains exac ly he 2(l+p)−1 spikes which ha e ac i a ed he neu on; hence, he ule a2(l+p)−1→a2(l+s(p))−1 is o be applied. Thus, we ha e go he compu- a ion C( )=⟨2P( eg1)x1,…,2P( egm)xm⟩+ (2(l+p)−1)em, ⟹ C ( +1)= ⟨ 2P( eg 1 )x 1 ,…,2P( eg n )x n⟩+ (2(l+s(p)) − 1)em,Reg(s(p)) . Simula ion o he HALT ins uc ion C ( )=⟨ 2P ( eg1 ) x1, … ,2P ( egm ) xm ⟩+( 2 ( l + p )− 1 ) em, ⟹ C ( +1)=⟨2P( eg1)x1,…,2P( egn)xn⟩ +(2p−1+2P( eg ))em, ⟹ C ( +2)=⟨2P( eg1)x1,…,2P( egn)xn⟩ +2P( eg )e m , +(2(l+q(p)) − 1)e m , Reg(q(p)) C( +2)=⟨2P( eg 1 )x 1 ,…,2P( eg n )x n ⟩ +2P( eg )e m, +(2(l+q(p)) − 1)e m,Reg(s(p)). C( )=⟨2P( eg 1 )x 1 ,…,2P( eg m )x m ⟩ +(2(l+p)−1)em, ⟹ C ( +1)=⟨2P( eg1)x1,…,2P( egn)xn⟩ −2P( eg )e m, +(2(l+q(p)) − 1)e m,Reg(q(p)).