Bevezetés
Egy galamb, egy szöcske vagy egy légy olyan képességekkel bír, amelyek utánzására sem a mai digitális szuperszámítógépek, sem robotok vagy vadászgépek sem képesek. Egy olyan egyszerűnek tűnő kérdés megválaszolására, hogy egy nyúl szemének mekkora a számítási komplexitása vagy teljesítménye, az elmúlt ötven évben kidolgozott nagyszerű számítástudományi apparátus elvileg is alkalmatlan. Jelen esszében felvázolunk néhány olyan példát az elmúlt néhány év tudományos eredményeiből, amelyek talán egy új világot nyitnak a számítógépről alkotott fogalmainkban, és nemcsak újfajta "analogikai" számítógépeket eredményeztek, de egyben választ adhatnak az élő világ információtechnikájának néhány fontos kérdésére, például közelebb visznek az idegrendszer néhány alapjelenségének megértéséhez is. Egyúttal talán újfajta megvilágításba kerül a számítási komplexitás is.
A digitális számítógépek "egyszerű" világa
Milyen bonyolult egy számítógép program egy adott feladat megoldásában?
Az elmúlt ötven évben az erre a kérdésre adandó válasz keresése során - a digitális számítógépek és elemi utasításaik, valamint ezek integrált áramköri megvalósításai fényében - kialakult, és mély eredmények sorában csiszolódott egy diszciplína: a számítási komplexitás elmélet.
Ennek leegyszerűsített lényege röviden talán így fogalmazható meg: egy adott feladat méretétől függően milyen mértékben nő a megoldáshoz szükséges műveletek száma. Például ha n számú várost akarunk bejárni, mindegyiket egyszer meglátogatni, akkor a minimális utazási hosszt jelentő város-sorrend meghatározásának a városok számának növekedésével párhuzamosan nagyon nő a számítási igénye, műveletszáma. A "nagyon" mondjuk exponenciálist jelent, azaz a műveletszám kˇen-nel arányos. A fenti feladatban, amelyet "utazó ügynök" problémának is neveznek, a bonyolultságot a keresés bonyolultsága jelenti.
Vannak azonban "könnyű" problémák is, amikor a "nehéz" feladatokkal ellentétben a szükséges műveletszám n-nel lineárisan vagy négyzetesen (n2, stb.), azaz polinom rendben nő.
És vannak a digitális számítógépekkel megoldhatatlan problémák: például annak eldöntése, hogy egy egész számokon értelmezett polinomnak általában van-e az egész számok között gyöke (megoldása).
Ugyancsak megoldhatatlan sok feladatban annak meghatározása, hogy mekkora a feladatot megoldó program minimális hossza.
Az elmúlt ötven évben a fenti elvi bonyolultság gyakorlati probléma is volt, mert az egyre hatékonyabb mikroprocesszorokban a chip felülete és hődisszipációja gyakorlatilag megmaradt a nagyjából 1 cm2 illetve 1 W tartományban. Így a kereső típusú feladatokban a program lefutási idejét mérő műveletszám az egyetlen lényeges gyakorlati bonyolultsági mérték volt.
Az elmúlt pár évben azonban észrevehettük, hogy a mikroprocesszoroknak egyre nagyobb "házuk" van, ugyanis egyre többet disszipálnak (20-30-40 W), és ezért egyre nagyobb hűtőegységek szükségesek hozzájuk. A nagyobb gépek ráadásul 2, 4, 8 vagy akár tízezer chipet is igényelnek (a memóriákon kívül). A valódi számítási bonyolultságnak tehát a megoldási idő mellett a szilíciumfelület és a disszipáció mértékét is figyelembe kell vennie (előbbi a m2, utóbbi a MW nagyságrendjébe is kerülhet).
A számítás - általános értelemben a feladatmegoldás - bonyolultsága és a számítógép bonyolultsága tehát összefügg.
A 80-as évek végén, majd a 90-es években ez az egyszerű, szép világ azonban ezen túlmenően is megváltozott. Kiderült, hogy a valós számokon, majd a képfolyamokon értelmezett számítógépekben egészen más nehézségi paraméterek lépnek be, mint a méret, másrészt a klasszikus elmélet olyan egyszerűnek látszó kérdések értelmezésével sem tud mihez kezdeni, mint például az, hogy mekkora egy retinamodell számítási bonyolultsága.
Jelen írásunkban ez utóbbi kérdésekkel foglalkozunk.
A valósokon értelmezett számítógépek
1989-ben Lenore Blum, majd Steve Smale és Michael Schub egy újfajta számítógépmodellt vezettek be, amely nem egész számokon, hanem folytonos, úgynevezett valós értékeken dolgozik. Az adattípus kivételével minden más diszkrét és iteratív maradt. Kiderült azonban, hogy ezeken a Newton-gépnek is nevezett számítógépen - a valósokon értelmezett "univerzális gépeken" (Universal Machine on Reals, UMR) - mások a megoldhatatlan és a nehéz problémák, mint a klasszikus, egészeken értelmezett univerzális gépeken (Universal Machine on Intergers, UMZ). A valósokon értelmezett univerzális gépen megoldhatatlan annak eldöntése, hogy egy adott érték rajta van-e egy egyszerűen definiálható, de látványra bonyolult képen, az úgynevezett Mandelbrot- vagy Julia-halmazokon. Itt is vannak "nehéz" feladatok, de ezek is mások, mint például az utazó ügynök probléma. Például több polinom esetén kérdés, hogy van-e közös valós gyökük. Az eldöntéshez szükséges műveleti szám exponenciálisan nő, és a polinom változóinak számát is növeli.
Bár ez idáig a valósokon értelmezett univerzális gépnek sem direkt elektronikai implementációja, sem élő rendszerbeli megfelelője nincs - jóllehet a digitális számítógépeken emulált verzióját nap mint nap használjuk -, mégis fontos kérdésekre mutatott rá. Például arra, hogy a számítási bonyolultság nemcsak a mérettől, hanem más paramétertől, például a pontosságtól is függhet. Sőt lehet, hogy ezek fontosabbak, mint a feladat mérete: ez utóbbi esetleg egyáltalán nem mérvadó.
A képfolyamokon értelmezett celluláris analogikai "hullám-számítógépek"
Ha számítógépünk alapadatai nem egész számok, és nem is valós számok, hanem képfolyamok (például a videoklipek), amelyekkel a valódi érzékszerveinkben is találkozunk, akkor a celluláris analóg-és-logikai - vagy analogikai - számítógépek világába jutunk. Ez az úgynevezett folyamokon értelmezett univerzális gép (Universal Machine on Flows, UMF), amely digitális értelemben is univerzális, minden olyan feladatot meg tud oldani, amit egy csupán egész számokon értelmezett gép. Ráadásul ezek a számítógépek olyan elemi (itt: könnyen megoldható) utasításokra képesek, mint például egy képfolyamon egy hullám-egyenlet megoldása, amelyek a digitális számítógépeken éppen a legnehezebbek. E számítógép formális leírása, amelyet CNN univerzális gépnek nevezünk, csupán néhány egyszerű analóg és bináris logikai építőelemet, építőkockát tartalmaz, de ezekből egy rácson, szomszédokat összekapcsolva és tárolt programozást lehetővé téve sokat helyezünk el. A CNN az analogikai celluláris számítógép magját, a celluláris neurális vagy nemlineáris hálózatot jelenti (Cellular Neural/nonlinear Network). Ez a sejtautomatához hasonló, de nemcsak logikai, hanem időben folytonos analóg jeleket is kezel, és a cellák közötti interakciók is valós értékűek. Fizikai megvalósításuk sokféle lehet: a részben digitálisan utánzott áramköri megvalósítástól egészen az optikai vagy nanoelektronikai megoldásokig.
Ezek a "hullám-számítógépek" viszont nagyon közel állnak ahhoz az idegrendszerben működő "számítási stílushoz", amelyet érzékszerveink többsége használ, ahol többnyire analóg hullámjelenségek és "logikai" (igen-nem) detekciók vannak térben elosztva. Tipikus példák: egy adott sebességtartományban mozgó objektum detekciója, egy madárdal felismerése, egy galamb felismeri a párját, egy bagoly sötétben megtalálja a hangot adó egeret.
Vajon ebben a számítógép világban melyek a megoldhatatlan és a nehéz problémák? Ez a kutatási irány éppen most van kibontakozóban, de néhány alapvető eredmény már van. Az egyik az, hogy itt is vannak "nehéz" problémák, amelyek közül éppen egy keresőprobléma bizonyult ilyennek. Ez nem véletlen, hiszen az új gép a logikai keresőfeladatokban nem jeleskedik, bár ezt is ugyanolyan jól tudja, mint a tisztán logikai gép. Ugyanakkor képes egyetlen utasítással megoldani olyan feladatokat, amely bármelyik másik két gépnek "nehéz".
Az is megmutatható, hogy ez a térben diszkrét, de időben, jelértékben és interakcióban folytonos gép egyetlen utasításában is gazdagabb, mint bármelyik, ehhez közelálló, úgynevezett "parciális differenciál egyenletrendszer" megoldásából adódó tér-időbeli dinamikus jelenség. Ez utóbbi egyenletrendszer a fizikai világ tipikusan legbonyolultabb leírási módja.
Milyen az "élő számítógép", mi az a feladat, amely számára egyszerű?
Érdekes az is, hogy ez az új számítógép paradigma nagyon közel áll az élő szervezetek idegrendszerének sok részletéhez: szerkezetében az anatómiájához, működésében a fiziológiájához. Mintha mesterséges, de egyszerű neuronprocesszorok lennének elhelyezve egy síkrácson, és a szomszédok egymással interakcióban, "receptív mezőszerűen" lennének összekapcsolódva. Ezen síkbeli processzorseregek vannak a harmadik dimenzióban egymásra helyezve, amelyben immár a közvetlen fel-le szomszédok is kapcsolatban vannak. Talán nem pusztán szerencse, hogy hamar kiderült: az új - tárolt programozható - analogikai számítógépmodellel nagyon egyszerűen és természetesen lehet bonyolult érzékelő és felismerő idegi funkciókat modellezni. Kiderült, hogy az idegrendszerre azért nehéz ráerőltetni a digitális számítógép-paradigmát, mert az idegi szerveződések természete ettől idegen. Ezzel szemben az analogikai celluláris hullám számítógépeké szinte erre is teremtetett. Itt a bonyolult egyszerűvé válik, az elemi utasítások a természetes szerveződéseket tükrözik. Ennyire egyszerű! De az számomra szinte már csoda, hogy például az emlősök retinájában a csatolt hullámegyenletek jelentik a "természetest", az egyszerűt. Az idegtudományok, a genetika és az immunológia új felfedezései máris elkezdték átformálni az egyszerűről és bonyolultról alkotott nézeteinket. Alaposan újra kellene gondolnunk a számítási komplexitás egész elméletét.
Egy újfajta algoritmikus gondolkodási és "logikai" elemei
A digitális számítógép diadalútjának technikai alapja az elmúlt negyven év integrált áramköri fejlődésének diadalútja, amely magába foglalja a modern természet és műszaki tudomány szinte minden szeletének csúcstechnológiáját. Szellemi alapját Neumann János tárolt programozási elve jelenti: az a lehetőség, hogy algoritmikus programozással ugyanazon a processzoron (mikroprocesszoron) milliárdnyi különböző feladatot tudunk megoldani. A gép kinyílt az emberi intellektus találékonysága felé. A CNN univerzális gépnek nevezett analogikai celluláris számítógép ugyancsak tárolt programozott, de egy komplexebb, és az érzékszerveinkhez (látás, tapintás, hallás, stb.) közelebb álló adattípuson, a képfolyamokon vagy videóklipeken működik, és hullámszerű effektusokat jelentő utasításkészlettel. Ez az algoritmikus "szép új világ" most indul, máris van néhány fiatal mestere. Öröm, hogy többen közülük éppen itthon dolgoznak.
Amint a logikai számítógép modellezheti és modellezi logikai gondolkodásunk, logikai következtetéseink folyamatait - ezt tükrözik például a XX. század első fele nagy logikusainak munkái, majd a mesterséges intelligenciának nevezett kutatási irány jelentős alkotói -, hasonlóképpen elindulhatunk azon az úton, amelyen az analogikai celluláris számítógép elemi utasításai és adattípusai egy új analogikai gondolkodási és következtetési módszer keretét jelenthetik.
Ebben az analogikai következtetésrendszerben az alapadataink, amelyeken az igaz-hamis állításainkat megfogalmazzuk, egy adott ideig tér-időbeli folyamok. Ebben keressük a mikor? mi van?, hol van? kérdésekre adott választ. Ha feketével jelezzük az igen-t, akkor ez a válasz egy fekete-fehér térképen az időben változó fekete területekkel jellemezhető. Például, ha költöző madarak repülését nézzük, és megkérdezzük, hogy hol vannak a fecskék, akkor a fecskéket jelentő fekete foltok mozgása adja az "analogikai" választ. Ennek a válasznak a megadásához az elemi következtetési lépések nem a logikai döntésekkel kezdődnek, hiszen a folyamatosan változó szürke képen ezek eredendően nem is értelmezhetőek.
Ez a kiterjesztett, tér-időbeli analóg-logika ma már sokféle "vizuális mikroprocesszoron", a CNN univerzális gépen alapuló "látó" chipen beprogramozható és alkalmazható, néhány idegi jelenségnek pedig sikeres modellezését tette lehetővé. Ilyen például a retina belső működése.
Mindenesetre megindultunk egy olyan úton, amely a természet jelenségeit figyelve, egy differenciáltabb és gazdagabb képet mutat a számítógépről, és a feladatok megoldásának bonyolultságáról.