Generation of Diophantine Sets by Computing P Systems with External Output

Gene a ion o Diophan ine Se s by Compu ing P Sys ems wi h Ex e nal Ou pu Ál a o ROMERO JIMÉNEZ and Ma io J. PÉREZ JIMÉNEZ Dp o. de Ciencias de la Compu ación e In eligencia A icial Uni e sidad de Se illa, España E-mail: {Al a o.Rome o,Ma io.Pe ez}@cs.us.es Abs ac . In his pape a a ian o P sys ems wi h ex e nal ou pu designed o compu e unc ions on na u al numbe s is p esen ed. These P sys ems a e s able unde composi ion and i e a ion o unc ions. We p o e ha e e y diophan ine se can be gene a ed by such P sys ems; hen, he uni e sali y o his model can be deduced om he heo em by Ma iyase ich, Robinson, Da is and Pu nam in which hey es ablish ha e e y ecu si ely enume able se is a diophan ine se . 1 In oduc ion In 1998 G. Pun ini ia ed a new b anch o he eld o Na u al Compu ing by in oducing a new model o molecula compu a ion, based on he s uc u e and unc ioning o he li ing cell: ansi ion P sys ems (see [3]). The amewo k wi hin which compu a ion a e pe o med in his model is he memb ane s uc- u e, which ec ea es he cell-like one. Mul ise s o symbol-objec s a e p ocessed along he compu a ions, making hem o e ol e and dis ibu ing hem among he memb anes. The esul o a hal ing compu a ion is he numbe o objec s collec ed in a specied ou pu memb ane. Since he in oduc ion o his model o compu a ion many a ian s o i ha e been p oposed. One o hem, p esen ed in [5] by G. Pun, G. Rozenbe g and A. Salomaa, is he model o ansi ion P sys ems wi h ex e nal ou pu . In his model, he esul o a hal ing compu a ion is no collec ed in a xed memb ane o he memb ane s uc u e, bu in he ex e nal en i onmen associa ed wi h i . In his way, he ou pu o a compu a ion can be hough as a se o s ings, ins ead o as a na u al numbe , as occu ed in he basic model. P sys ems a e usually conside ed as de ices which gene a e numbe s. Ne- e heless, besides gene a ing de ices, hey can also be hough as ecognizing de ices and as compu ing de ices. These kind o P sys ems ha e been s udied in [6]. In his pape we wo k wi h compu ing P sys ems, bu ins ead o he basic ansi ion ones we conside hose wi h ex e nal ou pu . Thanks o he special unc ioning o hese appa a us, we ha e been able o dene, in a com o able manne , se e al ope a ions be ween compu ing P sys ems wi h ex e nal ou pu ; mo e specically, we ha e dened composi ion and i e a ion, wha ha e allowed us o p o e he uni e sali y o hese de ices h ough he gene a ion o all he diophan ine se s. 2 Mul ise s. Memb ane s uc u es. E olu ion ules A mul ise o e a se , A , is an applica ion m:A→IN . A mul ise is said o be emp y ( esp. ni e) i i s suppo , supp(m) = {a∈A:m(a)>0} , is emp y ( esp. ni e). I m is a ni e mul ise o e A , we will deno e i m={{a1, . . . , ak}} , whe e he elemen s ai a e possibly epea ed. We w i e M(A) o he se o all he mul ise s o e A . The se o memb ane s uc u es , MS , is dened by ecu sion as ollows: 1. [ ] ∈MS ; 2. I µ1, . . . , µn∈MS , hen [µ1. . . µn]∈MS . A memb ane s uc u e, µ , can also be seen as a oo ed ee, V(µ), E(µ) . Then, he nodes o his ee a e called memb anes , he oo node he skin mem- b ane and he lea es elemen a y memb anes o he memb ane s uc u e. The deg ee o a memb ane s uc u e is he numbe o memb anes in i . The concep s o dep h o a memb ane s uc u e and dep h o i s memb anes a e easily dened om hose o a ee and i s nodes. We will also need he no ion o le el o a memb ane wi hin a memb ane s uc u e, which is dened as he die ence be ween he dep h o he second and he dep h o he  s . The memb ane s uc u e wi h ex e nal en i onmen associa ed wi h a mem- b ane s uc u e, µ , is µE= [Eµ]E . I we conside he la e as a oo ed ee, he oo node is called he ex e nal en i onmen o µ . Gi en an alphabe , Γ , we associa e wi h e e y memb ane o a memb ane s uc u e a ni e mul ise o elemen s o Γ , which a e called he objec s o he memb ane. We also associa e wi h e e y one o hese memb anes a ni e se o e olu ion ules . A e olu ion ule o e Γ is a pai (u, ) , usually w i en u→ , whe e u is a s ing o e Γ and = 0 o = 0δ , whe e 0 is a s ing o e Γ×{he e, ou }∪{inl:l∈V(µ)} The idea behind a ule is ha he objec s in u e ol e in o he objec s in 0 , mo ing o no o ano he memb ane and possibly dissol ing he o iginal one. 3 Compu ing P sys ems wi h ex e nal ou pu We a e now p epa ed o in oduce ou new model o compu a ion. Deni ion 3.1. A compu ing P sys em wi h ex e nal ou pu o o de (m, n) and deg ee p is a uple Π=Σ, Λ, Γ, #, µΠ, ι, M1, . . . , Mp,(R1, ρ1), . . . , (Rp, ρp) whe e  Σ is an o de ed alphabe o size m , he inpu alphabe .  Λ is an o de ed alphabe o size n , he ou pu alphabe .  Γ is an alphabe such ha Σ∪Λ⊂Γ , he wo king alphabe .  # is a dis inguished elemen in Γ Σ∪Λ) , he hal ing elemen .  µΠ is a memb ane s uc u e o deg ee p , whose memb anes we suppose labeled om 1 o p .  The inpu memb ane o Π is labeled by ι∈ {1, . . . , p} .  Mi is a mul ise o e Γ Σ associa ed wi h he memb ane labeled by i , o e e y i= 1, . . . , p .  Ri is a ni e se o e olu ion ules o e Γ associa ed wi h he memb ane labeled by i , and ρi is a s ic pa ial o de o e i , o e e y i= 1, . . . , p . To o malize he seman ics o his model we dene  s wha a congu a ion o a P sys em is, om wha ollows he no ion o compu a ion. Deni ion 3.2. Le Π be a compu ing P sys em wi h ex e nal ou pu .  A congu a ion o Π is a pai (µE, M) , whe e µ is a memb ane s uc u e such ha V(µ)⊆V(µΠ) and has he same oo han µΠ , and M is an applica ion om V(µE) in o M(Γ) . Fo e e y node nd ∈V(µE) we deno e Mnd =M(nd) .  Suppose ha Π is o o de (m, n) and Σ= (a1, . . . , am) . Then, any m - uple o na u al numbe s can be codied by a mul ise o e Σ and gi en as inpu o he P sys em. Thus, he ini ial congu a ion o Π o a uple (k1, . . . , km)∈ INm is he pai (µE, M) , whe e µ=µΠ , ME=∅ , Mι=Mι∪{{ak1 1. . . akm m}} and Mi=Mi , o e e y i6=ι . We can pass, in a non-de e minis ic manne , om one congu a ion o Π o ano he by applying o i s mul ise s he e olu ion ules associa ed wi h hei co esponding memb anes. This is done as ollows: gi en a ule u→ o a memb ane i , he objec s in u a e emo ed om Mi ; hen, o e e y (ob, ou )∈ an objec ob is pu in o he mul ise associa ed wi h he pa en memb ane (o he ex e nal en i onmen i i is he skin memb ane); o e e y (ob, he e)∈ an objec ob is added o Mi ; o e e y (ob, inj)∈ an objec ob is added o Mj (i j is no a child en memb ane o i , he ule canno be applied). Finally, i δ∈ , hen he memb ane i is dissol ed, ha is, i is emo ed om he memb ane s uc u e ( he objec s associa ed wi h his memb anes a e collec ed by he pa en memb ane, and he ules a e los . The skin memb ane canno dissol e). Mo eo e , he p io i y ela ion among he ules o bids he applica ion o a ule i ano he one o highe p io i y is applied. Gi en wo congu a ions, C and C0 , o Π , we say ha C0 is ob ained om C in one ansi ion s ep, and we w i e C⇒C0 , i we can pass om he  s o he second by using he e olu ions ules appea ing in he memb ane s uc u e o C in a pa allel and maximal way, and o all he memb anes a he same ime. Deni ion 3.3. Gi en a compu ing P sys em wi h ex e nal ou pu o o de (m, n) , Π , a compu a ion o Π wi h inpu (k1, . . . , km)∈INm is a sequence, possibly inni e, o congu a ions o Π , C0⇒C1⇒. . . ⇒Cq , q≥0 , such ha  C0 is he ini ial congu a ion o Π o (k1, . . . , km) .  Each Ci is ob ained om he p e ious congu a ion by one ansi ion s ep. We say ha a compu a ion, C , is a hal ing compu a ion o Π , i q∈IN and he e is no ule applicable o he objec s p esen in i s las congu a ion. Then, he ou pu o a hal ing compu a ion and o a compu ing P sys em wi h ex e nal ou pu can be dened in a na u al way. Deni ion 3.4. Le Π be a compu ing P sys em wi h ex e nal ou pu o o de (m, n) and suppose ha Λ= (b1, . . . , bn) . Le C be a hal ing compu a ion o Π wi h inpu (k1, . . . , km)∈INm and (µE, M) i s las congu a ion. Then, he ou pu o ha compu a ion is gi en by Ou pu (C) = ME(b1), . . . , ME(bn). Deni ion 3.5. Le Π be a compu ing P sys em wi h ex e nal ou pu o o de (m, n) . The ou pu o Π wi h inpu (k1, . . . , km)∈INm is gi en by Ou pu (Π;k1, . . . , km) = {Ou pu (C) : C is a hal ing compu a ion o Π wi h inpu (k1, . . . , km)}. The idea behind P sys ems wi h ex e nal ou pu is ha we canno know wha is happening inside he memb ane s uc u e, bu we can only collec he in o ma ion h own om i o he ex e nal en i onmen . In acco dance wi h i , i seems na u al ha he hal ing compu a ions o hese P sys ems epo o he ou side when hey ha e eached hei nal congu a ions. Fu he mo e, he idea behind compu ing P sys ems is o use hem as com- pu ing models o unc ions be ween na u al numbe s. These conside a ions lead us o he ollowing no ions: Deni ion 3.6. A compu ing P sys em wi h ex e nal ou pu o o de (m, n) , Π , is said o be alid when he ollowing is e ied:  I C is a hal ing compu a ion o Π , hen a ule o he o m u→ (#, ou ) mus ha e been applied in he skin memb ane o µΠ , and only in he las s ep o he compu a ion.  I C is no a hal ing compu a ion o Π , hen no ule o he p e ious o m is applied in he skin memb ane in any s ep o he compu a ion.  Fo e e y (k1, . . . , km)∈INm and o e e y wo hal ing compu a ions, C1 and C2 , o Π wi h inpu (k1, . . . , km) , Ou pu (C1) = Ou pu (C2) . Deni ion 3.7. A compu ing P sys em wi h ex e nal ou pu o o de (m, n) , Π , compu es a pa ial unc ion, : INm− → INn , i  Π is a alid P sys em.  Fo e e y (k1, . . . , km)∈INm • is dened o e (k1, . . . , km) i and only i he e exis s a hal ing com- pu a ion o Π wi h inpu (k1, . . . , km) . • I C is a hal ing compu a ion o Π wi h inpu (k1, . . . , km) , hen Ou pu (C) = (k1, . . . , km) . We deno e CEPm,n p(α, β, γ) , whe e m, n ∈IN, p ≥1 , α∈ {P i, nP i} , β∈ {Coo, Ca , nCoo} and γ∈ {δ, nδ} , he amily o unc ions compu ed by compu ing P sys ems wi h ex e nal ou pu o o de (m, n) , o deg ee a mos p , and wi h o wi hou p io i y, wi h coope a ion, only ca alys s o wi hou coop- e a ion (see [3]), and wi h o wi hou dissolu ion, espec i ely. The union, o all p≥1 , o he amilies o one o hese ypes is deno ed CEPm,n(α, β, γ) . 4 Composi ion o compu ing P sys ems wi h ex e nal ou pu We in oduce now he ope a ion o composi ion be ween compu ing P sys ems wi h ex e nal ou pu . Deni ion 4.1. Le : INm− → INn and g1: IN − → INs1, . . . , g : IN − → INs such ha s1+· · ·+s =m . Then, he composi ion o wi h g1 o g , deno ed C( ;g1, . . . , g ) , is a pa ial unc ion om IN o INn dened as ollows C( ;g1, . . . , g )(k1, . . . , k ) = (g1(k1, . . . , k ), . . . , g (k1, . . . , k )) Theo em 4.2. Le ∈CEPm,n(α, β, γ), g1∈CEP ,s1(α, β, γ), . . . , g ∈ CEP ,s (α, β, γ) , wi h α∈ {P i, nP i} , β∈ {Coo, Ca , nCoo} and γ∈ {δ, nδ} . Then, C( ;g1, . . . , g )∈CEP ,n(P i, Coo, γ) . P oo . Le Π =Σ , Λ , Γ ,# , µΠ , ι ,M 1, . . . , M p ,(R 1, ρ 1), . . . , (R p , ρ p ) Πg1=Σg1, Λg1, Γg1,#g1, µΠg1, ιg1,Mg1 1, . . . , Mg1 pg1,(Rg1 1, ρg1 1), . . . , (Rg1 pg1, ρg1 pg1) . . . Πg =Σg , Λg , Γg ,#g , µΠg , ιg ,Mg 1, . . . , Mg pg ,(Rg 1, ρg 1), . . . , (Rg pg , ρg pg ) be compu ing P sys ems wi h ex e nal ou pu ha compu e, espec i ely, he unc ion and he unc ions g1 o g . By means o a enaming o he elemen s o he alphabe s (and, he e o e, also o he ules), we can suppose ha  Σg1=· · · =Σg = (a1, . . . , a ) .  Λg1= (b1, . . . , bs1), . . . , Λg = (bs1+···+s −1+1, . . . , bm) .  Σ = (c1, . . . , cm) .  Λ = (d1, . . . , dn) .  Λg1∪ · · · ∪ Λg ∩Γ =∅ .  #gi6= #gj , o e e y i6=j . Le us conside he compu ing P sys em wi h ex e nal ou pu Π=Σ, Λ, Γ, #, µΠ, ι, M1, . . . , Mp,(R1, ρ1), . . . , (Rp, ρp) gi en by  Σ= (e1, . . . , e ) . (We suppose ha Σ∩S i=1 Γgi=∅ ).  The e exis dis inguished elemen s ⊕,, ∈ Γ (Γ ∪S i=1 Γgi) .  Λ= (d1, . . . , dn) .  #6= #gi , o e e y i= 1, . . . , , and #6= # .  µΠ= [1µΠg1. . . µΠg µΠ ]1 , whe e he memb anes om µΠg1, . . . , µΠg , µΠ ha e been adequa ely enamed (and he e o e, also he ules o he co es- ponding P sys ems ha e been adap ed). We deno e σg1, . . . , σg , σ he skin memb anes o he la e . Also, we conside ha ιg1, . . . , ιg , ι eec he new labeling o he inpu memb anes o Πg1, . . . , Πg , Π , espec i ely.  ι= 1 .  p=pg1+· · · +pg +p + 1 .  M1={{#,}} . The emaining mul ise s a e all emp y.  The e olu ion ules a e he ollowing: • E olu ion ules o memb ane 1: ei→(ei, inσg1). . . (ei, inσg ) (i= 1, . . . , )  → (, inσg1). . . (, inσg ) #g1. . . #g #→(, inσ )>#→#> bi→(bi, inσ ) (i= 1, . . . , m) di→(di, ou ) (i= 1, . . . , n) # →(#, ou ) • Fo e e y unc ion un =g1, . . . , g , and o e e y memb ane j o µΠ un , he ollowing ules a e included:  → ⊕(, inj1). . . (, injk) u⊕ → M un j>⊕ → ⊕ e olu ion ules associa ed wi h he memb ane in Π un whe e j1 o jk a e he child en memb anes o memb ane j and u is i s le el wi hin µΠ un . Mo eo e , i j is ι un , hen he ule ⊕ → ⊕ has highe p io i y han he o iginal ules o Π un o his memb ane. • Le un be as abo e and le j1, . . . , jq be he memb ane pa h om σ un o ι un . Then, o k= 1, . . . , q −1 he ollowing ules a e included in memb ane jk : ei→(ei, injk+1 ) (i= 1, . . . , ) o un =g1, . . . , g bi→(bi, injk+1 ) (i= 1, . . . , m) o un = Also, he ollowing ules a e included in memb ane jq=ι un . ei→ai(i= 1, . . . , ) o un =g1, . . . , g bi→ci(i= 1, . . . , m) o un = The P sys em cons uc ed in his way, deno ed C(Π ;Πg1, . . . , Πg ) , is a alid compu ing P sys em wi h ex e nal ou pu which compu es he composi ion o wi h g1 o g . Fu he mo e, i p ese es he use o no o dissolu ion om he P sys ems which compu e he unc ions. Indeed, he sys em wo ks as ollows:  Phase 1: Compu a ion o he unc ions g1 o g o e he inpu da a To pe o m his s age, we need o ca y ou wo ope a ions: he  s one consis s o aking he inpu a gumen s om memb ane 1, which ecall is he inpu memb ane o Π , o all he inpu memb anes o he P sys ems Πg1 o Πg . This is easily done by displacing he objec s ep esen ing he a gumen s h ough all he necessa y memb anes. The second ope a ion is a li le bi mo e complica ed: in o de o a specic P sys em Πgj o compu e co ec ly he alue o he unc ion gj o e he inpu da a, we need ha all he memb anes o his P sys em s a o apply hei o iginal ules a he same ime ( ha is, we ha e o synch onize locally he memb anes o each Πgj ). We achie e his by using coun e s o e e y one o hese memb anes. Fi s , we use he objec  o ac i a e he coun e s, ep esen ed by objec s ⊕ , in all he memb anes. These la e objec s use objec s  o coun and, when a ce ain quan i y is eached, he co esponding memb ane is allowed o use he ules o Πgj . Because o he way we ha e implemen ed his, hese quan i ies u n ou o be he le els o he memb anes in he s uc u e µΠgj . I is also impo an ha when he P sys em Πgj s a s o compu e he alue, he objec s ep esen ing he inpu da a ha e eached i s inpu memb ane. Howe e , as we pe o m he wo ope a ions abo e simul aneously, we ge i o ee. Finally, we ha e o wai un il all he alues om Πg1 o Πg ha e been compu ed, be o e allowing he P sys em Π o be used ( ha is, he e mus be a global synch oniza ion in he skin o Π ). Le us see wi h g ea e de ail he ules in ol ed in his phase: 1. A he  s s ep o a compu a ion o Π wi h inpu (k1, . . . , k ) , we ha e in memb ane 1 he mul ise {{ek1 1, . . . , ek ,#,}} and he o he mem- b anes a e emp y. The e o e, only he ules which send he objec s ei and he objec  in o he skins o µΠg1 o µΠg and he ule #→# in memb ane 1 can be applied. 2. Now, memb ane 1 wai s o he alues o g1 o g o e (k1, . . . , k ) by means o he ule #→# . Wi h ega d o memb ane s uc u es µΠg1 o µΠg , he ule  → ⊕(, inj1). . . (, injk) makes he objec  o sp ead o all hei memb anes, because when i eaches a pa icula memb ane, i is immedia ely ans o med in o a coun e objec ⊕ and also sen o he child en memb anes. Thus, om a s ep o he compu a ion o he nex one,  eaches he memb anes one dep h g ea e . Meanwhile, he ule ⊕ → ⊕ makes he objec ⊕ o gene a e objec s  . A close look o he si ua ion c ea ed shows ha he ac i a ing objec  ha e eached all he memb anes exac ly when he coun e objec s ⊕ ha e gene a ed in each memb ane a numbe o objec s  equal o hei le els in µΠ un ( un =g1, . . . , g ). A ha momen , he ule u⊕ → M un j in oduces in memb ane j he objec s associa ed wi h i in Π un , and his is done o all he memb anes o each Π un a he same ime. F om now on, he alues o g1 o g o e (k1, . . . , k ) a e compu ed exac ly in he same way han he P sys ems Πg1 o Πg would do i . 3. Simul aneously, he objec s ei co e he pa h om he skin memb ane o each µΠgj o he inpu memb ane o Πgj , by means o he ules ei→ (ei, injk+1 ) , and a e changed he e in o he co esponding objec s ai , by means o he ules ei→ai . No e ha he objec s ei and he objec  each he inpu memb ane a he same ime. So, when Πgj s a s i s o iginal unc ioning, as s a ed abo e, he inpu da a is in i s place.  Phase 2: Compu a ion o he unc ion Phase 1 ends when memb ane 1 has collec ed a leas one objec o each #g1 o #g . I is hen when he alues compu ed ha e o be sen as inpu da a o he P sys em Π . To synch onize he end o phase 1 wi h he beginning o phase 2, memb ane 1 apply once and again he ule #→# un il he ule #g1. . . #g #→(, inσ ) can be used. This la e ule sends an objec  in o he skin o µΠ , in o de o ini ia e i s memb anes' coun e s so ha hey s a o apply hei o iginal ules a he same ime (local synch oniza ion wi hin Π ). This is done jus as be o e. Also, in he nex s ep o he compu a ion he objec s bi , which ep esen he alues ob ained in phase 1, a e pu in o he skin o µΠ and, subsequen ly, mo ed, by means o he ules bi→(bi, injk+1 ) , h ough all he memb anes om his one o he inpu memb ane o Π . Nex , he ules bi→ci change hem in o he co esponding inpu objec s o Π . I is easy o see ha , al hough he e is a gap o one s ep o compu a ion be ween when  ge s in o a memb ane and when he bi s do so, his is no a all a p oblem. Now, he alue o he unc ion o e he a gumen s ep esen ed by he objec s ci is compu ed, and along his compu a ion objec s di ep esen ing he esul a e h own ou o µΠ . These objec s a e collec ed in memb ane 1, and immedia ely expelled om µΠ . The calcula ion nishes when some objec s # a e collec ed in memb ane 1 and hey a e expelled om µΠ as objec s # . u 5 I e a ion o compu ing P sys ems wi h Ex e nal Ou pu We in oduce now he ope a ion o i e a ing a compu ing P sys em wi h ex e nal ou pu . Deni ion 5.1. Le : INm− → INm . Then, he i e a ion unc ion o , deno ed I ( ) , is a pa ial unc ion om INm+1 o INm dened as ollows: I ( )(x,0) = x I ( )(x, n + 1) = I ( )( (x), n) Theo em 5.2. Le ∈CEPm,m(α, β, nδ) , wi h α∈ {P i, nP i} and β∈ {Coo, Ca , nCoo} . Then I ( )∈CEP m+1,m(P i, Coo, nδ) . P oo . Le Π =Σ , Λ , Γ ,# , µΠ , ι ,M 1, . . . , M p ,(R 1, ρ 1), . . . , (R p , ρ p ) be a compu ing P sys em wi h ex e nal ou pu such ha compu es . By means o a enaming o he elemen s o he alphabe s (and, he e o e, also o he ules), we can suppose ha  Σ = (a1, . . . , am) .  Λ = (b1, . . . , bm) . Le us conside he compu ing P sys em wi h ex e nal ou pu Π=Σ, Λ, Γ, #, µΠ, ι, M1, . . . , Mp,(R1, ρ1), . . . , (Rp, ρp)) e i ying he ollowing  Σ= (c1, . . . , cm+1) , and is such ha Σ∩Γ =∅ .  The e exis dis inguished elemen s ⊕,,,⊗, ∈ Γ Γ .  Λ= (c1, . . . , cm) .  #6= # .  µΠ= [1µΠ ]1 , whe e he memb anes om µΠ ha e been adequa ely e- named (and he e o e, also he ules o Π ha e been adap ed). We deno e σ he skin memb ane o he la e . Also, we conside ha ι eec s he new labeling o he inpu memb ane o Π .  ι= 1 .  p=p + 1 .  M1={{#}} . The emaining memb anes a e all emp y.  The e olu ion ules a e he ollowing: • E olu ion ules o memb ane 1: #cm+1 →(, inσ )>#ci→#(ci, ou ) (i= 1, . . . , m)> >#→(#, ou )># # →# ># →(, inσ )> >⊗ubi→ ⊗uci(i= 1, . . . , m)>⊗u→#> > ci→(ci, inσ ) (i= 1, . . . , m) whe e u is he deg ee o µΠ .