0. Viteza (de calcul) a fost dintotdeauna o obsesie pentru informatica.
1. Inainte insa de a vedea ce si cum in aceasta chestiune, se impun cåteva precizari-precautii.
Este vorba aici despre calculatorul «obisnuit», de tip PC, electronic, cu ecran, tastatura, mouse si o cutie plasata pe masa sau sub masa si care produce continuu un båzåit discret, ca un motor subtil mereu in functiune. Comandat prin tastatura si mouse, programat (eventual nevizibil pentru utilizator) in unul din numeroasele limbaje care compun veritabilul turn Babilon al limbajelor de programare. Calculator de tip von Neumann i se mai spune, desi «vinovatul» principal poate fi considerat A. Turing: John von Neumann a declarat explicit ca atunci cånd a proiectat primele calculatoare, prin anii 40, a fost esential influentat de rezultatele lui Alan Turing privind calculabilitatea, in particular, de arhitectura si modul de functionare (daca se poate spune astfel despre o masina virtuala, teoretica, un model matematic, de fapt) al masinii Turing.
Pentru cititorul care nu a «vazut» inca o masina Turing, mentionez ca, la nivel ne-formal, este vorba despre un dispozitiv format dintr-o banda infinita pe care pot fi scrise simboluri dintr-un alfabet finit precizat, un cap de citire-scriere care poate citi un simbol de pe banda, il poate modifica si se poate deplasa spre stånga sau spre dreapta cu un pas, sub controlul unei stari, element al unei multimi finite de stari; la fiecare pas de calcul, masina citeste deci un simbol de pe banda si, in functie de simbol si de starea curenta, modifica acel simbol, isi modifica starea si muta capul de citire-scriere la stånga sau la dreapta cu un simbol. Se pleaca dintr-o stare initiala precizata, cu un continut dat al benzii. Conform unui set specificat de instructiuni, masina fie «functioneaza» la infinit, si atunci nu avem nici un rezultat al calculului, fie se opreste, si atunci continutul benzii la momentul opririi poate fi considerat ca rezultat al calculului. De remarcat modul pur secvential de functionare, caracterul idealizat al «hardware»-ului (contam pe un spatiu de lucru nelimitat), minimalitatea modelului (nu se poate concepe un cadru mai simplu in care sa se poata prinde ideea curenta de calcul), precum si faptul ca, asa cum afirma teza Turing-Church, tot ce se poate calcula (algoritmic) poate fi calculat cu o masina Turing.
Dar, sa revenim (la limitele noastre). Am adus in discutie detaliile anterioare pentru a mentiona un fapt fundamental: calculatorul actual este eminamente secvential, el executa una dupa alta operatiile elementare de care este capabil si pe care se bazeaza intreaga sa functionare.
Electronic si secvential. Sa retinem aceste doua «acuzatii»
Grabindu-ne a sublinia ca nu este nici pe departe intentia acestor rånduri de a micsora lasa ca nici nu se poate asa ceva valoarea-meritele-utilitatea calculatorului asa cum il stim. Practic, nu se mai poate trai fara calculator: de la evidenta populatiei la jocuri, de la calculul salariilor (si impozitelor) la editare de texte, de la comertul electronic la planificarea si programarea productiei, si asa mai departe, o lista fara sfårsit si cu fiecare zi mai incapatoare. Suntem deja dependenti de calculator (vezi si preocuparea legata de «problema mileniului», de posibilele incurcaturi provocate de trecerea la anul 00 a calculatoarelor care nu pot recunoaste aici anul 2000) si vom deveni mereu mai dependenti. Asa «electronic si secvential» cum este el acum, calculatorul ne va deveni un partener de existenta precum ceasul, omniprezent, aproape insesizabil, dar indispensabil.
Intr-un spatiu speculativ, constatarile anterioare pot fi amplificate påna la un nivel care ar trebui sa ne dea frisoane. Sa acceptam structura triadica a materiei substanta, energie, informatie si sa observam ca omenirea a fost mai intåi preocupata de satisfacerea a ceea ce se cheama nevoi de baza, direct legate de substanta (hrana, imbracaminte, adapost), a intrat de cåteva secole in plina era energetica, iar de un numar bun de decenii consuma-proceseaza cu frenezie informatie. Mai ales prin intermediul ecranelor deocamdata. Sa amintim aici de Inteligenta artificiala, pentru a aduce vorba despre Viata artificiala (Artificial Life), un domeniu nou de cercetare, tintind spre simularea vietii (chiar daca deocamdata nici nu se prea stie cum poate fi ea definita ) in medii informationale, in particular pe calculator. Sa facem un prim pas dinspre science spre science-fiction si sa-l recitim pe Frank Tipler, cu a sa promisa viata vesnica intr-o lume-de-apoi informationala, pe undeva, prin punctul Omega din fizica Sau, sa intram din plin in science-fiction: asa cum Einstein a stabilit o ecuatie de transformare intre substanta si energie (celebra E = mc2), sa ne imaginam ca exista si o ecuatie care leaga, sa zicem, energia de informatie! Nu derivez aici consecinte posibile ale unei asemenea ecuatii, ale eventualei transformari informatie-energie-substanta. «La inceput a fost Cuvåntul» ar putea fi dublat de «Peste tot va fi Cuvåntul»
2. Sa revenim in prezentul (presupus) sigur al stiintei/informaticii: progresele teoretice si tehnologice privind calculatoarele au fost impresionante. Ajunge sa comparam «uzinele» anilor 50, cu camere intregi pline cu tuburi electronice, discuri magnetice de o jumatate de metru diametru si cititoare de benzi de dimensiunea unui dulap, cu laptopurile anilor 90 tårzii. Dimensiunile si pretul s-au micsorat continuu, capacitatea informationala, viteza si fiabilitatea au crescut continuu. De la tuburi la tranzitor si apoi la chip-ul de siliciu, inginerii au facut adevarate minuni. In particular, sa mentionam multe milioane de operatii elementare pe secunda pe care le pot efectua procesoarele moderne.
Dar, minunile ingineresti nu mai pot continua prea mult. Nu-i lasa nici matematicianii, nici fizicienii. Limitele tehnologice se afla la distanta unui brat intins.
Informatia nu poate circula cu o viteza mai mare ca a luminii, ne-a convins de asta fizica relativista (in particular, electronii nu pot circula decåt cel mult cu viteza luminii). Calcul inseamna procesare de informatie, deci si transport de informatie (fizic, de cele mai multe ori, transport de electroni). Pentru a mari numarul de operatii pe secunda, nu avem alta posibilitate decåt sa micsoram distantele. De aici, cursa pentru miniaturizare. Procesoarele actuale sunt deja plasate la nivel micro si se fac incercari sustinute pentru a se trece la nivel nano. Da, dar zåmbetul ingaduitor (daca nu si limba scoasa spre fotograf, deci spre lume, din mult mediatizata fotografie) al lui Einstein (si al celor ca el, din fizica cuantica) ne påndeste si aici: desi there is plenty of room at the bottom (R. Feinmann), pe acolo, pe jos, nu mai functioneaza fizica macro, buna fizica Galilei-Newton-Maxwell-etc., ci fizica cuantica, paradoxala (pentru mintea «macro») fizica Einstein-Plank-Bohr-Shrödinger-etc., unde nedeterminismul si probabilitatea sunt la ele acasa. Un calculator nedeterminist, chiar daca furnizånd anume garantii probabiliste, nu poate fi folosit in lumea «normala». Gånditi-va la calculatorul care va gestioneaza contul din banca sau care controleaza zborul avionului cu care tocmai zburati ca sa nu mai amintesc, apara Doamne, de calculatoarele din buncarele cu dolofane rachete nucleare pentru a vedea cam despre ce este vorba.
Miniaturizarea nu mai poate merge prea departe, bariera cuantica este deja vizibila. Viteza procesoarelor de siliciu va mai creste probabil o vreme, dar cu o rata mult incetinita, sa zicem, cel mult liniar, pentru a face legatura cu ideea imediat urmatoare.
3. Ajungem astfel la o limita matematica fundamentala a calculatorului de tip secvential, mai ales in raport cu asteptarile pe care le avem de la el: multe, daca nu majoritatea problemelor de interes practic sunt de complexitate exponentiala.
Cititorul fara preocupari (eventual nostalgii) matematice nu trebuie sa intrerupa aici lectura, voi explica imediat despre ce este vorba pe un exemplu, care nu este ales intåmplator.
Sa consideram o harta, pe care avem un numar de localitati, legate intre ele de o retea de sosele; sa presupunem ca unele tronsoane de sosea (de la o localitate la alta) sunt cu sens unic. Un turist doreste sa plece dintr-o localitate A, sa ajunga in final intr-o localitate B si sa treaca prin toate celelalte localitati de pe harta, o singura data prin fiecare. Exista un asemenea itinerar? Sa se indice unul (eventual, de lungime minima, daca se cunosc si distantele directe intre localitati). Un voiajor comercial ar putea sa-si puna o problema asemanatoare, la fel o biblioteca ambulanta sau o caravana cinematografica (chiar daca cititorul tånar nu prea stie ce este aceea). In terminologie matematica, avem o problema de drumuri in grafuri. Un graf este exact o harta, formata din puncte-localitati si arce-sosele. Problema noastra este cunoscuta sub numele de problema drumului hamiltonian si cere sa se spuna daca intr-un graf dat exista sau nu un itinerar care trece prin toate nodurile o singura data, plecånd si ajungånd in noduri dinainte stabilite. (Numele aminteste de matematicianul W. R. Hamilton, Sir, care pe la jumatatea secolului trecut a lansat un joc de tipul urmator: pe un dodecaedru regulat inchipuind globul pamåntesc, se cerea sa se viziteze toate cele 20 de orase-vårfuri, trecånd o singura data prin fiecare, folosind muchiile ca drumuri de legatura.)
Ei bine, problema noastra, asa simplu de formulat cum pare, este o «nuca prea tare» (expresia vine dinspre Lewis Carroll) pentru calculatorul actual: ea este o problema de complexitate exponentiala. Pentru a decide daca un graf cu n noduri contine sau nu un drum hamiltonian trebuie sa efectuam un numar de operatii elementare care este exponential in raport cu n, este de tipul lui 2n. Iar cu numere de tipul lui 2n este bine sa fim grijulii, ele cresc mult mai repede decåt ne-am astepta la o privire grabita amintiti-va de recompensa in boabe de gråu ceruta de inventarul jocului de sah imprudentului suveran, beneficiar al inventiei.
Afirmatia anterioara, privind complexitatea problemei drumului hamiltonian, cere, desigur, o justificare matematica. De fapt, ea nu are inca o asemenea justificare, in intelesul propriu al cuvåntului. Situatia este urmatoarea. In acest moment, toate procedurile de rezolvare a problemei cer un numar exponential de operatii, nu exista nici o metoda care sa fie esential mai buna decåt explorarea exhaustiva a multimii drumurilor posibile intr-un graf dat. (Iar numarul acestor drumuri este de nivel exponential: plecam dintr-un punct A si facem un pas in toate directiile posibile; pentru un graf care are n noduri, asta inseamna cel mult n 1 posibilitati; din fiecare nod in care am ajuns, ramificam din nou drumul; de fiecare data avem cel mult n 2 alegeri, pentru ca nu mai revenim si in nodul anterior; continuånd procedura, ajungem la situatia in care nu mai avem decåt o singura posibilitate de continuare; pe total, avem n-factorial drumuri. Evident, se pune acum problema sa alegem dintre acestea un drum hamiltonian daca el exista.)
Pe de alta parte, s-a demonstrat ca orice problema care poate fi rezolvata in timp exponential poate fi redusa la problema drumului hamiltonian, iar reducerea se poate face printr-o procedura (calcul) care lucreaza un timp polinomial (un polinom contine termeni de tip n, n2, n3 etc.; cititorul ar trebui sa fie convins ca n2 creste mult mai incet decåt 2n, ca exista o diferenta esentiala intre cresterea polinomiala si cea exponentiala).
Cu alte cuvinte, daca ar exista un algoritm de rezolvare a problemei drumului hamiltonian care sa fie de complexitate sub-exponentiala polinomial, de exemplu atunci orice alta problema de complexitate exponentiala ar putea fi rezolvata in timp polinomial. O asemenea consecinta este cu totul neplauzibila, practic nici un informatician-matematician nu o crediteaza cu vreo sansa de a fi adevarata.
Repet: nu s-a demonstrat inca formal ca problema noastra nu poate fi rezolvata in timp polinomial, iar ca ea sunt cunoscute sute (chiar mii) de probleme cu aceeasi proprietate. Chestiunea framånta de mai mult timp comunitatea stiintifica, ea este probabil cea mai importanta problema deschisa din informatica teoretica (ceva mai formal, problema intreaba daca P = NP nu precizez definitiile si sub acest nume este ea cunoscuta, «problema P = NP»).
Pe scurt, calculatorul secvential nu poate face fata complexitatii de tip exponential, iar probleme (banuite, cu mare plauzibilitate) de complexitate exponentiala apar peste tot, de la jocul de GO la programarea productiei, de la criptografie la recunoasterea formelor. Oricåt ar progresa (liniar) calculatorul traditional, el nu poate impinge prea departe bariera fezabilului.
4. Poate ar trebui adusa aici in scena distinctia dintre competenta si performanta, dintre ceea ce se poate face in principiu si ceea ce poate face in timp util. Discutia dinainte se referea la performanta calculatorului asa cum il stim. El are insa limite deja bine conturate la nivelul competentei. Teza lui Turing-Church este una dintre ele. Calculatorul (care lucreaza un timp finit, discret, cu informatie discreta) nu poate calcula mai mult decåt calculeaza masina Turing. Iar asta nu e deloc prea mult, in raport cu clasa tuturor problemelor (functiilor) de rezolvat (de calculat). Ca sa nu mai vorbim de limitele insele ale formalizarii matematice (axiomatice), de tipul faimoaselor teoreme de incompletitudine ale lui Gödel. Il rog pe cititor sa parcurga mai vechile, dar continuu, excelentele prezentari ale subiectului din S. Marcus, Gåndirea algoritmica (Editura Tehnica, 1982), sau C. Calude, Adevarat, dar nedemonstrabil (Editura{tiintifica si Enciclopedica, 1988).
5. Daca principala limita a calculatorului actual este resimtita la nivelul vitezei de calcul, multe altele i se pot reprosa (la nivelul de exigenta pe care l-am adoptat aici).
Legat de viteza este volumul de date pe care le poate stoca-procesa. Exista o balanta (trade-off) de mult pusa in evidenta intre timp si spatiu, plecånd de la mentionata necesitate a miniaturizarii pentru a micsora timpul de comunicare a informatiei si ajungånd la observatia oricarui programator ca beneficiind de memorie suficienta se pot imbunatati performantele unui program la nivelul timpului de lucru. Aceeasi dualitate-concurenta spatiu-timp apare in legatura cu una dintre cele mai promitatoare idei de marire a vitezei de calcul, paralelizarea. Folosesc acest termen general pentru a acoperi atåt cercetarile teoretice, cåt si pe cele tehnologice in domeniu. Ideea este simpla: daca o problema este prea complexa, rezolvarea ei dureaza prea mult, s-o spargem in subprobleme, sa incredintam aceste subprobleme unor procesoare separate, care sa le rezolve in paralel, apoi sa sintetizam solutia problemei din solutiile subproblemelor considerate. Din punct de vedere teoretic, acest demers ridica necesitatea studiului problemelor paralelizabile, a gasirii protocolului de lucru al procesoarelor si a modului de sintetizare a solutiei globale. La nivel tehnologic, problema revine la construirea unui hardware de tip paralel, de un tip complet diferit de cel Turing-von Neumann. Ce fel, cum si cåte procesoare trebuie-pot lucra in paralel? Pentru o reducere semnificativa a timpului de lucru, este de asteptat sa avem nevoie de o paralelizare semnificativa. Nu putem «bate» exponentialul astfel decåt prin exponential, deci in principiu avem nevoie de un numar exponential de procesoare. Limitele de timp se transforma astfel in limite de spatiu.
Intre teorie si tehnologie, cu legaturi intime cu amåndoua, sta problema programarii de tip paralel, a limbajelor de programare care sa faciliteze acest lucru.
Fara ca aceste multe probleme sa fie satisfacator rezolvate, exista numeroase (scuze pentru demodatul deja barbarism) implementari ale ideii de paralelism. Exista calculatoare paralele (CRAY e un exemplu), exista limbaje de programare si sisteme de operare care permit lucrul in paralel (UNIX este un exemplu), exista mai ales retele de calculatoare. Speranta este mai buna folosire a harrware-ului actual, nu neaparat paralelismul de nivel exponential. Chiar si marirea eficientei de calcul cu un factor liniar este un cåstig.
Apropo de retele de calculatoare: aproape pe nesimtite, Internet-ul a pus stapånire peste tot si peste toate, ceea ce-mi aduce in minte o povestire SF in care era vorba despre un grup de informaticieni care au reusit sa lege intre ele majoritatea calculatoarelor pamåntului, mai ales pentru a le da spre rezolvare problema-ultima a umanitatii, «Exista Dumnezeu?» Super-calculatorul de intindere planetara a pålpåit o vreme pe tacutelea, apoi a raspuns simplu: «Da, de acum exista!»
6. Intre timp (påna ce Internet-ul nu are de raspuns la intrebari-ultime), sa mai mentionam si alte limite ale «creierului electronic» (ar fi interesant de examinat soarta acestei sintagme: se speria gåndul pe vremea cånd calculatorul gåfåia la inversarea de matrici si-l numeam creier, dar nu-i mai recunoastem acum nici o trasatura «umana», desi nici macar Kasparov nu mai are spor in fata lui atentie, pe terenul lui Kasparov, nu la inversarea de matrici ). De pilda, calculatorul electronic consuma energie. Poate parea o banalitate, poate parea un moft pentru lumea oricum energofaga in care traim sa ne gåndim la economisirea celor cåtiva wati care-i trebuie unui calculator. Dar, dar pe o statie cosmica nu ne putem permite sa risipim nici un Joule. Da, dar din punct de vedere ingineresc, avem nevoie nu numai de surse de energie fiabile si eficiente (intreruperea curentului poate fi un dezastru pentru un calculator in functiune, iar bateria unui laptop nu este deloc un detaliu), dar si de sisteme de racire ale procesoarelor (micul motoras care båzåie continuu intr-un calculator este cooler-ul procesorului). Procesarea de informatie consuma energie cel putin la modul electronic actual.
Un vis, solutie a acestei probleme, este calculatorul reversibil. Nu prea este clar despre ce este vorba, dar se stie ca procesele reversibile, fie ele fizice sau biochimice, nu consuma energie (ceea ce nu inseamna ca citirea de informatie, de exemplu, a rezultatului unui calcul, nu va ramåne consumatoare de energie). Din punct de vedere teoretic, chestiunea a fost rezolvata: orice masina Turing poate fi simulata de o masina Turing reversibila (Ch. Bennett). In practica lucrurile nu am mers inca la fel de repede.
7. Am ajuns astfel, din limita in limita, la granita dinspre måine a calculatoarelor. Paralelism (eventual exponential)? Reversibilitate? Compacitate informationala? Toate acestea se pot intålni in fizica cuantica (unde, pe motiv de superpozitie cuantica nu ma intrebati ce este aceea , intr-un registru de marime n pot fi stocate 2n numere; operånd deci la nivelul lui n, obtinemanumite informatii despre toate cele 2n numere, de unde, in anumite cazuri rezulta accelerarea exponentiala de care avem nevoie), ba chiar si in propriile celule, la nivelul ingineriei genetice, a prelucrarii informatiei din molecula de ADN sau chiar la nivelul proceselor chimice si informationale care au loc in celula insasi. Din acest ultim teritoriu, al modului in care «calculeaza» natura (vie) se revendica asa-numitul Calcul Natural, cu cel putin patru directii de cercetare (unele deja de eficienta practica dovedita): retele neuronale, algoritmi genetici (mai general, programare evolutiva), calculabilitate de baza de ADN (DNA computing) si calcul cu sisteme de membrane (Membrane computing). Natura (vie) ne ofera sugestii indelung verificate de cum ar trebui/putea arata un calculator, iar de cåteva timp aceste sugestii au fost luate in serios. Calculatorului electronic pare a i se intrevedea ajutoare (nu concurenti) cu totul inedite: calculatorul cuantic si bio-calculatorul. Iar primul test al bio-calculatorului (pe baza de ADN) a fost facut chiar in rezolvarea in eprubeta a unei probleme (de mici dimensiuni) de drumuri hamiltoniene (L. Adleman, 1994).
Despre toate acestea insa intr-un numar viitor al revistei.