Foto: Unsplash

SVI SE PLAŠE UMJETNE INTELIGENCIJE, ALI NE ZNAJU OVO! Mnogi su se zaklinjali u savršenost stroja, a ovaj problem ih i danas koči: Hoće li mu programeri konačno doskočiti?

Autor: Zlatko Govedić/7dnevno

Posljednjih nekoliko desetljeća računala su napredovala velikim koracima, ali to ne znači da mogu riješiti sve. Čak i u doba umjetne inteligencije, neke probleme jednostavno je preteško riješiti. “Računala danas sasvim uvjerljivo mogu komunicirati s ljudima, skladati pjesme, slikati, igrati šah i dijagnosticirati bolesti, da navedemo samo nekoliko primjera njihove tehnološke moći. Ti se uspjesi mogu shvatiti kao pokazatelj da računalstvo nema granica”, tvrdi profesor računalnih znanosti Jie Wang sa Sveučilišta UMass (Lowell, Massachusetts, SAD).

Nedavno je zainteresirao svjetsku javnost svojim tekstom objavljenim 30. siječnja na platformi The Conversation. U njemu govori o onome što nam se u današnje vrijeme čini gotovo nemogućim. Kako to da postoje problemi koji su preteški čak i za umjetnu inteligenciju? Da bismo na to mogli odgovoriti, važno je razumjeti što računalo čini moćnim.

Dva su aspekta snage računala: broj operacija koje njegov hardver može izvršiti u sekundi i učinkovitost algoritama koje pokreće. Brzina hardvera ograničena je zakonima fizike. Algoritme, koji su zapravo skupovi uputa, pišu ljudi i prevode ih u niz operacija koje računalni hardver može izvršiti. Čak i kada bi brzina računala dosegla fizičku granicu, računalne prepreke ostale bi zbog ograničenja algoritama.
Te prepreke uključuju probleme koje je računalima nemoguće riješiti i probleme koji su teoretski rješivi, ali u praksi nadilaze mogućnosti čak i najmoćnijih inačica današnjih računala koje se mogu zamisliti. Matematičari i računalni znanstvenici pokušavaju utvrditi je li problem rješiv isprobavajući ih na zamišljenom stroju.

Moderni pojam algoritma, poznat kao Turingov stroj, formulirao je 1936. britanski matematičar i kriptograf Alan Turing koiji je pomoću svog računala uspio razbiti njemačke šifre.

Da ili ne

To je zamišljeni uređaj koji oponaša kako se aritmetički proračuni izvode olovkom na papiru. Turingov stroj predložak je na kojem se temelje sva današnja računala.

Riječ je o iznimno jednostavnom apstraktnom uređaju za manipulaciju znakovima (simbolima) koji, unatoč jednostavnosti dizajna, mogu biti prilagođeni da simuliraju logiku bilo kojeg računalnog algoritma. Stroj se ne koristi u praktične svrhe, već u misaonim eksperimentima, gdje najvažniju primjenu nalaze u istraživanju granica mogućnosti izračunavanja računalnim algoritmima. Proučavanje njihovih svojstava pruža dalekosežne uvide u pitanja računalne znanosti i teorije složenosti.

Kako bi se prilagodili izračunima za koje bi bilo potrebno mnogo papira da se rade ručno, pretpostavlja se da je zaliha imaginarnog papira u Turingovu stroju neograničena. To je ekvivalentno zamišljenoj neograničenoj vrpci s kvadratima, od kojih je svaki ili prazan ili sadrži jedan simbol.




Stroj je kontroliran konačnim skupom pravila i počinje s početnim nizom simbola na vrpci. Operacije koje stroj može izvesti jesu premještanje na susjedni kvadrat, brisanje simbola i pisanje simbola na prazno polje. Stroj računa izvođenjem niza tih operacija.
Kada stroj završi, ili se “zaustavi”, simboli preostali na vrpci jesu izlaz ili rezultat.

Računalstvo se često odnosi na odluke s odgovorima “da” ili “ne”. Analogno tome, medicinski test (vrsta problema) provjerava ima li pacijentov uzorak (instanca problema) određeni pokazatelj bolesti (odgovor “da” ili “ne”). Instanca, predstavljena u Turingovu stroju u digitalnom obliku, početni je niz simbola.

Problem se smatra “rješivim” ako se može dizajnirati Turingov stroj koji se zaustavlja za svaku instancu, bilo pozitivnu ili negativnu, te ispravno određuje koji odgovor instanca daje.




Polinomijalno vrijeme

Mnogi problemi jesu rješivi s pomoću Turingova stroja i stoga se mogu riješiti na računalu, no ima i onih nerješivih problema. Primjerice, “domino problem” jest varijacija problema s pločicama, a formulirao ga je kineski američki matematičar Hao Wang 1961. godine.

Vizualno se može predočiti kao skup kvadratnih pločica koje sa svake strane imaju jednu od četiri boje. Pločice se slažu jedna do druge s odgovarajućim bojama, bez okretanja ili rotacije. Osnovno pitanje problema jest može li se popločati ravnina ili ne, tj. može li se na taj način ispuniti cijela beskonačna ravnina.

Sljedeće pitanje je može li se to učiniti u periodičnom obrascu. Drugim riječima, zadatak je iskoristiti pločice za pokrivanje cijele mreže i, slijedeći pravila igre domino, uskladiti boju na krajevima pločica koje se dodiruju. Ispostavilo se da ne postoji algoritam koji može započeti sa skupom takvih domino pločica i odrediti hoće li skup potpuno pokriti ravninu ili ne.

Niz rješivih problema može se riješiti algoritmima koji se zaustavljaju u razumnom vremenu. Ti “algoritmi polinomijalog vremena” učinkoviti su, što znači da je praktično koristiti se računalom za rješavanje njihovih instanci. Za tisuće drugih teoretski rješivih problema nije poznato da imaju algoritme za polinomijalno vrijeme, unatoč intenzivnim naporima da se oni pronađu. To uključuje “problem trgovačkog putnika”.

Riječ je o logističkom problemu iz svakodnevnog života, koji se u teoriji grafova rješava tako što se pokušava naći šetnja kojom će se barem jednom proći kroz svaki vrh na grafu te se vratiti na početni vrh, učinivši to na najkraći mogući način, koristeći se usmjerenim ili neusmjerenim grafom. Mogu biti zadane i udaljenosti među vrhovima, pa se traži i da je ukupna prijeđena udaljenost najmanja.
Usporedba je s poštarom koji se kreće ulicama (u matematičkom modelu to je graf) te ima zadaću dostaviti pošiljke u svaku kuću (vrhovi dotičnog grafa), u najkraćem vremenu te se vratiti u poštu (polaznu točku).

Neučinkoviti algoritmi

Poštar želi potrošiti što manje vremena, truda i novca da bi izvršio svoju zadaću, upotrijebivši najkraću rutu. Primjena tog problema jest npr. planiranje ruta i redoslijeda prijevoza robe od skladišta do trgovina. Takve probleme, nazvane “NP-teški”, ranih 1970-ih neovisno su formulirala dvojica računalnih znanstvenika, Kanađanin američkog podrijetla Stephen Cook i Amerikanac ukrajinskog podrijetla Leonid Levin. Cook, čiji je rad bio prvi, nagrađen je Turingovom nagradom 1982., najvišom u računalnoj znanosti.

Najpoznatiji algoritmi za NP-teške probleme u biti traže rješenje od svih mogućih odgovora. Problemu trgovačkog putnika na grafu od nekoliko stotina točaka trebale bi godine da se pokrene na superračunalu. “Takvi algoritmi su neučinkoviti, što znači da nema matematičkih prečaca”, napominje Wang.

Praktični algoritmi koji rješavaju te probleme u stvarnom svijetu mogu ponuditi samo aproksimacije, iako se i one poboljšavaju. Postoje li učinkoviti algoritmi za polinomijalno vrijeme koji mogu riješiti NP-teške probleme među sedam je otvorenih “milenijskih problema” koje je privatna organizacija Clay Mathematics Institute objavila na prijelazu u 21. stoljeće, a svaki nosi nagradu od milijun američkih dolara.
Kada ih već spominjemo, treba napomenuti da je “Poincaréova pretpostavka” jedini dosad službeno riješen milenijski problem. Godine 1904. postavio ga je francuski matematičar Henri Poincaré (1854. – 1912.). U dvodimenzionalnoj mnogostrukosti, sferu karakterizira činjenica da je jedina zatvorena i jednostavno povezana površina. Poincaré je pretpostavio da je to istinito i u 3-mnogostrukosti, što je 2006. dokazao ruski matematičar Grigori Perelman. Zanimljivo, on je tu nagradu odbio, tvrdeći da je nepravedna.

Ostali milenijski problemi jesu: P naprama NP, Riemannova hipoteza, Hodgeova pretpostavka, postojanje Yang-Mills teorije i jaz masa, Navier-Stokesova jednadžba te Birchova i Swinertonnova pretpostavka.

Bezbroj pitanja

“Može li postojati novi oblik računanja izvan Turingova okvira?”, pita se Wang. Godine 1982. američki fizičar Richard Feynman (1918. – 1988.), dobitnik Nobelove nagrade za fiziku 1965. godine, iznio je ideju računanja temeljenog na kvantnoj mehanici. Godine 1995. Peter Shor, američki primijenjeni matematičar, predstavio je kvantni algoritam za faktoriranje cijelih brojeva u polinomijalnom vremenu. Matematičari vjeruju da je to nerješivo algoritmima polinomijalnog vremena u Turingovu okviru. Rastavljanje cijelog broja na faktore znači pronalaženje manjeg cijelog broja većeg od 1 koji može podijeliti cijeli broj. Na primjer, cijeli broj 688.826.081 djeljiv je s manjim cijelim brojem 25.253, jer je 688.826.081 = 25.253 x 27.277.

Glavni algoritam nazvan RSA algoritam, naširoko korišten u osiguravanju mrežnih komunikacija, temelji se na računskoj težini rastavljanja velikih cijelih brojeva na faktore. Shorov rezultat sugerira da će kvantno računalstvo, ako postane stvarnost, promijeniti naše poimanje kibernetičke sigurnosti.

Može li se izgraditi potpuno kvantno računalo za faktoriranje cijelih brojeva i rješavanje drugih problema? Neki stručnjaci vjeruju da je to moguće. Nekoliko skupina znanstvenika diljem svijeta intenzivno radi na izgradnji jednog takvog, a neki su već izgradili mala kvantna računala. “Unatoč tomu, kao i sve nove tehnologije izumljene prije, gotovo je sigurno da će se pojaviti problemi s kvantnim računanjem koji će nametnuti nova ograničenja”, zaključuje Wang.

Autor:Zlatko Govedić/7dnevno
Komentari odražavaju stavove njihovih autora, ali ne nužno i stavove portala Dnevno.hr. Molimo čitatelje za razumijevanje te suzdržavanje od vrijeđanja, psovanja i vulgarnog izražavanja. Portal Dnevno.hr zadržava pravo obrisati komentar bez najave i/li prethodnog objašnjenja.