Compu ing wi h Spiking Neu al P Sys ems:
T aces and Small Uni e sal Sys ems
Mihai Ionescu1, And ei P˘aun2,
Gheo ghe P˘aun3,4,andMa ioJ.P´e ez-Jim´enez4
1Resea ch G oup on Ma hema ical Linguis ics
Uni e si a Ro i a i Vi gili
Pl. Impe ial T`a aco 1, 43005 Ta agona, Spain
[email p o ec ed]
2Depa men o Compu e Science, Louisiana Tech Uni e si y
Rus on, PO Box 10348, Louisiana, LA-71272 USA, and
Uni e sidad Poli ´ecnica de Mad id – UPM, Faculdad de In o ma ´ıca
Campus de Mon egancedo s/n, Boadilla del Mon e
28660 Mad id, Spain
[email p o ec ed]
3Ins i u e o Ma hema ics o he Romanian Academy
PO Box 1-764, 014700 Bucha es , Romania
[email p o ec ed]
4Depa men o Compu e Science and AI, Uni e si y o Se illa
A da Reina Me cedes s/n, 41012 Se illa, Spain
[email p o ec ed], [email p o ec ed]
Abs ac . Recen ly, he idea o spiking neu ons and hus o compu ing
by spiking was inco po a ed in o memb ane compu ing, and so-called
spiking neu al P sys ems (abb e ia ed SN P sys ems) we e in oduced.
Ve y sho ly, in hese sys ems neu ons linked by synapses communica e
by exchanging iden ical signals (spikes), wi h he in o ma ion encoded
in he dis ance be ween consecu i e spikes. Se e al ways o using such
de ices o compu ing we e conside ed in a se ies o pape s, wi h uni-
e sali y esul s ob ained in he case o compu ing numbe s, bo h in he
gene a ing and he accep ing mode; gene a ing, accep ing, o p ocessing
s ings o infini e sequences was also p o ed o be o in e es .
In he p esen pape , a e a sho su ey o cen al no ions and e-
sul s ela ed o spiking neu al P sys ems (including he case when SN P
sys ems a e used as s ing gene a o s), we con ibu e o his a ea wi h
wo ( ypes o ) esul s: (i) we p oduce small uni e sal spiking neu al P
sys ems (84 neu ons a e sufficien in he basic defini ion, bu his num-
be is dec eased o 49 neu ons i a sligh gene aliza ion o spiking ules
is adop ed), and (ii) we in es iga e he possibili y o gene a ing a lan-
guage by ollowing he ace o a designa ed spike in i s way h ough he
neu ons.
1 In oduc ion
Spiking neu al P sys ems (in sho , SN P sys ems) we e in oduced in [6], wi h
he mo i a ion coming om wo di ec ions: he a emp o memb ane compu ing
o pass om cell-like a chi ec u es o issue-like o neu al-like a chi ec u es (see
[15], [12]), and he in iguing possibili y o encoding in o ma ion in he du a ion
o e en s, o in he in e al o ime elapsed be ween e en s, as i idly in es iga ed
in ecen esea ch in neu al compu ing (o “ hi d gene a ion”) [8], [9].
This double challenge led o a class o P sys ems based on he ollowing simple
ideas: le us use only one objec , he symbol deno ing a spike, and one-memb ane
cells (called neu ons) which can hold any numbe o spikes; each neu on fi es in
specified condi ions (a e collec ing a specified numbe o spikes) and hen sends
one spike along i s axon; his spike passes o all neu ons connec ed by a synapse
o he spiking neu on (hence i is eplica ed in o as many copies as many a ge
neu ons exis ); be ween he momen when a neu on fi es and he momen when
i spikes, each neu on needs a ime in e al, and his ime in e al is he essen ial
ing edien o he sys em unc ioning ( he basic in o ma ion ca ie – wi h he
men ioning ha also he numbe o spikes accumula ed in each momen in he
neu ons p o ides an impo an in o ma ion o con olling he unc ioning o
he sys em); one o he neu ons is conside ed he ou pu one, and i s spikes
p o ide he ou pu o he compu a ion. The sequence o ime momen s when
spikes a e sen ou o he sys em is called a spike ain. The ules o spiking
ake in o accoun all spikes p esen in a neu on no only pa o hem, bu no
all spikes p esen in a neu on a e consumed in his way; a e ge ing fi ed and
be o e sending he spike o i s synapses, he neu on is idle (biology calls his
he e ac o y pe iod) and canno ecei e spikes. The e a e also ules used o
“ o ge ing” some spikes, ules which jus emo e a specified numbe o spikes
om a neu on.
In he spi i o spiking neu ons, as he esul o a compu a ion (no necessa ily
a hal ing one) in [6] one conside s he numbe o s eps elapsed be ween he fi s
wo spikes o he ou pu neu on. E en in his es ic i e amewo k, SN P sys-
ems u ned ou o be Tu ing comple e, able o compu e all Tu ing compu able se s
o na u al numbe s. This holds bo h in he gene a i e mode (as ske ched abo e,
a numbe is compu ed i i ep esen s he in e al be ween he wo consecu i e
spikes o he ou pu neu on) and in he accep ing mode (a numbe is in oduced
in he sys em in he o m o he in e al o ime be ween he fi s wo spikes en e -
ing a designa ed neu on, and his numbe is accep ed i he compu a ion hal s).
I a bound is imposed on he numbe o spikes p esen in any neu on du ing a
compu a ion, hen a cha ac e iza ion o semilinea se s o numbe s is ob ained.
These esul s we e ex ended in [13] o se e al o he ways o associa ing a se o
numbe s wi h an SN P sys em: aking in o accoun he in e al be ween he fi s
kspikes o each spike ain, o all spikes, aking only al e na ely he in e als,
o all o hem, conside ing hal ing compu a ions. Then, he spike ain i sel
( he sequences o symbols 0, 1 desc ibing he ac i i y o he ou pu neu on: we
w i e 0 i no spike exi s he sys em in a ime uni and 1 i a spike is emi ed) was
conside ed as he esul o a compu a ion; he infini e case is in es iga ed in [14],
he fini e one in [2]. A se ies o possibili ies o handling infini e sequences o bi s
a e discussed in [14], while mo phic ep esen a ions o egula and o ecu si ely
enume able languages a e ound in [2]. The esul s om [2] a e b iefly ecalled
in Sec ion 5 below.
In his pape we di ec ly con inue hese in es iga ions, con ibu ing in wo
na u al di ec ions. Fi s , he abo e men ioned uni e sali y esul s ( he possibili y
o compu e all Tu ing compu able se s o numbe s) do no gi e an es ima ion on
he numbe o neu ons sufficien o ob aining he uni e sali y. Which is he size
o he smalles uni e sal “b ain” (o he o m o an SN P sys em)? This is bo h
a na u al and impo an ( om compu e science and, also, om neu o-science
poin o iew) p oblem, eminding he ex ensi e effo s paid o finding small
uni e sal Tu ing machines – see, e.g., [16] and he e e ences he ein.
Ou answe is a he su p ising/encou aging: 84 neu ons ensu e he uni e -
sali y in he basic se up o SN P sys ems, as hey we e defined in [6], while his
numbe is dec eased o 49 i sligh ly mo e gene al spiking ules a e used ( ules
wi h he possibili y o p oduce no only one spike, bu also wo o mo e spikes
a he same ime – such ules a e called ex ended).Thep oo isbasedonsimu-
la ing a small uni e sal egis e machine om [7]. (The ull de ails o he p oo
o hese esul s abou small uni e sal SN P sys ems will be p o ided elsewhe e
– see [11].)
Ex ended ules a e also use ul when gene a ing s ings: we associa e a symbol
biwi h a s ep when he sys em ou pu s ispikes and in his way we ob ain a
s ing o e an a bi a y alphabe , no only on he bina y one, as in he case
o s anda d ules. Especially flexible is he case when we associa e he emp y
s ing wi h a s ep when no spike is sen ou o he sys em we associa e ( ha is,
b0is in e p e ed as λ). Resul s om [3], conce ning he powe o ex ended SN P
sys ems as language gene a o s, a e also ecalled in Sec ion 5.
Then, ano he na u al issue is o b ing o he SN P sys ems a ea a no ion
in oduced o sympo /an ipo P sys ems in [5]: ma k a spike and ollow i s
pa h h ough he sys em, eco ding he labels o he isi ed neu ons un il ei he
he ma king disappea s o he compu a ion hal s. Because o he e y es ic i e
way o gene a ing s ings in his way, he e a e simple languages which canno
be compu ed, bu , on he o he hand, he e a e a he complex languages which
can be ob ained in his amewo k.
Due o space es ic ions, we do no gi e ull o mal de ails in defini ions and
p oo s (we e e o he abo e men ioned pape s o ha ); such de ails a e o will
be a ailable in sepa a e pape s o be ci cula ed/announced h ough [19].
2 Fo mal Language Theo y P e equisi es
We assume he eade o be amilia wi h basic language and au oma a heo y,
e.g., om [17] and [18], so ha we in oduce he e only some no a ions and no ions
used la e in he pape .
Fo an alphabe V,V∗deno es he se o all fini e s ings o symbols om
V; he emp y s ing is deno ed by λ, and he se o all nonemp y s ings o e V
is deno ed by V+.WhenV={a}is a single on, hen we w i e simply a∗and
a+ins ead o {a}∗,{a}+.I x=a1a2...a
n,a
i∈V, 1≤i≤n, hen he mi o
image o xis mi(x)=an...a
2a1.
A mo phism h:V∗
1−→ V∗
1such ha h(a)∈{a, λ} o each a∈V1is called
a p ojec ion, and a mo phism h:V∗
1−→ V∗
2such ha h(a)∈V2∪{λ} o each
a∈V1is called a weak coding.
I L1,L
2⊆V∗a e wo languages, he le and igh quo ien s o L1wi h
espec o L2a e defined by L2 L1={w∈V∗|xw ∈L1 o some x∈L2},
and espec i ely L1/L2={w∈V∗|wx ∈L1 o some x∈L2}. When he
language L2is a single on, hese ope a ions a e called le and igh de i a i es,
and deno ed by ∂l
x(L)={x} Land ∂
x(L)=L/{x}, espec i ely.
A Chomsky g amma is gi en in he o m G=(N,T,S,P), whe e Nis he
non e minal alphabe , Tis he e minal alphabe , S∈Nis he axiom, and
Pis he fini e se o ules. Fo egula g amma s, he ules a e o he o m
A→aB, A →a, o someA, B ∈N,a ∈T.
We deno e by FIN, REG, CF, CS, RE he amilies o fini e, egula , con ex -
ee, con ex -sensi i e, and ecu si ely enume able languages; by MAT we de-
no e he amily o languages gene a ed by ma ix g amma s wi hou appea ance
checking. The amily o Tu ing compu able se s o numbe s is deno ed by NRE
( hese se s a e leng h se s o RE languages, hence he no a ion).
Le V={b1,b
2,...,b
m}, o somem≥1. Fo a s ing x∈V∗, le us deno e
by alm(x) he alueinbasem+1o x(we use base m+ 1 in o de o conside
he symbols b1,...,b
mas digi s 1,2,...,m, hus a oiding he digi 0 in he le
hand o he s ing). We ex end his no a ion in he na u al way o se s o s ings.
All uni e sali y esul s o he pape a e based on he no ion o a egis e
machine. Such a de ice – in he non-de e minis ic e sion – is a cons uc M=
(m, H, l0,l
h,I), whe e mis he numbe o egis e s, His he se o ins uc ion
labels, l0is he s a label (labeling an ADD ins uc ion), lhis he hal label
(assigned o ins uc ion HALT), and Iis he se o ins uc ions; each label om H
labels only one ins uc ion om I, hus p ecisely iden i ying i . The ins uc ions
a e o he ollowing o ms:
–li:(ADD( ),l
j,l
k) (add 1 o egis e and hen go o one o he ins uc ions
wi h labels lj,l
knon-de e minis ically chosen),
–li:(SUB( ),l
j,l
k)(i egis e is non-emp y, hen sub ac 1 om i and go
o he ins uc ion wi h label lj, o he wise go o he ins uc ion wi h label
lk),
–lh:HALT ( he hal ins uc ion).
A egis e machine Mgene a es a se N(M) o numbe s in he ollowing way:
we s a wi h all egis e s emp y (i.e., s o ing he numbe ze o), we apply he
ins uc ion wi h label l0and we con inue o apply ins uc ions as indica ed by
he labels (and made possible by he con en s o egis e s); i we each he hal
ins uc ion, hen he numbe np esen in egis e 1 a ha ime is said o be
gene a ed by M. (Wi hou loss o gene ali y we may assume ha in he hal ing
configu a ion all o he egis e s a e emp y; also, we may assume ha egis e 1
is ne e subjec o SUB ins uc ions, bu only o ADD ins uc ions.) I is known
(see, e.g., [10]) ha egis e machines gene a e all se s o numbe s which a e
Tu ing compu able.
A egis e machine can also be used as a numbe accep ing de ice: we in-
oduce a numbe nin some egis e 0, we s a wo king wi h he ins uc ion
wi h label l0, and i he machine e en ually hal s, hen nis accep ed (we may
also assume ha all egis e s a e emp y in he hal ing configu a ion). Again,
accep ing egis e machines cha ac e ize NRE.
Fu he mo e, egis e machines can compu e all Tu ing compu able unc ions:
we in oduce he numbe s n1,...,n
kin some specified egis e s 1,...,
k,we
s a wi h he ins uc ion wi h label l0, and when we s op (wi h he ins uc ion
wi h label lh) he alue o he unc ion is placed in ano he specified egis e ,
, wi h all egis e s diffe en om being emp y. Wi hou loss o gene ali y we
may assume ha 1,...,
ka e he fi s k egis e s o M, and hen he esul o
he compu a ion is deno ed by M(n1,...,n
k).
In bo h he accep ing and he compu ing case, he egis e machines can be
de e minis ic, i.e., wi h he ADD ins uc ions o he o m li:(ADD( ),l
j)(add1
o egis e and hen go o he ins uc ion wi h label lj).
In he ollowing sec ions, when compa ing he powe o wo language gene -
a ing/accep ing de ices he emp y s ing λis igno ed.
3 Spiking Neu al P Sys ems
We gi e he e he basic defini ion we wo k wi h, in oducing SN P sys ems in he
o m conside ed in he small uni e sal SN P sys ems, hence compu ing unc ions
(which, ac ually, co e s bo h he gene a i e and accep ing cases).
A compu ing spiking neu al memb ane sys em (abb e ia ed SN P sys em), o
deg ee m≥1, is a cons uc o he o m
Π=(O,σ1,...,σ
m,syn,in,ou ),
whe e:
1. O={a}is he single on alphabe (ais called spike);
2. σ1,...,σ
ma e neu ons,o he o m
σi=(ni,R
i),1≤i≤m,
whe e:
a) ni≥0is heini ial numbe o spikes con ained in σi;
b) Riis a fini e se o ules o he ollowing wo o ms:
(1) E/ac→a;d,whe eEis a egula exp ession1o e a,c≥1, and
d≥0;
(2) as→λ, o s≥1, wi h he es ic ion ha o each ule E/ac→a;d
o ype (1) om Ri,weha eas/∈L(E);
3. syn ⊆{1,2,...,m}×{1,2,...,m}wi h (i, i)/∈syn o 1 ≤i≤m(synapses
be ween neu ons);
4. in, ou ∈{1,2,...,m}indica e he inpu and he ou pu neu ons o Π.
1The egula language defined by Eis deno ed by L(E).

The ules o ype (1) a e i ing (we also say spiking) ules, and hey a e applied
as ollows. I he neu on σicon ains kspikes, and ak∈L(E),k ≥c, hen he
ule E/ac→a;d∈Rican be applied. This means consuming ( emo ing) c
spikes ( hus only k−c emain in σi), he neu on is fi ed, and i p oduces a spike
a e d ime uni s (as usual in memb ane compu ing, a global clock is assumed,
ma king he ime o he whole sys em, hence he unc ioning o he sys em is
synch onized). I d= 0, hen he spike is emi ed immedia ely, i d= 1, hen he
spike is emi ed in he nex s ep, e c. I he ule is used in s ep and d≥1, hen
in s eps , +1, +2,..., +d−1 he neu on is closed ( his co esponds o he
e ac o y pe iod om neu obiology), so ha i canno ecei e new spikes (i a
neu on has a synapse o a closed neu on and ies o send a spike along i , hen
ha pa icula spike is los ). In he s ep +d, he neu on spikes and becomes
again open, so ha i can ecei e spikes (which can be used s a ing wi h he
s ep +d+1).
The ules o ype (2) a e o ge ing ules; hey a e applied as ollows: i he
neu on σicon ains exac ly sspikes, hen he ule as→λ om Rican be used,
meaning ha all sspikes a e emo ed om σi.
I a ule E/ac→a;do ype (1) has E=ac, hen we will w i e i in he
ollowing simplified o m: ac→a;d. I all spiking ules a e o his o m, hen
he sys em is said o be ini e (i can handle only a bounded numbe o spikes
in each o i s neu ons).
In each ime uni , i a neu on σican use one o i s ules, hen a ule om Ri
mus be used. Since wo fi ing ules, E1/ac1→a;d1and E2/ac2→a;d2,can
ha e L(E1)∩L(E2)=∅, i is possible ha wo o mo e ules can be applied in a
neu on, and in ha case, only one o hem is chosen non-de e minis ically. No e
howe e ha , by defini ion, i a fi ing ule is applicable, hen no o ge ing ule
is applicable, and ice e sa.
Thus, he ules a e used in he sequen ial manne in each neu on, bu neu ons
unc ion in pa allel wi h each o he ( he sys em is synch onized).
The ini ial configu a ion o he sys em is desc ibed by he numbe s n1,n
2,...,
nm, o spikes p esen in each neu on, wi h all neu ons being open. Du ing he
compu a ion, a configu a ion is desc ibed by bo h he numbe o spikes p esen
in each neu on and by he s a e o he neu on, mo e p ecisely, by he numbe o
s eps o coun down un il i becomes open ( his numbe is ze o i he neu on is
al eady open).
A compu a ion in a sys em as abo e s a s in he ini ial configu a ion. In
o de o compu e a unc ion :Nk−→ N, we in oduce kna u al numbe s
n1,...,n
kin he sys em by “ eading” om he en i onmen a bina y sequence
z=0
b10n1−110n2−11...10nk−110 , o someb, ≥0; his means ha he inpu
neu on o Π ecei es a spike in each s ep co esponding o a digi 1 om he
s ing z. No e ha we inpu exac ly k+ 1 spikes. The esul o he compu a ion
is also encoded in he dis ance be ween wo spikes: we impose o he sys em o
ou pu exac ly wo spikes and hal (some imes a e he second spike), hence
p oducing a ain spike o he o m 0b10 −110 , o someb, ≥0andwi h
= (n1,...,n
k).
I we use an SN P sys em in he gene a i e mode, hen no inpu neu on is
conside ed, hence no inpu is aken om he en i onmen ; we s a om he
ini ial configu a ion and he dis ance be ween he fi s wo spikes o he ou pu
neu on (o o he numbe s, see he discussion in he In oduc ion) is he esul o
he compu a ion. Dually, we can igno e he ou pu neu on, we inpu a numbe
in he sys em as he dis ance be ween wo spikes en e ing he inpu neu on, and
i he compu a ion hal s, hen he numbe is accep ed.
We do no gi e he e examples, because in he nex sec ion we show he ou
basic modules o ou small uni e sal SN P sys em.
4 Two Small Uni e sal SN P Sys ems
In bo h he gene a ing and he accep ing case, SN P sys ems a e uni e sal,
hey compu e he Tu ing compu able se s o numbe s. The p oo s om [6], [13]
a e based on simula ing egis e machines, which a e known o be equi alen
o Tu ing machines when compu ing (gene a ing o accep ing) se s o numbe s,
[10]. In [7], he egis e machines a e used o compu ing unc ions, wi h he
uni e sali y defined as ollows. Le (ϕ0,ϕ
1,...) be a fixed admissible enume a ion
o he se o una y pa ial ecu si e unc ions. A egis e machine Muis said o
be uni e sal i he e is a ecu si e unc ion gsuch ha o all na u al numbe s
x, y we ha e ϕx(y)=Mu(g(x),y). In [7], he inpu is in oduced in egis e s 1
and 2, and he esul is ob ained in egis e 0 o he machine.
l0:(SUB(1),l
1,l
2),l
1:(ADD(7),l
0),
l2:(ADD(6),l
3),l
3:(SUB(5),l
2,l
4),
l4:(SUB(6),l
5,l
3),l
5:(ADD(5),l
6),
l6:(SUB(7),l
7,l
8),l
7:(ADD(1),l
4),
l8:(SUB(6),l
9,l
0),l
9:(ADD(6),l
10),
l10 :(SUB(4),l
0,l
11),l
11 :(SUB(5),l
12,l
13),
l12 :(SUB(5),l
14,l
15),l
13 :(SUB(2),l
18,l
19),
l14 :(SUB(5),l
16,l
17),l
15 :(SUB(3),l
18,l
20),
l16 :(ADD(4),l
11),l
17 :(ADD(2),l
21),
l18 :(SUB(4),l
0,l
h),l
19 :(SUB(0),l
0,l
18),
l20 :(ADD(0),l
0),l
21 :(ADD(3),l
18),
lh:HALT.
Fig. 1. The uni e sal egis e machine om [7]
The cons uc ions om [6] do no p o ide a bound on he numbe o neu ons,
bu such a bound can be ound i we s a om a specific uni e sal egis e
machine. We will use he e he one wi h 8 egis e s and 23 ins uc ions om [7] –
o he eade con enience, his machine is ecalled in Figu e 1, in he no a ion
and he se up in oduced in he p e ious sec ion.
Theo em 1. The e is a uni e sal SN P sys em wi h 84 neu ons.
P oo . (Ou line) We ollow he way used in [6] o simula e a egis e machine by
an SN P sys em. This is done as ollows: neu ons a e associa ed wi h each egis e
( )andwi heachlabel(li) o he machine; i a egis e con ains a numbe n,
hen he associa ed neu on will con ain 2nspikes; modules as in Figu es 2 and 3
a e associa ed wi h he ADD and he SUB ins uc ions (each o hese modules
con ains wo neu ons – wi h p imed labels – which do no co espond o egis e s
and labels o he simula ed machine).
#
"
!#
"
!

 


#
"
!



SSS
Sw



HHHHH
Hj







ZZZ
Z~
li
a2→a;0
a→λ
l
il
i
a→a;0 a→a;0
lj
a2→a;0
a→λ
Fig. 2. Module ADD (simula ing li:(ADD( ),l
j))
The wo k o he sys em is igge ed by in oducing wo spikes in he neu on
σl0(associa ed wi h he s a ing ins uc ion o he egis e machine). In gene al,
he simula ion o an ADD o SUB ins uc ion s a s by in oducing wo spikes
in he neu on wi h he ins uc ion label. We do no desc ibe he e in de ail he
(p e y anspa en ) way he modules om Figu es 2 and 3 wo k – he eade
can consul [6] in his espec .
S a ing wi h neu ons σ1and σ2al eady loaded wi h 2g(x)and2yspikes,
espec i ely, and in oducing wo spikes in neu on σl0, we can compu e in ou
sys em in he same way as Mu; i he compu a ion hal s, hen neu on σ0will
con ain 2ϕx(y) spikes. Wha emains o do is o cons uc inpu and ou pu
modules, o eading a sequence o bi s and in oducing he igh numbe o
spikes in he neu ons co esponding o egis e s 1 and 2, and, in he end o he
compu a ion, o ou pu he con en s o egis e 0. Modules o hese ypes a e
gi en in Figu es 4, 5, ha ing se en and wo addi ional neu ons, espec i ely.
A e his di ec cons uc ion, we ge a sys em wi h 91 neu ons (9 o he
egis e s o he s a ing egis e machine – one u he egis e is necessa y o
echnical easons, 25 o i s labels, 24 ×2 o he ADD and SUB ins uc ions, 7
in he inpu module, and 2 in he ou pu module). Howe e , some “code op i-
miza ion” is possible, based on ce ain p ope ies o he egis e machine om
&
$
%






&
&
& %




/
AAAAAA
AU
QQQQ
Qs
?



/
HHHHH
Hj
JJ
J^
lia2→a;0
a→λ
(a2)+a/a3→a;0
a→a;1
l
i
l
i
a→a;0
a→a;1
lj
a2→a;0
a→λ
a2→a;0
a→λ
lk
Fig. 3. Module SUB (simula ing li:(SUB( ),l
j,l
k))
[7] ( o ins ance, consecu i e ADD ins uc ions can be simula ed by a specific
module, smalle han wo sepa a e ADD modules); we skip he echnical de ails
and we only men ion ha he final SN P sys em will con ain 84 neu ons.
This is a small numbe (a small “b ain”, compa ed o he human one; i would be
nice o know whe e in he e olu ion scale he e a e animals wi h abou 84 neu ons
in hei b ain), bu we do no know whe he i is op imal o no . Anyway, we
belie e ha in he p e ious se up, we canno significan ly dec ease he numbe
o neu ons om a uni e sal SN P sys em.
Howe e , we can do be e s a ing om he ollowing obse a ion. In many
modules men ioned abo e we need pai s o in e media e neu ons o duplica ing
he spike o be ansmi ed u he ( his is he case o neu ons σl
i,σ
l
iin Figu e
2), and his sugges s o conside a sligh ex ension o he ules o SN P sys ems:
o allow spiking ules o he o m E/ac→ap;d, whe e all componen s a e as
usual, and p≥1. The meaning is ha cspikes a e consumed and pspikes a e
p oduced. To be “ ealis ic”, we impose he es ic ion c≥p( he numbe o
p oduced spikes is no la ge han he numbe o consumed spikes).
Theo em 2. The e is a uni e sal SN P sys em wi h 49 neu ons, using ules o
he o m E/ac→ap;0,wi hp≥1.
(No e ha he delay is ze o in he ules o he ex ended o m used in he he-
o em.) As abo e, we do no know whe he his esul is op imal, bu we again
belie e ha i canno be significan ly imp o ed (wi hou , maybe, changing he
defini ion o SN P sys ems in an essen ial way).
2. H. Chen, R. F eund, M. Ionescu, Gh. P˘aun, M.J. P´e ez-Jim´enez: On s ing lan-
guages gene a ed by spiking neu al P sys ems. In P oc. o Fou h. B ains o ming
Week on Memb ane Compu ing, Se illa, 2006, ol. I, 169–193 (also a ailable a
[19]).
3. H. Chen, T.-O. Ishdo j, Gh. P˘aun, M.J. P´e ez-Jim´enez: Spiking neu al P sys ems
wi h ex ended ules. In P oc. o Fou h. B ains o ming Week on Memb ane Com-
pu ing, Se illa, 2006, ol. I, 241–266 (also a ailable a [19]).
4. O.H. Iba a, A. P˘aun, Gh. P˘aun, A. Rod ´ıguez-Pa ´on, P. Sosik, S. Woodwo h:
No mal o ms o spiking neu al P sys ems. In Fou h B ains o ming Week on
Memb ane Compu ing, Feb . 2006, Fenix Edi o a, Se illa, 2006, ol. II, 105–136
(also a ailable a [19]).
5. M. Ionescu, C. Ma in-Vide, A. P˘aun, Gh. P˘aun: Memb ane sys ems wi h sym-
po /an ipo : (unexpec ed) uni e sali y esul s. In P oc. 8 h In e na ional Mee ing
o DNA Based Compu ing (M. Hagiya, A. Ohuchi, eds.), Japan, 2002, 151–160.
6. M. Ionescu, Gh. P˘aun, T. Yokomo i: Spiking neu al P sys ems. Fundamen a In-
o ma icae, 71, 2-3 (2006), 279–308.
7. I. Ko ec: Small uni e sal egis e machines. Theo e ical Compu e Science, 168
(1996), 267–301.
8. W. Maass: Compu ing wi h spikes. Special Issue on Founda ions o In o ma ion
P ocessing o TELEMATIK, 8, 1 (2002), 32–36.
9. W. Maass, C. Bishop, eds.: Pulsed Neu al Ne wo ks, MIT P ess, Camb idge, 1999.
10. M. Minsky: Compu a ion – Fini e and In ini e Machines. P en ice Hall, Englewood
Cliffs, NJ, 1967.
11. A. P˘aun, Gh. P˘aun: Small uni e sal spiking neu al P sys ems. BioSys ems, o
appea .
12. Gh. P˘aun: Memb ane Compu ing – An In oduc ion. Sp inge -Ve lag, Be lin, 2002.
13. Gh. P˘aun, M.J. P´e ez-Jim´enez, G. Rozenbe g: Spike ains in spiking neu al P
sys ems. In e n. J. Found. Compu e Sci., o appea (also a ailable a [19]).
14. Gh. P˘aun, M.J. P´e ez-Jim´enez, G. Rozenbe g: Infini e spike ains in spiking neu al
P sys ems. Submi ed, 2006.
15. Gh. P˘aun, Y. Sakakiba a, T. Yokomo i: P sys ems on g aphs o es ic ed o ms.
Publica iones Ma hema icae Deb ecen, 60 (2002), 635–660.
16. Y. Rogozhin: Small uni e sal Tu ing machines. Theo e ical Compu e Science, 168
(1996), 215–240.
17. G. Rozenbe g, A. Salomaa, eds.: Handbook o Fo mal Languages,3 olumes.
Sp inge -Ve lag, Be lin, 1997.
18. A. Salomaa: Fo mal Languages. Academic P ess, New Yo k, 1973.
19. The P Sys ems Web Page: h p://psys ems.disco.unimib.i .