Omejitve računalnikov

V realnem svetu, kjer se srečujemo z realnimi problemi, obstajajo tudi problemi, katerih računalnik (in noben drug) ne bo sposoben rešiti in problemi, katerih zaradi omejenega časa in velikosti pomnilnika (prevelika časovna in prostorska zahtevnost), računalnik ne bo rešil (čeprav je problem rešljiv).

Neizračunljivi problemi

Nek problem je nerešljiv, če za njega ni mogoče zapisati algoritma. Zgolj naše neznanje še ne pomeni, da problem ni rešljiv. Ker je reševanje neizračunljivih problemov nesmiselno, se moramo omejiti na izračunljive. Edina stvar po kateri lahko prepoznamo izračunljiv problem je, da za njega obstaja algoritem. Eden izmed bolj znanih problemov je "problem ustavljanja"

Problem ustavljanja

Označimo z (M,x) nek Turingov stroj M, ki ima na začetku na traku zapisan vhodni podatek x. Rekli bomo da se (M,x) ustavi, če se stroj M, ki mu damo na vhod podatek x ustavi po končnem številu korakov. Naj bo fH(M,x) funkcija, ki je definirana za vse Turingove stroje in za poljuben vhodni podatek na naslednji način:

fH(M,x) = 1	če se (M,x) ustavi
fH(M,x) = 0	če se (M,x)  ne ustavi

Dokazati je mogoče, da funkcija fH(M,x) ni izračunljiva. To pomeni, da ni mogoče narediti algoritma, s katerim bi lahko ugotavljali ali se bo pri poljubnih vhodnih podatkih nek poljuben Turingov stroj zaustavil. Kako je sploh mogoče dokazati, da je nek problem neizračunljiv? S pomočjo slavnega postopka diagonalizacije, s katerim je nemški matematik Georg Cantor v 19-stem stoletju dokazal, poleg drugega, da je množica vseh realnih števil večja od množice vseh celih števil. Vzemimo, da algoritem za problem ustavljanja, obstaja. Potem si lahko zamislimo neskoncno tabelo, v kateri so na eni osi vsi Turingovi stroji M, na drugi pa vsi možni vhodi x. V tabeli so vrednosti funkcije fH(M,x) (0 ali 1), ki jo da naš algoritem. Turing je nato z uporabo diagonalizacije dokazal, da vedno obstaja tudi Turingov stroj, ki ga v tabeli ni. To je v nasprotju z našo začetno predpostavko in dokaz, da algoritem ne more obstajati. Vedeti pa moramo, da neizračunljivost velja samo, če želimo narediti preizkusni program za vse možne programe. To pomeni, da je za nek določen program ali neko določeno množico programov problem morda mogoče rešiti.

Z večino danes znanih neizračunljivih problemov, med katerimi omenimo še problem polaganja ploščic ("tiling problem") in Postov korespondenčni problem (post correspodence problem), obstaja prevedba "problema ustavljanja" nanje. To pomeni, da kljub temu, da so problemi videti zelo različni, so ekvivalenti. Če bi obstajal algoritem za enega, bi lahko rešili vse druge. Obstajajo pa še bolj neizračunljivi problemi. Zanje je dokazano, da jih z algoritmom za problem ustavljanja ne bi mogli rešiti. V resnici obstajajo celi razredi neizračunljivih problemov, katerih neizračunljivost narašča od enega razreda do drugega.

Vse skupaj je videti zelo hudo, vendar na srečo ni tako. Problem ne izračunljivih problemov na vsakdanje računanje je manjši, kot bi pričakovali. Pri resničnih problemih se ne pojavljajo tako pogosto, poleg tega pa jih velikokrat lahko obidemo tako, da omejimo število možnih vhodov (ali kaj drugega) in jih spremenimo v izračunljive.

Takšne omejitve pogosto delamo tudi pri izračunljivih problemih, ker nas v to silijo realne razmere (omejen čas in pomnilnik). Posledica tega je, da se z neizračunljivimi problemi ukvarjajo zgolj teoretiki - večina uporabnikov računalnikov sploh ne ve zanje. Ljudje se veliko več ukvarjajo s problemi, ki so sicer izračunljivi, pa jih ni mogoče rešiti zaradi iz realnega sveta izhajajočih omejitev. Te probleme imenujemo neobvladljivi problemi.

Gor Sistemi Motorola 68XX Omejitve računalnikov Neobvladljivi problemi

SERŠ Maribor, Strokovna gimnazija, leto: 2004/05, avtor: Peter Mertelj