O rešljivem, nerešljivem, obvladljivem in neobvladljivem

V vsakdanjem življenju pravimo, da obstajajo problemi, ki so rešljivi, včasih celo zlahka, pa tudi takšni, ki jih očitno ni mogoče rešiti, pa naj si še tako prizadevamo. In nekaj podobnega bi bilo mogoče reči za znanost: tudi tu obstajajo problemi, ki so po vsem sodeč nerešljivi. Morda celo za vselej. In s takšnimi se ukvarja teorija izračunljivosti (computability theory).

To nenavadno, a vznemirljivo temo, ki je neprimerno tesneje povezana z našim vsakdanjikom, kot bi marsikdo pomislil, tokrat predstavlja njen dober poznavalec, dr. Borut Robič, redni profesor računalništva in informatike, predstojnik katedre za teoretično računalništvo in vodja laboratorija za algoritme in podatkovne strukture na Fakulteti za računalništvo in informatiko Univerze v Ljubljani. In seveda avtor monografije The Foundations of Computability Theory (Temelji teorije izračunljivosti), ki je letos izšla pri mednarodni znanstveni založbi Springer.

A kaj natanko sploh je teorija izračunljivosti in v katero znanstveno kategorijo se uvršča, je neizogibno prvo vprašanje. »To področje spada v teoretično računalništvo, torej v tisti del znanosti, v katerem se prekrivajo računalništvo, matematika, v zadnjem času pa tudi kvantna fizika,« pojasni prof. Robič. In takoj postreže z natančnejšim odgovorom: »Teorija izračunljivosti raziskuje, kakšne probleme je z računalnikom mogoče rešiti in kakšnih ne. Pri tem bodisi upošteva, da narava omejuje računske vire, ki so na voljo za reševanje, na primer čas in prostor, ali pa se za te omejitve kratko malo ne zmeni. V tem primeru raziskuje, kakšne probleme je sploh – torej načeloma – mogoče rešiti in kakšnih ne.«

Torej obstajajo računski problemi, ki jih ni mogoče rešiti, ne glede na to, koliko časa, papirja in računalnikov bi imeli na voljo?

Tako je, takšni problemi ne samo obstajajo, ampak jih je v resnici neskončno veliko. To je tudi eno izmed presenetljivih odkritij teorije izračunljivosti. Drugo njeno odmevno odkritje je bilo spoznanje, da – vsaj na papirju – obstaja naprava, ki lahko reši sleherni problem, katerega je sploh mogoče rešiti. Nekoč so takšni napravi rekli univerzalni Turingov stroj, danes pa ji rečemo računalnik. Teorija izračunljivosti je torej napovedala računalnike, in to že leta 1936, ko na svetu ni bilo še nobenega. Tretja zanimiva problematika, s katero se ukvarja teorija izračunljivosti, pa so računski problemi, ki bi, če bi jih znali reševati v sprejemljivem času, dramatično spremenili naš vsakdanjik.

In kakšna je bila pot do teh zanimivih ugotovitev?

Da to razumemo, se moramo malo sprehoditi skozi zgodovino. Vse skupaj se je začelo okrog leta 1900. Takrat je nemški matematik Georg Ferdinand Cantor zasnoval t. i. teorijo množic. Njena moč in lepota je bila v tem, da je obetala postati podlaga vsem vejam matematike. Toda Cantor, čeprav izjemen, je bil pri njenem snovanju preveč svobodomiseln. To se mu je hitro maščevalo, saj so v njegovi – rečemo ji tudi naivni – teoriji množic odkrili protislovja.

Kaj to pomeni?

No, kot vemo, je protislovje trditev, ki jo je mogoče dokazati in hkrati ovreči. Če torej poenostavim, v naivni teoriji množic se je dalo dokazati, da je 0 različno od 1, pa tudi, da je 0 enako 1! Zato pravimo, da je bila ta teorija protislovna.

Ampak protislovne teorije so vendar nesmiselne?

Seveda, s protislovnimi teorijami je mogoče dokazati čisto vse. Takšne teorije zato nimajo spoznavne vrednosti, saj je namen sleherne teorije, da pojasni, kaj v nekem delu naše stvarnosti je res in kaj ne. Ker torej protislovne teorije ne služijo ničemur, jih je treba bodisi popraviti bodisi zavreči. Tudi naivno teorijo množic so poskušali popraviti. Kmalu po letu 1900 so nastale razne šole, ki so predlagale vsaka svoje popravke.

Kakšne, denimo?

Za nas je pomembna šola, imenovana formalizem. Ta je v 20. letih predlagala način, ki bi omogočil povsem mehanično razvijanje matematike. Povedano drugače: dokazovanje v matematiki bi bilo le mehanično manipuliranje s simboli! Ker človeku pri tem skoraj ne bi bilo treba razmišljati, bi se zmanjšala nevarnost napak, ki izvirajo iz njegovih miselnih zmot. In če bi zamisel formalistov uspela, v matematiki ne bi potrebovali ne navdiha ne ustvarjalnosti, zadoščala bi zgolj sistematičnost in potrpljenje.

No, takšnega matematičnega raja bi se marsikdo najbrž celo razveselil?

Najbrž res, a da bi takšen raj uresničili, bi bilo najprej treba izpolniti štiri temeljne pogoje; definiral jih je oče formalizma, nemški matematik David Hilbert. Formalisti so zato začeli razmišljati, kako bi izpolnili te pogoje. Toda njihove upe je leta 1931 pokopal avstrijski matematik Kurt Gödel, ko je dokazal, da dva od njih sploh nista uresničljiva. K sreči pa je eden od teh pogojev ostal neprizadet. Ta je zahteval, da se reši t. i. Entscheidungsproblem, to je, da se sestavi algoritem, ki bo za poljubno matematično formulo, torej trditev, ugotovil, ali je dokazljiva ali ni. Entscheidungsproblem je za našo zgodbo o teoriji izračunljivosti ključen, ker je v takratno dogajanje vpletel pojem algoritma.

Izraz algoritem razumemo kot postopek za reševanje danega problema, torej kot nekakšen recept. S tem pa smo verjetno že blizu računalnikom?

Drži, algoritem je recept, podobno kot recept za potico, le da se njegovi ukazi ne nanašajo na peko, ampak na računanje. Algoritmu moramo le zvesto slediti, natančno izvajati njegove ukaze, pa nas bo privedel do rešitve problema. To je bila intuitivna definicija pojma algoritma. Da pa bi rešili Entscheidungsproblem, je bilo treba poiskati še strogo definicijo, ki bi pojem algoritma – in tudi računanja – opisala v jeziku matematike. Takšni definiciji danes rečemo računski model. Znanstveniki so se torej proti koncu 20. let podali v lov za računskim modelom. Tako se je rodila teorija izračunljivosti. Za računalništvo pa bi lahko rekli, da je bilo takrat šele spočeto. Kajti v tistem času seveda še ni bilo računalnikov; pravzaprav si nihče ni niti mislil, da bi kaj takega sploh lahko obstajalo.

Kako uspešno pa je bilo iskanje računskega modela?

Kmalu je bilo predlaganih nekaj povsem različnih računskih modelov. A se je hitro pokazalo, da so si med seboj dokaj enakovredni – pač v smislu, da kar zmore eden, zmorejo tudi ostali. To je bilo znamenje, da je bilo iskanje stroge definicije pojma algoritma verjetno uspešno. Če povem bolj učeno: domnevali so, in še danes domnevamo, da je bil intuitivni pojem algoritma ustrezno formaliziran. Ta domneva, imenovana Church-Turingova teza, je bila prelomna, ker je na stežaj odprla vrata strogi, matematični obravnavi dotlej nejasnih, intuitivnih pojmov, kakršni so algoritem, računanje in reševanje računskih problemov.

Torej je prav strogo matematično raziskovanje privedlo do odkritja računalnika?

Tako je. Eden od predlaganih računskih modelov se je poleg drugega odlikoval po svoji naravnosti. To je bil tako imenovani Turingov stroj (TS), ki si ga je leta 1936 zamislil angleški matematik Alan Turing. To ni bil stvaren stroj, ampak nekaj, kar lahko narišemo na papirju in si zgolj predstavljamo, kako bi delovalo v praksi. Poleg tega si je Turing zamislil še prav poseben stroj, danes imenovan univerzalni Turingov stroj (UTS), ki je zmogel oponašati oziroma simulirati delovanje kateregakoli drugega TS. To pa je pomenilo, da bi UTS lahko rešil vsak problem, ki je rešljiv s kakim TS.

Seveda je tudi univerzalni Turingov stroj živel le na papirju. Turing se je dobro zavedal, da bi, če bi ga komu v resnici uspelo sestaviti kot stvaren stroj, z njim lahko reševali katerikoli računski problem. Tudi sam se je lotil sestavljanja takšnega stroja, a je moral delo med drugo svetovno vojno prekiniti; v Bletchley Parku je namreč vodil skupino za dešifriranje sporočil nemške Enigme. Na srečo pa so, bolj ali manj po zgledu UTS, tak stroj začeli sestavljati še drugje po svetu, tudi v ZDA. Tako so v prvi polovici 40. let sestavili nekaj takšnih strojev. Poimenovali so jih računalniki (computers) – in šele takrat se je računalništvo tudi rodilo. Skoraj vsi današnji računalniki so njihovi potomci.

A tudi danes računalniki še ne morejo rešiti vsakega računskega problema?

Žal ne. Teorija izračunljivosti je namreč na raznih področjih znanosti – od biologije in fizike do računalništva in matematike – odkrila probleme, ki so nerešljivi.

Kaj natanko pomeni, da problem ni rešljiv?

Pravimo, da je neki problem nerešljiv, če ni algoritma, ki bi lahko rešil vsak konkreten primerek tega problema. Če za reševanje takšnega problema uporabimo še tako izpopolnjen in domišljen algoritem, bo zagotovo odpovedal pri reševanju katerega od konkretnih primerkov problema. To je dobro vedeti, še posebej kadar je tak problem sestavni del zelo pomembne naloge – na primer upravljanja jedrske elektrarne.

Ugotavljanje nerešljivosti pa je koristno še drugače: če namreč za neki problem ugotovimo, da je nerešljiv, lahko prihranimo čas, energijo in denar množici vrhunskih raziskovalcev, da ne iščejo nečesa, kar sploh ne obstaja – namreč algoritem za ta problem.

Nerešljivih problemov torej ni mogoče rešiti niti načeloma – tudi če bi dali računalnikom za računanje neomejeno veliko časa in prostora?

Tako je. V praksi pa je še ena ovira. Poznamo namreč tudi probleme, ki so sicer rešljivi, a bi bilo računanje rešitev predolgotrajno. Nemalokrat bi se zavleklo v stoletja, tisočletja ali celo dlje. Zato pravimo, da so takšni problemi neobvladljivi.

Lahko omenite kakšnega?

Naj omenim tri. Kako, denimo, razdeliti kup krompirja na dva popolnoma enako težka kupa? Ali: na najmanj koliko zgoščenk lahko zapišemo dano množico skladb? Ali pa: v kakšnem vrstnem redu naj pismonoša obišče vse prejemnike pošte, da bo tisti dan naredil najkrajši možni obhod?

Pa teorija izračunljivosti proučuje tudi takšne neobvladljive probleme?

Seveda, in prav to proučevanje je izjemno pomembno za vsakdanje življenje. Poznamo namreč že na tisoče pomembnih praktičnih problemov, imenovanih NP-polni problemi; ti so sicer rešljivi, vendar domnevamo, da so neobvladljivi. To pomeni, da nobenega ne znamo rešiti v sprejemljivem času, dokaza, da to sploh ni možno, pa tudi (še) ni. A zanimivo je, da če bi znali rešiti enega samega od njih, bi avtomatično znali rešiti vse! To pomeni, da so NP-polni problemi med seboj solidarni po načelu »vsi ali nobeden«. Prav vprašanje, ali velja »vsi« ali »nobeden«, je trenutno najpomembnejše vprašanje teoretičnega računalništva; običajno ga zapišemo v obliki »Ali je P=NP?«.

Pravite, da ima tovrstni študij teorije izračunljivosti tudi praktični pomen?

O, seveda ga ima. Kajti če bi ugotovili, da je odgovor na vprašanje »Ali je P=NP?« pritrdilen, bi bile posledice velikanske. Sodobna kriptografija namreč sloni na domnevi, da v sprejemljivem času ni mogoče poiskati dveh števil, katerih zmnožek je enak tretjemu, vnaprej danemu in zelo velikemu številu. Če bi bil torej odgovor da , bi vedeli, da je takšni števili mogoče poiskati v sprejemljivem času. To pa bi dramatično ogrozilo varnost komunikacij v bančnih, vojaških in drugih sistemih. Seveda bi se vse to zgodilo tudi v primeru, da bi le za enega od tisočev NP-polnih problemov našli dovolj hiter algoritem – pač zaradi omenjene »solidarnosti«.

Omenili ste, da se zadnje čase v to dogajanje vključuje tudi kvantna fizika.

Tako je. Stopnja integracije v elektronskih čipih se namreč že dolgo vztrajno povečuje. Na čip lahko vsadimo čedalje več komponent, ker so pač čedalje manjše. V resnici postajajo že tako majhne, da bo kmalu treba upoštevati tudi kvantnomehanske pojave. Zakoni kvantne mehanike pa se zelo razlikujejo od zakonov, ki veljajo v »našem« makrosvetu, svetu večjih razdalj.

Kvantnomehanske zakone so tako v zadnjem desetletju poskušali uporabiti tudi v algoritmih; zato jim rečemo kvantni algoritmi. In kaže, da bi bili nekateri kvantni algoritmi zmožni rešiti neobvladljive probleme v sprejemljivem času! Na primer, omenjeni problem faktorizacije števil bi lahko rešili s kvantnim algoritmom v sprejemljivem času. Vendar še ni jasno, ali bo mogoče sestaviti tudi stvaren kvantni računalnik, ki bi izvajal kvantne algoritme. Glede varnosti torej panike še ni, na določeno nelagodje pa verjetno kažejo že potekajoče raziskave v kvantni kriptografiji. Ta namreč raziskuje, kako sestaviti kvantne algoritme, ki bi varovali komunikacijo, tudi če bi v prihodnosti vendarle dobili tudi kvantne računalnike.

Strogo matematično razmišljanje je torej privedlo do računalnikov. Bi rekli, da ste tudi sami po razmišljanju predvsem matematik?

Po srcu sem vsekakor matematik, po formalni izobrazbi pa računalnikar.

Kaj bi torej svetovali srednješolcu, ki ga vsa ta vznemirljiva tematika privlači – naj gre študirat računalništvo ali matematiko?

Eno ali drugo, ni važno. Pomembno je le, da ga snov zanima in da se je zanjo pripravljen potruditi in vztrajno delati; potem so mu odprta vsa vrata. Sicer pa naša fakulteta in Fakulteta za matematiko in fiziko UL organizirata skupni interdisciplinarni študij računalništva in matematike, imenovan IŠRM. Tam opremimo študente tudi s tovrstnim znanjem.