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)).