Simula ing he F edkin Ga e
wi h Ene gy–Based P Sys ems
Albe o LEPORATI, Claudio ZANDRON, Gianca lo MAURI
Dipa imen o di In o ma ica, Sis emis ica e Comunicazione
Uni e si `a degli S udi di Milano – Bicocca
Via Bicocca degli A cimboldi 8, 20126 Milano, I aly
E-mail: lepo a i/zand on/[email p o ec ed]
Abs ac . Re e sibili y plays a undamen al ole when he possibili y o pe -
o m compu a ions wi h minimal ene gy dissipa ion is conside ed. Many pa-
pe s on e e sible compu a ion ha e appea ed in li e a u e: he mos amous
a e ce ainly he wo k o Benne on (uni e sal) e e sible Tu ing machines and
he wo k o F edkin and To oli on conse a i e logic. The la e is based upon
he F edkin ga e, a e e sible and “conse a i e” (acco ding o a de ini ion
gi en by F edkin and To oli) h ee–inpu / h ee–ou pu boolean ga e.
In his pape we in oduce ene gy–based P sys ems as a pa allel and dis ibu ed
model o compu a ion in which he amoun o ene gy manipula ed and/o
consumed du ing compu a ions is aken in o accoun . Mo eo e , we show
how ene gy–based P sys ems can be used o simula e he F edkin ga e. The
p oposed P sys ems ha pe o m he simula ion u n ou o be hemsel es
e e sible and conse a i e.
1 In oduc ion
Conside a ions o he modynamics o compu ing s a ed in he ea ly i ies o he wen ie h
cen u y, when he possibili y o pe o m compu a ions wi h minimal ene gy dissipa ion
was i s conside ed. As a esul some bounds on he amoun o dissipa ed ene gy du ing
ansmission and compu a ion we e es ablished [18, 4, 2, 19], and some quan um heo e ic
models o compu a ion we e p oposed [3, 8]. As shown in [18], e asing a bi necessa ily
dissipa es kT ln 2 Joule in a compu e ope a ing a empe a u e T, and gene a es a co e-
sponding amoun o en opy. He e kis Bol zmann’s cons an and T he absolu e empe -
a u e in deg ees Kel in, so ha kT ≈3×10−21 Joule a oom empe a u e. Howe e , in
[18] Landaue also demons a ed ha only logically i e e sible ope a ions necessa ily dis-
sipa e ene gy when pe o med by a physical compu e . (An ope a ion is logically e e sible
i i s inpu s can always be deduced om i s ou pu s.) This esul ga e subs ance o he
idea ha logically e e sible compu a ions could be pe o med wi h ze o in e nal ene gy
dissipa ion. Indeed, since he appea ance o [18] many au ho s ha e concen a ed hei
a en ion on e e sible compu a ions. The impo ance o e e sibili y has g own u he
wi h he de elopmen o quan um compu ing, whe e he dynamical beha io o quan um
292
sys ems is usually desc ibed by means o uni a y ope a o s, which a e inhe en ly logically
e e sible. Le us no e, howe e , ha compu ing in a logically e e sible way says no hing
abou whe he o no he compu a ion dissipa es ene gy: i me ely means ha he laws
o physics do no equi e ha such a dissipa ion occu s.
Many pape s on e e sible compu a ion ha e appea ed in li e a u e; he mos amous
a e ce ainly he wo k o Benne on (uni e sal) e e sible Tu ing machines [4], and he
wo k o F edkin and To oli on conse a i e logic [11]. In pa icula , conse a i e logic has
been in oduced as a ma hema ical model ha allows one o desc ibe compu a ions which
e lec some p ope ies o mic odynamical laws o physics, such as e e sibili y and conse -
a ion o he in e nal ene gy o he physical sys em used o pe o m he compu a ions. In
his model, compu a ions a e pe o med by e e sible ci cui s composed by F edkin ga es.
In his pape we in oduce ene gy–based P sys ems as a pa allel and dis ibu ed model
o compu a ion in which he amoun o ene gy manipula ed and/o consumed du ing
compu a ions is aken in o accoun . In he mos gene al e sion, a gi en amoun o ene gy
is associa ed o each objec , memb ane and ule o he sys em. Some ene gy uni s a e
p o ided om he ex e nal en i onmen and a e used o build, ans o m o mo e objec s.
When an objec is ans o med in o ano he objec as he e ec o he applica ion o a
ule, he equi ed ( esp., exceeding) ene gy is aken om ( esp., eleased o) he egion
whe e he ule is applied. The applica ion o each ule consumes a gi en amoun o ene gy.
Memb anes can be hough o as ene gy ese oi s which a e able o accumula e a (possibly
bounded) amoun o ene gy and subsequen ly elease pa o i . A special case o ene gy–
based P sys ems a e conse a i e P sys ems, whe e he amoun o ene gy en e ing he
sys em wi h he inpu alues is comple ely e u ned wi h he ou pu alues a he end o
he compu a ion.
We show how he F edkin ga e can be simula ed wi h ene gy–based P sys ems. The
p oposed P sys ems ha pe o m he simula ion u n ou o be hemsel es e e sible and
conse a i e. The simula ion o e e sible F edkin ci cui s is cu en ly unde examina ion
and is p oposed he e as a di ec ion o u u e wo k.
This is by no means he i s ime ha ene gy is conside ed when dealing wi h P
sys ems. We ecall in pa icula [1, 12, 29, 13, 14, 15]. The las wo pape s we e inspi ed
by [16]. Mo eo e , his is no e en he i s pape which deals wi h he simula ion o
boolean ga es and ci cui s by biologically inspi ed models o compu a ion: o ins ance, in
[23] a model o simula ing boolean ci cui s (composed by and,o and no ga es) wi h
DNA algo i hms is p oposed, in [10] he same goal is eached using ini e splicing, and in
[9] some P sys ems ha simula e boolean ci cui s a e p esen ed. In [32], he ideas ound
in [9] a e applied o issue P sys ems. Finally we also men ion [17], whe e a biomolecula
implan a ion o logically e e sible compu a ion using sho s ands o DNA as inpu and
ou pu lines o a F edkin ga e is demons a ed, and a me hod o connec F edkin ga es in
o de o c ea e mo e complica ed gene ic ne wo ks is desc ibed.
The pape is o ganized as ollows. In sec ion 2 we ecall some basic no ions on conse a-
i e logic and he F edkin ga e. In sec ion 3 we in oduce he basic e sion o ene gy–based
P sys ems, whe e ene gy is only associa ed o symbol objec s wi h he equi emen ha
o each ule he amoun o ene gy occu ing on he le side is he same as he amoun o
ene gy occu ing on he igh side. Conse a i e ene gy–based P sys ems a e also in o-
duced. In sec ion 4 we show how he F edkin ga e can be simula ed using his kind o P
sys ems. In sec ion 5 we p opose some ex ensions o ou model oge he wi h some open
p oblems. Sec ion 6 concludes he pape wi h u he di ec ions o u u e esea ch.
293
2 Conse a i e Logic and he F edkin Ga e
Conse a i e logic is a ma hema ical model o compu a ion based upon he so called
F edkin ga e, a h ee–inpu / h ee–ou pu boolean ga e o iginally in oduced by Pe i in
[31] whose inpu /ou pu map g :{0,1}3→ {0,1}3associa es any inpu iple (x1, x2, x3)
wi h i s co esponding ou pu iple (y1, y2, y3) as ollows:
y1=x1
y2= (¬x1∧x2)∨(x1∧x3)
y3= (x1∧x2)∨(¬x1∧x3)
(1)
Table 1 shows he u h able o he F edkin ga e. A use ul poin o iew is ha he F edkin
x1x2x37→ y1y2y3
0 0 0 0 0 0
0 0 1 0 0 1
0 1 0 0 1 0
0 1 1 0 1 1
1 0 0 1 0 0
1 0 1 1 1 0
1 1 0 1 0 1
1 1 1 1 1 1
Table 1: T u h able o he F edkin ga e
ga e beha es as a condi ional swi ch (see Figu e 1): ha is, FG(1, x2, x3) = (1, x3, x2) and
FG(0, x2, x3) = (0, x2, x3) o e e y x2, x3∈ {0,1}. In o he wo ds, x1can be conside ed
as a con ol inpu whose alue de e mines whe he he inpu alues x2and x3ha e o be
exchanged o no .
1
a
b
1
EXC b
a
0
a
b
0
Id a
b
Figu e 1: The F edkin ga e as a condi ional swi ch
The F edkin ga e is unc ionally comple e o Boolean logic: in ac , by ixing x3= 0
we ge y3=x1∧x2, whe eas by ixing x2= 1 and x3= 0 we ge y2=¬x1.
The F edkin ga e is also e e sible, ha is, i compu es a bijec i e map on {0,1}3. As
we can see in Table 1, o e e y inpu /ou pu pai he numbe o 1’s in he inpu iple is
he same as he numbe o 1’s in he ou pu iple. In o he wo ds, he ou pu iple is
ob ained by applying an app op ia e pe mu a ion o he inpu iple. Le us no e ha he
applied pe mu a ion is inpu –dependen : namely, i x1= 1 hen he applied pe mu a ion
is (2 3), whe eas i x1= 0 hen he applied pe mu a ion is he iden i y. Indeed, g
seems o be he mos elemen a y inpu –dependen pe mu a ion which can be concei ed.
In [11] F edkin and To oli in e p e he conse a ion o he numbe o 1’s be ween inpu
294
and ou pu iples as he conse a ion o he amoun o ene gy associa ed o he inpu
iple, hus assuming ha wo di e en iples ha ing he same numbe o 0’s and 1’s
equi e he same amoun o ene gy o be ealized in a physical sys em. Le us no e ha
conse a i eness is de ined (bo h he e and in [11]) as a ma hema ical no ion; namely, i is
no equi ed ha he en i e ene gy used o pe o m he compu a ion is p ese ed, o ha
he compu ing de ice be a conse a i e physical sys em (an ideal bu un ealis ic si ua ion).
In pa icula , we do no conside he ene gy needed o ac ually pe o m he compu a ion,
ha is, o ans o m he inpu alues in o ou pu alues.
Basing upon hese obse a ions, F edkin and To oli in oduce a compu a ional model
o e e sible and conse a i e compu a ions. Compu a ions a e pe o med by e e sible
F edkin ci cui s ha ing he same numbe no inpu and ou pu lines. Unde his con-
s ain , he conse a i eness equi emen (p ese a ion o he numbe o 1’s) is again
equi alen o he equi emen ha he ou pu n- uple is ob ained by applying an app o-
p ia e (inpu –dependen ) pe mu a ion o he inpu n- uple. He e we jus men ion he ac
ha e e y pe mu a ion can be w i en in a unique way (up o he o de o ac o s) as a
composi ion o ansposi ions. This means no only ha he F edkin ga e can be used o
build an app op ia e ci cui o pe o m any gi en conse a i e compu a ion (and hus i
is uni e sal also in his sense wi h espec o conse a i e compu a ions), bu also ha
i is he mos elemen a y concei able ope a ion ha can be used o desc ibe conse a i e
compu a ions.
I is impo an o no e ha e e sibili y and conse a i eness a e wo independen no-
ions: a unc ion (compu ed by a ga e o ci cui ) may be only e e sible, only conse a i e,
bo h o none o hem. Howe e , o any unc ion :{0,1}n→ {0,1}mi is possible o
build a new unc ion R:{0,1}n+m→ {0,1}n+msuch ha Ris a bijec ion on he se
{0,1}n+mand mo eo e :
∀x∈ {0,1}n R(x, 0m) = (x, (x)),
whe e 0mis he m- uple consis ing o all 0’s. The unc ion Ris simply de ined as ollows:
∀x∈ {0,1}n,∀y∈ {0,1}m R(x, y) = (x, y ⊕ (x)),
whe e ⊕deno es he bi wise xo ope a ion. Hence, gi en a ci cui ha compu es he
unc ion i is always possible o build a e e sible ci cui ha , using some addi ional
inpu and ou pu lines, is able o compu e he alues assumed by on i s las mou pu
lines.
Analogously, o any unc ion :{0,1}n→ {0,1}mi is possible o build a conse a i e
unc ion C ha compu es he alues assumed by in i s i s mou pu bi s. P ecisely,
le us de ine he ollowing quan i ies:
O = max ½0,max
x∈{0,1}n{Em( (x)) −En(x)}¾,
Z = max ½0,max
x∈{0,1}n{En(x)−Em( (x))}¾.
In o mally, O ( esp., Z ) is he maximum numbe o 1’s ( esp., 0’s) in he ou pu pa e n
ha should be con e ed o 0 ( esp., 1) in o de o make he unc ion conse a i e. We
can hus de ine Cas an (n+O +Z )–inpu /(m+O +Z )–ou pu unc ion such ha :
∀x∈ {0,1}n C(x, 1O ,0Z ) = ( (x),1w(x),0z(x)),
295
whe e 1k( esp., 0k) is he k– uple consis ing o all 1’s ( esp., 0’s), and he pai
(1w(x),0z(x))∈ {0,1}O +Z is such ha w(x) = O +En(x)−Em( (x)) and z(x) =
Z −En(x) + Em( (x)). Hence, we use some addi ional inpu s ( esp., ou pu s) in o -
de o p o ide ( esp., emo e) he equi ed ( esp., exceeding) ene gy ha allows C o
compu e in a conse a i e way.
I is also possible, o any gi en unc ion :{0,1}n→ {0,1}m, o ex end he e e sible
unc ion Rbuil abo e o a e e sible and conse a i e unc ion RC by adding some
addi ional inpu and ou pu bi s. Fo he p oo we e e he eade o [7].
In [6, 7, 22] conse a i eness has been ex ended o e e sible and non e e sible ga es
whose inpu and ou pu lines may assume a ini e numbe do u h alues. Some many–
alued ex ensions o he F edkin ga e ha e also been p esen ed. By associa ing equispaced
ene gy le els o he u h alues, he au ho s ha e shown ha hei no ion o conse a-
i eness co esponds o he ene gy conse a ion p inciple applied o he da a which a e
manipula ed du ing he compu a ion. In he same pape s he no ion o conse a i e com-
pu a ion has been in oduced, unde he easonable assump ion ha a ga e may s o e, o
accumula e, some ene gy in i s in e nal machine y. Mo eo e , a new NP–comple e decision
p oblem conce ning conse a i e compu a ions has been de ined. Some cons an ac o
app oxima ion algo i hms o an associa ed NP–ha d op imiza ion p oblem a e cu en ly
unde examina ion.
3 Ene gy–Based P Sys ems
P sys ems (also called memb ane sys ems) we e in oduced in [24] as a new class o dis-
ibu ed and pa allel compu ing de ices, inspi ed by he s uc u e and unc ioning o cells.
The basic model consis s o a hie a chical s uc u e composed by se e al memb anes, em-
bedded in o a main memb ane called he skin. Memb anes di ide he Euclidean space
in o egions, ha con ain some objec s ( ep esen ed by symbols o an alphabe ) and e o-
lu ion ules. Using hese ules, he objec s may e ol e and/o mo e om a egion o a
neighbo ing one. The ules a e applied in a nonde e minis ic and maximally pa allel way:
all he objec s ha may e ol e a e o ced o e ol e. A compu a ion s a s om an ini ial
con igu a ion o he sys em and e mina es when no e olu ion ule can be applied. The
esul o a compu a ion is he mul ise o objec s con ained in o an ou pu memb ane o
emi ed om he skin o he sys em.
In wha ollows we assume ha he eade is al eady amilia wi h he basic no ions
and he e minology unde lying P sys ems. Fo de ails, see [27]. The la es in o ma ion
abou P sys ems can be ound on he Web page h p://psys ems.disco.unimib.i /.
In o de o ake in o accoun he amoun o ene gy used du ing compu a ions, we
de ine a new model which we call ene gy–based P sys em. In his model, we conside a
special symbol ewhich deno es a ee ene gy uni loa ing in o egions; mo eo e , he ules
a e de ined acco dingly o conse a i eness conside a ions. We will show how his model
can be used o simula e he F edkin ga e.
Fo mally, an ene gy–based P sys em (o deg ee m≥1) is a cons uc
Π = (A, ε, µ, e, w1, . . . , wm, R1, . . . , Rm, iin, iou ),
whe e:
•Ais an alphabe ; i s elemen s a e called objec s;
296

•ε:A→R+is a linea mapping ha associa es o each objec a∈A he eal
alue ε(a) (also deno ed by εa), which can be hough o as he “ene gy alue o
a”. P ecisely, i A={a1, a2, . . . , ad} hen o all i∈ {1,2, . . . , d}i holds ε(ai) =
ε(a1) + (i−1)δ o an app op ia e eal alue δ > 0. Hence, he ene gy alues
conside ed in he sys em a e equispaced by he quan i y δ. Th ough an app op ia e
escaling, we can always assume ha all ene gy alues a e posi i e in ege alues,
and ha δ= 1;
•µis a hie a chical memb ane s uc u e consis ing o mmemb anes. Fo he sake
o cla i y, we will label memb anes wi h mnemonic iden i ie s which ecall hei
unc ion;
•e6∈ Ais a special symbol ha deno es one ee ene gy uni , ha is, one uni o
ene gy which is no embedded in o any objec ;
•wi, o all i∈ {1, . . . , m}, speci y he mul ise s (o e A∪ {e}) o objec s ini ially
p esen in egion i;
•Ri, o all i∈ {1, . . . , m}, is a ini e se o e olu ion ules o e Aassocia ed wi h
egion i. Only ules o he ollowing ypes a e allowed:
aek→(b, p) , a→(b, p)ek,e→(e, p),
whe e a, b ∈A,p∈ {he e,in(name),ou }and kis a non nega i e in ege ;
•iin is an in ege be ween 1 and mand speci ies he inpu memb ane o Π;
•iou is an in ege be ween 0 and mand speci ies he ou pu memb ane o Π. I
iou = 0, hen he en i onmen is used o he ou pu , ha is, he ou pu alue is
he mul ise o objec s (o e A) emi ed om he skin.
A special a en ion is due o he de ini ion o ules. The meaning o ule aek→(b, p),
wi h a, b ∈A,p∈ {he e,in(name),ou }, and ka posi i e in ege numbe , is he ollowing:
he objec a, in p esence o k ee ene gy uni s, is allowed o be ans o med in o objec b.
I p= he e hen he new objec b emains in he same egion; i p= ou hen bexi s om
he cu en memb ane. Finally, i p= in(name) hen ben e s in o he memb ane labelled
wi h name, which mus be a child o he cu en memb ane in he memb ane hie a chy.
The meaning o ule a→(b, p)ek, when kis a posi i e in ege numbe , is analogous.
The objec ais allowed o be ans o med in o objec bby eleasing kuni s o ee ene gy.
As abo e, he new objec bmay op ionally mo e one le el up o down in o he memb ane
hie a chy. The k ee ene gy uni s can now be used by ano he ule o p oduce “mo e
ene ge ic” objec s om “less ene ge ic” ones.
When k= 0 he ule aek→(b, p) is w i en as a→(a, p), and simply mo es (i p6=
he e) he objec aupwa d o downwa d in o he memb ane hie a chy, wi hou acqui ing
no eleasing any ee ene gy uni . Analogously, ules e→(e, p) simply mo e (i p6= he e)
one uni o ee ene gy upwa d o downwa d in o he memb ane hie a chy.
A u he cons ain o he de ini ion o ules is ha each ule mus be “conse a i e”,
in he sense ha he amoun o ene gy occu ing on he le side o he ule mus be he
same as he amoun o ene gy which occu s on he igh side.
Wi h a li le abuse o no a ion, when he pai (x, p), wi h x∈A∪ {e}and p∈
{he e,in(name),ou }, appea s in o a ule we will w i e xp. Also, i p= in(name) and no
297
con usion a ises we will usually w i e jus he name o he memb ane. Mo eo e , ins ead
o w i ing ekwe will some imes explici ly w i e kins ances o e. I is also unde s ood ha
he posi ion o ek( ha is, on he le o on he igh o he symbol o A) ei he in o he
le o in o he igh side o a ule is unin luen . Finally, when he posi ion po an objec
which occu s in he igh side o a ule is “he e” we will omi o w i e i .
Example 3.1 Le us assume A={a, b, c, d}, whe e he objec s ha e ene gy alues εa= 1,
εb= 2,εc= 3 and εd= 4. Then he ule be2→(d, ou )(also w i en as bee →dou )
ans o ms an ins ance o he objec bin o an ins ance o he objec d, p o ided ha wo
ee ene gy uni s a e a ailable, and makes he new objec dlea e he cu en memb ane.
On he o he hand, he ule c→(a, he e)e2(also w i en as c→aee) ans o ms an
ins ance o he objec cin o an ins ance o he objec aand eleases wo ee ene gy uni s
in o he egion in which he ule is de ined.
Acon igu a ion o Π is he collec ion {M1, . . . , Mm}o mul ise s (o e A∪ {e})
o objec s con ained in each egion o he sys em. {w1, . . . , wm}is called he ini-
ial con igu a ion. Fo wo con igu a ions {M1, . . . , Mm},{M0
1, . . . , M0
m}o Π we
w i e {M1, . . . , Mm} ⇒ {M0
1, . . . , M0
m} o deno e a ansi ion om {M1, . . . , Mm} o
{M0
1, . . . , M0
m}, ha is, he pa allel applica ion o one o mo e ules o he sys em. The
e lexi e and ansi i e closu e o ⇒is deno ed by ⇒∗. A inal con igu a ion is a con igu-
a ion whe e no ule can be applied.
Acompu a ion is a sequence o ansi ions be ween con igu a ions o Π, s a ing om
he ini ial con igu a ion. A compu a ion is success ul i and only i i eaches a inal
con igu a ion o , in o he wo ds, i hal s. I is unde s ood ha he mul ise (o e A, ha
is, no conside ing ee ene gy uni s) o objec s which occu in wiin a e he inpu alues o
he compu a ion. Analogously, he mul ise (o e A) o objec s occu ing in he ou pu
memb ane (o emi ed om he skin i iou = 0) in he inal con igu a ion is he ou pu o
he compu a ion. A non–hal ing compu a ion p oduces no ou pu .
Since ene gy is an addi i e quan i y, i is na u al o de ine he ene gy o a mul ise as
he sum o he amoun s o ene gy associa ed o each ins ance o he objec s which occu
in o he mul ise . Analogously, he ene gy o a con igu a ion is he sum o he amoun s
o ene gy associa ed o each mul ise which occu s in o he con igu a ion. A conse a i e
compu a ion is a compu a ion whe e each con igu a ion has he same amoun o ene gy.
Aconse a i e ene gy–based P sys em is an ene gy–based P sys em ha pe o ms only
conse a i e compu a ions.
4 Simula ing he F edkin Ga e wi h Ene gy–Based
P Sys ems
In his sec ion we show how P sys ems, and speci ically he ene gy–based a ian in o-
duced in he p e ious sec ion, can be used o simula e a F edkin ga e.
When ying o simula e a F edkin ga e wi h a P sys em, pe haps he simples idea
is o associa e a symbol o each possible inpu /ou pu iple as shown in he able on
he le side o Figu e 2. Then, he ga e is i ially simula ed as shown on he igh
side o he same igu e: when a symbol co esponding o he inpu iple is injec ed in o
he skin o he P sys em, in one s ep he symbol co esponding o he ou pu iple is
expelled in o he en i onmen . Howe e , his me hod is no sui able o simula e ci cui s
composed by F edkin ga es. In ac , conside o ins ance he ci cui in Figu e 3. The
298
T iple Symbol
(0,0,0) a
(0,0,1) b
(0,1,0) c
(0,1,1) d
(1,0,0) e
(1,0,1)
(1,1,0) g
(1,1,1) h
FG
a a ou
bou
cou
dou
e e ou
g ou
g ou
h h ou
b
c
d
Figu e 2: A i ial simula ion o he F edkin ga e wi h a P sys em. To each possible
inpu /ou pu iple o he ga e is associa ed a symbol o he alphabe
x
x
x
x
x
2
3
4
5
6
1
2
3
x1y1
y2
y3
y4
y5
y6
Figu e 3: A 6–inpu /6–ou pu F edkin ci cui composed by h ee ga es
symbol co esponding o he inpu iple o ga e numbe 3 depends upon he symbols
co esponding o he ou pu iples o bo h ga es 1 and 2. I is immedia ely seen ha he
ou pu symbols o a laye o a F edkin ci cui canno be immedia ely used as an inpu o
he nex laye : ins ead, a non i ial ans o ma ion is equi ed.
An al e na i e app oach, ha sol es he p e ious p oblem, is o use an ene gy–based
P sys em as de ined in he p e ious sec ion. The sys em has 18 objec s, wi h in ege
ene gies going om 1 o 18. Howe e , we ac ually use only 12 objec s: p ecisely, hose
ha ing ene gies om 1 o 10 and hose ha ing ene gies 17 and 18. The objec s ha ing
ene gies om 11 o 16 ne e appea in o he sys em. These choices a e made in o de
o ha e objec s wi h dis inc ene gies and o gua an ee conse a i eness. Fo he sake o
cla i y, we deno e he 12 objec s used in o he sys em by [b, j] and [b0, j], wi h b, b0∈ {0,1}
and j∈ {1,2,3}. In ui i ely, [b, j] and [b0, j] indica e he boolean alue which occu s in
he j- h line o he F edkin ga e. I will be clea om he simula ion ha we need wo
di e en symbols o ep esen each o hese boolean alues. The ene gies a e associa ed o
he objec s as illus a ed in Table 2. In Figu e 4 he ene gy–based P sys em ha simula es
he F edkin ga e is depic ed.
The simula ion p oceeds as ollows. The inpu alues [x1,1],[x2,2],[x3,3], wi h
x1, x2, x3∈ {0,1}, a e injec ed in o he skin. I x1= 0 hen he objec [0,1] en e s
in o memb ane id, whe e i is ans o med o he objec [00,1] by eleasing 8 uni s o en-
e gy. The objec [00,1] lea es memb ane id and wai s o 8 ene gy uni s o ans o m back
299
Objec Ene gy
[0,1] 17
[1,1] 18
[0,2] 1
[1,2] 2
[0,3] 3
[1,3] 4
Objec Ene gy
[00,1] 9
[10,1] 10
[00,2] 5
[10,2] 6
[00,3] 7
[10,3] 8
Table 2: Associa ion be ween objec s and ene gies in he ene gy–based P sys em ha
simula es a F edkin ga e
FG
[0,1] ID
ID
[b,2] [b,2]
[0,1]
ID
EXC
[b,3] [b,3]
[b,3] [b,3]
[b’,1]ee [b,1] ou
[b’,2] e[b,2] ou
ou
e[b,3][b’,3]
[1,1] [1,1] EXC
EXC
[b,2] [b,2]
EXC
ID
[b,2]e ou
[b’,3]
[b,3]e ou
[b’,2]
[b,2] [b,2] ou
ou
[b,3] [b,3]
[1,1] ou
[1’,1] ee
[b,2]e ou
[b,3]e ou
[b,2] [b,2] ou
ou
[b,3] [b,3]
ou
[0,1] [0’,1] ee
[b’,2]
[b’,3]
Figu e 4: Simula ion o he F edkin ga e wi h an ene gy–based P sys em
o [0,1] and lea e he sys em. The objec s [x2,2] and [x3,3], wi h x2, x3∈ {0,1}, may
en e nonde e minis ically ei he in o memb ane id o in o memb ane exc; howe e , i
hey en e in o exc hey canno be ans o med o [x0
2,3] and [x0
3,2] since in exc he e a e
no ee ene gy uni s. Thus he only possibili y o objec s [x2,2] and [x3,3] is o lea e exc
and choose again be ween memb anes id and exc in a nonde e minis ic way. E en ually,
a e some ime hey en e (one a he ime o simul aneously) in o memb ane id. He e
hey ha e he possibili y o ans o m o [x0
2,2] and [x0
3,3] espec i ely, using he 8 uni s
o ee ene gy which occu in o he egion enclosed by id (al e na i ely, hey ha e he
possibili y o lea e id and choose nonde e minis ically be ween memb anes id and exc
once again). When he objec s [x0
2,2] and [x0
3,3] a e p oduced hey immedia ely lea e id,
and a e only allowed o ans o m back o [x2,2] and [x3,3] espec i ely, eleasing 8 uni s
o ene gy. The objec s [x2,2] and [x3,3] jus p oduced lea e he sys em, and he 8 uni s
o ene gy can only be used o ans o m [00,1] back o [0,1] and expel i om he skin.
On he o he hand, i x1= 1 hen he objec [1,1] en e s in o memb ane exc whe e
i is ans o med in o he objec [10,1] by eleasing 8 uni s o ene gy. The objec [10,1]
lea es he memb ane exc and wai s o 8 ene gy uni s o ans o m back o [1,1] and lea e
he sys em. Once again he objec s [x2,2] and [x3,3], wi h x2, x3∈ {0,1}, may choose
300
[16] S. Ji. The Bhopala o : An in o ma ion/ene gy dual model o he li ing cell. In P e–
P oceedings o he Wo kshop on Memb ane Compu ing, Cu ea de A ges, Romania,
Augus 2001, Technical Repo 17/01 o Resea ch G oup on Ma hema ical Linguis ics,
Ro i a i Vi gili Uni e si y, Ta agona, Spain, 2001, pp. 123-142 and Fundamen a
In o ma icae, 49(1-3):147–165, 2002.
[17] J.P. Klein, T.H. Lee e, H. Rubin. A biomolecula implemen a ion o logically e-
e sible compu a ion wi h minimal ene gy dissipa ion. Biosys ems 52:15–23, 1999.
[18] R. Landaue . I e e sibili y and hea gene a ion in he compu ing p ocess. IBM Jou -
nal o Resea ch and De elopmen , 5:183–191, 1961.
[19] R. Landaue . Unce ain y p inciple and minimal ene gy dissipa ion in he compu e .
In e na ional Jou nal o Theo e ical Physics, 21(3-4):283–297, 1982.
[20] M. Madhu, K. K i hi asan. P sys ems wi h memb ane c ea ion: Uni e sali y and e -
iciency. In M. Ma gens e n, Y. Rogozhin (Eds.), Machines, Compu a ions, and Uni-
e sali y, P oceedings o he Thi d In e na ional Con e ence, MCU 2001, Chisinau,
Molda ia, May 2001, Lec u e No es in Compu e Science 2055, Sp inge , 2001, pp.
276–287.
[21] C. Ma in–Vide, V. Mi ana. P Sys ems wi h alua ions. In I. An oniou, C. S. Calude,
M. J. Dinneen (Eds.), Uncon en ional Models o Compu a ion, UMC’2K, Sol ay In-
s i u es, B ussels, Decembe 2000, DIMACS: Se ies in Disc e e Ma hema ics and
Theo e ical Compu e Science, Sp inge , 2000, pp. 154–166.
[22] G. Mau i, A. Lepo a i. On he compu a ional complexi y o conse a i e compu ing.
In P oceedings o he 28 h In e na ional Symposium on Ma hema ical Founda ions o
Compu e Science (MFCS 2003), Lec u e No es in Compu e Science 2747, Sp inge –
Ve lag Heidelbe g, 2003, pp. 92–112.
[23] M. Ogiha a, A. Ray. Simula ing Boolean ci cui s on a DNA compu e . Technical
Repo 631, 1996. A ailable a : h p://ci esee .nj.nec.com/ogiha a96simula ing.h ml
[24] G. P˘aun. Compu ing wi h memb anes. Jou nal o Compu e and Sys em Sciences,
1(61):108–143, 2000. See also Tu ku Cen e o Compu e Science — TUCS Repo
No. 208, 1998. A ailable a : h p://www. ucs. i/Publica ions/ ech epo s/TR208.php
[25] G. P˘aun. Compu ing wi h memb anes. An in oduc ion. Bulle in o he EATCS,
67:139–152, Feb ua y 1999.
[26] G. P˘aun. Compu ing wi h memb anes. A a ian : P sys ems wi h pola ized mem-
b anes. In e na ional Jou nal on Founda ions o Compu e Science, 11(1):167–182,
2000. See also CDMTCS Technical Repo 098, Uni e si y o Auckland, 1999. A ail-
able a : h p://www.cs.auckland.ac.nz/CDMTCS
[27] G. P˘aun. Memb ane Compu ing. An In oduc ion. Sp inge –Ve lag, Be lin, 2002.
[28] G. P˘aun, G. Rozenbe g. A guide o memb ane compu ing. Theo e ical Compu e
Science, 287(1):73–100, 2002.
[29] G. P˘aun, Y. Suzuki, H. Tanaka. P Sys ems wi h ene gy accoun ing. In e na ional
Jou nal Compu e Ma h., 78(3):343–364, 2001.
307

[30] G. P˘aun, T. Yokomo i. Memb ane compu ing based on splicing. In E. Win ee,
D. K. Gi o d (Eds.), P oceedings o he 5 h DIMACS Wo kshop on DNA Based
Compu e s, Massachuse s Ins i u e o Technology, Camb idge, MA, USA, June 1999,
Ame ican Ma hema ical Socie y, 1999, pp. 213–227.
[31] C. A. Pe i. G ¨undsa zliches zu Besch eibung disk e e P ozesse. In P oceedings
o he 3 d Colloquium ¨ube Au oma en heo ie (Hanno e , 1965), Bi kh¨ause Ve lag,
Basel, 1967, pp. 121–140. English ansla ion: Fundamen als o he Rep esen a ion
o Disc e e P ocesses, ISF Repo 82.04, 1982.
[32] V. J. P akash, K. K i hi asan. Simula ing Boolean ci cui s wi h issue P sys ems.
Manusc ip , 2004.
[33] H. Vollme . In oduc ion o Ci cui Complexi y: A Uni o m App oach. Sp inge –
Ve lag, 1999.
[34] C. Zand on, C. Fe e i, G. Mau i. Using memb ane ea u es in P sys ems. Romanian
Jou nal o In o ma ion Science and Technology, 4(1-2):241–257, 2001.
[35] C. Zand on, G. Mau i, C. Fe e i. Uni e sali y and no mal o ms on memb ane sys-
ems. In R. F eund, A. Kelemeno a (Eds.), P oceedings o he In e na ional Wo kshop
on G amma Sys ems, July 2000, Bad Ischl, Aus ia, 2000, pp. 61–74.
308