Simulating the Fredkin Gate with Energy-Based P Systems

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