ÚJ ELV SZÁMÍTÓGÉPEK (Bevezetés az új számítási modellekbe és a nem-klasszikus "számítógépek" tudományába)

Nagy Benedek

ÚJ ELV SZÁMÍTÓGÉPEK (Bevezetés az új számítási modellekbe és a nem-klasszikus "számítógépek" tudományába)

mobiDIÁK könyvtár

Nagy Benedek

ÚJ ELV SZÁMÍTÓGÉPEK (Bevezetés az új számítási modellekbe és a nem-klasszikus "számítógépek" tudományába)

mobiDIÁK könyvtár SOROZATSZERKESZT Fazekas István

Nagy Benedek

ÚJ ELV SZÁMÍTÓGÉPEK (Bevezetés az új számítási modellekbe és a nem-klasszikus "számítógépek" tudományába) Egyetemi jegyzet Programozó, Programtervez®, Informatika szakos és egyéb érdekl®d® hallgatók részére

mobiDIÁK könyvtár Debreceni Egyetem Informatikai Kar

c Nagy Benedek, 2005 Copyright ° c elektronikus közlés mobiDIÁK könyvtár, 2005 Copyright ° mobiDIÁK könyvtár Debreceni Egyetem Informatikai Kar 4010 Debrecen, Pf. 12 http://mobidiak.inf.unideb.hu

A m¶ egyéni tanulmányozás céljára szabadon letölthet®. Minden egyéb felhasználás csak a szerz® el®zetes írásbeli engedélyével történhet. A m¶ A mobiDIÁK önszervez® mobil portál (IKTA, OMFB-00373/2003) és a GNU Iterátor, a legújabb generációs portál szoftver (ITEM, 50/2003) projektek keretében készült.

ELSZÓ

7

El®szó a sorozathoz A mobiDIÁK könyvtár a A mobiDIÁK önszervez® mobil portál (IKTA, OMFB00373/2003)) és a GNU Iterátor, a legújabb generációs portál szoftver (ITEM, 50/2003) projektek keretében készült dokumentumokat tartalmazza. A dokumentumok az informatika oktatása, kutatása, alkalmazása és népszer¶sítése legkülönöz®bb témaköreib®l kerülhetnek ki.

Tartalomjegyzék El®szó a sorozathoz . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7

I. Bevezetés . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 II. A Hagyományos Számítási Modell . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1. A Turing-gép . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2. A Neumann-elv . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3. Hagyományos számítógépek . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4. Néhány nem-hagyományos elv¶ algoritmus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

13 13 21 22 24

III. DNS Számítások . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 1. A DNS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2. Alapm¶veletek a DNS láncokkal. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3. Adleman kísérlete - Hamilton út probléma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4. Számítási modellek. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5. Sejten belüli számítások . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

27 35 42 44 48

IV. Membrán Számítások . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 1. A biológiai membránok . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2. Formális membrán-modell . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3. Multihalmazok és számítások: Parikh nyelvek . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4. M¶veletek a membrán-rendszerben . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5. Aktív membránok . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6. A kiszámíthatóság fogalma membrán-rendszerekben . . . . . . . . . . . . . . . . . . . . . . . . 7. Összefoglalás és a legújabb kutatási irányok . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

59 62 64 65 67 73 77

V. Kvantum Számítások . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79 1. A kvantum-mechanika "különös" jelenségei . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79 2. A "megfordítható" számítástechnika . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83 3. A kubit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87 4. A Kubit Transzformációi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88 5. A Kvantum Regiszter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91 6. Kubit dinamika: egyszer¶ kubit kapuk . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93 7. Egy NMR számítógép . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98 8. A szabályozott NOT-kapu. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100 9. Kvantum algoritmusok . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101 10.Kvantumszámítógépek a gyakorlatban, összefoglalás . . . . . . . . . . . . . . . . . . . . . . . . 107 9

10

TARTALOMJEGYZÉK

VI. Intervallum-számítógép . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109 1. Természetes motivációk . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109 2. Matematikai leírás . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110 3. A hagyományos számítógép modellezése . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116 4. A SAT probléma megoldása lineáris id®ben. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118 5. Lista-reprezentáció . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120

Irodalomjegyzék . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123

I. fejezet

Bevezetés A jegyzetet a hagyományos számítástechnika alapjainak áttekintésével kezdjük a II. fejezetben: elméletileg a Turing-gép, mint absztrakt modell, gyakorlatban a számítógépek a Neumann elv alapján épülnek fel, a klasszikus propozicionális logikát használva. A jegyzet ezután következ® fejezetei új-elv¶, nem a klasszikus módon m¶köd® számítási modellekbe nyújtanak bevezetést. Ezek a "nem hagyományos" számítógépek a következ®k: • III. fejezet: DNS-számítástechnika: biológiai alapok, a DNS felépítése, a kett®s spirál tulajdonságai, biológia folyamatai, "ragadós vég", enzimek szerepe, a DNS lánc "elolvasása"; Adleman kísérlete; H-rendszerek: DNS szeletelés, matematikai modell: sztring-szeletelés; gyakorlati példák; beszúró-törl® rendszerek; a sejt "számítási" folyamatai: makro- és mikro-nukleusz, DNSm¶veletek - különböz® absztrakciós szinteken. • IV. fejezet Membrán-rendszerek: biológiai motiváció: a sejt; membránrendszer, mint absztrakt számítási modell; alapmodell, katalizátorok, prioritás, szimbólum objektumok, kommunikáció a membránok között, aktív membránok; Parikh-halmazok, multihalmaz-nyelvek, példák. • V. fejezet: Kvantum-számítástechnika: kvantummechanikai alapok, részecske-hullám kett®sség, szuperpozíció, mérés, matematikai formalizmus. Kubit, Kubit-transzformációk, kvantum-regiszter, kvantum-kapuk és kvantum-algoritmusok. • VI. fejezet: Intervallum-számítások: intervallum-logika, az intervallum-bájt, lista-reprezentáció, számítások intervallumokkal, példák. Az ismertetésre kerül® számítási modellek a XX. század végén (leginkább a 90-es években) indultak fejl®désnek, és napjainkban is töretlenül fejl®dnek. Az irodalomjegyzékben rengeteg cikket és könyvet gy¶jtöttünk össze (dönt®en angol nyelven). Köszönet a tantárgy 2004-2005 év 2. félévi hallgatóinak (személy szerint is, Dandár Gábornak, Éger Tamásnak, Handki Sándornak, Hasulyó Lászlónak, Szanyi Gergelynek és Szegedi Lászlónak), akik sokat segítettek az anyag csiszolásában, és a jegyzet elkészítésében. Hasonlóan köszönet illeti szakdolgozómat, Tilki Lászlót is, aki a DNS-számítástechnikával kapcsolatban anyaggy¶jtéssel is hozzájárult a jegyzet elkészítéséhez. A jegyzet elkészítésében az OTKA T049409 is segítséget nyújtott.

11

II. fejezet

A Hagyományos Számítási Modell Miel®tt belekezdenénk a nemhagyományos számítások elméletébe, tekintsük át a hagyományosnak, illetve klasszikusnak nevezett Számítástechnika néhány alapvet® jellemz®jét. Els®ként a Turing-géppel és a kiszámíthatóság fogalmának átismétlésével kezdünk. Ezt Alan Turing 1937-ben vezette be a számítási eljárások tanulmányozására.

1.

A Turing-gép

A Turing gép egy absztrakt 'szekvenciális hozzáférés¶' számítási modell amit a számítástudomány ma is használ, és amellyel például az Algoritmuselmélet tantárgy foglalkozik behatóbban. A Turing-gépnek véges sok bels® állapota van. A gép képes rá, hogy egy végtelen hosszúnak tekintett szalagot mozgasson el®re-hátra, mindig egy-egy lépéssel. A gép a szalagról olvashat, és arra írhat is. A szalagon cellák találhatóak, melyekbe a Σ ábécéhez tartozó jelek vannak írva (illetve a speciális # szimbólum szerepel a szalag "üres" celláin). A Turing-gép szalagja végtelen, s mivel ezt bármely irányban mozgatni tudja, a gép (küls®-)memóriája végtelennek tekinthet® (1.1. ábra). A következ® deníció a Turing-gép matematikai megfogalmazása. Az hQ, Σ, δ, q0 , F i rendezett ötöst Turing-gépnek nevezzük, ahol

Q = {q0 , q1 , . . . , qn } a bels® állapotok véges halmaza; Σ = {a0 , a1 , . . . , ar } a szalagjelek véges halmaza; ezek mind az input, mind az output megadására szolgáló jelek; q0 ∈ Q kezd®állapot; F ⊂ Q a végállapotok halmaza; δ átmenet-függvény, amely a Q × (Σ ∪ {#})-t képezi le a Q × (Σ ∪ {#}) × {balra, jobbra, helyben} halmazba (állapotátmenet, szalagjel írás, fej mozgás). Az utolsó halmaz elemei a következ®t jelentik: balra esetén a Turing-gép egyet balra lép, azaz a szalagot eggyel jobbra húzza; jobbra esetén a gép egyet jobbra lép, azaz a szalagot balra húzza; helyben esetén pedig a szalagot nem mozdítja, a gép olvasó-író feje és a szalag helyben marad. 13

14

II. A HAGYOMÁNYOS SZÁMÍTÁSI MODELL

1.1. ábra. A Turing-gép rajza

A Turing-gép a következ®képpen m¶ködik: Eredetileg a q0 állapotban van, és az író-olvasó feje a bemeneti szó els® bet¶jére mutat (vagyis a szalag legbaloldalibb nem # elemére). Valamely qi állapotában olvas egy aj jelet a szalagról. Ennek hatására a δ függvény eredményének els® tagja szerinti ql állapotba kerül, a δ függvény eredményének második tagja szerint az aj helyére egy ak jelet írja a szalagra, valamint lépteti a szalagot, vagy nem mozdítja a δ harmadik tagja szerint. Ha az író-olvasó fej, amely a szalag megfelel® helyér®l olvas, illetve oda ír, éppen pi -re mutat, akkor balra után pi−1 -re fog mutatni, jobbra után pi+1 -re, helyben után pedig pi -re (lásd pl. a 1.2. ábrán ). Megjegyezzük, hogy bár a szalagot mindkét irányban végtelennek tekintjük, mindig csak véges sok #-tól különböz® jel lehet rajta.

II.

A TURING-GÉP

15

1.2. ábra. Egy kétszalagos Turing-gép sematikus rajza A Turing-gép fogalma szorosan összekapcsolódik a "kiszámíthatóság" fogalmával. Turing-géppel mindent (és pont azokat a feladatokat) ki lehet számolni, amit algoritmikusan meg lehet oldani. A Turing-gépnek több változata is ismert. Sokszor az egyszer¶bb leírás kedvéért többszalagos Turing-gépet használunk: (k, Q, Σ, δ, q0 , F ) k -szalagos Turing-gép, ahol k ∈ N természetes szám, ennyi szalagja van a Turing-gépnek; Q, Σ 6= ∅, mint az el®bb, δ : Q × Σk → Q × Σk × {balra, jobbra, helyben}k átmenetfüggvény. M¶ködését tekintve a többszalagos Turing-gép egy lépésben olvashat/írhat egyszerre több szalagra is. Kezd®kongurációban az egyik szalagon (input-szalag) van a feldolgozandó adat, a többi szalag pedig üres. Minden többszalagos Turing-gép m¶ködése szimulálható egyszalagos Turing-géppel, vagyis egyszalagos Turing-gép is el tudja végezni azt a számítást amit egy többszalagos Turing-gép.

16


Megkülönböztethetünk kiszámító és eldönt® Turing-gépeket a következ® deníció alapján. Amennyiben a Turing-gép célja adott függvény kiszámítása a megadott bemen® értékekkel, akkor a gép a megállásakor az (output)szalagon a megfelel® eredményt hagyja. Ezzel szemben vannak olyan számítások, amikor a választ egy igen-nem kérdésre keressük, ezesetben eldönt® Turing-gépr®l beszélünk. Az eldönt® Turing-gépekkel lehet pl. egy L nyelvet elfogadtatni a következ®képpen: bemenet egy v ∈ Σ∗ szó, a Turing-gép számításának eredménye pontosan akkor "IGEN" ha v ∈ L teljesül. A kiszámíthatóság fogalma a számítástudományban másként is megjelenik: a Turinggépekkel elfogadott nyelvek osztálya éppen a rekurzívan felsorolható nyelvek osztályával egyezik meg. Ugyanezt a nyelvosztályt lehet generálni a Chomsky féle generatív nyelvtanokkal (0-típusú nyelvtanok). Ha T egy Turing-gép, v ∈ Σk a számítás id®igényének a tT (v) függvényt nevezzük, mely a következ® alakú: tT (v) = max{n, l(v)} = max{n, k}, ha T az v inputon n lépés után megáll, egyébként pedig ∞. (Itt az l(v) függvény a v szó hosszát adja meg.) Egy konkrét számítási folyamat id®igényének meghatározása után olyan id®igényfogalmat vezetünk be, amely egy egész problémára, és nem csak annak egyes példányaira vontkozik. A tárigényt a bemenet hosszának függvényében fogjuk megadni. Azt mondjuk, hogy egy T Turing-gép id®igénye (legfeljebb) f (n), ha T futási ideje egyetlen n hosszú bementre sem több f (n)-nél. Ha egy f (n) id®igény¶ Turing-gép elfogad egy L nyelvet, akkor azt mondjuk, hogy L ∈ T IM E(f (n)). T IM E(f (n)) egy bonyolultsági osztály, ami tartalmazza azokat a nyelveket, amelyek f (n) id®ben eldönthet®ek. Formálisan tehát a T Turing-gép id®bonyolultsága (maximális id®bonyolultsága): tT (n) = max{tT (w), ahol l(w) ≤ n}. A tárbonyolultság a számítások közben a szalagokon el®forduló leghosszabb sztring. Az eddig leírt Turing-gépek determinisztikus m¶ködés¶ek (ahogy napjaink számítógépei is azok). A Turing-gépeknek nemdeterminisztikus verzióját is szokás használni. A nemdeterminisztikus verzióban a δ 'függvény' tulajdonképpen nem egyértelm¶en adja meg az új állapot, új szalagjel, fejmozgás hármas(oka)t (vagyis a δ nem függvény). Itt a kiszámíthatóságot úgy deniáljuk, hogy van olyan számítási sorozat amely az eredményt szolgáltatja. Számítási 'erejét' tekintve a nemdeterminisztikus verzió sem tud többet a determiniztikus változatoknál, vagyis minden ami nemdeterminisztikusan kiszámítható kiszámítható determinisztikusan is. (A másik irány triviális.) A nemdeterminisztikus változat számítási sebessége, hatékonysága viszont lehet jobb a determinisztikusénál. Ez azt jelenti, hogy pl. 'találgatással' hamarabb találhatunk megoldást. A következ® részben egy kicsit kitekintünk arra, hogy milyen problémák milyen költséggel oldhatók meg determinisztikus, illetve nemdeterminisztikus Turing-gép segítségével.

II.

A TURING-GÉP

17

1.1. Bonyolultsági osztályok Ebben a részben néhány fontos bonyolultsági osztályt említünk meg, pl. a polinomiálisan megoldható és bonyolultabb problémák, a P, NP, PSPACE problémaosztályait. A bonyolultsági osztályok meghatározásához szükségünk lesz a számítási módra, amely lehet determinisztikus vagy nemdeterminisztikus. Ezenkívül arra, hogy mely er®forrást (id®, tár: szalag) korlátozzuk. Mint az el®z® részben bevezettük, a determinisztikus módon, f (n) id®korlátozással számoló Turing gépekkel kiszámítható nyelvek a T IM E(f (n)) bonyolultsági osztályt alkotják. Általában az f (n) nemnegatív egészekhez nemnegatív egészeket rendel® függvényt®l megköveteljük, hogy monoton növekv® legyen. Ha f (n) = c egy c ∈ N konstansra, akkor a nyelv bármely v szavát maximum l(v) + c lépésben eldönti a T Turing-gép. Szokásos a lineáris függvény (f (n) = cn), illetve az n tetsz®leges polinómjának használata (ahol n a bemeneti szó hossza). Azon nyelvek (problémák) unióját, amelyekhez van olyan determinisztikus Turing-gép, ami a ezek szavait valamilyen polinomfüggvénnyel megadható id®ben eldönti (kiszámítja), P bonyolultági osztálynak nevezzük. Legyen most T egy nemdeterminisztikus Turing-gép. Azt mondjuk, hogy T f (n) id®ben eldönti/felismeri az L nyelvet, ha bármely v ∈ L szóval indítva a kezd®kongurációból van olyan számítás, amely elfogadja v -t legfeljebb f (n) lépés után (n = l(v)). Azon nyelvek unióját, amelyekhez van olyan nemdeterminisztikus Turing-gép, ami a ezek szavait valamilyen polinomfüggvénnyel megadható id®ben eldönti (kiszámítja), NP bonyolultági osztálynak nevezzük. A számítógéptudomány egyik legfontosabb eddig sem nem bizonyított, sem nem cáfolt problémája a P és NP bonyolultsági osztályok viszonyának eldöntése, vagyis mivel P ⊆ NP, ezért a kérdés P ≡? NP alakba írható. Általában elfogadott az a feltételezés, hogy a két osztály nem egyezik meg, egyel®re azonban nem ismert olyan feladat (nyelv) ami NP-ben van és bizonyítottan nincs P-ben. Minden NP-beli nyelvre (problémára) igaz, hogy minden szavára létezik egy 'tömör bizonyíték' (ami polinomiális id®ben ellen®rizhet®), hogy az adott szó benne van a nyelvben. Azokra a szavakra, amelyek nem elemei a nyelvnek nincs ilyen bizonyíték. Az NP osztály rengeteg természetes és a gyakorlatban is fontos számítási problémát tartalmaz. Például sok tervezési probléma (utak, kiértékelések, egyenletek megoldásai, VLSI tervrajzok) ilyen. Amikor optimális (egy adott feltételt kielégít®) megoldást keresünk, akkor a keresett objektum maga lesz a bizonyíték. Ezek a bizonyítékok gyakran zikai objektumok vagy azok matematikai absztrakciói, amelyek nem túl nagyok a probléma méretéhez képest és a feltételek is gyakran polinomiális id®ben ellen®rizhet®ek. Azokat a problémákat nevezzük NP-teljesnek, amelyek legkevésbé feltételezhet®ek, hogy egyben P-beliek is. Egy L problémát NP-teljesnek nevezünk, ha abból, hogy L ∈ P az következik, hogy P = NP. Ez az jelenti, hogy ha valaki determinisztikusan polinomiális id®ben tud megoldani egy NP-teljes problémát, akkor minden NP-beli problémát meg lehet oldani polinomiális id®ben determinisztikusan is.

18


1.3. ábra. A fontosabb bonyolultsági osztályok hierarchiája További fontos bonyolultsági osztályok a • PSPACE: determinisztikus Turing-géppel polinomiális szalagigénnyel kiszámolható problémák osztálya; • NPSPACE: nemdeterminisztikus módon polinomiális szalagigénnyel kiszámolható problémák osztálya; • EXP: determinisztikusan exponenciális id®ben kiszámolható problémák osztálya. A 1.3 ábrán a fent említett bonyolultsági osztályok egymáshoz képesti viszonya látható. A következ® alfejezetekben két széles körben ismert NP-teljes problémát ismertetünk.

1.1.1. A SAT probléma megfogalmazása. A SAT probléma alapvet® szerepet játszik a bonyolultságelméletben, ugyanis ez az egyik legismertebb NP-teljes probléma. A feladat maga röviden a következ®: adott egy propozicionális logikai formula, döntsük el, hogy kielégíthet®-e (vagyis lehet-e a propozicionális változóknak értéket adni úgy, hogy a formula igaz legyen). A feladatnak többféle speciális megfogalmazása is létezik, és használt mind az elméletben, mind a gyakorlatban. Az els® speciális alak, amikor a formula konjunktív normál formában adott. A feladat így is NP-teljes. A következ®, még speciálisabb alak, amikor a konjunktív normál forma mellett az is adott, hogy az egyes tagok hány

II.

A TURING-GÉP

19

literált tartalmaz(hat)nak. A feladat ilyen megszorítással történ® megfogalmazását nevezik n-SAT problémának. Az n-SAT n ≥ 3 esetén NP-teljes, míg a 2-SAT probléma P-beli. A tömör bizonyíték ezesetben egy kielégít® kiértékelés, amely megadja mely Booleváltozó értéke legyen igaz és melyek legyenek hamisak.

1.1.2. A Hamilton-út probléma megfogalmazása. A Hamilton-út probléma

a gráfelmélet egyik legismertebb NP-teljes problémája. Adott egy n csúcsú (irányított) gráf. A feladat, hogy megadjunk egy olyan élsorozatot, utat (vagy azt hogy van-e ilyen a gráfban), amely a gráf minden csúcsát pontosan egyszer tartalmazza és benne (az els® kivételével) minden él onnan indul, ahova az el®z® él érkezett. Az ilyen típusú utat hívjuk Hamilton útnak. Semmilyen egyszer¶ feltétel nem ismert ilyen út létezésének eldöntésére (szemben pl. az Euleri út problémájával, ahol minden élnek pontosan egyszer kell az útban szerepelnie). Ezesetben a polinomiálisan ellen®rizhet® bizonyíték magának egy Hamilton-útnak a megadása.

1.2. Univerzális Turing-gép Ebben a részben visszatérve a Turing-gépekhez, azoknak egy speciális fajtájával, az ún. univerzális Turing-géppel fogunk foglalkozni. Az univerzális Turing-gép többféleképpen is megadható, mi itt most az egyik ilyen megvalósítással fogunk foglalkozni. A k szalagos U Turing-gépet univerzálisnak nevezzük az l szalagos Turing-gépek halmazára nézve, ha minden l szalagos T Turing-géphez van olyan v ∈ Σ∗ , hogy minden s ∈ Σ∗ -ra a T futásának eredménye az s inputon megegyezik az U futásának eredményével a v#s inputon. A # jelet hashmark-jelnek nevezzük. A T 'programja' v (az U nyelvén), s pedig egy tetsz®leges szó. Ha T az s inputot kapja, akkor ugyanazt csinálja, mint U a v programmal az s-en. Az k szalagos Turing-gépek halmazához van k + 1 szalagos univerzális Turing-gép. Viszont azt is tudjuk, hogy minden egyes többszalagos Turing-géphez van egyszalagos amely szimulálja. Tehát van egyszalagos univerzális Turing-gép. Az univerzális Turing-gép tulajdonképpen egy általános elvont számítógép, ami minden Turing-gépet képes szimulálni, vagyis elvileg a programjának megfelel®en feldolgozni az input szót. Ez azt jelenti, hogy van olyan gép, ami minden kiszámítható függvényt ki tud számolni. Az alábbiakban egy példát adunk az univerzális Turing-gépre. Tulajdonképpen a δ átmenetfüggvényt kell megadnunk ami a Q × (Σ ∪ {#}) véges doménen és a Q × (Σ ∪ {#}) × {balra, jobbra, helyben} véges értékkészleten van értelmezve, illetve egy másik Turing-gép leírásának (program) kódolását. Legyen M valamilyen Turing-gép, melynek n darab bels® állapota van, és a szalagábécéje m bet¶t tartalmaz. Tegyük fel, hogy M-et kódolt formában adtuk meg (az [M] jelölést ). A továbbiakban vázlatosan ismertetjük, hogy hogyan tudjuk modellezni M

20


m¶ködését egy U univerzális Turing-géppel. Tegyük fel, hogy M a v inputon dolgozik. El®ször azt kell megadnunk, hogy adott [M] és [v] esetén ezeket az információkat miképpen tároljuk az U szalagján (azaz mi lesz U kezd®kongurációja), majd pedig azt, hogy ezek hatására U hogyan fog m¶ködni. Jelöljünk ki a szalagon egy mez®t, és írjunk ebbe a mez®be egy rögzített X jelet a szalagábécéb®l. A szalagnak a kiválasztott mez®t®l jobbra es® felét három részre osztjuk. Az els® részt nevezzük puerterületnek; ez közvetlenül az X jel után kezd®dik, legalább n+m+2 mez®t tartalmaz, és ezek mindegyikébe 0 van írva. A puerterülett®l jobbra es® szalagrész legels® mez®jébe egy Y jelet teszünk a szalagábécéb®l, utána beírjuk M kódolt formáját, [M]-et, három 0-t téve a végére. A szalagnak ezen részét nevezzük M kódolási területének. A harmadik rész a második részt®l jobbra helyezkedik el. Az els® mez®jébe egy rögzített Z jelet írunk a szalagábécéb®l, majd a v bemeneti szó [v] kódolása következik. A szalagnak e három részen kívül es® mez®i üresek. A puerterület arra szolgál, hogy mialatt M valamelyik lépését szimuláljuk, ide másolhassuk M pillanatnyi bels® állapotának, illetve az éppen leolvasott M-beli szalagjelnek a kódját. Az Y jel általában az el®tt a rendezett ötös el®tt fog állni, amely azt határozza meg, hogy milyen bels® állapotban van M, milyen szalagjelet olvasunk éppen, mivel kell ezeket kicserélni (új állapot és új szalagjel), s eközben milyen irányban mozduljon el M olvasófeje a szalagon. A Z jel az M szalagjára felírt jelek közül jelöli ki azt, amelyiket éppen olvasunk. Az U-ban lezajló számítási folyamatot, mellyel az M Turing-gép m¶ködését szimuláljuk az v bemeneti szóval, olyan szakaszokra bonthatjuk, melyek sorra megfelelnek az M egyes kongurációi közötti átmeneteknek. Az U m¶ködésének egy ilyen szakasza az alábbi módon zajlik le. Az U univerzális Turing-gép el®ször a puerterület elejére másolja azt az 1-esekb®l álló blokkot, amely közvetlenül az Y jel után következik - nevezzük ezt Y -blokknak -, majd a végére odaír még egy X jelet. Ezután kitörli Y -t, és jobbra haladva megkeresi a Z -t tartalmazó mez®t. Amikor ezt megtalálta, akkor a Z után következ® 1-esekb®l álló blokkot (Z -blokkot) is átmásolja a puerterületre az el®bb beírt második X jel után, majd visszaírja Y -t az M kódolt leírása, [M] elé. Így a puerterületre az aktuális bels® állapot és a szalagról éppen beolvasott jel kódja került. A következ® lépésekben U az Y jel után következ® két 1-es blokkot hasonlítja össze a puerterületen lev®kkel. Ezáltal azt ellen®rzi, hogy az M gép soron következ® kongurációátmenetét az a rendezett ötös határozza-e meg, amelynek kódja az Y jel után van leírva. Ha a blokkok megegyeznek, ez azt jelenti, hogy megtaláltuk a keresett ötöst. Ha nem, akkor U áthelyezi az Y jelet a következ® rendezett ötös kódolása elé, majd újrakezdi a blokkok összehasonlítását. Abban az esetben, ha az M leírásában szerepl® ötösök közül egyik sem felel meg, U leáll a m¶ködésével (az eredeti M is ugyanezt tenné a v inputra). Ha viszont megtaláljuk a keresett ötöst, akkor U kitörli a puerterületet, majd az Y jelet átteszi az ötösben szerepl® harmadik elem elé. Ezután kicseréli a Z után következ® blokkot az Y utáni blokkal, majd Y -t jobbra mozdítja el a rendezett ötös negyedik elem elé. Miután U leolvasta ezt a negyedik elemet is, mely az M olvasófejének elmozdulási irányát határozza meg, U átteszi a jelet az elem mögé, az ötödik elem elé. Attól függ®en, hogy a negyedik blokkban két vagy csak egy darab 1-est talált-e, az U egy blokkal jobbra vagy egy blokkal balra tolja el Z -t. Ha Z eredetileg a szalagszó bal szélén volt, és M-nek balra

II.

A NEUMANN-ELV

21

kellett lépnie, akkor U a szó kódolását jobbra tolja, és egy üres mez® kódjelét írja be a Z után. Ha pedig Z a szalagszó jobb szélén állt, s jobbra kellene elmozgatni, akkor U a szó végére írja egy üres mez® kódját. Amikor tehát mindezzel végeztünk, az Y jel után álló 1-es blokk az M aktuális bels® állapotát jelzi, a Z utáni blokk pedig azt a szalagjelet, amelyet M-nek a következ® lépésben be kellene olvasnia. Minden készen áll tehát arra, hogy az M következ® lépését szimuláló szakasz megkezd®dhessen. Az U m¶ködésének egyes szakaszai így M egy-egy lépését modellezik. U ezeken kívül még a következ®ket hajtja végre: a munka legelején a szalag mindhárom részében a 0-kat a saját üres-jeleire cseréli, a munka végeztével pedig, olyankor, amikor M leállna, U még ellen®rzi, hogy M-nek végállapota-e az az állapot, amelyben megállt, és ett®l függ®en kerül saját maga is végállapotba, ill. nem végállapotba. Minden Turing-gép m¶ködése szimulálható olyan Turing-géppel, amiben a szalagábécé bináris, vagyis Σ = {0, 1}. Az Univerzális Turing-gép létezése azt mutatja, hogy elvileg konstruálható olyan számítási eszköz, amely programozható és mindent ki tud számítani, ami kiszámítható. A gyakorlati megvalósulás felé a következ® lépés a Neumann elv, amit a következ® fejezetben ismétlünk át. Az absztrakt számítógép után lássuk a valódi gépek milyen elven m¶ködnek.

2.

A Neumann-elv

A hagyományos számítógépek atyjának tekinthetjük Neumann Jánost, aki sok más tudományos tevékenysége mellett, a klasszikus számítógépek m¶ködésének alapelveit is megadta. Ezek az elvek, amelyeknek megfelel®en épült a legtöbb számítógép, a következ®ek: • A tárolt program elve: A programot alkotó utasítások kifejezhet®k számokkal, azaz adatként kezelhet®k. Ezek a bels® memóriában tárolhatók, mint bármelyik más adat. Ezáltal a számítógép önállóan képes m¶ködni, hiszen az adatokat és az utasításokat egyaránt a memóriából veszi el®. A memória a numerikus adatokkal együtt tárolja a programot is, a vezérl®egység pedig végrehajtja az utasítások sorozatát. • Kettes számrendszer használata, és a számítógép legyen teljesen elektronikus: A kettes számrendszert és a rajta értelmezett aritmetikai ill. logikai m¶veleteket könny¶ megvalósítani kétállapotú áramkörökkel (pl.: 1- magasabb feszültség, 0 - alacsonyabb feszültség) • A számítógép legyen soros m¶ködés¶: A gép az egyes utasításokat egymás után, egyenként hajtsa végre. • A számítógépnek legyen bels® memóriája: A számítógép gyors m¶ködése miatt nincs lehet®ség arra, hogy minden egyes lépés után a kezel® beavatkozzon a számítás menetébe. A bels® memóriában tárolhatók az adatok és az egyes számítások részeredményei, így a gép bizonyos m¶veletsorokat automatikusan el tud végezni.

22


• A számítógép legyen univerzális: A számítógép különféle feladatainak elvégzéséhez nem kell speciális berendezéseket készíteni. Ugyanis Turing bebizonyította, hogy az olyan gép, amely el tud végezni néhány alapvet® m¶veletet, elvileg bármilyen számítás elvégzésére is alkalmas (Turing-gép).

3.

Hagyományos számítógépek

Ebben a részben röviden átfutjuk hogyan valósul meg a Neumann elv a gyakorlatban. A számítógéparchitektúrák alapjaival kapcsolatban a bitekr®l és a bájtokról valamint az ezeken az aritmetikai és logikai egység (ALU) által végzett operátorokról (m¶veletekr®l) lesz szó. A hagyományos számítógépek a klasszikus propozicionális logikára épülnek (nagyban köszönhet® ez a kettes számrendszer használatának).

3.1. A klasszikus logika A klasszikus logikában a formulák kijelentéseket szimbolizálnak. Ezek igazságértéke kétféle lehet: igaz, illetve hamis. Szokás ezeket az 1, illetve a 0 számértékekkel jelölni. Az úgynevezett atomi kijelentéseket logikai összeköt®jelekkel köthetjük össze, ezzel bonyolultabb, összetett kifejezést kapva. Lássuk most a klasszikus logika összeköt®jeleit. 1. táblázat. Az alapvet® logikai operátorok igazságtáblája Név Jel érték

Els® változó A 0 0 1 1

Második változó B 0 1 0 1

negáció

konjunkció diszjunkció implikáció

¬A 1 1 0 0

A∧ B 0 0 0 1

A∨ B 0 1 1 1

A→B 1 1 0 1

A többi logikai összeköt®jel a 1 táblázatban felsorolt alapvet® logikai operátorokkal deniálható, pl. a következ® módon: ekvivalencia: A ≡ B =def (A → B) ∧ (B → A), 'xor': A ⊕ B =def A ≡ ¬B , 'nand': A&B =def ¬A ∨ ¬B , 'nor': A|B =def ¬A ∧ ¬B .) Valójában ezek a logikai összeköt®jelek annyira nem függetlenek egymástól, hogy pl. a 'nor' vagy a 'nand' egymagában elegend® ahhoz, hogy minden mást deniáljunk vele. (A 'nor' m¶veletet szokás Sheer-vonásnak is nevezni H. Sheer után, aki 1913.ban megjelent cikkében bizonyította, hogy ez a m¶velet önmagában elegend® minden

II.

HAGYOMÁNYOS SZÁMÍTÓGÉPEK

23

logikai formula felírásához. A számítógépek chipjein hagyományosan egyféle logikai kaput szoktak használni, ez pedig a 'nand' kapu, mely ugyancsak univerzális.)

3.2. Bitek és bájtok Az információelméletben a bit az információ alapegysége, egy eldöntend® (igennem) kérdésre adott válasz. A számítógépekben általában egyszerre több bitnyi információt tárolunk és dolgozunk fel. A 80-as években a 8 bites számítógépek terjedtek el (pl. Commodore 64), amiket a 90-es években a 16 és a 32 bites gépek követtek. Napjainkban terjednek el a 64 bites architektúrák. Az, hogy egy számítógép 'hány bites' egy fontos jellemz®je a gépnek, minél nagyobb ez az érték, annál fejlettebb, jobb a számítógép. A logikai operátorok bitenként hajtódnak végre a bájt összes helyiértékén egymástól függetlenül (2. táblázat). 2. táblázat. Az alapvet® logikai operátorok m¶ködése egy bájton (bitek sorozatán), ahol minden xj és yi bit értéke a {0, 1} halmazból való A értéke

x1

A negáltja

B értéke

x2 . . . xn ¬x1 ¬x2 . . . ¬xn y1

y2 . . . yn

A és B konjunkciója x1 x2 . . . xn ∧ ∧ ... ∧ y1 y2 . . . yn

A és B diszjunkciója x1 x2 . . . xn ∨ ∨ ... ∨ y1 y2 . . . yn

Arithmetikai operátorok: a shift (eltolás), tulajdonképpen 2-vel való szorzás és osztás m¶veletének felel meg. 3. táblázat. A shift operátor hatása egy bájtra A bináris kódban x1 x2 . . . xn

left-shift A x2 x3 . . . xn 0

right-shift A 0 x1 x2 . . . xn−1

Az összeadás operátora az egyik legfontosabb m¶velet, tulajdonképpen szinte minden számítási m¶velet erre van visszavezetve. Az összeadást (add) hagyományosan logikai áramkörökkel szokták megvalósítani. Legyen Cn = An ∧ Bn . Ezutén: Ci = (Ai ∧ Bi ) ∨ (Ai ∧ Ci+1 ) ∨ (Bi ∧ Ci+1 ). (n > i ≥ 1) Az eredmény bitjei: Rn = An ⊕ Bn , és Ri = (Ai ⊕ Bi ) ⊕ Ci+1 . (n > i ≥ 1), valamint C1 jelenti a túlcsordulást (túlcsordulás bit). Ahogy láttuk a logikai m¶veletek bitenként párhuzamosan hajtódnak végre (ez végülis már valamiféle párhuzamosságot jelent, ezért tarjuk fejlettebnek azokat a számítógépeket, amelyekben több bit alkot egy bájtot, mint azokat amelyekben kevesebb), míg az aritmetikai operátoroknál általában a környez® bitek értékei is szerepet játszanak az eredmény bitjeinek kialakulásában.

24


4.

Néhány nem-hagyományos elv¶ algoritmus

Azért, hogy elszakadjunk a hagyományos értelemben vett "algoritmikus" gondolkodásmódtól mutatunk néhány olyan rendezési algoritmust, ami alapjában véve tér el a tanult rendezési módszerekt®l (beszúrásos-, buborékos-, legkisebb kiválasztásos-, gyorsrendezés, stb.).

4.1. A Spagetti-számítógép rendezési algoritmusa Legyenek adva különböz® hosszúságú rudak ('spagettik'). A feladat az, hogy rendezzük ®ket hosszuk szerint sorrendbe. Ahelyett, hogy mindig egy-egy elemet hasonlítanánk össze egy másikkal (mint a hagyományos rendezési algoritmusoknál), az összeset egy kötegnek tekintjük: kézbe vesszük, és az asztalra állítjuk ®ket. (Lásd a 4.4. ábrát.) Így ránézésre (egy méréssel) ki tudjuk választani közülük a legnagyobbat. Ezt kiemeljük, s a maradékot újra egy kötegnek tekintjük. Így n elem esetén a rendezést n lépésben, azaz lineáris id®ben hajthatjuk végre szemben a hagyományos algoritmusok általában négyzetes id®bonyolultságával.

4.2. Rendezés a gravitáció segítségével Most egy újabb rendezési algoritmust mutatunk be, ami egy mindennapi zikai jelenségen, a gravitáción alapul. Legyenek most adva a(z egész) számok, mint különböz® hosszúságú kockacukor csíkok. A feladat az, hogy mondjuk meg a csíkok hosszait pl. csökken® sorrendben. A rendezés során a gravitációt használjuk fel. Tegyük a csíkokat egymás fölé közös kezd®ponttal. Ha az alakzatokat elengedjük, a nagyobb számokat jelent® csíkok kockacukrai behullanak a rövidebb csíkoknál lev® lyukakba. Így a rendezés végére egy piramisszer¶ alakzatunk lesz, benne minden olyan szám szerepel (és ugyanannyiszor), mint az eredetiben. (Lásd pl. a 4.5 ábrán.)

II.

NÉHÁNY NEM-HAGYOMÁNYOS ELV ALGORITMUS

25

4.4. ábra. A spagetti rendezés: egy csoportos összehasonlítással kiválasztható a leghosszabb elem

26


4.5. ábra. A 'gravitációs' rendezés

III. fejezet

DNS Számítások Az élet egyik alapvet® molekulája a dezoxiribo-nukleinsav, röviden DNS. A most következ® fejezetben megnézzük hogyan foghatóak számításokra ezek a molekulák, amikkel a természet évmillió évek óta "számítja ki az él®lényeket". A molekuláris genetika és ennek köszönhet®en a DNS-számítások is forradalmi és új területei a tudománynak.

1.

A DNS

El®ször is nézzük a DNS felépítését. A nukleinsavak nukleotid egységekb®l álló polimerek. Mindegyik nukleotidban foszfátcsoport, cukor és egy purin vagy pirimidin bázis (lapos, gy¶r¶ alaku, szént (C) és nitrogént (N) tartalmazó molekula) van. A nukleotidok csak ezekben a bázis okban különböznek egymástól. Amikor sok nukleotid összekapcsolódik, polinukleotid keletkezik. A DNS-ek felépítésében négy nukleotid vesz részt: ezek az adenin, a citozin, a guanin és a timin. Lásd a 1.1., 1.2, 1.3 és 1.4 ábrákat, amelyeken a négyféle nukleotid bázisának kémiai felépítését mutatjuk be; a szén és nitrogén atomok számozva szerepelnek.

1.1. ábra. Az Adenin bázisának szerkezeti felépítése

Az 1.5. ábrán az adenin molekula látható (a szén atomok nincsenek jelezve külön az ábrán), minden bázishoz ugyanígy kapcsolódik a cukormolekula és a foszfát-csoport. 27

28

III. DNS SZÁMÍTÁSOK

1.2. ábra. A citozin bázisának felépítése

1.3. ábra. A guanin bázisának kémiai felépítése Szokás a cukor szénatomjait a bázistól kezd®d®en számozni: így az oxigén az 1. és 4. szénatomot kapcsolja össze, a foszfát-csoport pedig az 5. szénhez kapcsolódik. Egy DNS molekula tehát egy bázisból, egy cukor molekulából és a foszfát-csoportból áll, ez sematikusan a 1.6 ábrán látható. Az 1940-es évek végén már valószín¶síthet® volt, hogy a DNS olyan rendszeresen ismétl®d® szerkezeti egységekb®l áll, amelyekben mindegyik bázis ismétl®dik a lánc mentén. Még érdekesebbnek t¶nt a a felvetés, hogy igen sokféle DNS molekula létezhet, s mindegyik sajátos bázissorrenddel jellemezhet®. Ma már tudjuk, hogy ez az a mód, ahogyan a DNS molekulák felépülnek, s a DNS változatos bázissorrendjében hordozza azt a hatalmas (genetikai) információmennyiséget, ami az él®világban található fehérjék igen sok lehetséges aminosavsorrendjének tárolásához szükséges. Az 1950-es évek elején a Cambridge-i Egyetem Kémiai Laboratóriumában dolgozó kutatócsoport

III.

A DNS

29

1.4. ábra. A timin molekula bázisa

meghatározta a nukleotidokat összekapcsoló pontos foszfátészterkötéseket. Az eredmény meglep®en egyszer¶ volt. Ezek a kötések mindig ugyanolyanok voltak: a foszfátcsoport a dezoxiribóz, a cukor 5' szénatomját köti a következ® nukleotid cukrának 3' szénatomjához (kovalens kötéssel) (1.7. ábra). A cukor és a foszfátcsoportok közötti foszfodiészter-kötések képezik a DNS gerincét. Az egyszálú DNSben a nukleotidok összekapcsolódnak egymással, mégpedig úgy, hogy az egy adott molekula cukrának 5' része kovalens kötéssel kapcsolódik az el®z® molekula cukrának 3' szénatomjához, amíg 5' része szintén kovalens kötéssel a következ® molekulához. Amikor a nukleotidok összekapcsolódnak ily módon minden egyen 3' szénatomnál egy-egy vízmolekula (H2 O) keletkezik. Tehát a DNS polinukleotidláncai, a fehérjék polipeptidláncaihoz hasonlóan, szigorúan lineáris molekulák. Kromatográás elválasztási módszereket alkalmazva vizsgálták a purin és pirimidin bázisainak mennyiségét. 1951-re már nemcsak az volt ismeretes, hogy a négy bázis nem egyenl® mennyiségben van jelen, hanem nyilvánvaló volt az is, hogy mennyiségük igen változó. Azt is felfedezték, hogy a négy bázis mennyisége nem egymástól függetlenül változik; minden egyes vizsgált fajban az adenin purin mennyisége majdnem vagy tökéletesen pontosan megegyezik a timin pirimidinével. Hasonlóképpen, a másik purin, a guanin mennyisége mindig nagyon hasonló vagy azonos volt a másik pirimidin, a citozin mennyiségével. A purinok száma a DNS-ben így megközelít®en egyenl®nek mutatkozott a pirimidinekével. Egy vonatkozásban a DNS nagyon szabályos: ismétl®d® cukor- (dezoxiribóz-) foszfát csoportokat tartalmaz, amelyek mindig pontosan ugyanazzal a kémiai kötéssel kapcsolódnak. Ezek az azonos, ismétl®d® csoportok alkotják a DNS gerincét. Másrészt a DNS négy különböz® bázisa valamilyen rend szerint kapcsolódhat a gerinc mentén, és ez a variabilitás adja a DNS-molekulák nagyfokú egyediségét. Központi kérdés volt a molekula 3 dimenziós szerkezete is, melyet röntgen-dirakciós eljárással próbáltak meghatározni el®ször 1938-ban. A vizsgálatok megmutatták, hogy a DNS cukor-foszfát gerince spirális kongurációt mutat, illetve a spirál átmér®jének a méréséb®l kiderült,

30


1.5. ábra. Az adenin: a bázis a cukor és a foszfát csoport szerkezete és kapcsolódásának módja

hogy az túl nagy volt egy olyan molekulához, amely csak egy láncból áll. A DNS alapvet® egységének így két, összetekeredett láncból kellett állnia (1.9. ábra), de ellenkez® irányú szállefutással. A kétszálú DNS-láncok felépítésében aéapvet® szerepet játszik a Watson-Crick komplementaritás. James D. Watson és Francis H. C. Crick 1953-ban bizonyították a DNS kett®s-spirál felépítését, és ezért a feéfedezésükért Nobel-díjban részesültek.

1.1. Watson-Crick párok Mérési eredmények szerint a DNS-ben az adenin mennyiség közel azonos a timin mennyiségével, míg a guaniné a citozinnal. Watson és Crick ismerték ezeket az eredményeket, mégis sokáig nem vették gyelembe. Egyszer¶en nem tartották fontosnak

III.

A DNS

31

1.6. ábra. Nukleotid sematikus rajza valamilyen B bázissal a DNS szerkezete szempontjából. Amíg a m¶helyben készültek a bázismodellek, Watson azokat kartonból kivágta és elkezdte tologatni. E közben hirtelen rádöbbent, hogy az adenin-timin pár, amelyet két H-kötés tart össze, azonos formájú a legalább két H-kötéssel összetartott guanin-citozin párral. Ekkor jutottak eszébe a mérési eredmények. Így már adta magát a DNS molekuláris szerkezete: a cukor-foszfát-gerinc a molekula küls® részén van, a purin és a pirimidin bázisok pedig belül; olyan módon, hogy az ellenkez® oldalon lév® bázissal H-hidat alakíthassanak ki. Ugyanolyan fontos az is, hogy az adenin és a guanin purinok nem válogatás nélkül kapcsolódhatnak a két pirimidinhez, a timinhez és a citozinhoz. Az adenin csak a timinhez, a guanin viszont csak a citozinhoz tud köt®dni (lásd a 1.10. ábrát). A nukleotidmolekulák (báziaik segítségével) tehát (komplementer-) párokat alkotnak, az adenin kett®s hidrogén kötéssel kapcsolódhat (és a kétszálú DNS-ban kapcsolóik is) a timinhez, míg a guanin hármas hidrogén kötéssel a citozinhez. Ezeket a párokat nevezzük Watson-Crick pároknak a felfedez®ik után. Amikor nem érdekel minket a nukleotid felépítése használhatjuk például a következ® sematikus ábrákat (1.11., 1.12., 1.13 és 1.14. ábrák) a Watson-Crick komplementaritásnak megfelel®en. A nukleotidokra ezentúl általában kezd®bet¶jükkel hivatkozunk: A, C, G és T. A 1.15. ábrán láthatjuk a kett®s-spirál szerkezetet megfelel® (komplementer) bázispárokból felépítve. Sematikusan, két-dimenzióban ezt a 1.16. ábrán látható módon ábrázolhatjuk, ahol a szerepl® B bázisokra a Watson-Crick komplementaritásnak kell teljesülnie. Tehát a kétszálú DNS lét darab egyszálú DNS-b®l áll, amik a bázisokból alkotott Watson-Crick párokon keresztül kapcsolódtak össze hidrogén kötéssel. Mindegyik bázispárnak a szimmetriája lehet®vé teszi, hogy a kett®s spirálba kétféle módon illeszkedjék be (A=T; T=A; G≡C; C≡G); így bármely adott DNS-lánc mentén mind a négy bázis minden lehetséges sorrend¶ permutációban létezhet. Emiatt a specikus bázispárképzés miatt, ha ismerjük az egyik szál szekvenciáját (pl. TCGCAT),

32


1.7. ábra. A nukleotidokból a foszfodiészter kötéssel egyszálú DNS lánc épül fel

III.

A DNS

33

1.8. ábra. Az egyszálú DNS lánc sematikus rajza

1.9. ábra. A DNS molekula kett®sspirál alakú akkor a másik szálét is tudjuk (AGCGTA). A szemben lév® sorrendet komplementernek nevezzük és a megfelel® polinukleotidpartnert komplementer szálnak. Ha van egy egyszálú DNS-ünk, akkor az felírható a bázisokkal. Mivel a szerkezet lineáris láncnak tekinthet®, egyszer¶en felsoroljuk ®ket sorban, de még így is kétfajta sorrend lehet, mert olvashatjuk 5'-t®l a 3' felé és fordítva, ezért a felírásnál meg kell adni az olvasási sorrendet. Ha nem adunk meg mást akkor 5'-t®l 3' irányig lesz az alapértelmezés. A kétszálúnál is hasonlóan lehet eljárni, és elég az egyik szálat leírni, mivel a másik ennek a komplementere.

34


1.10. ábra. A citozin és a guanin bázisai közt háromszoros hidrogénkötés alakulhat ki

1.11. ábra. Az adenin sematikus jelölése

1.12. ábra. A citozin sematikus rajza

1.13. ábra. A guanin sematikus ábrája

Pl.:

5' 3' TCGCAT AGCGTA

III.

ALAPMVELETEK A DNS LÁNCOKKAL

35

1.14. ábra. A timin sematikus rajza

2.

Alapm¶veletek a DNS láncokkal

Ebben a fejezetben áttekintjük milyen m¶veleteket végezhetünk a DNS láncokkal, milyen utasításokból kell a DNS gép programját felépíteni. A kísérletek során az úgynevezett (molekuláris) levessel dolgoznak a kutatók, ami általában olyan vizes oldat, ami a DNS molekulákon kívül tartalmazhat különböz® enzimeket, katalizátorokat. Fromális szempontból az ilyen molekuláris levest egyszálú és kétszálú DNS molekulák multihalmazának tekintjük. (Általában tekinthetjük halmaznak is, feltételezve, hogy mindenféle molekulából elegend®en sok áll rendelkezére. Ez a gyakorlatban elterjedt eljárások során valójában nem jelent megszorítást, ahogy látni fogjuk.)

2.1. Denaturálás A DNS molekula komplementer párjai közötti hidrogén-kötés másodrend¶ kötés, jóval gyengébb, mint az egyszeres láncokon belüli foszfodiészter kötés (els®rend¶ kovalens kötés). Az egyes bázispárokat könnyebben el lehet választani egymástól. Erre az egyik megoldás a molekula melegítése - denaturáció -, amelynek hatására a molekula két összekapcsolódott lánca különválik egyszeres DNS láncokat eredményezve.

2.2. Renaturálás vagy hibridizáció Az egyszeres láncok a h¶tés hatására újra összekapcsolódhatnak (rekombinálódnak), vagy más egy szálú DNS-el új kétszálút hozhatnak létre. (Természetesen a Watson-Crick komplementaritás gyelembe vételével). Tehát az egyszeres láncok duplaszálú DNS-sé állhatnak össze. Mint kés®bb látni fogjuk ebben a lépésben fontos szerepet játszhat a ligáz enzim. Az el®z® két m¶velet tulajdonképpen implicit részm¶velet, valójában összetettebb m¶veletekben fogjuk ®ket általában használni.

2.3. Szintetizálás Ha még nincs DNS láncunk, akkor gyakorlati módszerek vannak arra, hogyan állíthatunk el®. Egyszálú DNS láncot szintetizálhatunk vagyis, meseterségesen el®állítunk (felépíthetünk), bármilyen bázissorendben néhány 100 nukleotidot tartalmazó méretig. Ezt a m¶veletet hívjuk szintetizálásnak.

36


1.15. ábra. A DNS lánc két spirálját a bázisok közti H-kötések tartják össze

2.4. Sokszorozás Fontos probléma, hogy hogyan er®síthatjük meg a kis mennyiség¶ számunka fontos DNS molekula jelenlétét a hatalmas mennyiség¶ számunkra nem fontos darab között.

III.


37

1.16. ábra. A két szál sematikusan

Az erre szolgáló technikát polimeráz láncreakció nak nevezzük. Segítségével milliószámra lehet el®állítani a kívánatos molekulákat egyetlen molekulából. Ez egy összetett m¶velet, ami arra szolgál, hogy a kívánt kétszálú DNS-láncokból elég sok legyen jelen a levesben. Ennek egyik lépése a denaturálás ami során megfelel® egyszálú DNS láncaink jönnek létre. Az oldatban lev® nukleotidokból az egyszeres láncok kétszálúakká egészít®dnek ki pl. a polimeráz enzim segítségével. Lássuk az enzim m¶ködését. Az enzim létez® DNS molekulához további nukleotidokat képes hozzákapcsolni a következ® módon: tegyük fel, hogy a DNS-szál eleje kétszálú, és egy adott ponttól kezdve csak a 3' - 5' irányú szál van meg (2.17. ábra). Ekkor ha az oldatban jelen vannak a nukleotidok a polimeráz enzim felismerve, hogy milyen bázisú nukleotidnak kell következnie a még hiányzó 5' - 3' irányú láncon beilleszti a következ® nukleotidot. Ezáltal lépésenként haladva létrehozza a teljes kétszálú DNS-t úgy, hogy a hiányzó molekulákat sorban hozzáf¶zi a meglév® lánchoz. Az enzim csak

38


2.17. ábra. A polimeráz enzim kiegészíti a DNS láncot 3' szénatomhoz kapcsolódó új nukleotidot (azt annak az 5' szénatomjával kapcsolva) képes a kiterjesztést véghez vinni. A sokszorozás m¶veletében tehát a polimeráz enzimek kulcsfontosságú szerepet játszanak, ezt a következ® módszerrel tudjuk kihasználni. Tegyük fel, hogy olyan kétszálú DNS láncaink vannak, ami végeinek ismert a bázissorrendje. Legyenek az oldatban az adott láncon kívül az ismert végek komplementer láncai (β -primer és γ -primer az 2.18. ábrán). Ekkor melegítéssel elérhetjük, hogy a láncok egyszálú DNS-ekké esnek szét. Kicsit h¶tve a levest a komplementerpárok az egyszálú láncok végéhez tapadhatnak. Így tehát van egy egyszálú DNS-ünk, aminek az elején (az 5' végén) néhány nukleotid már kétszálúra van kiegészítve. és a levesben megtalálható mind a négyféle nukleotid a kell®en nagy számban. Ezután a polimeráz enzim az oldatban található nukleotidokból kétszálúvá egészíti a molekulát. Így sokszorosíthatjuk a láncokat, ha van egy kétszálú DNS-ünk akkor ezt szétválasztjuk a bázis párok mentén, mondjuk melegítéssel, utána az enzim segítségével el® tudunk állítani a kiinduló lánccal megegyez® két láncot. Az eljárás során rövöd id® alatt exponenciális gyorsasággal emelhet® meg adott molekulák száma a levesben, akár milliószorosára is emelhet® egyes láncok száma. DNS molekulák kiválasztására kétféle módszert szoktak használni, az els® adott minta alapján választja ki a megfelel® molekulákat, a második pedig hossz alapján.

2.5. Pecázás Legyenek egyszálú DNS láncaink a molekuláris levesben. A célunk az oldatot 2 részre osztani oly módon, hogy az egyikbe olyan molekulák kerüljeneknek melyek adott rövid bázissorozatot tartalmaznak. Ekkor a levesbe egyszálú DNS-láncokat (a kívánt láncrész komplementerláncát) lógatunk, amikhez azok a láncok tudnak a levesb®l hozzátapadni (H-kötéssel) amelyek tartalmazzák a belógatott lánc komplementer sorozatát, vagyis tartalmazzák a kívánt bázissorrend¶ részt. Így kipecázhatjuk a megfelel® molekulákat.

III.


39

2.18. ábra. Ismert vég¶ kétszálú DNS-lánc el®készítése a polimeráz enzim számára

40


2.6. Hosszmérés Egy DNS hosszán a benne tálaláható bázisok, vagy bázis párok darabszámát értjük. Most a célunk az, hogy az oldatból kiválasszuk az adott hosszúságú DNS láncokat. A mérés alapját a gél elektroforézis nev¶ eljárás képezi. Töltéssel rendelkez® részecskék elektromos térben töltésükkel ellentétes irányban mozognak. A DNS molekulák negatív töltés¶ek, a pozitív töltés¶ anód felé haladnak. A molekula töltése arányos a hosszával, csakúgy, mint a mozgatásához szükséges energia. Ez a két hatás kioltja egymást, ezért azonos méret¶ molekulák azonos sebességgel mozognának, viszont most olyan speciális anyagban, gélben kell haladniuk, ami a hosszabb milekuláknak komolyabb ellenállást jelent. Így különböz® méret¶ molekulák sebessége különböz® lesz, így adott távolság megtételéhez szükséges id®b®l ki lehet számítani a molekula méretét. Az eljárás a következ®: A molekuláris levest (f®ként a benne szerepl® DNS molekulákat) egy speciális gélt tartalmazó kádba rakják. A DNS molekulák eredetileg a gél egyik szélén helyezkednek el, ezután a gélnek erre a végére a oldalára kapcsolják a negatív pólust, ennek hatására a molekulák elindulnak a másik (a pozitív) pólus, a katód irányba. Tehát, amikor az oldatra egyenáramot kapcsolnak, ekkor a töltéssel rendelkez® DNS molekulák az elektromos áramot vezetve mozgásnak indulnak. Minél hosszabb egy molekula annál nagyobb ellenállást kell leküzdenie a gélben való haladáshoz, így a molekulák a hosszuk alapján fognak elrendez®dni egy adott pillanatban. Tudjuk azt hogy adott hosszúságú molekula egységnyi id® alatt mekkora távolságot tesz meg, illetve egy n-szer hosszabb molekulának n-szer nagyobb id®re van szüksége ugyanakkora távolság megtételéhez. Így nagyon pontosan meg lehet mondani, hogy a gél melyik részében lesz a kívánt hosszúságú molekula, ezt a részt a gélb®l kivágva megkaptuk az összes ilyen hosszúságú molekulát. A 2.19. ábra mutatja sematikusan a mérést. Ehhez hasonló módszerrel megy egy DNS lánc bázissorendjének meghatározása is. Nézzük tehát, hogyan olvashatunk el DNS láncot. Ezt az ún. Sanger módszerrel tesszük, amit a felfedez®jér®l nevezték el. Az eljárás során analóg nukleotidokat gyártunk le oly módon, hogy a 3' szénatom OH csoportját H-re cseréljük. Az így létrehozott Dideoxy Adenin (ddA), Dideoxy Citozin (ddC), Dideoxy Guanin (ddG) és dideoxy Timin (ddT) molekulák szerkezete olyan, hogy bennük a 3' szénatomhoz nem tud másik molekula foszfoidészter kötéssel kapcsolódni. Módosítjuk az el®z® sokszorozó algoritmust. Négy lombikban fogjuk a sokszorosítást végezni, ezek mindegyikébe valamelyik analóg molekulából is teszünk. Ez alapján fogjuk megkülönböztetni a lombikokat. Egy lombikban keletkezhet teljes duplaszálú DNS, de olyan is amit a polimeráz enzim nem tud folytatni, mert az eredeti nukleotid helyett annak analóg párját, dedoxi nukleotidot tartalmaz. Ekkor a sokszorozás után, ha újra denaturáljuk a molekulákat lesznek olyan egyláncú DNS-ek amik nem a teljes hosszúságúak, hanem valahol dideoxy nukleotiddal fejez®dnek be. Ezután a molekulák hosszának mérésével megállapítható, hogy az egyes lombikokban milyen hosszúságban játszódhatott le a kiterjesztés folyamata. Világos, hogy ezek a hosszak pontosan a lehetséges dedoxy molekulák helyeit jelentik az adott lombikból. Viszont a dedoxy molekula csak az ® analóg párjának megfelel® helyen lehet a molekulában, tehát az

III.


41

2.19. ábra. DNS láncok kiválasztása hossz alapján gélelektroforézissel eredeti molekulában ezen a helyen az a nukleotid szerepelt, aminek analógját az adott lombik tartalmazza. Így a négy analóg nukleotidokat (is) tartalmazó lombikra elvégezve a gél elektroforézist megkapjuk az eredeti molekula nukleotidsorrendjét.

2.7. Enzimek Egyes alapm¶veletek végrehajtásában a természet által adott enzimeket használjuk. A már részletezett polimerázon kívül ilyenek pl. a következ®k: A ligáz enzim alapvet® szerepet játszik az él® sejtekben is. A kett®s DNS-láncokon végighaladva ellen®rzi a foszfodiészter kötéseket, ha valahol hiányzik a kötés akkor helyreállítja (a molekula nem esik szét a két láncot összetartó hidrogén-kötések, illetve a másik láncon meglev® foszfodiészter-kötés miatt). A számítások során is fontos szerepet játszik ez az enzim, amikor rövidebb láncokból építünk fel hosszabbakat. (Rövid láncok összekötése, a kés®bbiekben mutatunk erre példát.) Egyes számításokban fontos szerepet játszanak az ún. vágóenzimek (restrikciós endonukleázok). Ezekb®l nagyon sok ismert. Általános m¶ködési elvük a következ®: Dupla láncot vágnak ketté és csak meghatározott helyen. Az enzim megköti a molekulát egy specikus felismer® helyen, ezen belül vagy kívül kettéhasítja azt. Ha egy DNS molekula több ilyen felismer® helyet tartalmaz, az enzim bármelyik ilyen helyen elvágja azt. Ez

42


a vágás lehet lépcs®zetes is, két 'ragadós' 5' véget (pl. 2.20. ábra) vagy két 'ragadós' 3' véget hagyva meg. Bizonyos restrikciós enzimek nem ennyire specikusak és 'tompán' vágják ketté a dupla láncot.

2.20. ábra. Egy vágás 'ragadós végek' létrehozásával

3.

Adleman kísérlete - Hamilton út probléma

1994-ben Adleman kísérlete jelentett áttörést. Végre a gyakorlatban is sikerült "számításra fogni" a DNS molekulákat: Adleman a Hamilton út problémát oldotta meg a 3.21 ábrán látható hét csúcsú gráfra. Tehát a gráfban keressük azt az utat, amely minden csúcsot csak egyszer érint (ha van ilyen). A gráf minden csúcsához hozzárendelünk egy-egy húsz nukleotid hosszúságú egyszeres DNS láncot. Például a kísérletben a 2.-4. csúcsnak a következ® láncok feleltek meg: 2. csúcs: TATCGGATCG GTATATCCGA 3. csúcs: GCTATTCGAG CTTAAAGCTA 4. csúcs: GGCTAGGTAC CAGCATGCTT Ezek a 20 hosszú láncok olyan 10 hosszúságú láncokból épülnek fel, amelyek egyediek, és komplementer láncaik is különböznek mindegyikt®l. Hasonlóan az élekhez szintén 20 hosszú egyszeres láncokat rendelünk, ezeket a csúcsok láncainak segítségével hozzuk létre. Ha két csúcs közt vezet él, akkor a második csúcs els® tíz nukleotidjának komplementer láncához kapcsoljuk az els® csúcs második tíz nukleotidjának megfelel® komplementerláncot. A példánál maradva: a 2. csúcsból a 3.-ba mutató él: CATATAGGCT CGATAAGCTC a 3. csúcsból a 2.-ba mutató él: GAATTTCGAT ATAGCCTAGC a 3. csúcsból a 4.-be mutató él: GAATTTCGAT CCGATCCATG Így ha két csúcs között él van, létre tudnak hozni egy olyan kétszálú molekulát, amiben az egyik szál a csúcsokat tartalmazza, a másik az éleket.

III.

ADLEMAN KÍSÉRLETE - HAMILTON ÚT PROBLÉMA

43

3.21. ábra. Az Adleman által vizsgált gráf A gráfot tekintve, például létrejöhet a 3.22. ábrán látható utat megtestesít® kétszálú DNS lánc.

3.22. ábra. A csúcsoknak és az éleknek megfelel® láncokból a H-kötések által létrejönek az utakat jelent® kétszálú DNS láncok Az összes csúcsnak és élnek megfelel® láncot berakjuk a levesbe. A folyamat során elméletileg el®állhat az összes lehetséges út, gyakorlatilag ez elég nagy méretig így is van (minden rövid út meglesz az oldatban). Ezután végzünk egy hossz vizsgálatot és az összes megfelel® hosszúságú molekulát kivesszük: azokat amelyek hossza megegyezhet a Hamiltoni-út hosszával (jelen esetben 140 nukleotid). A mintát sokszorosítjuk, majd pecázás következik az els® csúcsnak megfelel® komplementer szálal, az így nyert mintában biztos, hogy minden molekula tartalmazza az els® csúcsot, ezután megint sokszorosítás és pecázás a következ® csúcsra, ezt megismételjük minden csúcsra, így ami marad, az a molekula a probléma megoldását jelenti, mivel a keresett hosszúságú és tartalmaz minden csúcsot.

44


Tehát végül azt kell eldöntetnünk, hogy maradt-e olyan DNS szálunk ami eleget tesz az összes el®z® mérésnek, kiválasztásnak. (Egyébként a példában a csúcsokat növekv® sorrendben végigjárva éppen egy Hamiltonutat kapunk.)

4.

Számítási modellek

Ebben a fejezetben további módszereket mutatunk be a Watson-Crick komplementaritás kihasználására a DNS számításokban.

4.1. H-rendszerek (Szeletelés) Tekintsük el®ször az ún. szeletel® rendszereket, amelyeket H-rendszereknek is neveznek. A H-rendszer elnevezés Tom Head nevéb®l ered, aki az ún. vizes számítások atyja, már Adleman kísérlete el®tt, 1987-ben elkészítette elméleti modelljét a DNSszámításokról. A vizes számítás arra utal, hogy a hagyományos számítógépekkel (amelyeknek a víz halálos ellenségük) ellentétben a DNS-számítások vizes közegben mennek végbe.

4.23. ábra. A H-rendszerekben a tompán vágó enzimek nem használhatóak

4.24. ábra. Azok az enzimek amelyek a felimerési mintát lépcs®zetesen vágják ragadós vég¶ molekulákat hoznak létre

4.25. ábra. A létrejött ragadós vég¶ molekulák

III.

SZÁMÍTÁSI MODELLEK

45

A számítás tulajdonképpen a vágóenzimek által hagyott 'ragadós vég¶' molekulákon alapul. A ragadós végek kapcsolódási felületet nyújtanak másik molekuláknak. Ha két molekulának a megfelel® a ragdós vége (pl. ugyanazzal az enzimmel lettek elvágva), akkor ezek a végek összeragadhatnak összekapcsolva a két molekulát. A szeletelést vágóenzimek végzik, melyek nem rongálva vágják a DNS láncokat. A legtöbb ilyen enzim palindrom mintát tud vágni. Egy láncrészt akkor nevezünk palindromnak, ha a másik szálat olvasva (ugyanúgy 5' - 3' irányba) ugyanazt a nukleotidsorrendet kapjuk. A 4.26 ábrán egy palindrommintát felismer® vágóenzimet mutatunk be.

4.26. ábra. Vágóenzim által felismert minta és a vágás módja Tehát a ragadós vég¶ molekulák újra összekapcsolódva a újabb láncokat alkothatnak. Ezeket a láncokat hidrogénkötések tartják össze. A lánc stabilizálására a ligáz enzim szolgálhat, amely a két szálon a kovalens kötéseket is képes létrehozni. Pl. három vágóenzim m¶ködési elvét láthatjuk a 1 táblázatban.

Enzim neve

Vágása

Típusa

Felismerési minta, ragadós vég

TagI

ϕ

(T,CG,A)

SciNI

ϕ

(G,CG,C)

HhaI

κ

(G,CG,C)

és

1. táblázat. Három enzim m¶ködése, amikkel kétszálú DNS láncokat lehet elvágni A szeletel®rendszerekben a következ® két f® operátor áll rendelkezésre: - Szétvágás a minta mentén. - Rekombináció, ragadós végekkel újra összekapcsolás. A szétvágott molekula is újra össze tud kapcsolódni, és más, új molekula is képz®dhet. A Watson - Crick komplementaritás miatt a vágás helye az egyik láncfél által is egyértelm¶en meghatározott, így a vágást egy hármassal adhatjuk meg: a fels® szálat

46


tekintve: (felismerési minta 1. része, szétvágott rész, a minta utolsó része). A rekombinációhoz az is fontos viszont, hogy melyik molekulának melyik szála hosszabb: ez alapján két típusról beszélhetünk (ϕ vagy κ). Csak az azonos típusúak kapcsolódhatnak össze. Matematikailag tekintve a következ® esetekben kapcsolódhatnak a láncok: w1 = w10 u1 xv1 w1 ” w2 = w20 u2 xv2 w2 ” Az összekapcsolódás feltétele, hogy a ragadós végek megegyezzenek. A következ® új láncok jöhetnek létre: z1 = w10 u1 xv2 w2 ” z2 = w20 u2 xv1 w1 ” Így matematikailag formális nyelvekre értelmezhetjük ezt a szeletel®-rekombináló m¶veletet. Egy szeleltel® rensdzer megadásáhos szükség van egy kezdeti nyelvre (milyen láncaink vannak eredetileg a 'DNS ábécével', vagy a matematikai formalizmust tekintve bármilyen ábécé felett megadva). Ezen kívül meg kell adnunk a szeletel® operátorainkat. A szabályokat a következ® alakban adhatjuk meg: r : (u1, u2, u3, u4 ), ezt egy szeletel®operátornak nevezzük. Az operátor alkalmazása: ha az x és y láncaink már vannak x, y ∈ L és ezek a következ® alakúak: x = x 1 u 1 u2 x 2 y = y1 u3 u4 y2 Akkor a z : z = x1 u1 u4 y2 is benne lesz a nyelvben. A szabály fenti alkalmazását (x, y) `r z alak jelöli. w = x 1 u3 u2 x 2 Ugyanez teljesül a w-re is, bár ezt matematikai modellekben nem feltétlenül szokták hozzávenni, viszont valódi DNS rendszerekben ez a lánc is létrejöhet/jön. Egy szeletel® rendszer által generált nyelv azon szavak halmaza, amelyek a kezdeti szavakból, és az azokból levezetett szavakból a megadott operátorok segítségével levezethet®ek. Amennyiben véges vagy reguláris nyelvb®l indulunk ki, és a szabályink száma véges, akkor reguláris lesz a generált nyelv is. A szabály sugara alatt a szabályt alkotó stringek hosszának maximumát értjük. |r| =def max(|u1 |, |u2 |, |u3 |, |u4 |). Érdekes probléma az olyan rendszerek vizsgálata, amikben a szabályok mérete korlátozott. A DNS rendszerekben mindig el®fordulhat, hogy a rekombináció során az eredeti molekula jön létre, vagyis olyan molekulák kapcsolódnak össze, amilyeneket szétvágtunk. Viszont el®fordulhat, hogy más létrejöv® molekulákra a felismerési minta már nem egyezik egyik az oldatban lev® vágóenzimre sem, míg azok a molekulák amik újra létrejöttek megint szétvághatóak ugyanazzal az enzimmel. Egy id® után így nagy valószín¶séggel már csak új láncok lesznek az oldatban. Az így létrejöv® nyelvet, ami az eredeti láncokat már nem tartalmazza feln®tt nyelvnek nevezzük.

III.

SZÁMÍTÁSI MODELLEK

47

Például a következ® kísérlet egy ilyen feln®tt nyelvet állít el®: Egy oldatban egy 500 nukleotidból álló molekula található (természetesen hatalmas példányszámban) A molekulát 400 és 100 nukleotidból álló darabokra vágó enzim van jelen. Mind a 400, mind a 100 hosszúságú darab képes kapcsolódni a másik fajtához és a saját típusához is. Vizsgáljuk, hogy bizonyos id® elteltével milyen hosszúságú láncok vannak az oldatban. A kiindulásban tehát csak 500 hosszúságú molekulák voltak jelen, a folyamat megkezdésekor 100 és 400 hosszúságúak is megjelennek. Egy ideig a kezdeti nyelvet követ®en, az ún. aktív nyelvben 100 és 400 hosszúságú, valamint az 500-on kívül a 200 és 800 hosszúságúak is megjelennek. Mivel viszont az oldatban lev® enzim a 200 és 800 hosszúságú molekulákat nem tudja szétvágni, egy bizonyos id® eltelte után ezek lesznek abszolút többségben, majd kés®bb már csak a 800 és a 200 hosszúságú molekulákból lesz az oldatban. Matematikai modellekben elegend® egy szót deniálni, azonban a DNS-számításokhoz jobban köt®d® rendszerekben szokás minden szó fordítottját is tekinteni (mintha a másik végér®l olvasánk a duplaláncot). Tekinthetünk olyan kétszálú DNS láncokat, amelyek egyik vége a másikkal kapcsolódott össze. Az ilyen körkörös molekulák létrejöhetnek pl. szeletelés során: a molekulalánc két ragadós vége egymáshoz ragadhat, így saját magával gy¶r¶vé kapcsolódik össze a molekula. Gyakorlatban ez információ tárolására lehet alkalmas, oly módon, hogy egy enzimmel szétvágjuk, kiegészítjük egy rövid nukleotid sorozat darabbal (a tárolni kívánt információval), majd újra zárjuk; CEL (cut - extend - lock) technológia. Olyan rövid a gy¶r¶, hogy a saját végét hamar meg s találja.

4.2. A SAT probléma megoldása A SAT probléma is NP-teljes. Most nézzük ennek megoldását DNS-ek segítségével. Legyen adott az alábbi formula (konjunktív normál formában):

A = (x1 ∨ ¬x2 ∨ x3 ) ∧ (x2 ∨ x3 ) ∧ (¬x1 ∨ x3 ) ∧ ¬x3 A megoldás során el®ször a 4.27. ábrán látható gráfban lev® utakat hozunk létre a kezd®ponttól a végpontig. Természetesen ekkor minden ilyen út minden x változóra pontosan vagy a változót, vagy a negáltját tartalmazza. A változóknak és a negáltjaiknak egyszálú DNS láncokat feleltetünk meg, mint ahogy a Hamilton-út problémánál tettük.

4.27. ábra. Három változós kiindulási gráf SAT problémához

48


Ebben a gráfban az összes Hamilton út egy értékelést jelent. Így mindenféle lehetséges megoldási kombinációnk el®áll (n változóra 2n variáció). Ez után vesszük a logikai és oparátorokkal összekötött klózokat (zárójelben elhelyezett kifejezéseket) és keressük azokat az értékeléseket amelyekre mindegyik klózban van igaz literál (4.28).

4.28. ábra. A megadott klózok literáljai szerint sz¶rünk Eredetileg tehát mindenféle értékelésünk ott van a levesben. Ezután sorra vesszük a klózokat, és minden klózra a következ® lépéseket tesszük. El®ször is annyi másolatot készítünk a lombikból (a benne lev® DNS szálakról) amennyi literál van az adott klózban. Vagyis a sokszorosítás m¶veletét is felhasználva szétosztjuk a lombik tartalmát ennyi részre. Ezután a literáloknak megfelel® komplementerkkel pecázunk, mindegyik levesb®l kiválasztjuk azokat a láncokat amikben az adott literál igaz. Ezután összeöntve a lombikok tartalmát azok a láncaink maradnak meg amelyekben az adott klóz igaz. Az eljárást megismételve a többi klózra is, végül csak azok a láncok maradnak az oldatban, amelyek kielégítik az egész formulát. Eddig mesterséges környezetben használtuk a DNS molekulákat. A következ® fejezetben a DNS alapú számításoknak egy olyan ágával ismerkedünk meg, ami az él® sejten belül történik.

5.

Sejten belüli számítások

Napjainkban a számítógépes tudósokat a molekuláris biológia segíti annak a kutatásában, hogy hogyan lehetne helyettesíteni (vagy kiegészíteni) a szilikon alapú számítógépeket DNS alapú számítógépekkel. A legtöbb kutatás a DNS számításokkal kapcsolatban, mint ahogy az eddigiekben is írtuk a biomolekulák kémcs®ben való használatával foglalkozik, vagyis az él® sejteken kívül. Azonban most egy új, fontos és izgalmas ágát vizsgáljuk meg a DNS számításoknak: az él® sejtekkel foglalkozunk, a DNS molekulákat természetes környezetükben vizsgáljuk. Ez a terület is hozzátartozik

III.

SEJTEN BELÜLI SZÁMÍTÁSOK

49

a bioinformatikához, mert hozzájárul hogy megértsük az összetett biologiai rendszerekben végbemen® "számítási folyamatok" természetét. A DNS-számításokat sziliátokban vizsgáljuk, amik az egysejt¶ek egy nagyon régi csoportját alkotják. Annak ellenére, hogy egysejt¶ek, a bonyolultabb DNS m¶veletekre képes él® szervezetek közé tartoznak. Érthet® számítási szerkezettel rendelkeznek, s®t tulajdonképpen határozottan azt mondhatjuk, hogy a láncoltlista adatszerkezetet használják. Különösen érdekes számítási szempontból a génképzés folymata a mikronukleuszból a makronukleusz alakig. Ezt a folymatot mind sztring-, mind gráf modellel leírjuk a három molekuláris m¶veletettel együtt. Ez a három m¶velet univerzális abban az értelemben, hogy ezekkel össze tudunk állítani bármilyen génállomány makronukleuszát a mikronukleusz alakból. Habár a gráfmodell sokkal elvontabb, mint a sztringmodell, mégis minden génképzési folyamat felírható mindkét formában. Tulajdonképpen ez a témája a [15] könyvnek és több újabb DNS-számítás témájú cikknek is.

5.1. A sziliátok Mint említettük a sziliátok (ciliated protozoa) kb. 2 milliárd éves egysejt¶ él®lények. Az eukariótáknak ez az ®si csoportja kb. 8000 különböz® fajt takar. Genetikai anyagukat tekintve is hatalmas különbség van köztük (több mint a gyümölcslégy és az ember közt). Ezekben az egysejt¶ekben az örökít®anyag kétféle forma egyikében található meg. Mikronukleusz formában van jelen a genetikai információ a szaporodás nyugalmi fázisaiban. A mikronukleusz tulajdonképpen egy nagy hosszúságú kétszálú DNS-lánc, aminek csak kb. 5 százaléka rejt genetikai információt. Ezzel szemben a szaporodási fázisban a genetikai információ sokkal tömörebb formában, csak magukat a géneket tartalmazva van jelen. Jelen fejezetben azt fogjuk áttekinteni, hogy a genetikai információt a sejt hogyan rakja össze. A mikronukleuszban jelenlev® olyan részek amelyek nem géneket kódolnak els® látásra feleslegesnek t¶nnek, napjainkban köszönhet®en a nagyfokú érdekl®désnek, egyre több hasznos funkciójukra derítenek fényt kutatók. Tehát a genetikai kód a szaporodási fázis kezdetén mikronukleusz formából makronukleusz formába alakul át. Ez a folyamat számítási néz®pontból is érdekes, a DNS számításokkal foglalkozó közösség egyik f® vizsgálati tárgya.

5.2. A génképzés sziliátokban A szokásos jelölést használva az egyszálú DNS-t az {A, C, G, T} ábécé feletti sztringek, a kétszálú DNS láncokat pedig dupla szavak fogják jelölni. A teljes dupla láncokban a fels® és az alsó sztringhossz ugyanannyi, és minden egyes bet¶ az els® sztringb®l a komplementere a másik sztring megfelel® bet¶jének. Egy ilyen láncot pl. a µ ¶ pi . A pi egyszálú DNS láncot a pi inverzének nevezünk. Hasonlóan a kétszálú DNSpi lánc inverze, amikor a másik végér®l tekintjük. Ezenkívül ragadós vég¶ molekulákat is fogunk használni.

50


A γ mikronukleuszban a genetikailag fontos részeket (Macronuclear Destined Sequence) egymástól genetikai információt nem hordozó IES (Internally Eliminated Sequence) részek választják el. Az MDS-ek {M1 , ..., Mk } halmazának (k > 1) minden eleme pontosan egyszer fordul el® a γ -ban. Ezeknek az Mi értékeknek a felépítése a következ®: µ ¶ pi pi+1 Mi = ,µ , , pi i pi+1 ahol 2 ≤ i ≤ k − 1; az els® és az utolsó MDS pedig: ¶ µ ¶ µ pk p2 , Mk = , µk , e . M1 = b, µ1 , p2 pk A µi részek az Mi gén 'testének' tekinthet®ek, ezek teljes dupla szálrészek. Ezzel szemben a pi egyszeres szál Watson-Crick komplementere a pi , a kett® együtt pedig p mutatóként funkcionál. A i DNS láncot az Mi MDS bementi, az Mi−1 MDS-nek pi pedig kimeneti mutatójának nevezzük. A γ mikronukleuszban minden mutató kétszer fordul el®, egyszer bementi-, egyszer pedig kimeneti mutatóként. A b és e kétszálú láncok pedig a kezd®- és a végjelz®k, ezek olyan láncszakaszok, amik pontosan egyszer fordulnak el® a γ -ban. Fontos, hogy ezek a jelz®k és mutatók mindig az MDS és az IES határán helyezkednek el, azokat elválasztva egymástól. Az Mi részek inverzei: µ ¶ pi+1 pi Mi = ,µ , , pi+1 i pi az els®nek és az utolsónak pedig: µ ¶ p2 M1 = ,µ ,b , p2 1

µ Mk =

p e, µk , k pk

¶ .

Ezek tulajdonképpen ugyanazt a duplaláncszakaszt jelentik fordított irányban elhelyezkedve (pl. a γ -ban). Pl. a mikronukleusz lehet M3 I1 M5 I2 M1 I3 M6 I4 M2 , ahol M5 az M5 inverze, az I1 , I2 , I3 és I4 láncszakaszok pedig az IES-ek (5.29. ábra). A mikronukleusz és a makronukleusz közti kapcsolat az, hogy a makronukleuszt megkaphatjuk a mikronukleuszból 'átfed® ragasztásokkal', úgy, hogy az eredetileg nem sorrendben lev® MDS-ek a helyes sorrendben és az IES-ek nélkül alkotják a makronukleuszt (5.30. ábra). A génképzés m¶velete alatt, a mikronukleuszt transzformáljuk makronukleáris formába, az IES-ek a sorozatban fokozatosan kivágódnak, és a MDS-ek összeilleszt®dnek a szükséges sorrendben. Ahogy látni fogjuk, a természet tulajdonképpen évmilliók óta használja a láncoltlista adatszerkezetet. A mikronukleuszban a mutatók jelzik az MDS-ek sorrendjét, méghozzá oly módon, hogy a makronukleuszban maguk a mutatók is a gének részei és genetikai információt hordoznak. Ha a mutató kétszer ugyanabban a formában fordul el®, akkor direkt ismétlésnek, ha az egyik el®fordulás a másik inverze, akkor inverz ismétlésnek hívjuk.

III.


51

5.29. ábra. Az MDS-ek egy lehetséges elhelyezkedése a mikronukleuszban

5.30. ábra. A makronukleusz felépítése, az összerakott gének

5.3. A génképzés m¶veletei Nézzük most mi az a három m¶velet, aminek segítségével a mikronukleuszból a makronukleusz kialakul.

5.3.1. Az ld m¶velet. Az els® ilyen m¶velet az ld, aminek neve a loop, directrepeat szavak rövidítése. Ez a m¶velet olyan mutatópárnál mehet végbe, amikor egy mutató kétszer jön egymás után, és mindkétszer ugyanolyan formában (vagy mindkett®ben invertálva, vagy mindkett®ben nem invertálva), vagyis direkt ismétléssel. Ekkor el®fordulhat, hogy a lánc egy kör alakú hurkot ír le, ahol egymás mellé kerül a mutató két el®fordulása. Ekkor azokat ragadós véggel elvágva, és újra egyesítve a lánc két részre esik szét: egy körre és egy láncra (5.31. ábra). Az operátor alkalmazásánál azért fontos, hogy a mutatók el®fordulása egymás melletti legyen, mert a genetikai információnak együtt kell maradnia. Ha a mutató két el®fordulása közt más mutató, így más MDS is lenne, akkor a genetikai információ szétszakadna. Márpedig olyan m¶veletünk, amely két DNS molekulát kapcsol össze

52


5.31. ábra. Az ld operátor nincs, ezért általában feltételezzük, hogy az ld m¶velete(ke)t a génképzés utolsó szakaszában hajtjuk végre.

5.3.2. A hi m¶velet. A hajt¶ (hi) m¶velet a hairpin és az inverted-repeat

szavak rövidítéséb®l kapta nevét. Ez a m¶velet akkor hajtható végre, ha egy mutató egyik el®fordulása invertált, vagyis inverzen ismét®dik. Ekkor a láncot hajt¶alakba hajtva, és a mutatónál elvágva az összeillesztés úgy is létrejöhet, hogy a lánc középs® szakasza megfordul (invertálva kerül vissza a láncba, lásd az 5.32. ábrán).

5.32. ábra. A hi kivágás és újraillesztés operátor

5.3.3. A dlad m¶velet. A dlad m¶velet a double loop és alternating directrepeat szavakból kapta nevét. Ennek megfelel®en a m¶velet akkor hajtható végre, ha két mutató felváltott sorrendben fordul el®, és az azonos mutatók azonos formában (direkt ismétl®déssel). Ekkor a dupla hurok alakban (lásd 5.33. ábra) az operátor hatására a lánc két része felcserél®dik. Nagyon fontos, hogy a fent leírt három m¶velet univerzális abban az értelemben bármilyen mikronukleuszból el®állítható bel®le a helyes MDS sorrend¶ makronukleusz.

5.4. A génképzés modellezése A génképzés m¶velete a mikronukleuszból a fenti három m¶velet segítségével makronukleuszt készít, az IES-ek a fokozatosan kivágódnak a sorozatból az ld m¶velettel,

III.


53

5.33. ábra. A dlad kivágás és újraillesztés operátor

az MDS-ek pedig összeilleszt®dnek a kívánt sorrendben. A három transzformációs m¶veletben a mutatók a dönt®k. Így, a jelölés egyszer¶sítéseként a mutatókra pozitív számokkal fogunk hivatkozni 2, 3, ..k , a mutatók inverzeit pedig a 2, 3, ..., k fogják jelölni. Ezen kívül megtartjuk a b, e (mint els® és k + 1. mutató helyetti szakaszokat) és b, e jelölést ezek inverzére. A génképzési folyamat modellezésében a f® ötlet az, hogy csak a mutatókat és a jelz®ket tartjuk meg. A mutatók sorrendbe transzformációja, illetve az azonos mutatók egymás melletti direkt ismétlésbe kerülése a cél. Az ld pedig ekkor a mutató két el®fordulása közti (IES) szakszt kivágva két egymás mellé ill® MDS-t összeilleszt. Ekkor tulajdonképpen a felhasznált mutató megsz¶nik mutatónak lenni (a génképzésben további szerepe nincs), a létrejött MDS szakaszt másik két mutató (vagy jelz®) határolja. A génképzés tulajdonképpen akkor ér véget, ha az MDS-ek egy folytonos szakaszt alkotnak, a b és e jelz®k határolják, vagyis létrejött a makronukleusz. Ha a m¶veletek eredményeként a makronukleusz létrejött, akkor azt mondjuk a génképzés stratégiája sikeres volt. 5.4.1. Példa. Számítási szempontból tehát maguk az MDS-es és IES-ek nem érdekelnek minket, a m¶veletek a mutatók helyét®l és egymáshoz viszonyított elhelyezkedését®l függnek, és azokon dolgoznak. Használjuk tehát az (i, i + 1) jelölést az i. MDS-re. Így az inverze: (i + 1, i). (Ahol i = 1 a b, i = k + 1 pedig az e; a többi i érték a pi mutatót jelöli.) Ekkor a γ = (4, 5)(2, b)(5, e)(4, 3)(3, 2) egy lehetséges MDS sorozatot leíró sorozat. Három m¶velet is használható erre a sorozatra: ld a 3 mutatóra, a hi a 4-re, míg a dlad az 5, 2 mutatópárra. Az ld-t végrehajtva a γ -ra: (4, 5)(2, b)(5, e)(4, 2)-t kapunk. (Itt a ((4, 2) azt rövidíti, hogy a 3. és a 2. MDS már egymás mellé került, nincs köztük IES szakasz a láncban. A hi végrehajtásával a γ -ból a (e, 5)(b, 2)(5, 3)(3, 2) sorozatot kapjuk. Ha a γ -ra a dlad m¶veletet alkalmazzuk, akkor (4, e)(4, 3)(3, b) az eredmény. Ha a dlad, hi, ld sorrendben alkalmazzuk a m¶veleteket, akkor: a dlad után folytatva a hi-vel a 4-es mutatóra: (e, 3)(3, b), végül az ld a 3-asra: (e, b). Ez azt jelenti, hogy minden MDS a helyére került a b és e közt helyezkednek el a helyes sorrendben IES-ek nélkül (a jelen esetben a kett®s láncot a végér®l olvasva). Tehát a génképzési stratégia sikeres volt.

54


5.5. Sztring-modell a génképzésre Nézzük most, hogy a DNS-szálakat sztringként kezelve a m¶velteket hogyan írhatjuk le formálisan. Az el®z® példában párok sorozatával írtuk le a makronukleuszt. Most egy absztrakciót végrahajtva egyszer¶sítjük a jelölést, mégpedig elhagyjuk a zárójeleket, a b és az e szimbólumokat. A sztringben egy mutató (bet¶) el®fordulása pozitív, ha nem felülhúzott jellel fordul el®; ellenkez® esetben a bet¶ negatív el®fordulásáról beszélünk. Az el®bbi γ -nak megfelel® sztring: 45253432. Nézzük a m¶veleteket hogyan írhatjuk ebben az alakban. Az ld m¶velet tulajdonképpen azt jelenti, hogy ha egy mutató kétszer közvetlenül egymás után fordul el® direkt ismétl®déssel, akkor elhagyhatjuk mindkett®t a sztringb®l. Ugyancsak az ld m¶veletet fogja jelenteni az, amikor egy mutatópár direkt ismtl®dése úgy fordul el®, hogy a sztring els®, illetve utolsó bet¶je az adott mutató. Ekkor a mutatópár törlése annak felel meg, hogy az összes MDS-t tartalmazó DNS részlet a m¶velet során a gy¶r¶ alakú részbe kerül (és a láncrész az ami csak IES részeket tartalmaz). A hi m¶veletnek megfelel® sztringm¶velet akkor alkalmazható, ha valamely p bet¶re igaz, hogy mind a p, mind a p formában megtalálható a sztringben. Hatására az xpypz sztringb®l az xyz sztringet kapjuk, ahol y nem más, mint az y visszafelé olvasva és bet¶nként invertálva (ami nem volt felül húzva az úgy lesz, ami úgy volt az nem lesz). A dlad operátor sztringmegfelel®je akkor használható ha két direkt ismétléses mutatópár átfed, vagyis a szó xpyqzpvqw alakba írható (a p-k és/vagy a q -k lehetnek páronként felülhúzottak is). Ekkor az operátor hatására az xvzyw sztring keletkezik. Világos, hogy ebben a modellben egy stratégia akkor sikeres, ha az üres szót sikerül el®állítani a kiinduló sztringb®l. Másrészt fontos, hogy az absztrakciót megtehetjük, vagyis az eredeti sikeres stratégiák és a sztringmodell sikeres stratégiái megfelelnek egymásnak. Ez pedig azt is jelenti, hogy a használt három m¶velet univerzális abban az értelemben, hogy segítségükkel minden lehetséges (öszzekevert) mikronukleuszból el®állítható a gének makronukleusz formája. Mint a dlad operátor sztring változatánál láttuk a mutatók átfedései fontos szerephez jutnak. Ez alapján deniálhatjuk a mutatópároknak megfelel® intervallumokat, mint az ®ket tartalmazó legrövidebb részszavakat. Például a 45253432 sztring 3-intervalluma a 343, 4-intervalluma a 452534 sztring. Láthatjuk, hogy a 3 és a 4 átfed®ek. (Mindkett® intervallumában pontosan egyszer fordul el® a másik.) A következ® alfejezetben ezeket az átfedéseket kihasználva egy még magasabb absztrakciós szintre visszük a génképzés modelljét.

5.6. Átfedési gráf modell Most még absztraktabb szinten mutatjuk be a génképzést, a mutatók sorrendjéb®l csak az átfedési relációt megtartva. Az intervallum-átfedési gráfot a következ®képpen deniálhatjuk: Legyenek a csúcsok a mutatók. Minden csúcsot egy el®jellel is ellátunk,

III.


55

attól függ®en, hogy a mutató két el®fordulása ugyanolyan (paritású)-e (−), vagy egyszer pozitív és egyszer negatív az el®fordulás (+). Két csúcs között pontosan akkor vezet él, ha a két csúcsnak megfelel® mutatópárok a sztringben átfedési relációban vannak (intervallumaik a másik mutató pontosan egy el®fordulását tartalmazzák). Itt jegyezzük meg, hogy többszörös éleket, illetve hurok élt(aminek végpontjai megegyeznek) nem engedünk meg a gráfban. Bármilyen mikronuklesz sztring alakját felírhatjuk gráf alakban is. Lássuk a m¶veleteknek milyen megfelel®ik lesznek ezen az absztrakciós szinten. Az ld m¶veletnek az fog megfelelni, hogy a − jel¶ csúcsokat, amik nincsenek összekötve egyetlen csúccsal sem (izoláltak) törölhetjük a gráfból. A hi m¶velet átfedési gráf szint¶ megfelel®je: + jel¶ csúcs törölhet® a gráfból, legyen ekkor V azon csúcsok halmaza, ami a törlend® csúccsal össze van kötve. A m¶velet során minden az adott csúccsal összekötött csúcs (a V minden eleme) paritást vált (−-ból + lesz és fordítva), valamint V két csúcsa pontosan akkor lesz összekötve, ha az el®z® gráfban nem volt (mintha az élek is 'paritást' váltanának 'volt'ból nincs és 'nem volt'ból van). Végül a dlad a gráfban a következ®nek felel meg: a m¶velet két összekötött negatív jel¶ csúcsra (legyenek ezek A és B ) alkalmazható. Hatása: legyen VA , VB és VAB rendre azon csúcsok halmaza a gráfban amelyek: (VA :) össze vannak kötve A-val, de B -vel nem; (VB :) össze vannak kötve B -vel, de A-val nem; (VAB :) össze vannak kötve A-val és B -vel is; Ekkor a m¶velet hatására az adott két csúcs (A és B ) elt¶nik (azokkal az élekkel együtt amelyeknek legalább az egyik végpontja e két csúcs közül való), és a VA -ban lev® csúcsok pontosan akkor lesznek összekötve, ha eddig nem voltak; és hasonlóan a VB -beli csúcsok közti élek is pontosan azok lesznek, amelyek az eddigi gráfban nem voltak; a többi él (így pl. a VAB -beli csúcsok köztiek) nem változik. A gráfokra vonatkozó transzformációs szabályokat nevezhetjük 'negatívcsúcs'-, 'pozitívcsúcs'- és 'duplacsúcs-szabálynak'. A 2423656435 sztringnek megfelel® gráfot a 5.34. ábrán mutatjuk be. Az ezt követ® két ábrán példát mutatunk szabályok alkalmazására. Gráfoknál akkor mondjuk, hogy a gráf-stratégia sikeres, ha az üres (csúcsnélküli) gráfot sikerült elérni. Láthatjuk, hogy egy átfedési gráf nem egyértelm¶en adja meg azt, hogy mely sztringb®l képeztük. (A lehetséges sztringekb®l a gráfokra történ® léképezés több az egyhez típusú.) Fontos azonban, hogy mégis ekvivalensek a modellek, vagyis pontosan akkor van sikeres stratégia a gráfban, ha a sztringre is van. Az, hogy a sikeres sztringstratégiának megfelel sikeres gráf-stratégia triviális, a lépések ugyanabban a sorrendben megadnak egy sikeres gráfstartégiát. Ezzel ellentétben a sikeres gráfstratégiák nem egy-az-egyben fordíthatók sikeres sztring-stratégiává, néha a lépések sorrendjét át kell rendezni. A következ® részben ugyancsak az él® sejtekkel kapcsolatos számítási modellt veszünk, a membrán számítások viszont csak a motivációt tekintve rokonok az él® sejt folyamataival, maguk a számítások elvont modelleket használnak.

56


5.34. ábra. Példa átfedési gráfra el®jeles csúcsokkal

5.35. ábra. Negatívcsúcs szabály alkalmazása a 4-es csúcsra

III.


57

5.36. ábra. Duplacsúcs szabály alkalmazása a 4-es és 5-ös csúcspárra (a 5.34. ábra gráfjára)

IV. fejezet

Membrán Számítások A DNS számítástechnika alapjai és a sziliátok után most nézzünk egy másik számítási modellt, amihez az el® sejtek m¶ködése adta a mintát. Ebben a fejezeteben, tehát a membránrendszerekkel, mint absztrakt számítási modellekkel fogunk részletesebben megismerkedni. A Membrane Computing fogalma Gheorghe Paun nevével köt®dik össze, ezért a membrán-számítógépeket P-rendszereknek (P-systems) is szokták hívni. Tulajdonképpen a számítástechnikának ez az ága még 10 éves sincsen. A membránrendszerek a számítások egy a természet, mégpedig a biológiai membránok néhány jellemz®je által motivált modelljei. A membránrendszerek objektumok multihalmazaival dolgoznak. A membránrendszer strukturált, a membránokhoz "reakció-szabályok" tartoznak, amik maximálisan párhuzamos, nemdeterminisztikus módon alkalmazandók. Az objektumok áthatolhatnak a membránokon, a membránok töltése, vastagsága (áthatolhatósága) változhat, membránok megsz¶nhetnek, illetve osztódhatnak. Ezeket a jellemz®ket használhatjuk a rendszer kongurációinak átmeneteinek és magának a számításnak a deniálására. Rengeteg variációját deniálták már ezeknek a rendszereknek, a legtöbb ezek közül univerzális, vagyis számítási ereje megegyezik a Turing-gépével. Ezzel szemben köszönhet®en a párhuzamos m¶ködésüknek, illetve hogy akár exponenciális tárhellyel is dolgozhatnak, bonyolult problémák (NP-teljes, PSPACE stb.) is hatékonyan oldhatók meg (lineáris, polinomiális id®ben) segítségükkel. Most az alapötletet, és néhány membrán-rendszer (és a velük történ® számítások) néhány alaptulajdonságát fogjuk kicsit részletesebben megvizsgálni.

1.

A biológiai membránok

Tulajdonképpen durván azt mondhatjuk, hogy az 'él®-anyag alapegysége a sejt'. Ez azt jelenti, hogy az él®lények sejtekb®l épülnek fel. Nagyon sokféle sejt fordul el®, de van néhány jellemz® tulajdonság ami minden sejtre jellemz®. A természetben minden él® sejtet az úgynevezett sejthártya határolja (lásd a 1. és 2.3. ábrákat). A sejten belül különböz® alkotórészek helyezkednek el, amiket ugyancsak speciális hártya vesz körül. Például a növényi sejteken belül jellemz®en megtalálható a sejtmag, azon belül a magvacska; a Golgi-komplex, a színtest, a mitokondrium, lizoszóma stb. A membránok egyes molekulák számára nem áthatolhatóak, pl. egyes sejtalkotók nem hagyhatják el a sejtet; vagy egyes mérgez® anyagokat a hártya nem enged be a sejtbe. Bizonyos molekulák számára viszont (egy vagy mindkét irányban) átjárható 59

60

IV. MEMBRÁN SZÁMÍTÁSOK

1.1. ábra. A sejt membránjának szerkezete

IV.

A BIOLÓGIAI MEMBRÁNOK

1.2. ábra. A membránalkotó Foszfolipid molekula szerkezete

61

62


a membrán, pl. tápanyagot fel tud venni a sejt, a keletkezett felesleges illetve káros anyagok pedig távozhatnak bel®le. Azt a tényt, hogy egyes molekulák áthatolhatnak membránok hártyáin fogjuk a membrán-régiók közti kommunikációra használni a modellünkben. Itt emeljük ki, hogy a modellel most nem az el® sejt m¶ködésének (vagy annak egyes folyamatainak) a vizsgálata illetve modellezése a cél, hanem egy a sejtben meggyelhet® folymatok által inspirált számítási modell, elvi számítástechnikai eszköz leírása.

2.

Formális membrán-modell

Ami a biológiai membránokból fontos nekünk, hogy régiókat választanak el egymástól, illetve környezetükt®l; valamint néhány speciális molekula áthaladásának engedélyezésével megengedik a "kommunikácót" a régiók közt. A továbbiakban a szaknyelvet átvéve magukat a régiókat fogjuk membránnak nevezni, és nem az ®ket határoló hártyákat. Fontos, hogy minden membránnak (a legküls®t, ami magának a sejtnek felel meg kivéve) pontosan egy szül®membránja van. A membránok egy fa-struktúrát alkotnak. A struktúra gyökere maga a sejt, ez néhány fontos tulajdonságban különbözni fog a többi membrántól a modellben. Azt a membránt, amiben nincs további membrán, elemi (elementary) membránnak nevezzük. Értelmezhetjük a membránrendszer mélységét az alapján, hogy mekkora a rendszert leíró fa magassága. Továbbmenve a számítási eszköz felépítésében, a következ® lépés az hogy objektumokat adunk a struktúrához. Minden egyes membrán objektumok multihalmazát és evolúciós szabályok halmazát tartalmazza. Biológiai értelemben ez jelenthet különféle molekulákat, esetleg mérgez® anyagokat vagy éppen tápanyagot, illetve magát a cselekvést, amivel a membrán az anyagot feldolgozza: megemészti, kiválasztja, stb. Modellünkben az objektumokat egy adott ábécé szimbólumaival jelöljük. A membránok az objektumokkal, mint üzenetekkel tulajdonképpen egy kommunikációs rendszert alkotnak, mivel ezek az objektumok mozoghatnak a sejten belül (pl. a hártyák proteincsatornáin át). A membránrendszert ábrázolhatjuk Euler-Venn-diagrammal (mint a 2.3 ábrán), fával, vagy egymásba ágyazott zárójelek sorozatával is. Formálisan:

Π = (V, T, C, µ, w1 , ...wn , (R1 , ρ1 ), ..., (Rn , ρn ), i0 ) egy membrán-számítógép, ahol

• V egy véges ábécé, a számítás során fellép® szimbólumok (objektumok) halmaza; • T ⊆ V a kimeneti jelek halmaza; • C ⊆ V \ T a katalizátorok halmaza; • µ a membránstruktúra n membránnal (a membránok számozva 1-t®l n-ig), ezt a fastruktúrát pl. egymást tartalmazó zárójelpárokkal adhatjuk meg;

IV.

FORMÁLIS MEMBRÁN-MODELL

63

2.3. ábra. A sejt, mint membrán-számítási modell

• n a Π foka (ennyi membránt tartalmaz); • wi a számítás kezdetén az i. membránban lev® objektumok multihalmazát írja le (általában ezt egy V ∗ szóval tesszük, pl. azzal amiben valamilyen ábécésorrendben vannak a szimbólumok); • Ri pedig az i. membrán evolúciós szabályainak véges halmaza, ρi , a prioritási reláció egy féligrendezés a membrán szabályai közt. Az evolúciós szabályok u → v alakúak értelmezésük a formális nyelvekben megszokott szabályokéhoz hasonló: ha az adott membránban rendelkezésre állnak az u-t alkotó szimbólumok, akkor a szabállyal történ® evolúció során ezeket az objektunokat a v objektumaival helyettesítjük. (Az u objektumainak kölcsönhatásából a v objektumai keletkeztek.) Az evolúciós lépésre és a szabályokra kés®bb még visszatérünk.

64


• végül, i0 egy 0 és n közé es® természetes szám, ami az ún. kimeneti membrán sorszáma. Az i0 = 0 esetben a környezetbe (a legküls® mwmbránon kívülre) távozó objektumok multihalmazát tekintjük a számítás kimenetének. (valójában a T és a C megadását a szabályok, illetve a kimeneti membrán maga helyettesíti, deniálja) Természetesen bármelyik id®pillanatban bármelyik membránra teljesülhet az, hogy az üres halmazt alkotják a benne lev® szimbólumok, vagyis üres az adott membrán. Hasonlóan az is el®fordulhat, hogy egy membránhoz nulla darab szabály tartozik (pl. ez a kimeneti membránnal gyakran el®fordul). A membránrendszereket gyakran grakusan is ábrázolni szokták. Ekkor az egymást tartalmazó membránok különböz® egymást tartalmazó régiókat jelentenek (lásd 2.3. ábra), minden régióba beleírjuk az adott membrán evolúciós szabályit (a prioritási sorrendeket pl. nyilakkal tudjuk a szabályok közt jelezni), valamint az aktuálisan ottlev® objektumokat (pl. egy olyan w szóval, ami minden objektumból pontosan a megfelel® mennyiségben tartalmaz. A természetben lejátszódó folyamatok alapján továbbfejleszthetjük a számítási modellt úgynevezett aktív membránok bevezetésével. Például bevezethetünk egy olyan speciális m¶veletet ami egy membrán megsz¶nésének, kilyukadásának felel meg, ekkor a tartalma egy szinttel feljebb kerül a membránstrukturában. Egy membrán tehát tartalmazhatja többször ugyanazokat az elemeket, így a membránokkal történ® számítások tulajdonképpen multihalmazokkal történ® számítások. Ezt részletezzük a következ® fejezetben.

3.

Multihalmazok és számítások: Parikh nyelvek

Egy V rendezett ábécé felett adott w szó Parikh vektorát deniáljuk a következ®képpen: Φ(w) = (|w|ai ), ahol ai ∈ V és w az ábécé i. bet¶jét pontosan |w|ai -szer tartalmazza. Tulajdonképpen az w szó kommutatív képeinek halmaza jellemezhet® ezzel a vektorral, mintha a sztringekben a bet¶k sorrendje nem számítana: így multihalmaz adatszerkezettel írhatjuk le ®ket. Éppen ezt jelentik a Parikh-vektorok. Például az {a, b, c} rendezett ábécé feletti ababbcaa szó Parikh-vektora: (4, 3, 1), mivel a szó 4 a, 3 b és 1 c bet¶t tartalmaz. Tehát egy Parikh-vektor bijektív módon ad meg egy multihalmazt (rendezett ábécé fölött). Adott L nyelv, az L nyelv Parikh-halmazát a következ®képpen deniáljuk: Φ(L) = {Φ(w)|w ∈ L}. Egy nyelv Parikh-halmaza tehát a nyelv szavainak Parikh-vektorait tartalmazó halmaz. Legyen az ábécénk számossága n. Egy nyelvet (Parikh értelemben) lineárisnak nevezünk, ha Parikh halmaza lineáris, vagyis teljesül rá½a következ® feltétel: van k +1 darab ¾ k P olyan n-dimenziós vektor (v0 , ...vk ), hogy Φ(L) = v|v = v0 + αi vi , αi ≥ 0(∀i) . i=1

Egy L nyelv szemilineáris, ha Parikh halmaza lineáris halmazok véges uniója.

IV.

MVELETEK A MEMBRÁN-RENDSZERBEN

65

Köztudott, hogy minden környezetfüggetlen nyelv szemilineáris. Tehát ha egy nyelv nem-szemilineáris (ilyen pl. a {an |∃m ∈ N : n = m2 } nyelv) akkor az nem lehet környezetfüggetlen. Mivel a membránok a bennük lev® vegyületek multihalmazát tartalmazzák, a membránszámításokat tulajdonképpen multihalmaz-számításoknak is nevezhetjük. Tehát tulajdonképpen így nyelvek helyett azok Parikh-halmazaival dolgozhatunk. Most térjünk vissza a membrán modellhez, és nézzük milyen lépésekb®l áll a számítás.

4.

M¶veletek a membrán-rendszerben

Membránt nevezhetünk régiónak is. Egy ilyen objektumok multihalmazát és ezekhez tartozó evolúciós szabályokat tartalmaz. Tekintsük most az evolúciós szabályokat.

4.1. Evolúciós szabályok Egy evolúciós szabály (más átíró rendszerekhez hasonlóan) szimbólumokat (a használt ábécé szimbólumait) tartalmazza az alkalmazás el®tti és utáni id®pontban. Egy u → v szabálynál az u szó által leírt multihalmaz számosságát (azaz az u hosszát) a szabály sugarának nevezzük. Ha minden szabály sugara 1 akkor a rendszer nem-kooperatívnak hívjuk. (Ekkor a rendszer a környezetfüggetlen nyelvtanokkal tekinthet® analógnak, e tekintetben.) Ha van olyan szabály a rendszerben aminek a sugara legalább kett®, akkor a rendszer kooperatív. Például a ca → cbinj dout e szabály jelentése a következ®. Ha az adott membránban rendelkezésre áll egy c és egy a szimbólum (molekula) akkor lehetséges az, hogy ezek kölcsönhatása nyomán az a elt¶nik, a c megmarad, továbbá egy b szimbólum bemegy a j . membránba (általában elvárjuk, hogy a j . membrán ilyen esetekben éppen az aktuális membrán egy gyermeke legyen a fastruktúrát tekintve), egy d szimbólum kimegy az adott membránból (eggyel feljebb a membránhierarchiában), és egy e szimbólum is keletkezik, ami az aktuális membránban marad. Egy szabályban esetlegesen el®forduló olyan szimbólumokat, amelyeknek száma nem változik meg egyetlen szabály alkalmazása következtében sem katalizátoroknak nevezzük. A fenti példában ilyen a c, ® maga nem változik meg, de szükség van rá a szabály végrehajtásához. (A generatív nyelvtanok szabályaihoz hasonlítva az evolúciós szabályokat, a katalizátoros (katalitikus) szabályok valamiképpen a környezetfügg® szabályoknak feleltethet®ek meg.) A membrán struktúra egy számítási állapotát írja le a konguráció, vagyis a membránoknak megfelel® multihalmazok. Egyik kongurációból a másikba úgy megyünk át, hogy a szabályokat nemdeterminisztikus módon, maximálisan párhuzamos módon alkalmazzuk. A maximálisan párhuzamos mód azt jelenti, hogy egyik membránban sem maradhat ki a szabályok alkalmazásából olyan objektumok multihalmaza, amely tartalmaz

66


valamely ott lev® szabályhoz minden szükséges szimbólumot (a megfelel® példányszámban). Például legyen egy membrán tartalma a5 b2 . (Így adjuk meg azt a multihalmazt, ami 5 darab a és 2 darab b szimbólumot tartalmaz.) Továbbá legyenek a membránhoz tartozó evolúciós szabályok a következ®k: 1. a → ab 2. ab → a3 . Ekkor a nemdeterminisztikus maximálisan párhuzamos m¶ködés a következ® eseteket jelentheti: lejátszódhat 5-ször egyszerre az els® szabály (ekkor az alkalmazás után a5 b7 lesz a membrán tartalma); vagy 4-szer az els® és egyszer a második szabály (ekkor a7 b5 multihalmazt kapjuk); illetve 3-szor az els® és 2-szer a második szabály (a a9 b3 -t eredményezve). Minden membrán szabályai között prioritási reláció van értelmezve (ez lehet üres is, ami azt jelenti, hogy a régió minden szabálya azonos prioritású). Ez azt jelenti, hogy egy alacsonyabb prioritású szabály nem hajtható végre amíg egy nála magasabb prioritású szabály bal oldalához minden szimbólum rendelkezésre áll. Tehát ahoz, hogy egy alacsonyabb prioritású szabály (is) végrehajtódjon egy lépésben az szükséges, hogy ne legyen olyan nála nagyobb prioritású szabály ami egyel több példányban is végrehajtódhatna a lépés során. Ha például az el®bbi példában az (ab → a3 ) > (a → ab) reláció áll fenn, akkor az a5 b2 állapotból a a9 b3 állapot jöhet csak létre. Világos hogy egy membránból kiküldött szimbólum közvetlenül a szül®-membránban fog megjelenni. Ezalól viszont kivétel maga a sejt, vagyis a legküls® membrán, aminek nincs szül®je. Az innen kiküldött szimbólumok a környezetbe megy. A környezetben (elméletileg) végtelen számú el®fordulás van minden típusú objektumból, amikre akkor lehet szükség, ha van olyan szabály a legküls® membránban ami innen "beszív" szimbólumokat. Egy konguráció "meghalt" (a rendszer, illetve a számítás megállt, a számítás befejez®dött), ha nincs olyan régió, ahol szabályt lehetne alkalmazni. Nagyon fontos a számítás eredményének meghatározása (a befejezett számítások esetén).

4.2. A számítás eredménye A számítás eredményét többféleképpen is deniálhatjuk, céljainktól függ®en. A számításnak pl. a Turing-gépek számításaihoz hasonlóan akkor van eredménye, ha a számítás megállt. Ekkor, az els® módszer. Van egy kimeneti membrán, amely a membránstruktúrában tetsz®legesen elhelyezett, kitüntetett membrán. Ezesetben az eredmény a kimeneti membránban keletkezik a számítás során, a számítás végén a membrán tartalma az eredmény (melyik szimbólumból mennyi van itt.) Más számításoknál eredménynek tekinthetjük a környezetet is, oly módon, hogy tekintjük azon objektumok multihalmazát, melyek elhagyták a küls® membránt. Ily

IV.

AKTÍV MEMBRÁNOK

67

módon akár a kimeneteket stringekként is deniálhatjuk, a végeredményt (és csak azt) tekintve visszatérve a hagyományos számításokra (bár a számítás bels® lépései multihalmaz számítási lépések). Legyen L0 = {λ}. Legyen a számítás i. lépésében a környezetbe kilép® szimbólumok multihalmazának Parikh-vektora v . Ekkor Li = Li−1 · {w|Φ(w) = v}. Ha a számítás a j . lépésben véget ér, akkor Lj jelenti a futás által generált nyelvet. Tehát ha az egy lépésben a környezetbe kimen® szimbólumok összes lehetséges permutációját konkatenáljuk az addigi kimeneti nyelvhez, akkor az aktuális kimemeti nyelvet kapjuk, ami a számítás végén az adott számítás kimemeti (sztring)nyelvét adja. Tekintve a nemdeterminisztikus m¶ködést, az összes lehetséges befejez®d® számítási folyamat által generált nyelv unióját tekinthetjük az adott membrán-rendszer által generált nyelvnek. Az evolúciós szabályok nemdeterminisztikusságának valamilyen szint¶ irányítását adhatjuk meg a számításokban következ® módokon: Katalizátorok segítségével. Prioritási relációval a szabályok közt az adott membránon belül. Aktív membránok által, amit majd a következ® fejezetben részletezünk. Most nézzünk egy példát a membránrendszer m¶ködésére (4.4. ábra). A rendszer kezd®állapotában tehát egy-egy a ás b objektum található az 1. régióban, a 2. régió (ez a kimeneti membrán) üres. Az evolúciós szabályok közti prioritási reláció üres. A rednszert nyelvgenerálásra fogjuk használni. A végállapotot (megállt számítás) kivéve a rendszer minden állapotára igaz, hogy a küls® régióban pontosan egy a és egy b objektum van. Ha ezekb®l bármelyik abban az evolúciós szabályban vesz részt, ami a 2. régióba küld be szimbólumokat, akkor a maximális párhuzamosság miatt a másik szimbólum is a hasonló jelleg¶ szabály szerint kell hogy fejl®djön. Ezekben a párhuzamos lépésekben két-két a és három-három b jut be a 2. membránba. A 2. régióban nincs felhasználható szabály, ezért ami oda bekerült változatlanul ott marad a számítás befejezéséig. A számítási folyamat addig tart, amíg az els® régióban a kooperatív szabály végre nem hajtódik kiküldve az itt lev® a és b szimbólumokat a környezetbe. A számítás leáll ezzel a lépéssel. A rendszer által generált multihalmaznyelv Parikh halmaz formában írva: {(2n, 3n)|n ∈ N}. Ez a nyelv (Parikh-értelemben) lineáris, vagyis a halmaz elemei (mint kétdimenziós vektorok) egy lineáris halmazt alkotnak.

5.

Aktív membránok

Egy aktív membránnal a következ® dolgok is megtörténhetnek (a bennük lev® szimbólumok multihalmazának evolúciós szabályokkal történ® változtatásain kívül) • megsz¶nik, • keletkezik, • kettéválik (osztódik).

68


4.4. ábra. Példa kooperatív membránrendszerre

Ezek a m¶veletek azt jelentik, hogy a számítás során maga a membránstruktúra is változik. (Attól függ®en, hogy milyen a struktúrát változtató m¶veleteket engedünk meg mi állíthatjuk be a számítási modell 'erejét'. Általában a membrán megsz¶nését sokkal több modellben meg szoktuk engedni, mint pl. az új membránok létrehozását.) Például a

( ( ) ( ( ) ( ( ) ( ) ) ( ) ) 1 2 2 3 4 4 5 6 6 7 7 3 8 8 1 alakban felírt struktúrából a 2. és 7. membrán megsz¶nésével, illetve a 8. membrán osztódásával a ( ( ( ) ( ( ) ) ( ) ( ) ) 1 3 4 4 5 6 6 3 8a 8a 8b 8b 1 membránstruktúra keletkezik. Tehát az aktív membrán pl. osztódni tud. Nézzük a modellt formálisan: A membrán-számítógép:

Π

= (V, H, µ, w1 , ..., wm , R),

ahol m ≥ 1 a membránok iniciális száma. A V halmaz a szimbólumok halmaza: a rendszer ábécéje. Mindegyik membrán neve a H halmaznak, a membráncímkék véges halmazának egy eleme. µ a kezdeti membránstruktúra, m címkézett membránt tartalmaz.

IV.

AKTÍV MEMBRÁNOK

69

Az wi multihalmazok az eredeti m darab membrán tartalmát adja meg a számítás kezdetén. (wi ∈ V ∗ ) Eredetileg minden membrán semleges töltés¶. Az R a rendszer szabályainak véges halmaza. Az R elemei a következ® típusúak lehetnek: 1. [h a → v]αh (Objektum evolúciós szabálya, a töltés is megváltozhat.) h ∈ H a membrán neve amire ez a szabály érvényes, a ∈ V szimbólum, aminek az adott szabály evolúciós szabálya, v ∈ V ∗ szó, ami szimbólumokból áll, végül α ∈ {+, −, 0} töltés. 2. a[h ]αh → [h b]βh (Egy objektumot beviszünk a h membránba.) a, b ∈ V szimbólumok, h a membrán neve, α, β ∈ {+, −, 0} töltések. 3. [h a]αh → [h ]βh b (Egy objektumot kiküldünk a h membránból.) a, b ∈ V szimbólumok, h a membrán neve, α, β ∈ {+, −, 0} töltések. 4. [h a]αh → b (A h membrán megsz¶ntetése.) a, b ∈ V szimbólumok, h a membrán neve, α, β ∈ {+, −, 0} töltések. 5. [h a]αh 1 → [h b]αh 2 [h c]αh 3 (Elemi membrán osztódása.) a, b, c ∈ V szimbólumok, h ∈ H egy elemi membrán címkéje, α1 , α2 , α3 ∈ {+, −, 0} töltések. Ezen szabály használatakor, az egy helyett két azonos címkéj¶ membránt kapunk; az egyik membránban az a a b szimbólummal, a másikban c szimbólummal lesz helyettesítve, az összes többi szimbólum ami az adott membránban volt duplázódik, és mindkét membránban benne lesz egy-egy példányban. Az objektumok reakciója során a membrán címkéje nem változik, de az lehetséges, hogy a töltése megváltozik. Itt is nemdeterminisztikus módon (amennyiben több szabály is alkalmazható lenne egyszerre) maximálisan párhuzamosan történik a szabályok alkalmazása: minden id®pillanatban amelyik objektum tud evolúcióban részt venni, annak kell is. Viszont minden egyes membrán és minden egyes szimbólum (példány) egyid®ben csak egy szabályban vehet részt, természetesen az 1. típusú szabályokban csak az objektumokat számoljuk (ezek nem változtatnak semmit a membránon, a töltését sem). A párhhuzamos m¶ködésben minden membrán is csak egy szabályban (2.-5. típusúak) vehet részt egyszerre egyébként. Tehát ha pl. egy 2. típusú szabályt alkalmazunk egy i membránon, akkor ezt a membránt ebben a lépésben már használjuk, sem másik 2. sem egyéb 3.-5. típusú szabály nem használható a membránra. Amikor egy membrán megsz¶nik, akkor a tartalma a környez® membrán tartalma lesz.

70


Csak elemi membránok tudnak osztódni. A legküls® se osztódni, se törl®dni nem tud, de elektromosan az is tölthet®. A 3. típusú szabálynál objektumok hagyhatják el a rendszert. Általánosítása a rendszernek, ha nem csak elemi membránoknak engedjük meg az osztódást. Ilyenkor a bels® membránok is osztódnak, vagyis mindkét új membránban megjelennek teljes tartalommal. Ezt formálisan így írhatjuk (a fenti jelölést megtartva): 5'. [h a]αh 1 → [h b]αh 2 [h c]αh 3 , ahol h tetsz®leges (nem feltétlenül elemi) membrán címkéje. Exponenciális teret nem csak membránok osztódásával, hanem membránok létrehozásával is kaphatunk. Formálisan: 6. a → [i b]i Létrehoz egy új i címkéj¶ membránt benne a b objektummal. Az eredeti modell egy másféle kiterjesztése, amikor a membránok falának vastagsága (értsd: átereszt®képessége) változhat, illetve speciálisan a membrán így is megsz¶nhet (kb. túl vékonnyá vált és kiszakadt). A membrán falának vastagságágát speciális δ, σ ∈ / V szimbólumok segítségével szabályozhatjuk. Ezek a speciális szimbólumok szabályok jobboldalán fordulhatnak el®, és nem jelennek meg objektumként a membránban, e helyett hatásuk azonnal megjelenik a membrán tulajdonságában. Alapállapotban a membrán normálisan (átereszt® üzemmódban m¶ködik). Ha δ objektum keletkezik valamely szabály alkalmazása során, akkor a membrán megsz¶nik. Ha egy membrán megsz¶nik, akkor a benne lév® szabályok is megsz¶nnek, a benne lev® szimbólumok pedig a membrán (fastruktúrabeli) szül®membránjába kerülnek. Ha a normál állapotú membránban a másik speciális szimbólum (σ ) keletkezik, akkor a membrán fala megvastagszik, se ki se be nem juthat objektum amíg ez a vastag, nem átereszt® állapot fennáll. A nemátereszt® állapot csak a δ speciális szimbólum hatására tud visszaállni az eredeti állapotra (lásd a 5.5. ábrát). Egy membrán megsz¶nésekor a szabályai megsz¶nnek, az aktuális tartalma (a benne lev® objektumok multihalmaza) pedig a membránstruktúrában lev® szül® membránjába kerül. Egy membrán megsz¶ntetése egy benne lev® v → wδ alakú szabály végrehajtását jelenti. (Ezt úgy lehet legegyszer¶bben modellezni, hogy a rendszerben minden membrán ellen®rzi minden lépés után, hogy nem keletkezett e benne δ szimbólum. Ha keletkezett, akkor ez 'kilyukasztja' a membránt, és minden V ábécébeli szimbóluma 'kiszabadul'. Most nézzünk néhány példát olyan renszerekre, ahol membránok sz¶nhetnek meg (a δ speciális szimbólum hatására). A 5.6. ábrán egy olyan számításból látszik példa, ahol a 3. membrán megsz¶nik. A 5.7. és 5.8. ábrákon egy nyelv-generáló membránrendszer kiindulási kongurációja (a szabályokkal, és a köztük lev® prioritási relációval), illetve egy példaszámítás látható. A 3. régióban az a → ab és f → f f szabályokat iterálhatjuk (hajthatjuk végre párhuzamosan az a és az f minden el®fordulására) tetsz®legesen sokszor (i-szer, ahol i ∈ N).

IV.

AKTÍV MEMBRÁNOK

71

5.5. ábra. A membránfal vastagsága (átjárhatósága, megléte) speciális szimbólummal szabályozható

Mivel más membránban nincs objektum kezdetben, a számítás csak a 3. membránban folyik egészen addig amíg az (i + 1). lépésben a → ab szabály helyett az a → bδ végre nem hajtódik (e lépésben is hajtódik/nak végre f → f f szabályok is). i Ekkor, mivel az (i). lépés után abi f 2 -vel leírható multihalmaz volt a 3. régióban az (i+1). lépésben a harmadik régió megsz¶nik és a tartalma (az objektumok a szabályok i+1 nélkül) a 2. membránba kerül bi+1 f 2 lesz így a második membrán tartalma a lépés után. Most a 2. membrán szabályai szerint folyik a számítás: A szabályok közti prioritási reláció miatt, amíg az f -ek száma osztható kett®vel a membrán nem sz¶nik meg, hanem el®bb di+1 f 2i lesz a tartalma (b → d és f f → f szabályok), majd di+1 ei+1 f 2∧(i−1) (d → de és f f → f szabályok alkalmazása minden d és f -re) stb... Itt minden lépésben felelz®dik az f -ek száma, a d-k száma nem változik, az e-k száma pedig minden lépésben (i + 1)-gyel n®. Ez a lépés i-szer fog lejátszódni. A harmadik membrán megsz¶nése utáni (i + 1). lépés után di+1 ei(i+1) f lesz a membrán tartalma. Ekkor az f f → f szabály nem hajtható végre többször, de az f → δ szabály igen: 2 a kettes membrán megsz¶nik, és az egyesbe kerül a di+1 e(i+1) -vel leírható multihalmaz. Az els® régió szabályai szerint: a következ® lépésben az összes e a környezetebe megy. Így e(i+1)∧2 tulajdonképpen megfelel az (i + 1)2 számnak. A számítás leáll, nincs végrehajtható szabály. Az eredményt a környezetbe távozó objektumokkal értelmezve a generálható halmaz: {e, eeee, e9 , e16 , e25 , ...}, vagyis éppen a négyzetszám hosszú csak e-kb®l álló szavak. Ez a rendszer tehát legyártja a négyzetszámokat, a négyzetszámok nyelve (egybet¶s ábécével) nem környezetfüggetlen (a nyelv nem szemilineáris), vagyis 1-es típusú.

72


5.6. ábra. Részlet egy membránrendszer számításából

IV.

A KISZÁMÍTHATÓSÁG FOGALMA MEMBRÁN-RENDSZEREKBEN

73

5.7. ábra. Kiinduló állapot

6.

A kiszámíthatóság fogalma membrán-rendszerekben

Mint láttuk az el®z® példán tudunk generálni olyan halmazokat, melyek veremautómatával nem felismerhet®k. Lássuk mire is képesek számítási szempontból a membránrendszerek.

74


5.8. ábra. Egy példaszámítás Vesszük az összes rekurzíve felsorolható nyelvet: RF. Ezen nyelvek Parikh halmazainak halmaza Φ(RF). Mint ahogy már említettük egy membránrendszerbeli számítás a következ®: adott kezdeti kongurációból indul. egy kongurációból egy másik konguráció 'közvetlenül elérhet®', ha egy lépésben nemdeterminisztikusan maximálisan paralell módon hasznááljuk a szabályokat. (Átmenet két konguráció között: az összes régióra végrehajtjuk a rájuk vonatkozó szabályokat nemdeterminisztikus maximálisan párhuzamosan.) a közvetlen elérhet®ség szokásos tranzitív és reexív lezártjával deniálhatjuk az 'elérhet®ség' fogalmát. A kezd®állapotból induló, kongurácók közti átmenetek sorozata az adott rendszer egy számítása. El®fordulhatnak olyan kongurációk, melyeket a rendszer adott evolúciójában nem lehet elérni. Egy számítás eredményes, ha megáll, vagyis

IV.

A KISZÁMÍTHATÓSÁG FOGALMA MEMBRÁN-RENDSZEREKBEN

75

nincs további alkazható szabály. A hagyományos membrán-számításokban a párhuzamosság és a nemdeterminizmus szabályozására rendelkezésre állhatnak különböz® dolgok, pl. a katalizátorok, a szabályok közti prioritás, kontroll a membrán vastagságának változtatásával, valamint címezhet®ek az objektumok (kommunikációt irányítjuk, azzal hogy megmondjuk melyik membránba menjen be az objektum). Néha a számítási folyamat 'nyomon követés'ével deniálunk outputot. Például, azt gyeljük, hogy egy adott egyedi molekula (pl. katalizátor, amib®l végig pontosan egy van a számítás során) melyik membránban van az egymást követ® kongurációkban. Ekkor minden (befejez®d®) számítás egy-egy szót jelent a membánok címkéi, mint ábécé felett. Membrán rendszereket használhatjuk nyelvgenerálásra: minden egyes futás általában egy szót (vagy azonos Parikh-vektorú szavak halmazát) ad. Membránrendszerekkel id®ben hatékonyan oldhatunk meg nehéz problémákat. A következ® alfejezetben a Hamilton-út probléma egy hatékony megoldását mutatjuk be. Az aktív membránok segítségével ahogy megyünk az id®ben (lineárisan), (exponenciális) teret csinálhatunk számításainknak. Ez adja e rendszerek erejét (gyorsaságát). Aktív membránokkal a Hamilton út probléma négyzetes id®ben oldható meg, a SAT probléma pedig lineáris id®ben (az 1., 2. ,3. ,4. és 5'. típusú szabályok alkalmazásával).

6.1.

A Hamilton-kör feladat megoldása

Legyen adott egy gráf, csúcsai: N és élei: E . Legyen a csúcsok száma n: N = {a1 , ..., an }. A feladat az, hogy döntsük el van-e a gráfban Hamilton-út az a1 -t®l az an ig. Induljunk ki a következ® membránstruktúrából: µ = [0 [1 ]1 ]0 , tehát két membrán, az 1-es a 0-on (a küls® membrénen) belül. Ezen kívül legyen az (a1 , 1) objektum az 1ben. Használjuk a következ® ábécét: V = {(ai , j), (a0i , j)|1 ≤ i, j ≤ n} ∪ {M ⊆ N |M 6= 0}, vagyis az objektumaink párok, illetve a csúcsok nemüres részhalmazai lesznek. Szabályaink a következ®ek: R0 = {N → yesout } Ri = {(ai , j) → (a0k1 , j + 1) . . . (a0ks , j + 1)|(ai , akr ) ∈ E, minden1 ≤ r ≤ si , si ≥ 1 i és 1 ≤ j ≤ n − 1} ∪{(a0k , j) → [k (ak , j)]k |1 ≤ k, j ≤ n − 1} ∪{(a0n , n) → {an }} ∪{M → (M ∪ {ai })out |M ⊆ N }, minden i = 1, 2, ..., n − 1 Az ötlet ami a konstrukció mögött van: Az (ai , j) objektum jelenti azt, hogy az a1 -b®l eljutunk a ai csúcsig úgy, hogy j csúcson mentünk keresztül. Ahány helyre mehetünk az ai csúcsból tovább, annyi ilyen (a0k , j + 1) típusú objektum lesz bevezetve. Minden ilyen (a0k , j + 1) objektum létrehoz egy k címkéj¶ membránt. A lehetséges utak tehát a membrán struktúrába lesznek bekódolva. Ha van n hosszúságú utunk, akkor az a membrán struktúrában n mélységben van. Követve a számítást, amennyiben van a1 -b®l an -be vezet® Hamilton-út, akkor 3n − 2 lépés után 'IGEN' választ kapunk. Itt jegyezzük meg, hogy a felhasznált ábécé számossága a probléma méretével exponenciálisan n®. Ha Turing géppel, vagy generatív grammatikával oldjuk meg, akkor az ábécé véges, rögzített. Ezzel szemben a membrán-számítások során általában indexelt bet¶ket használva az ábécé mérete függhet a konkrétan megoldandó feladat méretét®l.

76


Membrán rendszereknél az objektumok száma, s®t a membránok száma is exponenciálisan n®het az id®ben. Tulajdonképpen ez ad esélyt ezeknek a rendszereknek arra, hogy kis id®bonyolultsággal oldjanak meg bonyolult (NP-teljes, P-space) problémákat is. Lehet csinálni determinisztikus membrán rendszereket is, mint ahogy az el®z® példán láttuk. Ezek a membrán rendszerek szimulálhatóak determinisztikus T-géppel, polinomiális lassulással. Exponenciális problémák determinisztikus membrán rendszerel nem oldhatóak meg polinomiális id®ben. Akkor tudunk könnyek pl. NP-teljes (vagy EXP) problémákat polinomiális id®ben megoldani, ha tudunk új membránokat létrehozni. A következ® részben a formális nyelvek elméletéb®l az ún. mátrix nyelvtanokkal ismerkedünk meg, amik nagyon hasznosak egyes membránrendszerek számítási univerzalitásának bizonyításához.

6.2.

Mátrix nyelvtanok

Ebben a fejezetben megint a formális nyelvek elméletéhez fordulunk segítségért. A Mátrix nyelvtanok olyan környezetfüggetlen szabályokat tartalmazó rendszerek, amelyekben a szabályok alkalmazásának sorrendje nem tetsz®leges, így akár a 0.-típusú nyelvtanok generáló ereje is elérhet® velük.

6.9. ábra. Példa mátrix-nyelvtanra Tulajdonképpen egy 2.-es típusú (környezetfüggetlen) nyelvtanunk van, de a szabályok táblázatokban (mátrix) helyezkednek el. Kiindulunk az S mondatszimbólumból. Minden levezetési lépésben szabály helyett most választani kell egy táblát és annak szabályait a sorrendjükben, mindet pontosan 1-szer kell alkalmazni. A 6.9. ábrán látható rendszer generálja az úgynevezett 'copy' nyelvet: {ww|w ∈ {a, b}∗ }, amely közismerten nem környezetfüggetlen. Ha a szabály mellett van a ⊗ jel, akkor az adott szabály kihagyható, ha nem alkalmazható. Az ilyen rendszerrel minden RF nyelv generálható. Jellemz®je ezeknek a rendszereknek: a csapdaszimbólum, amit jelenlét ellen®rzésre használhatunk. Például a {⊗ A → F, B → BB} mátrixot alkalmazva olyan mondatformára, amiben A található bevezeti az F nemterminálist. Ha sehol nincs olyan

IV.

ÖSSZEFOGLALÁS ÉS A LEGÚJABB KUTATÁSI IRÁNYOK

77

szabály, aminek a baloldalán az F van, akkor ez a levezetés nem tud terminálni. Ha viszont az A nincs benne a mondatformában, akkor egyszer¶en egy benne lev® B lesz megkett®zve a mátrix alkalmazásával. A membrán rendszerek univerzalitásának bizonyításait ilyen rendszerekre vezetik vissza. Végül néhány univerzalitási eredmény. A maximum két membránt tartalmazó katalizátort tartalmazó (aktív membránt nem tartalmazó) membránrendszerekkel minden RF nyelv Parikh-halmaza kiszámítható. Ugyancsak minden kiszámítható számhalmazt megkaphatunk kooperatív szabály(oka)t tartalmazó legfeljebb két membránt tartalmazó rendszerekkel. Minden RF nyelv Parikh-halmaza kiszámítható legfeljebb 4 membránnal az 1., 2. és 3. típusú szabályok segítségével is. (Ezekben a rendszerekben aktív membránokat és töltéseket használunk, de minden szabály sugara 1.)

7.

Összefoglalás és a legújabb kutatási irányok

A membrán-rendszereknek, mint absztrakt számítási modelleknek a biológiai motivációja a sejt, mint membrán-rendszer. Ez alapján egy absztrakt számítási modell került kidolgozásra, f®leg Gheorghe Paun vezetésével, amely alapja a membránhierarchia. Többféle modellt vizsgáltunk meg: az alapmodell, amely tartalmazhat katalizátorokat, prioritási relációt az ún. evolúciós szabályok között stb. A számításban szimbólum objektumok vesznek részt, amelyek a membránok közti kommunikációban is részt vesznek. Az aktív membránok osztódni, megsz¶nni képesek, ezzel hatékonyabbá téve a rendszert. A rendszer m¶ködése a magasszint¶ párhuzamosságra épül, a számítás akkor áll meg, ha nincs végrehajtható evolúciós szabály. A membrán rendszerek multihalmazokkal dolgoznak, minden membrán az objektumok multihalmazát tartalmazza minden lépésben. Matematikailag tehát Parikh-halmazokról, multihalmaz-nyelvekr®l van szó. A membránrendszerekkel Parikh-értelemben minden rekurzívan felsorolható halmaz generálható. Példát láttunk nem környezetfüggetlen nyelv generálására, illetve a Hamilton-út probléma hatékony megoldására is. A matematikai formalizmust tekintve a membrán-számítógépek, ugyanúgy mint a DNS-sel történ® számítások a formális nyelvek átírási szabályaival rokonok. A szakterületnek van külön honlapja, amit a Milánói Egyetem üzemeltet, innen szinte bármilyen a témával kapcsolatos anyag letölthet® ([45]). A bemutatott modelleken kívül rengeteg egyéb modell ismert, pl. elektromos töltések bevezetésén túl, olyan kommunikációs szabályok használata, amelyek megkövetelik, hogy egy adott szimbólum membránfalon történ® átjutásával egyid®ben ugyanazon a membránfalon más objektum is áthaladjon (akár ellenkez® irányban). Rengeteg olyan modell van amely a DNS-számítások valamelyikét (pl. szeletelés) ötvözi a membrán-rendszerekkel. Az aktuális kutatási irány (2005 nyara) az id®nélküli, a maximális helyett minimális párhuzamosságot megkövetel® rendszereket, valamint azokat a rendszereket is magába foglalja, amelyekben a membránokon, mint hártyákon történnek különböz® reakciók.

V. fejezet

Kvantum Számítások A kvantummechanika a XX. század egyik legnagyobb tudományos áttörése. Rengeteg a klasszikus zika által nem leírható jelenséget sikerült általa megmagyarázni. Ezek többsége megtalálható napjaink háztartási eszközeiben is. Ahhoz, viszont hogy olyan hatékony kvantumszámítógépet építsenek, amely a gyakorlatban old meg, más eszközzel nem megoldható feladato(ka)t a XXI. század feladata.

1.

A kvantum-mechanika "különös" jelenségei

A XX. század elejére a klasszikusnak nevezett zikai elméletek készen voltak és nagyjából megadták a természeti jelenségek leírását. Csak néhány apróbbnak hitt jelenség lógott ki. A zikusok azt várták, hogy néhány év alatt megválaszolják ezeket az apró kérdéseket, és meglesz a teljes zikai világ zikai leírása. Ezzel szemben ezt a pár apróbbnak hitt jelenséget tanulmányozva egy sor meghökkent® dologra került fény, kiderült, hogy a jelenségek egy hatalmas csoportja nem magyarázható meg a klasszikus elmélet keretein belül. Ebben a fejezetben néhány alapvet® nemklasszikus zikai törvényr®l és jelenségr®l fogunk szólni. A világban el®forduló véletlen eseményeket két részre bonthatjuk aszerint, hogy valódi véletleneseményr®l, vagy nem valódi véletlen eseményr®l van szó. Utóbbi esetben nem ismerjük (nincs elég információnk), vagy nagyon bonyolult lenne el®re pontosan mgjósolni a jelenséget. Ilyen pl. a dobókocka vagy a pénzérme dobása, s®t a lottóhúzás is. Ezzel a szemben a kvantummechanikai jelenségek, mint pl. a rádioaktív bomlás vagy a kvantumoptikai jelenségek valódi véletlenesemények, vagyis elméletileg sem jósolható el®re meg a kimenetelük, csak valószín¶ségeket ismerhetünk. Most egy optikai kísérletet fogunk bemutatni. Vegyünk egy polarizált fényforrást. (Köztudott, hogy a fény transzverzális hullám, vagyis a rezgés ami terjed mer®leges a terjedés irányára. Ez azt jelenti, hogy a rezgés a fény sebességére mer®leges síkban játszódik le. Polarizált fény esetén ez a rezgés egydimenziós.) Ha a polarizált fényt kalcit kristályon engedjük át az két fénysugárra törik: az egyik egyenesen megy át a kristályon, a másik eltolódással. A kristályt elhagyva a két fénysugár párhuzamos, és polarizáltságuk egymásra mer®leges. (Mintha az eredeti polarizáció vektort mer®leges vektorok összegére bontanánk.) Ha a szétbontott fény útjába egy másik kalcit kristályt helyezünk, az újra egyesíti ®ket (1.1. ábra, a polarizáltsági irányok fekete nyilakkal berajzolva). A második kristályból kilép® fény pont olyan mint az eredeti. 79

80

V. KVANTUM SZÁMíTÁSOK

1.1. ábra. A polarizált fényt az els® kalcit kristály ketté bontja, a második egyesíti

Ha a kísérletben az alsó vagy a fels® fénysugár útját elzárjuk (valamit odateszünk, amin nem tud áthaladni), akkor a második kristály utáni fény pontosan olyan polarizáltságú lesz, mint a megmaradó fénysugár. Végezzük most el ugyanezt a kísérletet egyetlen (polarizált) fotonnal (a fénysugár helyett egyetlen fény-részecskével). Az els® kristályon áthaladva 50% esély van, hogy a foton a fels®, és ugyanennyi, hogy az alsó ágon fog haladni. (Polarizáltsága is ennek megfelel®en változik). Tegyük most be a második kristályt is. Ekkor a foton az eredetivel megegyez® polarizációval fogja a második kristályt elhagyni. Azt mondhatnánk(?), volt 50% esély, hogy a fenti, és 50% esély, hogy a lenti úton haladt a foton, vagy ezen, vagy azon haladt. De (!) folyatssuk a kísérletet a következ®képpen. Blokkoljuk a fels®, majd az alsó utat. Ekkor a foton polarizációja a második kristályból kilépve megegyezik a nem blokkolt úton lev® polaritással. Ha viszont a foton csak az egyik úton haladt volna, akkor itt, a második kristály után fele-fele arányban kellene az alsó, illetve a fels® útnak megfelel® polarizácó értéket mérni. Ezzel szemben, ha mindkét út szabad akkor az eredeti polarizációt mérjük. Tehát a foton nem vagy ezt vagy azt az utat választotta, hanem egyszerre ment mindkett®n, a két út szuperpozíciójában haladt, egyszerre volt ott mindkét úton (és a második kristálynál interferált saját magával). Ez egy nemklasszikus jelenség ami a kvantumszuperpozíció nevet viseli. Ha nem mérjük meg a fotont, akkor egyszerre van jelen több állapotban. A kísérletben tehát megjelent a fény részecske-hullám kett®ssége, az állapotok szuperozíciója, illetve a mérés problémája is. Nagyon érdekes, és számunkra is fontos az a jelenség, aminek különlegessége a Schrödinger macskája nevet visel® paradoxonban fogalmazódik meg. Tehát tegyük fel, hogy egy (fekete) dobozban van egy macska, a dobozhoz csatlakozik egy csap, amin mérgez® gáz áramolhat be a dobozba. A csap vezérl®je egy

V.

A KVANTUM-MECHANIKA "KÜLÖNÖS" JELENSÉGEI

81

kvantummechanikai jelenséghez (pl. rádióaktív atom bomlása) van kötve, olyan elreendezésben, hogy 50% esély van arra, hogy a csap kinyílik és mérges gáz lepi el a dobozt, illetve ugyancsak 50% annak az esélye, hogy a acsap zárva marad a kísérlet során. Tegyük fel, hogy a kísérlet lejátszódott. Vajon él-e a macska? Amíg nem nyitjuk ki a dobozt és nem nézzük meg, addig nem tudhatjuk. Viszont, mint az el®z® kvantummechanikai kísérletben is el®fordult, amíg nem végzünk mérést (nem nézzük meg a macskát), addig a rendszer a lehetséges rendszerek szuperpozíciójában van. Ez pedig azt jelenti, hogy a macska félig életben van (50% esély) és félig halott. Ez az állapot mindaddig fennáll amíg ki nem nyitjuk a dobozt. Viszont ebb®l az következik, hogy a doboz kinyitásakor (a rendszer beáll saját-állapotba, vagyis) vagy élve marad a macska teljesen, vagy teljesen meghal. Ez viszont csak a doboz kinyitásakor d®l el. Ez paradoxon, jó magyarázat nem ismert rá. Valószín¶ arról lehet szó (ez a szerz® saját véleménye), hogy nem csak az számít mérésnek, ha egy ember megnézi mi történt, hanem ha bármilyen nem kvantumzikai folyamat függ az adott kvantum jelenségt®l. A nemkvantum jelenség méri a kvantum jelenséget, hogy bekövetkezzen-e vagy sem... Ebben a paradoxonban is megjelenik a kvantummechanikában szerepl® szuperpozíció, illetve a mérés különleges és fontos szerepe. A Heisenberg-féle határozatlansági reláció kimondja, hogy olyan állapot nem létezik, amelyben minden zikai mennyiség egyidej¶leg pontos értéket vesz fel. Vannak olyan egymással párban álló mennyiségek (ezek a fel nem cserélhet® operátorokkal leírható mennyiségek) amiknek értékei minden állapotban elmosódottak, vagyis a két mennyiség egyidej¶ mérésének pontossága elméletileg sem lehet bármekkora. Ilyen mennyiségek például a hely és az impulzus. Formálisan: ~ 4x4px ≥ , 2 ahol a ~ egy univerzális zikai állandó, x az egyik helykoordináta, 4x a helykoordináta mérési bizonytalansága (hibája), px az x irányú lendület (impulzus, px = mvx , ahol m a részecske tömege, vx pedig az x irányú sebességkomponense), 4px pedig az x irányú impulzus bizonytalansága. Ez azt jelenti, hogy a helykoordináta és az ezirányú sebességkomponens egyidej¶leg csak bizonytalanul ismerhet® (mérhet®), minél pontosabban mérjük az egyiket, annál nagyobb hibával ismerhetjük csak a másik értéket. Heisenberg több gyakorlati példát is mutatott az összefüggés alátámasztására. A határozatlansági relációnak fontos szerepe van az úgynevezett részecske-hullám kett®sség megmutatkozásában is. Az ugyanis, hogy egy adott részecske állapota a klasszikus tömegpont, vagy a klasszikus hullám fogalmához áll-e közelebb az attól függ, hogy milyen típusú m¶sszerrel mérjük: olyannal ami a helyet vagy olyannal ami az impulzust méri pontos(abb)an. Egyszerre a két mennyiség a határozatlansági összefüggés értelmében nem mérhet® pontosan. Nézzük tehát, hogyan aknázhatjuk ki a kvantum-mechanika egyes jelenségeit, hogyan foghatjuk számításra a "kvantumokat". A további fontos jellemz®i vannak a kvantum-elméletnek: Nem klónozhatunk: ellenben pl. a hagyományos számítástechnikával, ahol a változókat többször felhasználhatjuk értékadásokban (jobb oldalán) anélkül hogy értékük változna, a kvantumelméletben tetsz®leges érték nem másolható. Mint láttuk a

82


"klónozás" a DNS számítógép egyik "fegyvere", ett®l hatékony, rövid id® alatt akár millió példányban lesz jelen az adott molekula. Ezzel szemben a kvantummechanikában csak ismert (megmért) értékek másolhatók le, ismeretlen érték¶ kvantum állapot (és kvantum-bit, röviden kubit) nem másolható. Ennek nem gyakorlati hanem elméleti okai vannak. A következ®kben egy újabb kvantumjelenséget írunk le ami Einstein, Podolsky és Rosen nevéb®l az EPR rövidítést kapta. Ennek egy kísérleti megfogalmazása Mermin nevéhez f¶z®dik. A berendezés három semmilyen módon nem összekötött darabból áll. Van két detektor (D1 és D2) és egy részecske forrás (F). A forrás a két detektor közt helyezkedik el, oly módon, hogy gombnyomásra a forrás egy-egy részecskét indít a két detektor felé. Mindkét detektor három állapotú, és rendelkezik egy piros és egy zöld lámpával (1.2. ábra). A lámpák azért vannak, hogy a meggyel® információhoz jusson. A detektorokon mindig kigyullad az egyik lámpa, ha részecske érkezik. Mivel semmilyen kapcsolat nincs a berendezések közt, az F-en lev® gomb megnyomása, vagyis a részecskék indítása a felvillanásokkal csak az F-b®l a D1-be illetve D2-be érkez® részecskékkel köt®dik össze. Ismételjük a következ® lépéseket. 1. Állítsuk a D1 és D3 berendezéseket véletlenszer¶en valamelyik állapotba, úgy hogy mind a kilenc állapot-párnak azonos valószín¶sége legyen. 2. nyomjuk meg az F gombját: részecske indul D1 és D2-höz. 3. kicsit kés®bb mind D1-nek, mind D2-nek felvillan az egyik lámpája (piros vagy zöld). 4. Vegyük fel a futás eredményét ijXY alakban: D1 az i, D2 a j állapotban volt a D1 az X fényt, D2 az Y -t villantotta fel. Ekkor elég sok futás után azt kapjuk, hogy az i = j esetekben mindkét detektor ugyanazt a színt villantotta fel: a piros-piros és a zöld-zöld azonos valószín¶séggel villant, a piros-zöld és a zöld-piros kombináció soha nem fordult el®. Az i 6= j esetekben pedig ugyanaz a szín az esetek negyedében villant fel (ezen belül egyforma valószín¶séggel a piros-piros és a zöld-zöld), különböz® szinek pedig az esetek 3 -ében. 4 Mivel a detektorok közt nincs kapcsolat, feltehetjük, hogy a beérkez® részecske valamilyen tulajdonsága alapján döntenek arról melyik szín¶ lámpa fog kigyulladni. Mindegy mi ez a tulajdonság, a lényeg az, hogy a részecskébe ez a tulajdonság mintegy be van programozva. Habár D1 és D2 nincs összekötve, tehát nem tudhat a másik állapotáról, csak így lehet összefüggés köztük. Tehát legyenek a részecskék típusai leírhatóak az XY Z alakban. Ez a típus azt jelzi, hogy az els® állapotban lev® detektor az X színt, a második állapotban lev® az Y -t, a harmadik állapotban lev® a Z -t gyújtja/aná ki az adott részecskére. Tehát két hipotézissel magyarázhatjuk a jelenséget: legyen 8 féle típusú részecskénk (a színeknek megfelel®en), és legyenek azonos típusúak az F-ben egyszerre generált részecskék. A detektorok ugyanazt a színt gyújtják ki, ha ugyanabban az állapotban vannak, mivel a kapott részecskékben ugyanaz a 'program' van. Ehhez az F-nek semmit sem kell tudnia a detektorok állapotáról. A kísérletben nem a két detektor kommunikált egymással, tehát az nem mond ellent a fénysebesség határsebességének. Viszont a mi szempontunkból a fontos az, hogy léteznek olyan részecskepárok, hogy az egyik mérése kihat a másik értékére is.

V.

A "MEGFORDÍTHATÓ" SZÁMÍTÁSTECHNIKA

83

1.2. ábra. Mermin kísérlete A kvantum-számítástechnikában egy "algoritmus", illetve egy "program" általában arról szól, hogy megkonstruálunk valamilyen zikai folyamatot, aminek a végén egyetlen mérés segítségével kell tudnunk eldönteni a választ a kérdésünkre. Bevezetésként nézzünk egy feladványt (nem a kvantum-mechanika világából), ami hasonló gondolkodást kíván, okosan kell elrendezni a dolgokat, hogy egy méréssel megkaphassuk az eredményt. Adott 10 automata, mindegyik érméket gyárt. Adottan, minden érmének 10 gramm súlyúnak kellene lennie. Tudjuk, hogy egy automata meghibásodott, és 0,1 grammal eltér® súlyú érméket gyárt (azt nem tudjuk, hogy könnyebbeket vagy nehezebbeket). Döntsük el egyetlen mérés (mérleg) segítségével, hogy melyik automata gyártja a hibás érméket! Megoldás: Tehát egyetlen kísérleti eredményb®l kell rekonstruálnunk a helyzetet. Számozzuk meg az automatákat egyt®l tízig. Vegyünk mindegyik atomata által készített érmékb®l pontosan annyit, amennyi a sorszáma az adott automatának. Tegyük fel az összeszedett érméket a mérlegre és mérjük meg a súlyukat. Világos, hogy az eltérés tized grammokban a legközelebbi egészt®l éppen a hibás automata sorszámát adja eredményül. (Lásd a 1.3. ábrát.) Tulajdonképpen, matematikai szempontból a kvantumszámítógép annyivel általánosabb a hagyományosnál, hogy a kétérték¶ bit helyett (ami lehetne pl. +1 és -1) egy egy abszolútérték¶ komplex szám lehet a bit értéke. (Így, viszont a valós 2 ilyen érték helyett végtelen sok különböz® értéket vehet fel a kubit.) Viszont méréskor csak a klasszikus értékeket kaphatjuk meg (bizonyos valószín¶ségekkel).

2.

A "megfordítható" számítástechnika

Most összekapcsoljuk a számítástechnikát a zikával: ugyanis a számítások a hardver szintjén zikai folyamatokkal történnek. Létezik egy fogalom amit Kvantum Turing-gép nek neveznek. Megmutatták, hogy ez ekvivalens a kvantum áramkörökkel bizonyos probléma osztályra, de az még nincs bizonyítva, hogy ez az ekvivalencia univerzális is lenne. Ez nem okoz problémát, hiszen a kvantum áramkörök azok amikkel valójában dolgozunk a kvantum számítások során,

84


1.3. ábra. Érmék kiválasztása a méréshez

illetve ezek alkotják az egyetlen napjainkban elérhet® nyelvet a kvantum algoritmusok szabályrendszeréhez. Tehát a Kvantum Turing-gép csak egyfajta elméleti dekoráció. Ezzel szemben ha lenne valamiféle kvantum lambda kalkulusunk, akkor ez már egy sokkal hasznosabb eszköz lenne, mert megengedné, hogy egy magasszint¶ nyelven gondolkodjunk a kvantum algoritmusokon és a kvantummechanikán. Az els® digitális áramkörök és napjaink számítógépeinek is meghatározó elemei a tranzisztorok és más alkatrészek. A számításokról való elképzeléseinket is annyira befolyásolja a digitális elektronika, hogy hajlamosak vagyunk megfeledkezni az analóg számításokról, és analóg jelfeldolgozásról, pedig ezek mindegyike jelent®sen gyorsabb, illetve energiatakarékosabb, mint digitális megfelel®je. A kvantum számítás visszahozza ezeket az analóg eszközöket, és egy bizonyos úton ez eredményezi a Kvantum Számítógépek hatalmas erejét. Mérnöki szemszögb®l vizsgálva a Turing-gép és a lambda kalkulus sem teljes leírása annak amit a számításnak hívunk. Mindkett® szekvenciális programozási nyelv így mondanak ugyan valamit általánosan a számítógépekr®l mint gépekr®l és egy keveset a párhuzamos számításról és kommunikációról, de semmit sem a számítások termodinamikájáról.

V.

A "MEGFORDÍTHATÓ" SZÁMÍTÁSTECHNIKA

85

Példaképpen egy bit információ törlésénél legkevesebb kT ln 2 Joule h® keletkezik, ahol T a környezet h®mérséklete, ahol a számítás végbemegy és k pedig a Boltzmann állandó. Ez az eredmény, ami Landauer-nek köszönhet®, nagyon fontos a mérnököknek és zikusoknak. Sem a Turing-gépet, sem a lambda-kalkulust nem lehet arra használni, hogy ilyen zikai szinten fontos megállapításokat felhasználhassunk. Vegyük észre, hogy bármely nem egyértelm¶ érvelés látszólag elvesztett információt eredményez. Például a klasszikus számítások univerzális kapuja a NAND kapu információt veszít. A kaput a következ® formulával írhatjuk le: (x, y) → ¬(x ∧ y). Ha a jobb oldali érték 1, akkor x ∧ y = 0. Ez azt jelenti, hogy x vagyy vagy mindkett® 0. Nem tudjuk, hogy melyik. Ez az információ elvész, tehát h®nek kell keletkeznie. Ezt az észrevételt felhasználhatjuk mint feltételt a tételek bizonyítása során ellen®rzésre. Miután különböz® utakon manipuláltuk a formuláinkat, egyszer¶en vizsgáljuk meg, hogy mennyi h®t generáltunk. Amennyiben nem generáltunk semennyit, abban az esetben valószín¶leg semmivel sem kerültünk közelebb a bizonyításhoz. A fenti számítások leginkább a zikában m¶ködnek. Ahhoz, hogy egy h®er®gépet munkára bírjunk, egy bizonyos mennyiség¶ h®t el kell pazarolnunk. Ez az eredmény Carnot nevéhez f¶z®dik (Carnot-körfolymat). Az élet tele van apró meglepetésekkel, és meglep® módon legalább az elméletben lehetséges úgy végeznünk számításokat, hogy nem veszítünk információt. Létezik egy 3-bemenet¶ kapu a Tooli kapu ami univerzális és ugyanakkor visszafordítható, tehát nem veszít információt, és ebb®l kifolyólag nem keletkezik h®. A Toffoli kapu a következ®képpen van deniálva:

(x, y, z) → T (xc , yc , zt ) = (x, y, (x ∧ y) ⊕ z). Néha szokták nevezni vezérelt-vezérelt -NEM kapunak is. Az els® két paramétert nevezhetjük vezérl® ágaknak a harmadikat pedig cél ágnak. A cél ág csak akkor változik, ha mindkét vezérl® ág értéke 1 ahol ⊕ = +2 a bináris összeadás operátora, vagy más néven a kizáróvagy operátor. (Vegyük észre, hogy 0 ⊕ x = x és 1 ⊕ x = ¬x) A T (xc , yc , zt ) jelölés megengedi a vezérl® ágak és a cél ág szerepének felcserélését, tehát ki tudjuk számolni a T (xc , yc , zt ) = (x, y, (x ∧ y) ⊕ z) értékét. A Tooli kapu diagrammja a 2.4. ábrán látható. Ha a z helyére 1-et írunk akkor a következ®t kapjuk:

T (xc , yc , 1) = (x ∧ y) ⊕ 1 = ¬(x ∧ y) ami nem más mint x NAND y . Tehát ahogy a NAND úgy a Tooli kapu is univerzális, segítségével bármilyen logikai kapu szimulálható. Ugyancsak könny¶ észrevenni, hogy a kapu nem veszít információt. A fels® két szálon nem vész el információ, ezért az alsón mindig újra tudjuk konstruálni az inputot, ha tudjuk, hogy mi az output. A ⊕ szimbólum a legalsó szálon felfogható egy egyszer¶ kapuként 3 bemenettel x, y , és z és egy kimenettel (x∧y)⊕z . Ahogy információt veszít abból kifolyólag h®t is termel. A tény, hogy az input információt eltároljuk a fels® két szálon még nem változtatja meg azt, hogy maga a kapu információt veszít, és ezáltal nem visszafordítható.

86


2.4. ábra. A Tooli kapu diagrammja

Ha a fenti módszer alapján próbálnánk implementálni a Tooli kaput, nem jutnánk semmivel el®rébb, ugyanúgy veszne az energia a h®termeléssel. Ahhoz, hogy tényleg h® termelése nélkül m¶ködjön, teljesen másképpen, egy alap 3 × 3-as kapuként kell implementálni. 1982-ben javasolta Fredkin és Tooli a Billiárd Golyó Számítási Modellt, amely a Tooli kapu egy valóban visszafordítható megvalósítását demonstrálja. Akárcsak a billiárd golyók a játékban a golyók Fredkin és Tooli számítógépében is egymásnak és a falnak ütköznek, miközben számítás megy végbe. Ha az ütközések rugalmasak, és az asztalon keletkez® súrlódást ki lehetne küszöbölni, akkor a számítások h® termelése nélkül zajlanának le. Persze ez a két feltétel gyakorlatilag teljesíthetetlen, így a Billiárdgolyó Számítógép csak egy idealizált modell. A Tooli kapunak nagyobb jelent®sége van a kvantum számításokban, mivel kvantum megfelel®je a Deutsch kapu a kvantum számításokhoz univerzális. Ezenfelül a kvantum számítások reverzibilisek, vagyis elvileg h®termelés nélkül végezhet®ek. Ha az információt kvantum rendszerekbe kódolnánk, és a feldolgozáshoz kvantum m¶veleteket használnánk, hamar észrevennénk, hogy számos dolgot nem tehetünk meg ami a klasszikus világban egyébként biztosítva van, ilyen például az információ másolása az egyik helyr®l a másikra. A kvantumok világában az információt teleportálni lehet két hely közt, és a folyamat során a kiindulási helyszínen meg kell semmisülnie. Másrészr®l számos olyan dolgot megtehetünk a kvantum-világban amit a klasszikusban nem. Például el®állíthatjuk az IGAZ és HAMIS szuperpozícióját, az IGAZ és HAMIS tetsz®leges arányával. Ez a kvantum számításokban a logikai értékeket többérték¶vé, a fuzzy logika értékeihez hasonlóvá teszi, de a kvantumelméletben a logika annál sokkal gazdagabb, mivel a kvantumvilágban a logikai változók komplex érték¶ek, nem csak valós számok.

V.

A KUBIT

87

Nézzük most azokat a legegyszer¶bb elemeket, amik a kvantum rendszerek megvalósításához szükségesek. A klasszikus számítógépek egységei, mint például a NAND kapuk (ezek legalább két tranzisztort és több ellenállást is tartalmaznak) rendkívül bonyolultak. Ezzel szemben a kvantum számításokhoz szükséges elemi berendezések sokkal egyszer¶bbek, így m¶ködésük is könnyebben érthet®.

3.

A kubit

A kvantumzika egyik legegyszer¶bb és mégis egyik legérdekesebb jelensége az elemi részecskék mágneses polaritása. Ha egy protonnyalábot átküldünk egy lyukon amiben ∇B 6= 0 irányszög¶ B inhomogén mágneses mez® van, akkor a nyaláb két nyalábra szakad. Az eszközt Stern-Gerlach berendezésnek hívják, amit Otto Stern és Walther Gerlach talált fel 1920-ban. Ami a dologban rejtélyes az az, hogy a klasszikus zika szerint a nyalábnak el kéne ken®dnie ahelyett, hogy két részre szakad. A klasszikus zika úgy hiszi, hogy egy proton mágneses dipólusmomentuma µp egy nem polarizált sugárban képes bármilyen irányba mutatni, és bármekkora értéket felvehet attól függ®en, hogy az elektromos töltések milyen gyorsan keringenek a protonban. A Stern-Gerlach kísérlet meglep® eredménye, hogy a proton mágneses dipólusmomentuma mindig igazodik a küls®leg alkalmazott mágneses mez® irányához. Mutathat a mez® irányába, vagy az ellenkez® irányba. Ezenkívül a proton mágneses momentuma, amit el®ször Otto Stern mért meg, és 1943-ban Nobel Díjat kapott érte, mindig ugyanannyi (µp = 2, 792782 ± 0, 000017µn ). A proton energiája egy B statikus mágneses mez®ben továbbra is mérhet® a klasszikus E = −(±µp )B képlettel, ahol az el®jel a dipólus irányától függ (B irányával megegyez®, vagy azzal ellentétes). Ha B irányával megegyezik, akkor a proton energiája E− = −µp B , ha vele ellentétes, akkor E+ = +µp B . Egy küls® mágneses mez®be ágyazott proton ebben a két állapotban lehet: egy magasabb és egy alacsonyabb energiájú állapotban. Ezt a két állapotot a következ®kben |+i és |−i szimbólumokkal jelöljük. Bármi ami | és i között helyezkedik el ezentúl a kvantumállapot nevet fogja viselni. A |+i és |−i állapot stabil. Ez azt jelenti, hogy ha egy protont elhelyezünk a |−i állapotba, akkor az ebben az állapotban marad egészen addig, amíg valami ki nem zökkenti bel®le. Hasonlóan, ha a |+i állapotba helyezzük, akkor egy jó darabig úgy is marad. Nem marad így örökre, mivel ez nem alapállapot, tehát végül a proton kibocsát egy fotont, és az alacsonyabb |−i energiaállapotba kerül. Ezt a jelenséget hívjuk spontán emissziónak, vagy disszipációnak, és ez az egyik f® hibaforrása a kvantumszámításoknak. Ennek ellenére a |+i állapot elég hosszú ideig 'él' ahhoz, hogy a gyakorlatban felhasználhassuk számításainkban. Megfeleltethetjük a logikai IGAZ-at vagy 1-et a |+i jelöléssel, és a logikai HAMISat vagy 0-át a |−i jelöléssel, így adatot tudunk tárolni a protonban. A kvantum számításokban a következ® jelölést használjuk:

|1i ≡ |+i

88


|0i ≡ |−i és a kvantum állapotokat számítási bázis állapot -nak nevezzük. Ezt az egyszer¶ atomi adattárolót, ami egy protonon egy bit információt enged tárolni, kubit (qubit)-nak hívják a quatum bit rövidítéséb®l. Ha az információt kubitbe kódoljuk, még nem jelenti azt, hogy kvantum számításokat is kell alkalmaznunk. Végezhetünk klasszikus számításokat kubiteken. Ha ezen az úton használjuk ®ket, akkor nem fognak különbözni a klasszikus bitekt®l a méret illetve a formájuk és m¶ködésük egyszer¶ségének kivételével.

4.

A Kubit Transzformációi

Most lássuk, hogy miben is különböznek a kubitek a bitekt®l. Képzeljük el a következ® kísérletet. Tegyük fel, hogy van egy protonunk, aminek a mágneses momentuma a B mágneses mez® irányába van állítva. A proton a |−i állapotban van. Most kapcsoljuk ki a mez®t, ekkor a proton ugyanabban az állapotban marad, anélkül, hogy a mez® ott lenne. Most eresszünk a protonra egy másik mez®t B't ami az eredetivel valamilyen α szöget zár be. Természetesen, ahogy Stern kísérlete is mutatja a proton egy új kvantum állapotba kerül, amelyben a mágneses momentuma megegyez® (|−0 i) vagy ellentétes (|+0 i) irányban áll a B' mez®vel. De vajon melyikbe? Nem tud(hat)juk. Nincs sem matematikai, sem kísérleti, sem másféle olyan módszer, amivel meg tudnánk mondani el®re, hogy a proton a |−i állapotból a |−0 i és |+0 i állapotok közül melyikbe tér át. A proton azt csinál amit akar. Napjainkban a hivatalos meggy®z®dés a zikában az, hogy egy önálló kvantum rendszer viselkedése megjósolhatatlan (teljesen véletlen). A kísérletet többször megismételve a protonok egy része a |+0 i a másik része a |−0 i állapotba vált. Amennyiben a kísérletek száma vagy az azonosan el®készített protonok száma elég nagy, akkor a két rész aránya egy számhoz fog konvergálni, ami csakis α függvénye lehet. Az eredmények aránya, ami a kísérletek statisztikai együttesén alapul, a |−i -ból |+0 i -ba vagy a |−i -ból |−0 i -be való átmenet valószín¶sége. A kvantum mechanika alapvet® fogalma a valószín¶ségi amplitúdó. A |−i-ból |+0 ibe való átmenet valószín¶ségi amplitúdójának jelölése: h+0 |−i és hasonlóan h−0 |−i jelöli a valószín¶ségi amplitúdóját a |−i |−0 i átmenetnek. A valószín¶ségi amplitúdó általában komplex szám. Az átmenet valószín¶ségét úgy kapjuk, hogy vesszük a megfelel® valószín¶ségi amplitúdót és megszorozzuk a komplex konjugáltjával. Például,

P|+0 i,|−i = h+0 |−ih+0 |−i∗ ahol P|+0 i,|−i a |−i-ból |+0 i állapotba való átmenet valószín¶sége. Az amplitúdók valószín¶ségi megfelel®je a következ® kézenfekv® feltételt adja: 1 = P|+0 i,|−i + P|−0 i,|−i = h+0 |−ih+0 |−i∗ + h−0 |−ih−0 |−i∗ (4.1) Ha egy átmenet több al-átmenetb®l áll, akkor az átmenet valószín¶ségi amplitúdója az al-átmenetek valószín¶ségi amplitúdójának a szorzata lesz. Például ha egy proton átvált |−i-ból |−0 i-be utána pedig |−0 i-b®l |+”i-be akkor a teljes folyamat valószín¶ségi amplitúdója: h+00 |−i = h+00 |−0 ih−0 |−i.

V.

A KUBIT TRANSZFORMÁCIÓI

89

Igazán érdekes dolog történik, ha a proton választhat, hogy |−i-ból |−0 i-be vagy |+0 i-be tér át a | + ”i felé vezet® úton. Ekkor a folyamat valószín¶ségi amplitúdóját az összes lehet®ség valószín¶ségi amplitúdójának az összege adja.

h+”|−i = h+”|−0 ih−0 |−i + h+”|+0 ih+0 |−i (4.2) Ezt a sajátságos kvantum eektust kvantum interferenciá nak vagy kvantum párhuzamosság nak szokták nevezni. Az ok amiért a zikusok kvantum párhuzamosságnak nevezik az az, hogy a feltételek értelmezhet®ek úgy, hogy a proton |−i-ból | + ”i -be egyidej¶leg megy |−0 i és |+0 i állapotokon keresztül is. Feynman út integrál formulája a kvantum mechanikában ugyanezt a dolgot jelenti. Van egy részecskénk, ami kibocsátódik egy jól deniált helyr®l valamilyen id®ben, majd egy másik id®pontban megérkezik egy máshol elhelyezett detektorhoz. A kiindulási ponttól a detektorig a részecske különböz® utakon, más-más röppályákon és különböz® sebességgel érkezhet. A Feynman elv azt mondja, hogy a részecske egyszerre párhuzamosan követi ezeket a röppályákat. Minden röppályához tartozik egy valószín¶ségi amplitúdó. A teljes folyamat valószín¶ségi amplitúdója megegyezik az egyes röppályákhoz tartozók összegével. Most gondolkodjunk el a következ® kísérleten, amelyben a proton el®ször B-hez majd B'-hez majd ismét B-hez igazodik. Tegyük fel, hogy a proton a |−i állapotban van. A valószín¶ségi amplitúdója annak, hogy a folyamat végére ebben is marad: h−|−0 ih−0 |−i + h−|+0 ih+0 |−i mivel a proton |−i -ból ugyan ide két úton juthat: |−0 i-n és |+0 i-n keresztül. Mivel a statikus mágneses mez® nem végezhet semmilyen munkát, ezért a folyamat teljes lefolyása alatt nem történhet energiaáramlás. Ebb®l arra következtethetünk, hogy a proton megtartja eredeti állapotát. Emiatt a fenti folyamat amplitúdójának 1-nek kell lennie. Most vessük össze az eredményünket az el®z®ekkel ami a (4.1) egyenl®séggel kezd®dött. Tekintve a megfelel® amplitúdókat a következ® két egyenl®séget kapjuk:

1 = h−|−0 ih−0 |−i + h−|+0 ih+0 |−i, 1 = h−0 |−i∗ h−0 |−i + h+0 |−i∗ h+0 |−i. Ennek a két egyenl®ségnek minden α szögre teljesülnie kell. Ez csak akkor lehetséges, ha h−|−0 i = h−0 |−i∗ , és

h−|+0 i = h+0 |−i∗ . Ugyan ez mutatható meg |+i, |−i, |+0 i és |−0 i összes többi kombinációjára. Tehát kijelenthetjük, hogy ha|bihb|ai∗ minden |ai és |bi kvantum állapotra. Most egészítsük ki a meggyelésünket a következ® állításokkal: • Mivel h+|+i és h−|−i szimmetrikusak, ezért valósaknak is kell lenniük.

90


• Ha egy protont a |−i állapotba helyezünk, akkor a valószín¶sége annak, hogy ugyan ebben az állapotban marad azután, hogy nem csináltunk vele semmit 1. Tehát 1 = P|−i,|−i = |h−|−i|2 , és h−|−i = 1 Ugyanez érvényes h+|+i-ra is. • Ha egy protont a |−i állapotba helyezünk, akkor a valószín¶sége annak, hogy a |+i állapotba kerül miközben nem csináltunk vele semmit 0. Tehát 0 = P|+i,|−i = |h+|−i|2 , és h+|−i = 0 Ugyanez érvényes h−|+i-ra is. Most tekintsük meg újra a (4.2)-es képletet, amely egy átmenetet ír le B-b®l B' n keresztül valamilyen B -be. Minden végs® |x00 i állapotra felírhatjuk az alábbi összefüggéseket: hx00 |−i = hx00 |−0 ih−0 |−i + hx00 |+0 ih+0 |−i, hx00 |+i = hx00 |−0 ih−0 |+i + hx00 |+0 ih+0 |+i. Mivel ez minden |x00 i-re és minden B -re fennáll, ezért a fenti egyenletek mindkét oldaláról elhagyhatjuk az hx00 | el®tagot. Ekkor a következ®ket kapjuk:

|−i = |−0 ih−0 |−i + |+0 ih+0 |−i, |+i = |−0 ih−0 |+i + |+0 ih+0 |+i. Ez a két egyenlet fejezi ki a kvantum mechanikai szuperpozíció elvét. Láthatjuk, hogy ez nem más, mint a kvantum párhuzamosság. Az összes eddigi tapasztalatunkat összevetve a következ®ket kapjuk: • A |+i és |−i állapotok kifejezhet®k a |+0 i és |−0 i álapotok lineáris kombinációjaként, és fordítva. Ez azt jelenti, hogy egy mágneses mez®be ágyazott proton kvantum állapotai 2-dimenziós vektorteret alkotnak. • Ezen lineáris felbontások együtthatói valószín¶ségi amplitúdók, ezért a vektortér a komplex számok felett van. • A valószín¶ségi amplitúdók rendelkeznek a komplex érték¶ skaláris szorzatok minden tulajdonságával, ezért a vektortér Hilbert tér. • A |+i és |−i állapotok mer®legesek egymásra, és a hosszuk 1. Ugyanez mondható el a |+0 i és |−0 i állapotokról is. • A {|−i, |+i} és {|−0 i, |+0 i} állapot párok két különböz® ortonormált bázist alkotnak a Hilbert térben. • Az amplitúdók bal oldalát (pl.: h+|) tekinthetjük ko-vektoroknak a Hilbert térben. Ha a B' mer®leges a B -re, akkor a |+i és |−i állapotok szimmetrikusak a |−0 i és |+0 i állapotokra nézve, és fordítva. Ebb®l következtethetünk arra, hogy a {|−i, |+i}ból {|−0 i, |+0 i}-ba vezet® transzformációnak is rendelkeznie kell hasonló szimmetriával, vagyis nem támogathat jobban egy bizonyos bázisvektort a többinél. Íme egy példa egy ilyesmi transzformációra:

|−i = √12 (|−0 i + |+0 i) |+i = √12 (|−0 i − |+0 i) (4.3) Ez egy azon transzformációk közül, amik a proton 90-os elforgatását írják le. A neve Hadamard transzformáció.

V.

A KVANTUM REGISZTER

91

Tegyük fel, hogy a protonunk a |−i kezd®állapotban van, de ekkor átkapcsoljuk a mágneses mez®t B' -re ami mer®leges B -re, és ebben az új rendszerben végzünk számításokat. A kezd®állapota a protonnak ekkor:

1 1 1 √ (|−0 i + |+0 i) = √ (|00 i + |10 i) = √ (|HAMISi + |IGAZi) 2 2 2 Másrészr®l a proton sem nem |00 i-t sem nem |10 i-t tartalmaz, hanem a két lehetséges logikai értéknek egy furcsa kinézet¶ szuperpozícióját. B és B' által bezárt α szögt®l függ®en a protont megtölthetjük az IGAZ és HAMIS tetsz®leges arányával. Emlékezzünk vissza, hogy csak akkor tudhatjuk meg mi ez az arány, ha méréseket végzünk egyénileg el®készített és feldolgozott protonok statisztikai együttesén. Az egy protonon elvégzett mérés eredménye vagy IGAZ' vagy HAMIS' lesz és, hogy melyik, az rendszerint megjósolhatatlan.

5.

A Kvantum Regiszter

Eddig arról volt szó, hogy hogyan tárolhatunk el egy bit információt egyetlen protonban, vagy a |0i és |1i állapotok szuperpozícióját egyes protonok statisztikai együttesén. De hogyan tárolhatnánk kett®, vagy annál több bit információt? Jó megoldásnak t¶nik egy új elemi részecske bevonása, mint például a neutron. Habár a neutronnak nincs elektromos töltése, rendelkezik mágneses dipólusmomentummal ami µn = (1, 913148 ± 0, 000066)µN . Emlékezzünk, hogy ugyanez a protonnál µp = (2, 792782 ± 0, 000017)µN . Tehát amit eddig a protonról elmondtunk, az érvényes lesz a neutronra is, csak a µp -t kell kicserélnünk µn -re. Tehát ha a neutront belehelyezzük egy B mágneses mez®be, akkor a |+in vagy a |−in kvantumállapotot veheti fel. Most már tudunk tárolni 2 bitet, egyet a protonon, egyet pedig a neutronon. Tegyük fel, hogy a következ® állapotokba helyezzük a részecskéinket: |+in és |−ip . ahol a p index a proton állapotát jelöli. Mit mondhatunk a rendszer átmeneti valószín¶ségeir®l? Ha forgatjuk a mágneses mez®t, (tegyük fel, hogy mindkét részecskére ugyanaz a mez® hat,) és méréseket végzünk a részecskéken, akkor ismét csak azt kapjuk, hogy el®re nem meghatározható mi lesz az eredmény. De ha ugyanolyan mérések sorozatát végezzük el, vagy megegyez®en el®készített proton-neutron párok nagy halmazán végzünk egyszeri méréseket, akkor azt kapjuk, hogy jól deniált valószín¶ségek rendelhet®k a különböz® átmenetekhez, és ezek a valószín¶ségek klasszikus szabályok szerint alakulnak. Például annak a valószín¶sége, hogy a neutron a |+in - ból a |−0 in állapotba megy és eközben a proton a |−ip -b®l a |−0 ip -be:

P|−0 in ,|+in P|−0 ip ,|−ip = |n h−0 |+in |2 |p h−0 |−ip |2 = |n h−0 |+in p h−0 |−ip |2 . Eszerint a 2-részecskés folyamat amplitúdója egyenl® a megfelel® 1-részecskés folyamatok amplitúdójának a szorzatával. Eszerint gondolhatunk az egyes részecskék állapotainak formális szorzatára, mint külön állapotokra. Pl.: |+in |−ip . A formális szorzat azt jelenti, hogy azon kívül, hogy

92


a két állapotot leírjuk egymás mellé, mást nem teszünk velük. Minden egyes vektor a saját külön Hilbert terében van. Akárhányszor forgatást, vagy más m¶veletet végzünk ezen a két-részecskés rendszeren, minden vektorhoz hozzá kell rendelnünk egy megfelel® egy-részecskés operátort. Az ilyen szorzatot nevezik a matematikusok tenzor szotzat nak és a ⊗ szimbólummal jelölik. A zikusok egyszer¶en elhagyják a két vektor közötti i| jeleket, és valahogy így írják | +n −p i. Eddig vagy egy protont vagy egy protont és egy neutront vizsgáltunk egy mágneses térrel kitöltött vákuumtérben. Most gondoljunk a protonra, mint egy molekulához kémiai kötéssel kapcsolódó elemre. A molekulának különleges felépítése lehet, amely befolyásolhatja a különböz® módon csatlakozott protonokat, attól függ®en, hogy azok hol helyezkednek el a molekulában. Ez elég különböz®séget biztosíthat ahhoz, hogy mindegyikhez külön kommunikációs csatornát rendelhessünk. Mivel a protonok már nem identikusak, ezért a fenti matematikai összefüggések már nem érvényesek rájuk, különböz®képpen fognak viselkedni. Tegyük fel, hogy 8 protont rendelünk egy molekulához ezen az úton. Az összesített kvantum állapota ezeknek a protonoknak a következ®képpen is kinézhet:

|+i7 |+i6 |−i5 |−i4 |+i3 |+i2 |−i1 |−i0 , ahol a 0-tól 7-ig tartó indexek azt mutatják meg, hogy melyik protonhoz tartozik a jelzett állapot. Tartsuk magunkat ahhoz, hogy a 0. proton mindig a legjobboldalibb helyen áll a 7. pedig a legbaloldalibb (vagyis az els®) helyen. Így elhagyhatjuk az indexeket, és ugyanazon állapotra írhatjuk a következ®t:

|+i|+i|−i|−i|+i|+i|−i|−i. Továbbá elhagyhatjuk a i| jeleket a vektorok közül, miáltal az állapotot a következ®képpen írhatjuk újra: | + + − − + + − −i. Végezetül átválthatunk az energia szint jelölésr®l (|±i) számítási bázis jelölésre ahol |−i ≡ |0i és |+i ≡ |1i, ami a következ®t eredményezi |11001100i. Ez nem más, mint a 204 bináris reprezentációja mivel épp most implementáltunk egy 8-kubites regisztert ami 0-tól 255-ig képes számokat tárolni. De ez a kvantum regiszter sokkal többre képes. A Hadamard transzformációt láttuk egy kubitra. Nézzük hogyan megy egy kvantum regiszterre. Tegyük fel, hogy az összes kubit a B-re nézve a |0i állapotba volt el®készítve. A mágneses teret elforgatjuk 90kal. Mi lesz ekkor a rendszer B'-höz igazított állapota ebben az új bázisban? A kérdés megválaszolásához a következ® szorzást kell elvégeznünk: √1 (|00 i7 + |10 i7 ) √1 (|00 i6 + |10 i6 ) √1 (|00 i5 + |10 i5 ) √1 (|00 i4 + |10 i4 ) · 2 2 2 2 · √12 (|00 i3 + |10 i3 ) √12 (|00 i2 + |10 i2 ) √12 (|00 i1 + |10 i1 ) √12 (|00 i0 + |10 i0 ) . Ez egyenl® lesz: √1 (|07 06 05 04 03 02 01 00 i + |07 06 05 04 03 02 01 10 i + |07 06 05 04 03 02 11 00 i+ 27 +|07 06 05 04 03 02 11 10 i + |07 06 05 04 03 12 01 00 i + ...+ +|17 16 15 14 13 12 11 00 i + |17 16 15 14 13 12 11 10 i) .

V.

KUBIT DINAMIKA: EGYSZER KUBIT KAPUK

93

Az alsó indexek elhagyása és a decimális jelölésre való áttérés után a következ®t kapjuk: 1 √ (|0i + |1i + |2i + |3i + |4i + ... + |254i + |255i) . 27 A fenti jelölésben pl. a |4i nem jelent mást mint |07 06 05 04 03 12 01 00 i, azaz ez a zikai reprezentációja ennek a számnak, ami bináris és ebben az esetben 8 kubiten van kódolva. A Hadamard transzformáció általános végrehajtása egy n kubites rendszeren, ahol a kubitek a |0i kezd®állapotba vannak el®készítve: n −1 n 2P N |xi (5.4) H |0i|0i...|0i = √12n | {z } x=0 k=1 n ami a szuperpozíciója az összes egész számnak 0-tól 2n − 1-ig. Ez az összes szám egy id®ben helyezkedik el egy kvantum regiszteren belül. Bármely m¶velet amit regiszteren hajtunk végre, végrehajtódik az összes számon egy id®ben, párhuzamosan. Ez a kvantum párhuzamosság m¶ködés közben. Szükségtelen elmondani, hogy minden ismert kvantum algoritmus alkalmazza ezt a Hadamard transzformációs trükköt a számítások elején. Tekintsünk egy csekély 64 kubit méret¶ regisztert. Ez a regiszter 18 446 744 073 709 551 616 számot képes tárolni. A regiszteren elvégzett m¶velet egyszerre hajtódik végre az összes 18.5 kvintillió számon. Sajnos ez jóval több, mint amit a jelenlegi technológia képes el®állítani. De a verseny folytatódik tovább az skálázható kvantum számítógép irányába melynek regisztere több ezer, vagy akár több tízezer kubitet tartalmaz majd.

6.

Kubit dinamika: egyszer¶ kubit kapuk

Általánosan a dipólus állapotát leírhatjuk a bázis állapotok szuperpozíciójaként:

|Ψi = |−ih−|Ψi + |+ih+|Ψi ahol h−|Ψi és h+|Ψi két valószín¶ségi amplitúdó, vagy skaláris szorzat (ez kett® ugyanaz a kvantummechanikában), és mind a kett® komplex szám. A jelölések egyszer¶sítése után kapjuk a |Ψi = C− |−i + C+ |+i képletet ahol C− és C+ a megfelel® valószín¶ségi amplitúdók. A Hilbert térben speciális bázis választással a |Ψi-nek megfeleltethetjük C− és C+ oszlopvektorát: ¶ µ C− . |Ψi ≡ C+ A C− és C+ együtthatók a t id® komplex érték¶ függvényei. A Schödinger-Pauli egyenlet írja le ezt a dinamikát. A következ®képpen néz ki: µ ¶ µ ¶µ ¶ d C− (t) Bz (t) Bx (t) − iBy (t) C− (t) i~ = −µ . (6.5) Bx (t) + iBy (t) −Bz (t) C+ (t) dt C+ (t)

94


Az irodalomban a következ® rövidítéseket és szaknyelvet használják. A jobboldali ˆ -val jelö−µ-vel megszorzott mátrixot Hamiltonfüggvény nek nevezik, és H -val néha H lik. Ezt a jelölést használva az egyenletünk a következ® alakra hozható:

d |Ψ(t)i = H(t)|Ψ(t)i, dt ami lehet hogy elegánsabb, de kevésbé informatív. A mágneses dipólus momentum Hamiltonfüggvényét gyakran írják a következ® alakban: µµ ¶ µ ¶ µ ¶ ¶ 0 1 0 −i 1 0 H = −µ Bx + By + Bz . 1 0 i 0 0 −1 Azokat az egyszer¶ mátrixokat, amikkel a Bx -et, a By -t és Bz -t szorozzuk Pauli mátrixoknak nevezik, és általában σ x , σ y és σ z -vel jelölik, de szokták még használni az X, Y, Z jelölést is. Pauli mátrixokat használva az alábbi alakra hozhatjuk a SchrödingerPauli egyenletet: d i~ |Ψ(t)i = −µ(σx Bx (t) + σy By (t) + σz Bz (t))|Ψ(t)i, dt ami szépen néz ki, és valamivel kifejez®bb. Találkozhatunk még a következ® rövidítésekkel is:   σx −  σy  ≡ → σ, σz   Bx −  By  ≡ → B, Bz és − → − σx Bx + σy By + σz Bz ≡ → σ ·B amivel a Schrödinger-Pauli egyenlet leírása: i~

− → d − |Ψ(t)i = −µ→ σ B (t)|Ψ(t)i. dt A klasszikus zikában ismert az E = −µB összefüggés. A Hamiltonfüggvényt ehhez nagyon hasonló alakba írhatjuk, ha bevezetjük az alábbi jelölést: i~

→ µ ≡ µ− σ. A Pauli mátrixok speciális értékei miatt ezt tekinthetjük a proton dipólusmomentum újradeniálásának. A formulák ezen felírási módja ismer®s a zikában járatosak számára. De van még egy hasznos mellékhatása is ezeknek az alakoknak: felvet®dik az hogy a kvantummechanikában a Hamiltonfüggvénynek köze van az energiához. A proton alapú kubiteket különböz® irányú és er®sség¶ mágneses mez®kkel tudjuk manipulálni, mivel ezek az egyetlen változó mennyiségek, amik a Schrödinger-Pauli egyenletben megjelennek. Ez igaz majdnem minden más kvantum rendszerre is.

V.


95

Ahhoz, hogy jobban megértsük a mágneses dipólus momentum dinamikáját, oldjuk meg a Schrödinger-Pauli egyenletet néhány egyszer¶ esetre. El®ször tegyük fel, hogy B = Bz ez ahol ez egy z irányba mutató egységvektor, Bz pedig egy konstans. Az egyenlet a következ® alakra egyszer¶södik:

d i~ dt

µ

C− (t) C+ (t)

¶

µ = −µ

0 Bz (t) 0 −Bz (t)

¶µ

C− (t) C+ (t)

¶

µ =

−µBz C− (t) µBz C+ (t)

¶ .

Mint látjuk az egyenlet szétválik, és a megoldás:

C− (t) = C− (0)eiµBz t/~ , C+ (t) = C+ (0)e−iµBz t/~ . Vegyük észre, hogy |C− (t)|2 = |C− (0)|2 és |C+ (t)|2 = |C+ (0)|2 , melyek annak a valószín¶ségét jelölik, hogy a protont a |−i vagy a |+i bázisállapotban találjuk nem változik az id®vel. A kifejezés a következ®képpen írható át: C− (t) = C− (0)e−iE− t/~ , C+ (t) = C+ (0)e−iE+ t/~ , ahol E− = −µBz és E+ = µBz , az állapotokhoz rendelt energiák, vagy: C− (t) = C− (0)e−iω− t , C+ (t) = C+ (0)e−iω+ t . ahol ~ω− = E− , és ~ω+ = E+ a Planck formula kifejezései ami összeköti a frekvenciát és az energiát. Ha a protont a |+i állapotba készítettük el®, és a proton visszatér az alapállapotába (ezt a folyamatot nem írja le a Schödinger-Pauli egyenl®ség), akkor egy ω = (E+ − E− )/~ = 2µBz /~ frekvenciájú foton kibocsátódik. Ez a dipólus rezonancia frekvenciája. Tegyük fel, hogy a z irányba mutató statikus mágneses mez®höz hozzáadunk egy y irányba mutató ingadozó komponenst: B = Bz ez + By cos ωtey ahol Bz , By és ω konstansok. A Schrödinger-Pauli egyenlet a mozgásra: d i~ C− = −µBz C− + iµBy C+ cos ωt = E− C− + iµBy C+ cos ωt dt d i~ C+ = −iµBy C− cos ωt + µBz C+ = E+ C+ − iµBy C− cos ωt. dt Ezeket az egyenleteket nem könny¶ megoldani, de a rezonancia közelében azaz ω = (E+ − E− )/~ = 2µBz /~ egy harmonikus oszcillátorrá egyszer¶södnek, így a megoldás: C− (t) = γ− (t)e−iE− t/~ , C+ (t) = γ+ (t)e−iE+ t/~ , ahol

γ− (t) = a cos

µBy µBy t + b sin t 2~ 2~

96


µBy µBy t − a sin t. 2~ 2~ Tegyük fel, hogy a protont a |−i állapotba készítettük el®. Ekkor a t = 0-ban C− = 1, C+ = 0, tehát a = 1, b = 0 és az állapot a következ®képpen alakul: µBy µBy t|−i − e−iE+ t/~ sin t|+i. |−i −→ e−iE− t/~ cos 2~ 2~ A megfelel® átmenet valószín¶ségek: µBy P|−i,|Ψi = cos2 t, 2~ µBy t. P|+i,|Ψi = sin2 2~ µB π~ Ez azt jelenti, hogy ha 2~y t = π2 vagy t = µB akkor biztos, hogy a protont a |+i y állapotban fogjuk találni. Ha kezdetben a proton a |+i állapotban volt, akkor a = 0 és b = 1 valamint γ+ (t) = b cos

|+i −→ e−iE− t/~ sin

µBy µBy t|−i + e−iE+ t/~ cos t|+i. 2~ 2~

A megfelel® átmenet valószín¶ségek:

µBy t, 2~ µBy P|+i,|Ψi = cos2 t. 2~ π~ , akkor a proton biztosan a |−i állapotban lesz. Tehát ha t = µB y Ez az eszköz tehát egy klasszikus NEM kapu. De még nem valódi kvantum-NEM kapu, hiszen ha jobban megnézzük az egyenleteket, akkor azokat átírhatjuk az alábbiakra: |−i −→ −e−iπBz /By |+i és |+i −→ eiπBz /By |−i. De ha a By -t úgy választjuk, hogy Bz /By egész, s®t, páros legyen, akkor a létrejöv® átmenet: |−i −→ −|+i és |+i −→ |−i. Ez még mindig nem egy tiszta kvantum-NEM kapu, de kétségtelenül egy szép kapu. Leírhatnánk ezt a kaput mint −iσy . Ha −iσy -t egy olyan operátornak vesszük, ami a dipólust 180 -kal elforgatja, akkor egy újabb 180-os forgatás nem vezet vissza a kiindulási állapotba. P|−i,|Ψi = sin2

|−i −→ −|+i −→ −|−i. De ha a forgatás 720 = 4 × 180, akkor visszakapjuk az eredeti állapotot:

|−i −→ −|+i −→ −|−i −→ |+i −→ |−i.

V.


97

Itt jelenik meg a mágneses dipólus spinjének az a tulajdonsága, hogy a spin állapot önmagába való visszaforgatásához 720-kal kell azt elforgatnunk. π~ Mi történik akkor, ha megállunk t = 2µB id®ben ahelyett, hogy megvárnánk a y π~ teljes µBy id®t? Ekkor a formulák a következ®ket adják:

¢ 1 ¡ |−i −→ √ eiπBz /(2By ) |−i − e−iπBz /(2By ) |+i 2 ¢ 1 ¡ iπBz /(2By ) |−i + e−iπBz /(2By ) |+i . |+i −→ √ e 2 Bz Válasszuk By -t úgy, hogy 2By páros egész legyen. Ekkor 1 |−i −→ √ (|−i − |+i) 2

és

1 |+i −→ √ (|−i + |+i) 2 ami tulajdonképpen a Hadamard transzformációval egyezik meg |+i ≡ |0i és |−i ≡ |1i megfeleltetés esetén (a megfeleltetés rajtunk múlik, a lényeg, hogy ha egyet kiválasztottunk, akkor egy számításon belül azt használjuk). Ugyanezt az érvelést megismételhetjük egy x irányú ingadozó mágneses mez®re. A Schrödinger-Pauli egyenlet ekkor: d C− = E− C− − µBx C+ cos ωt dt d i~ C+ = E+ C+ − µBx C− cos ωt dt és a megoldás a rezonancia környezetében: i~

C− (t) = γ− (t)e−iE− t/~ C+ (t) = γ+ (t)e−iE+ t/~ ahol

µBx µBx t + b sin t 2~ 2~ µBx µBx γ+ (t) = −ib cos t + ia sin t. 2~ 2~ A megfelel® átmenetek |−i-ra és |+i-ra a fenti megállapodás szerint: γ− (t) = a cos

µBx µBx |−i + e−iE+ t/~ sin |+i 2~ 2~ µBx µBx |+i −→ e−iE− t/~ sin |−i + e−iE+ t/~ cos |+i. 2~ 2~ π~ id® múlva. Itt is fellép a fáziseltolódás, ami: Nézzük a rendszert t = µB x |−i −→ e−iE− t/~ cos

|−i −→ ie−iπBz /Bx |+i,

98


|+i −→ ieiπBz /Bx |−i. Ha Bx -et most is úgy választjuk, hogy Bz /Bx páros legyen akkor:

|−i −→ i|+i |+i −→ i|−i. Ez már közelebb áll√a tiszta kvantum-NEM kapuhoz, ugyanis ez egy iNEM, vagy iσx , más jelöléssel egy NEM kapu. Ha azután, hogy Bx -et kikapcsoltuk várunk t = 3π~/(2µBz ) ideig, akkor ez az állapot a következ®vé alakul:

i|+i −→ −|+i i|−i −→ |−i. Ha nem csinálunk semmit csak várunk, akkor ez is egy kaput jelent, mivel a kvantum rendszerek sosem alszanak. Ebben az esetben a kapu:

µ

eiµBz t/~ 0 −iµBz t/~ 0 e

¶ .

Hogyan szabadulhatnánk meg i-t®l a σx el®tt, hogy egy tiszta kvantum-NEM kaput kapjunk? A megoldás egyszer¶. Emeljük meg az egész kísérleti berendezést ∆z -vel. Ez megnöveli az egész rendszer gravitációs energiáját, ami megjelenik mind a |−i és |+i álapotokban ugyanazzal az e−igmp ∆zt/~ szorzófaktorral. Ha gmp ∆zt/~ = π/2, vagyis várunk pontosan t = π~/(2gmp ∆z) id®t, akkor ez a faktor egyenl® lesz −i-vel, ami kiejti i-t a σx el®l. Ahelyett, hogy az egészet megemelnénk ∆z -vel, a következ® ötletet is használhatjuk: egyszer¶en vigyük lejjebb a vonatkoztatási pontunkat ugyanezzel a mennyiséggel (persze nem a már megkezd®dött számítás közben). Így generálhatjuk az e−igmp ∆zt/~ faktort mindenféle zikai beavatkozás nélkül. Ez arra utal, hogy a |−i és |+i el®tt megjelen® i valójában nem okoz gondot. Ez egy konstans fázis faktor, ami kiesik mikor a valószín¶ségeket számoljuk. Extra odagyeléssel, különösen mikor belekeverjük az interferenciát, élhetünk ezzel. A Pauli-mátrixok a rendszer generátorai, bármilyen egy kubiten elvégezhet® operátor leírható segítségükkel. Az egy kubites univerzális számítógép után nézzük, mi a helyzet a több kubites gépekkel.

7.

Egy NMR számítógép

A kvantumszámítógépek egy lehetséges megvalósítása az úgynevezett NMR számítógép (Nuclear Magnetic Resonance Quantum Computers). Ez az el®z®ekben ismertetett mágneses rezonancián, illetve azon a tényen alapul, hogy a rezonancia egy nagyon éles frekvenciaértéknél következik be (éles a rezonanciacsúcs).

V.

EGY NMR SZÁMíTÓGÉP

99

Itt fontos megjegyeznünk, hogy valójában egy molekula minden spinje párban áll minden másikkal egy dipol-dipol kölcsönhatással. Ezek a párok lehetségessé tesznek néhány nemtriviális kvantumszámítást. Lehet®ségünk van molekulákat tervezni és felépíteni általános számításhoz vagy adott algoritmushoz, felhasználva a gyógyszerkészítés és a kvantum kémia eszközeit. Használjunk NMR berendezést ahhoz, hogy kommunikálhassunk azonos molekulák egy halmazával egy folyékony közegen belül. Ez gyakorlatban is egyszer¶, másrészt ett®l a számítás is stabilabb lesz. A kvantum rendszerek közismerten instabilak, és hajlamosak a hibára. Ha egymástól elkülönített azonos regiszterek nagy halmazával dolgozunk, és mindegyiken ugyanazt a m¶veletet hajtjuk végre, akkor sikerül létrehoznunk egy egyszer¶ hibajavítást, ami a teljes számítási folyamat sokszoros végrahjatásán alapul. Amikor az utolsó mérés is lezajlott, a hibák kiátlagolódnak a kimeneten, és az NMR csúcsaiban, ami továbbra is helyesen megadja a számítás eredményét. Persze, ha a számítás túl hosszú, akkor a hibák felhalmozódnak, és a csúcsok teljesen elmosódnak, tehát limitálni kell a kvantum m¶veletek számát. Egy NMR minta általában mágnesesen inaktív oldószerben mágnesesen aktív oldatot tartalmaz. Az oldat nagyon fontos, mivel megszünteti a molekulák közötti kölcsönhatásokat, amik befolyásolhatnák a számítást. Az 1 cm3 -re jutó molekulák száma 100 millió felett van. Ha ez alatt van, akkor a jel általában túl gyenge ahhoz, hogy észlelni tudjuk. Egy normál NMR mérésnél használt molekulának tartalmaznia kell számos protont melyek mindegyike mágnesesen aktív, és egy 12T (tesla) körüli mágneses mez®ben 500 MHz körüli NMR jelet produkál. Az NMR szíve egy szupervezet® mágnes ami homogén mágneses teret kelt a z irányba egy kb. 1cm3 -es régióban. A mintának be kell férnie ebbe a térbe, hogy a molekulák mindegyikére azonos irányú és erej¶ mez® hasson. Helmholtz tekercseket használhatunk kis, ingadozó mágneses tér keltésére x és y irányokban, ami a dipólust kapcsolgathatja a |−i és a |+i kvantumállapot között. Ezek a terek nagyon gyorsan tudnak pulzálni, de a homogenitásukat nagyon nehéz biztosítani, mivel sokkal kisebbek, mint a szupervezet® tekercsek, amik a háttér mez®t generálják. A számítás általában egy pár perces várakozással kezd®dnek, hogy az energia termikusan kiegyenlít®djön a molekulák közt. Ezután különböz® frekvenciájú rádióhullámokat alkalmazunk, melyek polarizáltságát, és hosszát hagyományos számítógép vezérli. Rögtön azután, hogy az impulzusok sorozatát alkalmaztuk, a nagy teljesítmény¶ impulzus er®sít®t kikapcsoljuk, egy nagyon érzékeny el®-er®sít®t pedig be, így a dipólusok végs® állapota mérhet®, értéke pedig:

V (t) = V0 tr

¡¡ (k) ¢ ¢ σx + σy(k) e−iHt/~ ρeiHt/~

ahol σx és σy a k -adik dipólushoz rendelt Pauli mátrixok, H az NMR Hamilton operátora, ami sokkal egyszer¶bb mint a részecskék nukleáris dipólusát leíró valódi Hamilton operátor, V0 egy konstans ami a tekercsek geometriai és elektromos tulajdonságaitól függ, ρ pedig a s¶r¶ség operátor ami a regiszterek együttesét írja le. Egy egyszer¶ kubit rendszer s¶r¶ségmátrixa ebben a környezetben a következ® alakú: (k)

(k)

100


µ

¶ (a0 − a)e−t/τ1 + a0 be−t/2τ2 ρ= b∗ e−t/2τ2 (a0 − a)e−t/τ1 + 1 − a0 ahol τ1 a longitudinális τ2 pedig a transzverzális relaxációs hányados. A s¶r¶ségmátrix id®függése egy egyszer¶ modellt ad a 'decohere' jelenségre, vagyis arra, hogy az egy ideig egymással párban álló értékek elvesztik ezt az összekötöttséget. Az NMR-ben tehát meggyelhet® a decohere jelenség. Ez általában az itt el®forduló spinek esetén pár percet is igénybe vesz, tehát ezek a molekulák jól felhasználhatóak kvantumregiszterként.

8.

A szabályozott NOT-kapu

Bármely n-kubites regiszteren végrehajtott m¶velet implementálható egy-kubites kapuk, és két kubites szabályozott NEM-kapuk kombinációjával. Ez könnyen bizonyítható, ha els®ként megnézzük, hogy a gyakran emlegetett Deustch kapu univerzális a kvantum m¶veletek végrehajtására. A Deutsch kapu hasonló a Toffoli kapuhoz, azzal a különbséggel, hogy most az alsó szál ⊕ operátora helyett a következ® van: R = −iei(θ/2)σx = −i(cos(θ/2) + iσx sin(θ/2)) ahol θ nem összemérhet® π -vel. A tény, hogy a Tooli-kapu univerzális a klasszikus számításokban, felhasználható a bitonyításban. Az 8.5. ábra megmutatja, hogyan lehet a Deutsch kaput létrehozni elemi kapuk, és szabályozott-NEM kapuk kombinációjával.

8.5. ábra. Deutsch kapu realizációja szabályozott-NEM kapukkal Minden elemi-kontrollált kapu létrehozható szabályozott-NEM kapuk és egyszer¶ kubit kapuk kombinációjával. Ilyen sémát mutat a 8.6. ábra, ahol megfelel®en választhatjuk az A,B és C -t.

V.

KVANTUM ALGORITMUSOK

101

8.6. ábra. NEM és kubit kapuk kombinációja Kvantum értelemben a szabályozott-NEM kapu reverzibilis kapu, és a következ®képp van deniálva:

⊕(|0ic |0it ) = |0ic |0it ⊕(|0ic |1it ) = |0ic |1it ⊕(|1ic |0it ) = |1ic |1it ⊕(|1ic |1it ) = |1ic |0it ahol ⊕ a kapu operátor, c index jelzi a a vezérl® kubitet és t indexeli a a cél kubitet. Egyszer¶en leírva, ha a vezérl® kubit |0ic , akkor a cél kubitet békén hagyjuk, ha pedig a vezérl® kubit |1ic , akkor a cél kubit az ellenkez®jére vált. Az áramköri kapcsolástól függ, hogy melyik kubit lesz a vezérl®. Tehát a szabályozott NOT kapu valamivel összetettebb, mint a Tooli kapu, de csak egy vezérl®szállal. A megvalósításban a pároknak, azok feloldásának és az újra párosításnak is van szerepe.

9.

Kvantum algoritmusok

Ebben a fejezetben a kvantum-algoritmusokról ejtünk néhány szót.

9.1. A Deutsch algoritmus Talán a legegyszer¶bb, és legrégebbi kvantum algoritmus ami ugyanakkor megmutatja a kvantum számítások erejét, az a Deutsch orákulum. Tulajdonképpen, mint látni fogjuk alapfeladatként azt szeretnénk megtudni, hogy két bit értéke megegyezik-e, vagy különböz®. A kvantum számítástechnikában szokásos módon egyetlen mérés eredményéb®l fogjuk megtudni az eredményt. Az ezt megvalósító áramkör 9.7. Ábrán látható. (Ábráinkon a szokásos balról jobbra történ® számítási folyamatot mutatjuk be. A kapukat négyzet alakú dobozok jelképezik.)

102


9.7. ábra. A Deutsch algoritmus Ebben H a Hadamard kapu, ami nem csinál mást, mint elforgatja a kubitet félig az IGAZ és HAMIS közé:

1 H|0i = √ (|0i + |1i), 2 1 H|1i = √ (|0i − |1i). 2 Uf egy f (x) által vezérelt kapu, aminek formális deníciója: Uf |xi|yi = |xi|yi +2 f (x)i. Az f függvény a {0, 1}-b®l képez a {0, 1}-be, és ez lehet konstans, vagy kiegyensúlyozott. (Egy {0, 1}-re képez® és diszkrét halmazon értelmezett függvényr®l akkor mondjuk, hogy kiegyensúlyozott, ha mind a 0, mind az 1 értéket ugyanannyiszor veszi fel. Ez a jelen esetben egyszer-egyszer, tahát a {0, 1} → {0, 1} függvények vagy konstansok vagy kiegyensúlyozottak.) Egy klasszikus számítógépen két mérés szükséges, hogy kitaláljuk, hogy melyik. Mivel a fels® szálon lév® Hadamard operátor a |0i -át a √1 (|0i + |1i) -be viszi át, ezért egyid®ben betölthetjük x-be a |0i-át és |1i-et. 2 Ha f (x) konstans:

(−1)f (0) − (−1)f (1) = 0 és a fels® szál állapota egyenl®: ¢¢ 1¡ ¡ |0i (−1)f (0) + (−1)f (1) = ±|0i 2

Ha f (x) kiegyensúlyozott:

(−1)f (0) + (−1)f (1) = 0

V.


103

ekkor a fels® szál állapota:

¢¢ 1¡ ¡ |0i (−1)f (0) + (−1)f (1) = ±|1i. 2 Ahhoz, hogy megtudjuk, hogy f (x) konstans, vagy kiegyensúlyozott, nem kell mást tennünk, mint megmérni a fels® szál állapotát. Ha ez |0i, akkor f (x) konstans, ha |1i, akkor kiegyensúlyozott. Az Uf összekapcsolja a két vonal kvantumállapotát egy páros-kvantumállapotba. Ezt a jelenséget, hogy az egy páros állapot tárolja az információt entanglement -nek hívjuk. Az információ nem egyes kubitekhez tartozik. Ha egy ilyen páros-kubit egyik tagján mérés vagy decohere jelenség következik be, akkor ennek állapota összeomlik, de információ más kubit-kapukba juthat a párja segítségével. Ez tulajdonképpen a bevezet®ben említett EPR jelenség, és annak kihasználása.

9.2. A Deutsch-Jozsa algoritmus A Deutsch-Jozsa algoritmus nagyon hasonlít az el®z®ekben tárgyalt Deutsch-féléhez, tulajdonképpen annak általánosítása több bitnyi információ együttes tartalmának mérésére. Az algoritmust megvalósító áramkört a 9.2. Ábrán mutatjuk be három fels® szállal (valójában n szálra is hasonlóan néz ki). A Hadamard kapuk ebben az áramkörben ugyanúgy m¶ködnek, mint eddig és az Uf kaput most nem egy, hanem n darab szál vezérli. Az f függvény {0, 1}n -b®l képez a {0, 1}-be, és akárcsak ezel®tt, feltételezzük, hogy az f vagy konstans lehet, vagy kiegyensúlyozott. (Itt jegyezzük meg, hogy ellenben a Deutsch algoritmusnál tárgyaltakkal, ezesetben kett®nél több bit együttese esetén természetesen nem csak konstans, illetve kiegyensúlyozott függvények értelmezhet®ek. A Deutsch-Jozsa algoritmusnál viszont feltétel, hogy az f függvény e két kategória egyikébe essen.) A feladatunk, hogy mindössze egyetlen méréssel megállapítsuk, hogy a kett® közül melyik. Klasszikus esetben ehhez 2n mérésre lenne szükség. Ha f (x) konstans, akkor a mért vezérl® szálak mindegyikének a kimenete |0i kell, hogy legyen. Minden más esetben f (x) kiegyensúlyozott lesz.

9.3. A Simon algoritmus Az ebben az alfejezetben tárgyalt algoritmus a kriptográa szempotjából is fontos szerepet játszik. A Simon algoritmus az f : {0, 1}n → {0, 1}n függvény periodikusságát vizsgálja. Az argumentumok és az értékek bináris vektorként vannak értelmezve, így lehet periodikusságukról szó. Mindazonáltal csak egy kis változtatás kell az algoritmusban, hogy tesztelje az f : {0, .., 2n − 1} → {0, .., 2n − 1} típusú függvényeket (ahol a bitsorozatok természetes számként vannak interpretálva) is. Az utóbbi egy nagyon fontos problémája a kriptográának. Röviden, ha polinomiális id®ben meg tudjuk találni az f függvény periódusát, akkor az RSA nyíltkulcsú titkosítási algoritmust is polinomiális

104


9.8. ábra. A Deutsch-Jozsa algoritmus kapcsolási rajza id®ben tudjuk feltörni. Ez az eredmény Shor nevéhez f¶z®dik, aki kicserélte a Hadamard sz¶r®t a Simon algoritmusban, Kvantum Fourier Transzformáció sz¶r®re, hogy megmutassa, hogyan is kell ezt csinálni. Egy példa látható a 9.3. Ábrán a Simon algoritmusra egy f : {0, 1}3 → {0, 1}3 alakú függvényre. Általánosan az algoritmus tartalmaz a tetején n szálat, amik ugyanazok, mint a Deutsch-Jozsa algoritmusban, illetve n szálat alul. Ezen n szálak mindegyike megfelel egy-egy fi : {0, 1}n → {0, 1} típusú függvénynek melyek együttesen alkotják az f függvényt. Az Ufk -val jelölt négyzetek szabályozott-NEM kapuk, ahol a vezérlésr®l fk (x) gondoskodik. Összefoglalva a Simon algoritmus az alábbi függvényt teszteli:

f : {0, 1}n → {0, 1}n ami n darab skalár érték¶ függvényre bomlik:

V.


105

9.9. ábra. A Simon algoritmus

fk : {0, 1}n → {0, 1}. A Simon algoritmus függvényének a következ® feltételeket kell kielégítenie: • f minden értékére igaz, hogy pontosan két különböz® vektor van (x1 és x2 ), hogy f (x1 ) = f (x2 ). • f periodikus, azaz létezik olyan a vektor, hogy f (x +2 a) = f (x). Megmérve a fels® n szálat egy y vektort kapunk, ami mer®leges a-ra. De ez lehet bármelyik vektor az alsó n szálon a megfelel® mérés által generált szuperpozícióból. Ha a elég sok mérést elvégezzük, hogy kapjunk n különböz® yk vektort, akkor n független egyenletet kapunk:

106


y1 · a = 0 y2 · a = 0 ... yn · a = 0 és ezek klasszikusan megoldhatók a-ra. Nézzük mit®l olyan hatékony ez az algoritmus. A Hadamard transzformáció alkalmazása a |0i inputokra a fels® n szálon, létrehozza az összes lehetséges 0-tól 2n − 1-ig el®forduló egészszám egy szuperpozícióját egyetlen regiszterben. Egy másik regiszternek átadódik ez az érték párt létrehozva, így kiértékel®dik az f függvény. Az f az összes lehetséges argumentumértékre egy id®ben értékel®dik ki. Hagyományos esetben 2n − 1 kiértékelésre lenne szükségünk, hogy helyettesítsük ezt az egyetlen kvantum lépést. Az Uf kapuk szolgálnak az entanglement létrehozására. Végül az EPR jelenséget és a szuperpozíciót kihasználva, az a-t kapjuk a fels® n kubites regiszterben, az egyes kubitek elforgatása után pedig megkapjuk a-ra mer®leges vektorok egy szuperpozícióját. A következ®kben egyéb kvantumalgoritmusokkal fogunk megismerkedni.

9.4. Kvantum keres® algoritmusok Egy másik kategóriája az algoritmusoknak a kvantum keres® algoritmusok, amelyek közül a legismertebbek a Grover algoritmusok. A Grover algoritmus is arra támaszkodik, hogy az összes szám szuperpozícióját bekódoljuk a probléma karakterisztikus függvényébe, majd speciális módon megsz¶rve a regisztert megkapja a választ a problémára.√ Itt a fejl®dés nem exponenciális, hanem gyökös (a klasszikus n kiértékelés helyett n kvantum kiértékelés szükséges). Például, ha van egy adatbázisunk 250 000 000 (250 millió, vagyis negyed milliárd) adattal ez a szám nagyjából megegyezik az USA lakosságával , akkor a Grover algoritmussal a teljes adatbázisban, bármely lekérdezésre nem több, mint 16 000 kereséssel kapunk választ. Érdekes kérdés, hogy mennyire is kvantum ez az algoritmus, és vajon lehetne-e implementálni hatékonyan egy (klasszikus) optikai számítógépen, ahol szuperpozíciót és interferenciát használhatunk, de entanglement-et nem.

9.5. Kvantum hiba ellen®rzés Van az algoritmusoknak egy osztálya, melyeket arra használunk, hogy a kvantum számítások alatt fellép® hibákat kezelje. Ezeknek egy része klasszikus kódokból származik. Például a gyakran emlegetett Calderbank-Shor-Steane kódok klasszikus lineáris kódokon alapulnak. De klasszikus megfelel®ikkel ellentétben a kvantum-hibajavító algoritmusok rendkívül kubit igényesek. Például a legrövidebb kód ami szükséges egyetlen kubiten fellép® hiba kijavítására, 5 kubitet igényel. Ha szeretnénk implementálni egy 7-kubites Shor számítást, akkor 35 zikai kubitet kell használnunk.

V.

KVANTUMSZÁMÍTÓGÉPEK A GYAKORLATBAN, ÖSSZEFOGLALÁS

9.6.

107

Kvantum-kriptográa

Néhány szót szólnunk kell a kvantum-informatikának a kriptográához való viszonyáról is. Tulajdonképpen két fontos dolgot említünk meg. Az els® a kvantum-mechanika EPR jelenségének a lehetséges kihasználása üzenettovábbítás biztonságosságának ellen®rzésére. Alice elküldi Bobnak egy páros kubit egyik példányát aminek értéke √12 |00i+ √12 |11i (a Hadamard operátorral könnyen el®állítható ilyen). Bármelyikük is méri meg el®bb a nála lev® kubitet 1/2 valószín¶séggel fog 0-t, illetve 1-et mérni. Tegyük fel, hogy Alice megméri a sajátját, és 0-t mér. Ezzel az állapot összeomlik, a Bobnál lev® példány állapota is módosul, értéke csak 0 lehet. Hasonlóan alakul a jelenség, ha Alice kubitje 1-et ad a mérésre. Így a párok segítségével kommunikálhatnak. A következ®kben azt írjuk le, miért lehet teljesen biztonságos kommunikáció Alice és Bob között. Az elküldött kubit (mérés nélkül) nem másolható, így egy harmadik személy nem szerezheti meg az információt a nélkül, hogy Alice és Bob tudomást ne szerezzen err®l. A mérés beavatkozás: az állapot összeomlik. Például egy jó módszer, ha Bob Alicenak elküldi a kubitpár egyik tagját, Alice transzformálja azt kvantumkapuval a megfelel® küldend® információt belekódolva és így küldi vissza Bobnak, aki rendelkezik ezután a pár mindkét tagjával, és mérést tesz, hogy az információhoz jusson. (Természetesen több információhoz több ilyen párra van szükség.) A másik fontos említésre méltó dolog az, hogy a kriptográában napjainkban használt algoritmusok nagyrésze számelméleti sejtéseken alapul. Ilyenek az ún. egyirányú függvények, ahol az egyik irány gyorsan kiszámítható, a másik irány viszont sokkal bonyolultabb. Ilyen például a prímfaktorizáció. Prímszámok összeszorzása egyszer¶, de az eredményt prímtényez®kre bontani már nagy számoknál nem mindig. A kventumjelenségeket kihasználva van olyan kvantumalgoritmus ami hatékonyan határozza meg számok prímtényez®it. Már korábban is említettük a Shor nevét, aki ezt az algoritmust kidolgozta [49]. Az algoritmus elméleti szempontból teljesen jó, viszont mint a következ® fejezetben írjuk a gyakorlat még le van maradva.

10.

Kvantumszámítógépek a gyakorlatban, összefoglalás

A kvantummechanikának azt a jelenségét, hogy egy foton véletlenszer¶en halad át vagy ver®dik vissza egy féligátereszt® tükrön, a folyamat el®re elvileg sem kiszámítató módon megy végbe, a gyakorlatban is használják valódi véletlenszámok generálására. A 10.10. ábrán látható eszközt (a Quantis-t) megvéve és a számítógéphez kapcsolva a felhasználó valódi véletlengenerátort használhat. (Itt jegyzend® meg, hogy (determinisztikus) számítógéppel elvileg lehetetlen valódi véletlenszámokat generálni, bár

108


10.10. ábra. Igazi véletlenszám-generátor, aminek m¶ködése kvantumzikai (optikai) jelenségen alapul rengeteg kutatás folyt és folyik az irányba, hogy a generált számsorozat minél közelebb álljon egy valódi véletlen számsorozathoz. A következ®kben arra mutatunk néhány példát, hogy az elméletben igen ígéretes kvantum-számítástechnika, illetve a kvantumalgoritmusok a megvalósítás oldalán még eléggé gyerekcip®ben járnak. Tehát: Hol is tart a kvantum-számítástechnika a gyakorlatban? A kvantum prímfaktorizáló algoritmus a gyakorlatban a 15-r®l már nagy valószín¶séggel mondja, hogy 5-ször 3, nagyobb számokra egyel®re még nem m¶ködik (nem készült el a kísérleti berendezés). Mint láthattuk, tehát valójában csak olyan kismértet¶ inputra vannak gyakorlati megvalósítások, amik megoldása valójában akár bármilyen számítógép használata nélkül is egyszer¶. Az, hogy a gyakorlatban is hatékonyan sikerül felhasználni a kvantum-számításokat még a jöv® feladata. (Bár, nem biztos, hogy azonnal tudomást szerzünk arról, ha kísérleti áttörés történik, mivel a kutatások igen jelent®s része a hadügy által támogatott; ennek megfelel®en az eredmények nem publikusak.) Itt említjük meg, hogy Penrose szerint ([43]) az emberi agy m¶ködésének hatékonysága is a kvantumzikán alapul.

VI. fejezet

Intervallum-számítógép Ebben a részben megismerkedünk egy olyan számításokat végz® rendszerrel, amely a [0, 1] feletti intervallum-értékeket használja. El®ször néhány egyszer¶ érvet mutatunk arra, hogy miért lehet természetes, érdekes és hasznos az intervallumok használata. A matematikai modellben az intervallum-értékeket pontokból és atomi intervallumokból építjük föl. A logikai operátorokat természetes módon terjesztjük ki az intervallum-értékekre. A hagyományos számítógép bájtjait intervallum-értékekre cserélve kapjuk meg az intervalum-számítógépet. A számítási teljességhez még néhány operátort bevezetünk a már említett Boole-operátorokon kívül, pl. az eltolás és a szorzás operátorokat. Ezekkel az operátorokkal az intervallum számítógép már tudja szimulálni a hagyományos számításokat. Megmutatjuk, hogy elméleti értelemben az Intervallum-számítógép sokkal hatékonyabb, mint a klasszikus modell, az intervallum-értékek által megengedett kontinuum parallelizmusnak köszönhet®en. Megmutatjuk, hogy hogyan lehet a SAT problémát lineáris id®ben megoldani az Intervallum-számítógép segítségével. A listareprezentáció segítségével hagyományos számítógépeken szimulálhatjuk az Intervallumszámítógépet mind matematikai, mind hagyományos számítási értelemben. Természetesen ezzel a szimulációval elveszítjük a párhuzamosság okozta hatékonyságot.

1.

Természetes motivációk

Amikor egy gyerek (vagy feln®tt) rajzol akkor tulajdonképpen pontokat, illetve szakaszokat vet a kétdimenziós papírra. Ha egy dimenzióra szorítkozunk, akkor pontokról és intervallumokról beszélhetünk. Így azt mondhatjuk az intervallum fogalma nagyon is kézenfekv® a mindennapi életben is. Mint láttuk pl. a DNS-számítások elméletében (III. Fejezet), vagy a membránrendszereknél (IV. Fejezet) el®fordul hogy a természetben talált eszközök alapján készítünk matematikailag absztrakt számítási modelleket. Vegyünk most is a 'természetb®l' példát: a hagyományos fényképezés képfelbontása ismerten nagyon magas. A használt ezüst-oxid oldatok és vegyületek lehet®vé teszik, hogy a fényképez®gép lmjén szinte atomonként változhasson az eredményezett kép. Egy atom mérete, vagyis átmér®je kb. 1å (egy Ångstromnyi), ami 10−10 métert jelent, ez azt jelenti, hogy egy 1 méter hosszú rúdon kb. 1010 atom helyezkedik el egymás mellett. Ha valamilyen zikai mennyiséget atomonként tudunk változtatni és mérni, akkor ez egy olyan intervallumnak felel meg, ami 1010 pontból áll. 109

110

VI. INTERVALLUM-SZÁMÍTÓGÉP

Most is elrugaszkodunk kicsit a valóságtól és feltesszük, hogy végtelen (s®t kontinuum) sok pontból áll matematikai értelemben az intervallumunk. (Ahogy egy ceruzavonást is általában végtelen sok pontból állónak szoktunk feltételezni.)

2.

Matematikai leírás

A modell pontos megadásához megadjuk az Intervallum-értékek és az azokon értelmezett m¶veletek pontos denícióját.

2.1. Intervallum-értékek Az Intervallum-értékeket egy induktív denícióval adjuk meg. A [0, 1] zárt intervallum lesz tulajdonképpen az Univerzumunk, ennek részhalmazait fogjuk használni. Tehát a deníció: Atomi intervallumnak hívunk minden [a, b] alakú intervallumot, ahol 0 ≤ a ≤ b ≤ 1. Speciálisan a = b választással azt mondhatjuk, hogy a [0, 1] pontjai is atomi intervallumok. Az atomi intervallumok Intervallum-értékek. Iterációs lépés: Intervallum-értékek uniója és (halmazelméleti) különbsége is Intervallum-érték. Minden Intervallum-értékre igaz, hogy az vagy atomi intervallum, vagy el®áll azokból az iterációs lépés véges sokszori alkalmazásával. Van két speciális Intervallum-értékünk: az üres (a ⊥ jellel fogjuk jelölni) és a teljes intervallum (>). A 2.1. ábrán látható a grakus reprezentációjuk.

2.1. ábra. A ⊥ és > Intervallum-értékek grakus ábrázolása

A > egy atomi intervallum, míg a ⊥ bármely atomi intervallum és > vagy bármely atomi intervallum és önmaga különbége. Egy intervallum karakterisztikus függvénye minden 0 ≤ x ≤ 1 pontról megmondja, hogy része-e a pont az adott intervallumnak. Mivel, a jelölésrendszer nem lesz zavaró, egyszer¶en az Intervallum-érték nevével fogunk a karakterisztikus függvényére is hivatkozni, zárójelben megadva utána a paraméterként vizsgálandó pontot. Tehát

VI.

MATEMATIKAI LEÍRÁS

111

ezen függvények értelmezései tartománya a [0, 1], míg értékkészélete a {0, 1} nemüres részhalmaza. (Ha az A Intervallum-érték különbözik a ⊥ és > Intervallum-értékekt®l, akkor A(x) felveszi mind a 0, mind az 1 értéket.) Formálisan: ½ 1, ha x ∈ A A(x) = 0 egyébként. Most nézzük, hogy milyen m¶veleteket lehet az Intervallum-értékekkel végezni. Kezdjük a logikai operátorokal.

2.2. Logikai operátorok A klasszikus logika operátorai (lásd 3.1. alfejezet) természetes módon kiterjeszthet®ek Intervallum-értékekre, hiszen az Intervallum-értékek karakterisztikus függvényei 0, és 1 érték¶ek. Tehát, legyenek a logikai operátorok a következ® módon értelmezve: Az eredmény Intervallum-érték karakterisztikus függvénye legyen az, amely a [0, 1] intervallum minden pontjára pontonként megegyezik az arguemtum(ok) abban a pontban lev® karakterisztikus függvényére ható megfelel® klasszikus logikai operátor értékével. A 1 táblázat mutatja az eredményt a logikai alapm¶veletekre. 1. táblázat. Az alapvet® logikai operátorok Intervallum-értékeken Név Jel Érték Halmazelméletileg:

negáció ¬A >\A komplementer

konjunkció A∧B A∩B metszet

diszjunkció implikáció A∨B A→B A∪B ¬(A\B) = ¬A ∪ B unió

Világos, hogy a negáció eredménye is Intervallum-érték lesz, hiszen ez a > és az adott Intervallum-érték különbsége. A 1. táblázat alsó sora alapján könnyen belátható, hogy a diszjunkció operátora sem vezet ki az Intervallum-értékek halmazából. A konjunkcióra az állítás a halmazelméleti De-Morgan azonosság (A∩B azonos a ¬(¬A∪¬B ) értékkel) segítségével látható be. Nézzünk néhány példát grakusan is.

Az 2.2. ábra negációra mutat példát, míg a 2.3. ábrán az Intervallum-értékek konjunkciójára és diszjunkciójára láthatunk példát. Hasonlóan felírható és ábrázolható az implikáció, a kizáró vagy ('xor'), a 'nand' stb. m¶velet is az Intervallum-értékekkel, ezt most itt nem részletezzük.

2.3. Nem-logikai operátorok Ahhoz, hogy számítási szempontból univerzális legyen a rendszer be kell vezetnünk olyan operátor(oka)t, amelyek segítségével az információt az intervallum-bájt egyik

112


2.2. ábra. Példa negációra Intervallum-értékekkel

2.3. ábra. Példa konjunkcióra és diszjunkcióra Intervallum-értékekkel

VI.


113

részér®l a másikra tudjuk mozgatni. (Mint láttuk a logikai operátorok nem ilyenek, ott nagyfokú párhuzamosság van, de az információ nem tud elmozdulni az intervallumérték adott helyér®l.) A hagyományos számítógépeken meglev® eltolás (shift) mintájára itt is bevezetünk eltolási operátorokat, de a helyzet kicsit bonyolultabb. A klasszikus shift operátorok egy bittel (a legkisebb egységgel) tolták el az értékeket, viszont az Intervallum-értékek esetén nincs ilyen legkisebb eltolás, az intervallumban folytonosan lehetnek a 0 és 1 értékek. Ezért, itt szükség lesz az eltoláshoz egy második operandusra is, amely megszabja, hogy mennyivel történjen az eltolás. Ehhez el®bb bevezetünk egy függvényt, amely minden Intervallum-értékhez egy 0 és 1 közé es® (valós) számot fog rendelni, méghozzá az els® nemnulla hosszúságú komponensének hosszát (ha van ilyen). Formálisan:

BalHossz(A) = b − a, ha az (a, b) nyílt intervallum része A-nak, és nincs olyan (a0 , b0 ) ⊂ A, hogy a0 < a és/vagy b < b0 . Ha nincs ilyen a és b, vagyis az A csak véges sok pont uniója, akor BalHossz(A) = 0. Az el®z® függvényt felhasználva vezzesünk most be két eltolás operátort, mindkett®t két Intervallum-érték¶ argumentummal. (Azért, hogy a rendszerünk hatékonyabb legyen nem teljesen szimmetrikus lesz a két m¶velet viszonya.) Tehát legyenek Lshif t(A, B) és Rshif t(A, B) az Intervallum-értékek miután az A Intervallum-értéket balra, illetve jobbra toltuk BalHossz(B)-nek megfelel® mértékben. A matematikai leírásban a karakterisztikus függvényeket fogjuk használni:

Lshif t(A, B)(x) = A(x + BalHossz(B)) ha 0 ≤ x + BalHossz(B) ≤ 1, és Lshif t(A, B)(x) = 0 egyébként. Rshif t(A, B)(x) = A(frac(x − BalHossz(B))), ahol x < 1. A frac függvény a törtrészét adja meg az argumentumként megadott valós számnak, vagyis frac(x) = x − int(x), ahol int(x) pedig az egészrészfüggvény, vagyis azt a legnagyobb egészet jelenti, amely még nem nagyobb a megadott x valós értéknél. Végül, hogy teljes legyen a leírás legyen Rshif t(A, B)(1) = Rshif t(A, B)(0). A 2.4. ábrán mutatunk néhány eltolást. Látható az Rshif t és az Lshif t operátor hatása is. A második (segéd-) operandust, vagyis tulajdonképpen az eltolás mértékének megfelel® intervallumhosszt szürkével tüntettük fel a jobb érthet®ség kedvéért. Amint láthatjuk az Lshif t operátor alkalmazásakor az Intervallum-értéknek az a része, amit kitolunk a [0, 1]-b®l elt¶nik. Ezzel szemben az Rshif t operátor alkalmazásakor az eltolt Intervallum-értéknek az a része ami az 1 érték felé csúszik, nem t¶nik el, hanem megjelenik az Intervallum-érték elején (0-tól kezd®d®en). Így a két eltoló operátor kombinált alkalmazásával egy Intervallum-érték bármely részét ki tudjuk törölni. Egyes számítások meggyorsítására bevezetünk még egy operátort az intervallumértékeken, az intervallum-értékek szorzását. Ez a szorzás a következ®képpen deniálható:

114


2.4. ábra. Példák az Intervallum-értékek eltolásaira

Legyen A Intervallum-érték olyan, hogy k darab atomi intervallum komponenst tartalmaz amelyek végpontjai (határpontjai) ai,1 , ai,2 (1 ≤ i ≤ k). Hasonlóan, ha B l darab atomi intervallum komponensb®l áll, akkor legyenek ezek végpontjai a bi,1 , bi,2 (1 ≤ i ≤ l) pontokban. Ekkor a C = A*B Intervalum-érték legyen a következ®: C-nek legyen k · l atomi intervallum komponense. A C komponensekre dupla indexekkel fogunk hivatkozni. Legyen a kezd®, illetve a végpontja az ij -edik atomi intervallum komponensnek az ai1 + bj1 (ai2 − ai1 ) és az ai1 + bj2 (ai2 − ai1 ) pontok. Egy határpont pontosan akkor fog a C Intervallum-értékhez tartozni, ha az eredeti határpontok hozzátartoztak az A, illetve a B Intervallum-értékhez.

VI.


2.5. ábra. Példák két Intervallum-érték szorzataira

115

116


Az Intervallum-értékek szorzása a tulajdonságait tekintve, rokon a számok szorzásával, abban az értelemben, hogy az eredmény Intervallum-érték deníció szerint annyi intervallum-komponenst tartalmaz, mint az operandusok komponensszámának szorzata, illetve az eredmény intervallumainak összhossza meg fog egyezni a két operandus Intervallum-érték intervallum összhosszainak szorzatával. Másrészt, viszont a Descartes-féle szorzásra is hasonlít, ugyanis az eredmény Intervallum-érték részintervallumai éppen az operandusok egy-egy részintervallumának valamiféle kölcsönhatásából származnak. Nézzünk, most egy érdekességet, ha egy Intervallum-értéket szorzunk, £2 ¤ £ 1 ¤ önmagával akkor a hatványozást is értelmezhetjük. Kiindulva az A= 0, 3 ∪ 3 , 1 Intervallumértékb®l az A2 , A3 , A4 , A5 ... sorozat éppen a Cantor-halmaz (az egyik legegyszer¶bb és legismertebb fraktál) el®állítási folyamata. (Lásd az 2.6 ábrát is. Határértékben fogjuk megkapni a Cantor-halmazt, vagyis Ai , ha i → ∞ akkor éppen maga a Cantorhalmaz. Viszont maga a Cantor-halmaz nem lesz Intervallum-érték, hiszen végesen nem állítható el®.) Az Intervallum-értékek szorzását így Fraktáli-szorzásnak is nevezhetjük.

2.6. ábra. A Cantor-halmaz el®állítása az Intervallumok szorzásával Ahogy a 2.6 ábrán bemutatott példákon is látszik, a Fraktáli-szorzás nem szimmetrikus az argumentumait tekintve. Viszont a > mindkétoldali egységeleme az operátornak, míg a ⊥ bármivel szorozva ⊥-t eredményez.

3.

A hagyományos számítógép modellezése

Ebben a részben megmutatjuk, hogy az Intervallum-számítógéppel könnyen szimulálható a hagyományos számítógép Arimetikai-Logikai Egységének m¶ködése.

VI.

A HAGYOMÁNYOS SZÁMÍTÓGÉP MODELLEZÉSE

117

Tegyük fel, hogy a szimulálandó számítógép egy bájtja n bitet tartalmaz. Vegyük az [m/n, (m + 1)/n] (atomi) Intervallum-értékeket (0 ≤ m ≤ n − 1 értékekre), ezek mindegyike a megfelel® (m + 1)-edik bitet fogja jelenteni. Amikor a hagyományos számítógép ALU-ja valamilyen bájt(ok)on dolgozik, akkor most az Intervallum-értékekkel dolgozó eszköz az adott bájtoknak megfelel® Intervallum-értékekkel fog dolgozni. A logikai m¶veletek szimulálása triviális módon megy a megfelel® Intervallumértékeken m¶köd® operátorokkal. A hagyományos shift operátorokhoz szükség van a bit-hossznyi eltolást segít® P= [0, 1/n] atomi Intervallum-értékre. Így a Left-shift egyszer¶ módon szimulálható az Intervallum-értékek Lshif t operátorával. Lássuk a right-shift szimulációját (a megfelel® Intervallum-m¶velet nem töröl, hanem a 'kimen®' rész bejön a [0, 1] másik végén. Kis számítással megmutatható, hogy

Rshif t(Lshif t(Rshif t(A, P), P), P) éppen a kívánt eredményt fogja adni, vagyis olyan P argumentumú jobbra-tolást ahol elt¶nik a kitolt rész. Most bevezetünk egy rövidítést: Rshif t(A, 2B) jelentse azt, hogy kétszer alkalmaztuk a jobbra-tolást a B második operandussal egymás után: Rshif t(Rshif t(A,B), B). Ezt a rövidítést bármely pozitív egész esetére bevezethetjük (esetünkben a P-vel való eltolásnak maximum n-szer van értelme egymás után). Hasonlóan: Lshif t(A, k B) =def Lshif t(Lshif t(. . . (Lshif t(A,B), . . .), B), B) ahol k -szor alkalmaztuk az Lshif t operátort. Nézzük a legfontosabb aritmetikai operátor (az add) szimulációját. Legyen A és B két olyan Intervallum-érték, amelyek számértékeket fejeznek ki bitekre visszavezetve. Az eltolás operátorokat fogjuk felhasználni a következ®képpen: El®ször a túlcsordulásnak (a túlcsordulás biteknek) megfelel® C Intervallum-értéket konstruáljuk meg. A C utolsó bitje Cn = Rshif t(Lshif t(A ∧ B, ¬P), ¬P). Itt jegyezzük meg, hogy Lshif t(A ∧ B, ¬P) ugyanazt jelenti, mintha (n − 1)P lenne az eltolás operátor második paramétere. Hasonló állítás teljesül a Rshif t m¶veletre is. A következ® iterációs módszerben, amiben összegy¶jtjük a C bitjeit, az i változó értéke n − 1-t®l 2-ig csökken lépésenként eggyel Ci = Ci+1 ∨ Lshif t(Rshif t(Rshif t(Lshif t(A ∧ B, (i − 1)P), (i − 1)P)∨

Rshif t(Lshif t(A ∧ Lshif t(Ci+1 , P), (i − 1)P), (i − 1)P)∨ Rshif t(Lshif t(B ∧ Lshif t(Ci−1 , P), (i − 1)P), (i − 1)P), (n − i)P), (n − i)P). (Az utolsó érték, C2 tartalmazza az összes átvitel (túlcsordulás) bitet, ami szükséges a számításhoz. A C túlcsordulás bájt els® bitje a valódi túlcsordulás bitet jelenti, ami az iteráció következ® lépésében állna el® a C1 értékkel. A hagyományos számítógépi értelemben vett összeg eredményének kiszámításához erre nincs szükség (ez a bit egy plusz információt tartalmaz, de nem az összeget tartalmazó bájtban van). Végül a kizáró vagy (`xor') operátort használva kapjuk meg az A és a B 'összegét': A + B = (A ⊕ B) ⊕ Lshif t(C2 , P).

118


Mint láttuk az Intervallum-számítógép képes a klasszikus számítógépet szimulálni, így minden azzal kiszámítható dolgot kiszámítani. A szimulációban véges sok bitnyi infromációt tároltunk egy Intervallum-értékben, maximum n atomi intervallum-értéket felhasználva. Csak olyan Intervallum-értékeket használtunk fel, ami a P= [0, 1/n] atomi Intervallum-értékb®l a logikai és az eltolás operátorok véges sokszori alkalmazásával el®áll. Mindezeket gyelembe véve azt mondhatjuk tehát, hogy az Intervallum-számítógép a klasszikus számítógép egy absztrakt általánosítása. Ezenfelül, logikai m¶veletek végrehajtásakor az Intervallum-számítógép úgy viselkedik, mintha végtelen (kontinuum) sok bit építene fel egy bájtot: a [0, 1] minden pontja megfelel egy-egy bitnek. Mivel egy processzor min®ségét szokták a bájtjainak bitszámában mérni, az Intervallum-érték¶ számítógép egy idealizált határesetet jelképez.

4.

A SAT probléma megoldása lineáris id®ben

Szokás a modellek 'erejét' azzal megmutatni, hogy bonyolult problémákra gyors választ/megoldást ígérnek. A már többször el®került SAT problémát tesszük megint vizsgálatunk tárgyává. Általában a formulákat normál formában szokták vizsgálni, de ezesetben ez nem követelmény, a formula bármilyen propozicionális logikai formula lehet. Legyen n a formulában el®forduló propozicionális bet¶k száma. Minden propozicionális változóhoz hozzárendelünk egy-egy Intervallum-értéket. Az i-edikhez az 2i−1 [−1 · j 2j + 1 ¶ Ai = , 2i−1 2i j=0 értéket. Ezeket a szorzás operátor felhasználásával elég gyorsan le tudjuk gyártani: Ai+1 = Ai ∗ [0, 0.5) ∨ ¬Ai ∗ [0, 0.5). Ezután egyszer¶en értékeljük ki az adott logikai formulát a megfelel® Ai Intervallumértékekkel. Amennyiben az eredmény a ⊥ Intervallum-érték lesz, akkor a formula kielégíthetetlen. Ellenkez® esetben pedig a formula kielégíthet®, s®t amennyiben az eredmény intervallum-komponenseinek összege 1, a formula logikai törvény (Boole tautológia). Megmutatjuk, hogy milyen értékeléssel lesz igaz egy kielégíthet® formula: vegyünk egy olyan x pontot, ahol az eredmény Intervallum-értékének karakterisztikus függvénye 1-et ad. (Ilyen érték biztos, hogy van, hiszen az eredmény különbzött a ⊥-tól. Nézzük meg, hogy ebben az x pontban milyen karakerisztikus függvényértékkel bírnak a propozicionális változók. Ha minden változóra fennáll, hogy az i-edik változó értéke éppen Ai (x), akkor a propzicionális formula értéke igaz lesz. A kiértékelés folyamatát mutatja az 4.7. ábra, amin a ¬((B ∧ C) → ¬(C ∨ (D → ¬B))) formulát vizsgáljuk. Az ábráról leolvasható, hogy a formula kielégíthet® (akkor igaz, ha B és C is igazak), de a formula nem Boole tautologia. Látható, hogy egy formula kielégíthet®ségének vizsgálatához nincs szükség több Intervallum-értékre, mint a formula hossza. Pontosabban mondva, a változók számának

VI.

A SAT PROBLÉMA MEGOLDÁSA LINEÁRIS IDBEN

119

4.7. ábra. A ¬((B ∧ C) → ¬(C ∨ (D → ¬B))) formula kielégíthet®ségének vizsgálata.

120


és a logikai összeköt®jeleknek az összege fels® korlátot ad a szükséges Intervallumértékek számára. Rövidzár kiértékelés nélkül az eredeti formula összes részformulájának Intervallum-értékét kell meghatároznunk. A logikai formulák kielégíthet®ségének vizsgálata az Intervallum-számítógéppel tulajdonképpen olyan, mintha a kiértékelésben párhuzamosan (lépésenként soronként) építenénk fel a formula igazságtábláját.

5.

Lista-reprezentáció

Ebben a részben az Intervallum-értékek lista-reprezentációját mutatjuk meg. Ezen reprezentáció segítségével a hagyományos számítógépeken is (egyszer¶en) szimulálhatjuk az Intervallum-számítógépet, sorosan végrehajtva az utasításait (ezzel elveszítve a beépített párhuzamosság okozta hatékonyságot). Számlistákkal fogjuk az Intervallum-értékeket reprezentálni. A lista elemei kétfélék lesznek, aláhúzott és aláhúzás nélküli számok. Az aláhúzott értékek azok a határpontokat fogják jelenteni, amelyek hozzátartoznak az Intervallum-értékhez (zárt az atomi intervallum), a nem aláhúzott értékek pedig a nyílt határpontokat fogják jelenteni. A listákat is induktívan vezetjük be:

• Els® lépésként, minden A= [a, b] atomi inervallumhoz az (a, b) listát rendeljük. • Az indukciót az Intervallum-értékekkel végezhet® operátorok alapján végezzük. Legyen az A lista-értéke (x1 , y1 , x2 , y2 , . . . , xn , yn ) (ahol ezek az értékek 0 és 1 közti (aláhúzott vagy aláhúzás nélküli) valós számok monoton nemcsökken® sorban) valamilyen n ∈ N-re. Ennek a jelentése a következ®: Ha egy x érték a lista olvasása közben páratlanadik helyre következne (páratlan pozicióban vagyunk, ha páratlan az ennél nem nagyobb értékek darabszáma a listában), vagyis van olyan i, hogy xi ≤ x ≤ yi , akkor x-nél az A karaterisztikus föggvénye 1-et ad (egyenl®ség esetén, csak ha aláhúzott értékr®l van szó). Lássuk el®bb a logikai operátorok hatását: • ¬A lista-reprezentációja: (0, x1 , y1 , x2 , y2 , . . . , xn , yn , 1). Tehát a 0 és az 1 értékek bejönnek a lista két végére aláhúzva, az összes addigi érték pedig köztük marad. Viszont minden addig aláhúzott érték nem lesz aláhúzva, és ami az A-ban nem volt aláhúzva, az a ¬A-ban alá lesz húzva (ezt a cserét jelzi a fölülhúzás jel a képletben). • Az A∨B Intervallum-értékének lista-reprezentációja a következ®: Párhuzamosan olvassuk az A és a B listáját monoton nemcsökken® sorrendben. Ha páratlan pozícióba kerülünk bármelyik listában, akkor ezt a pontot változtatás nélkül az A∨B listába másoljuk onnan ahol most beléptünk. Amikor olyan ponthoz érünk, hogy mind az A mind a B listában kikerülünk a páratlan pozícióból, akkor ezt a pontot is változtatás nélkül másoljuk. (Tartsuk magunkat ahhoz, a konvencióhoz, hogy belépési pontként az aláhúzott érték alacsonyabbnak számít, mint ugyanaz az érték aláhúzásmentesen; míg páratlan pozícióból történ® kilépéskor az aláhúzott érték számít magasabbnak.) • Az A∧B Intervallum-értékének lista-reprezentációja a következ®képpen áll el®: Párhuzamosan olvassuk az A és a B listáját monoton nemcsökken® sorrendben.

VI.

LISTA-REPREZENTÁCIÓ

121

Ha páratlan pozícióba kerülünk mindkett® listában, akkor ezt a pontot változtatás nélkül az A∧B listába másoljuk onnan ahol most beléptünk. Amikor olyan ponthoz érünk, hogy legalább az A és a B egyikének listájában kikerülünk a páratlan pozícióból, akkor ezt a pontot is változtatás nélkül másoljuk.

• •

• •

•

•

Szükség van a listában egy karbantartó lépésre is. Ha a lista két egymást követ® eleme megegyezik, akkor azokat kitörölhetjük a listából a következ® eseteket kivéve: mindkett® aláhúzott, és az els® el®fordulás páratlanadik helyen van a listában: xi = yi (ez egy atomi intervallumot jelez, ami egy pont) egyik érték sincs aláhúzva, és az els® párosadik helyen szerepel: yi = xi+1 . Most nézzük a speciális Intervallum-értékek lista-reprezentációját: A > és a ⊥ listaértékei: (0, 1) és az üres lista (). Végül a nem-logikai operátorok hatása a lista-reprezentációban: A BalHossz (A) = yi − xi , a legkisebb i indexre, melyre yi 6= xi , és 0 ha nincs ilyen index, így speciálisan az üres listára is. Lshif t(A,B) a következ® listával reprezentálható: (max(0, x1 − BalHossz(B)), max(0, y1 − BalHossz(B)), max(0, x2 − BalHossz(B)), max(0, y2 − BalHossz(B)), . . . , max(0, xn −BalHossz(B)), max(0, yn −BalHossz(B))) (eltávolítva a maximális páros számú 0-t a lista elejér®l). Rshif t(A,B) listareprezentációjának elemei: (x1 + BalHossz(B), y1 + BalHossz(B), x2 + BalHossz(B), y2 + BalHossz(B), . . . , xn + BalHossz(B), yn + BalHossz(B)), ahol minden 1-nél nagyobb érték helyett annak törtrésze használandó. Ezenkívül, ha valamely i-re xi + BalHossz(B) < 1 < yi + BalHossz(B), akkor listába fel kell vennünk a 0 és 1 értékeket is (mindkett®t aláhúzottan). Végül, hogy megkapjuk a listareprezentációt az elemeket monoton nemcsökken® sorrendbe kell rendeznünk. A fraktál-szorzás m¶veleténél, tulajdonképpen az operátor deníciójában szerepl® ij atomi Intervallum-érték határait kell felsorolni, ahogy a denícióban tettük.

Az Intervallum-értékeket reprezentáló listákra igaz az, hogy ugyanazt az elemet maximum kétszer tartalmazzák. A lista elemei tulajdonképpen azok a pontok, ahol az Intervallum-érték karakterisztikus függvénye változik.

Irodalomjegyzék [1] Adleman, Leonard H.: Molecular computation of solutions to combinatorial problems, Science 266 (1994) 1021-1024. [2] Ausiello, Giorgio: Algoritmusok és rekurzív függvények bonyolultságelmélete, M¶szaki Könyvkiadó, Budapest, 1984. [3] Bell, J.L. és Machover, M.: A course in mathematical logic, Elsevier Science, Amsterdam, New York, Oxford, North-Holland, 1977. [4] Buhrman, Harry: Quantum Computing, tutorial (3 lectures), CiE 2005: "Computability in Europe": New Computational Paradigms, Amsterdam, Hollandia [5] Calude, Cristian S.: Quantum Computing: From Classical to Unconventional, Complexity Roadmap, European Comission (IST-2001-32802). [6] Calude, Cristian S. és Boris Pavlov: Coins, quantum measurements, and Turing's barrier, Quantum Information Processing vol. 1, 1-2 (2002), 107-127. [7] Calude, Cristian S. és Gheorghe Paun: Computing with Cells and Atoms: An Introduction to Quantum, DNA and Membrane Computing, Taylor & Francis/Hemisphere, London, Bristol, PA, USA, 2001. [8] Calude, Cristian S.: Quantum Computing, a course for the Second International PhD School in Formal Languages and Applications, Tarragona, 2003. [9] Csaba György és Madarász Bálint: A sejt szerkezete, Medicina könyvkiadó, Budapest, 1981. [10] Csuhaj-Varjú Erzsébet: On Language-theoretic Aspects of Watson-Crick Complementarity: Models and Results. In: Proc. Theorietag 2000 mit Workshop New Computing Paradigms: Molecular Computing and Quantum Computing, szerk.: R. Freund, Technische Universität Wien, Viena, (2000), 11-33. [11] Dassow, Jürgen és Gheorghe Paun: Regulated rewriting in Formal Language Theory, Springer, Berlin, 1989. [12] Demetrovics János, Jordan Denev és Radiszlav Pavlov: A számítástudomány matematikai alapjai, Nemzeti Tankönyvkiadó, Budapest, 3. kiadás, 1994. [13] Dragálin Albert: Bevezetés a matematikai logikába, egyetemi jegyzet, KLTE, Debrecen, 1996. [14] Ehrenfeucht, Andrzej; Tero Harju, Ion Petre, David M. Prescott és Grzegorz Rozenberge: Formal systems for gene assembly in ciliates, Theoretical Computer Science 292 (2003) 199-219. [15] Ehrenfeucht, Andrzej; Tero Harju, Ion Petre, David M. Prescott és Grzegorz Rozenberg: Computation in Living Cell. Gene Assembly in Ciliates, (Natural Computing Series), Springer, Berlin, Heidelberg, New York, Hong Kong, London, Milan Paris, Tokyo, 2004. 123

124

IRODALOMJEGYZÉK

[16] Frisco, Pierluigi: Theory of Molecular Computing (Splicing and Membrane Systems), IPA Dissertation Series, 2004. [17] Garzon, Max H. and Russell J. Deaton: Biomolecular Computing and Programming (Extended Abstract), SOFSEM (1999), 181-188. [18] Giord, David K.: On the Path to Computation with DNA, Science 266 (1994), 993-994. [19] Head, Tom: Splicing systems, aqueous computing, and beyond, (in: I. Antoniou, C.S. Calude és M.J. Dineen szerk.: Unconventional Models of Computation UMC'2K ), Springer, London (2001) pp. 68-84. [20] Head, Tom: Formal language theory and DNA: an analysis of the generative capacity of specic recombinant behaviours, Bulletin of Mathematical Biology 49 (1987), 737-759. [21] Hennig, W.: Genetik, Springer-Verlag, Berlin, Heidelberg, 1995. [22] Hirvensalo, Mika: Quantum Computing, Springer-Verlag, Berlin, Heidelberg, 2004. [23] Leeuwen, J. van (szerk.): The Handbook of Theoretical Computer Science, MIT Press, Cambridge, Massachusetts, 1990. [24] Liu, Qinghua; Liman Wang; Anthony G. Frutos; Anne E. Condon; Robert M. Corn és Lloyd M. Smith: DNA computing on surfaces, Letters to Nature 403 (2000), 175-179. [25] Loos, Remco és Benedek Nagy, On the Concepts of Parallelism in Biomolecular Computing, kézirat, GRLMC szeminárium 2004. [26] Kari, Lila; M. Daley és I. McQuillan: Families of languages dened by ciliate bio-operations. Theoretical Computer Science, 320 (2004), pp. 51-69. [27] Mankiewicz, Richard: A matematika históriája, HVG-könyvek, 2003. [28] Marx György: Kvantummechanika, M¶szaki Könyvkiadó, Budapest, 1964. [29] Meglicki, Zdislaw: Three Lectures on Quantum Computing, Foundations of Computing seminar, Indiana University, Bloomington, Indiana, USA, 2002. [30] Nagy Benedek: "Interval-valued logic as a generalization of many valued logics," Technical Report 2002/20., Mathematikai és Informatikai Intézet, Debreceni Egyetem, 2002. (36 oldal) [31] Nagy Benedek: "Intervallum-logika," diplomamunka, Debreceni Egyetem, 1998. (korábbi verzió: OTDK különdíjas dolgozat, Eger, 1997.) [32] Nagy Benedek: An Interval-valued Computing Device, CiE 2005: "Computability in Europe": New Computational Paradigms, Amsterdam, Hollandia, ILLC publication, 166-177. [33] Nagy Benedek: The languages of SAT and n-SAT over nitely many variables are regular, Bulletin of the European Association for Theoretical Computer Science 82 (2004 Febr.), 286-297. [34] Nagy Károly: Kvantummechanika, Tankönyvkiadó, Budapest, 1978. [35] Ogihara, Mitsunori és A. Ray: Biomolecular computing recent theoretical and experimental advances, SIGACT News, 30(2) (1999) pp. 22-30. [36] Ouyang, Qi; Peter D. Kaplan; Shumao Liu és Albert Libchaber: DNA Solution of the Maximal Clique Problem, Science 278 (1997), 446-449. [37] Paun, Gheorghe: Membrane Computing (An Introduction), Springer-Verlag, Berlin, 2002.

IRODALOMJEGYZÉK

125

[38] Paun, Gheorghe: Computing with membranes, Journal of Computer and System Sciences 61, 1 (2000) 108-143. [39] Paun, Gheorghe és Grzegorz Rozenberg: A guide to membrane computing, Theoretical Computer Science 287, (2002) 73-100. [40] Papadimitrou, Christos H.: Számítási bonyolultság, Addison-Wesley, 1995., magyar fordítás: Novadat Bt. 1999. [41] Patterson, D. és Hennessy, J.: Computer Organization and Design: The Hardware/Software Interface, Morgan Kaufmann, 1997. [42] Pásztorné Varga Katalin és Várterész Magda: A matematikai logika alkalmazásszemlélet¶ tárgyalása, Panem, Budapest, 2003. [43] Penrose, Roger: A császár új elméje: számítógépek, gondolkodás és a zika törvényei, Akadémiai Kiadó, Budapest, 1993. (eredeti kiadás: The Emperor's New Mind: Concerning Computers, Minds, and the Laws of Physics, Vintage, London, 1989. Penguin, USA, 1991.) [44] Peth® Attila: Algoritmuselmélet, egyetemi el®adás jegyzete [45] The P Systems Web Page, http://psystems.disco.unimib.it, a legújabb kutatási eredmények is letölthet®ek a membrán-számítások témával kapcsolatban. [46] Rozenberg, Grzegorz és Arto Salomaa: Handbook of Formal Languages, 3 kötet, Springer Verlag, Berlin, Heidelberg, 1997. [47] Rozenberg, Grzegorz; Gheorghe Paun és Arto Salomaa: DNA Computing: New Computing Paradigms, Springer-Verlag, Berlin, Heidelberg, 1998. [48] Sheer, H.: A set of ve independent postulates for Boolean algebras, with application to logical constants, Trans. American Mathematical Society 14, (1913) pp. 481-488. [49] Shor, Peter W.: Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer, SIAM Journal on Computing 26/5 (1997) pp. 1484-1509. [50] Straub F. Brunó: Szerves kémia (orvostanhallgatók számára), Medicina könyvkiadó, Budapest, 1967. [51] Tomek, Ivan: The Foundations of Computer Architecture and Organization, Computer Science Press, New York, 1990. [52] Vincze János és Vincze Mária: Kibernetika - Idegrendszer - Számítógép, Kriterion könyvkiadó, Bukarest, 1977. [53] Wang, Zhenghan: Introduction to Topological Quantum Computing, Lecture Notes, Indiana University, Bloomington, Indiana, USA, 2002.

ÚJ ELV SZÁMÍTÓGÉPEK (Bevezetés az új számítási modellekbe és a nem-klasszikus "számítógépek" tudományába)

Recommend Documents