Teorija izračunljivosti (računarstvo)

U računarstvu, teorija izračunljivosti je grana teorije računanja koja proučava probleme koji su računski rješivi koristeći različite modele računanja.

Teorija se izračunljivosti razlikuje od povezane discipline računske teorije složenosti, koja se bavi pitanjem koliko se učinkovito problem može riješiti, mjesto je li uopće rješiv.

Uvod

Središnje pitanje računarstva jest ono ograničenja računarskih uređaja. Jedan pristup u odgovaranju ovog pitanja jest razumijevanje problema koje možemo riješiti uz pomoć računala. Suvremeni računarski uređaji često naizgled posjeduju beskonačan kapacitet za računanje, i lako je zamisliti da, uz dovoljnu količinu dostupnog vremena, možemo koristiti računala za rješavanje bilo kojeg problema. U drugu ruku, moguće je pokazati jasne granice mogućnosti računala, čak i uz dane proizvoljno velike računske resurse, za rješavanje naizgled jednostavnih problema. Problemi se formalno izražavaju kao problem odluke koji se sastoji od konstrukcije matematičke funkcije koja za svaki ulaz vraća ili 0 ili 1. Ukoliko je vrijednost funkcije za ulaz jednaka 0, tada je odgovor "ne", inače je odgovor "da".

Kako bi istražili ovo područje, računalni su znanstvenici izmislili teoriju automata koja se bavi problemima poput sljedećeg: za dani formalni jezik i string, je li string član tog jezika? Ovo je ponešto ezoteričan način postavljanja ovog pitanja, tako da primjer djeluje prosvjetljujuće. Taj se jezik može definirati kao npr. skup svih stringova znamenke čije predstavljaju prost broj. Pitanje je li ulazni string član ovog jezika je istovjetno pitanju je li broj koji string predstavlja prost broj. Slično, definira se jezik kao skup svih palindroma, kao skup svih stringova koji se sastoje samo od slova 'a'. U ovim primjerima, lako je vidjeti da je konstruiranje računala za rješavanje jednog problema u nekim slučajevima lakše nego u nekim drugima.

Ali u kojem je stvarnom smislu ova opservacija istinita? Može li se definirati formalni način u kojem se može shvatiti koliko je težak pojedini problem za rješavanje računalom? Cilj je teorije izračunljivosti i teorije automata da odgovori na ovo pitanje.

Formalni modeli računanja

Kako bi se odgovorilo na središnje pitanje teorije automata, potrebno je na formalni način definirati što je uopće automat. Postoji nekoliko korisnih modela automata. Neki od široko poznatih su:

Deterministički konačni automat: ili kraće DKA je jednostavno konačni automat, jednostavni model računanja. Stvarni računarski uređaji koji danas postoje se mogu modelirati kao konačni automati. Takav stroj posjeduje skup stanja, te skup prijelaza stanja koji djeluju u odnosu na ulazni tok. Određena su stanja definirana kao prihvatljiva. Ulazi tok se usmjerava u stroj jedan po jedan znak (simbol). Prijelazi stanja za trenutno stanje se uspoređuju sa ulaznim tokom, i ako postoji sparujući prijelaz stroj može ući u novo stanje. Ako je na kraju čitanja ulaznog toka stroj u prihvatljivom stanju, cijeli ulazni tok je prihvaćen.

Potisni automat: Sličan konačnom automatu, osim što ima još dostupan i stog izvršavanja, kojem se dozvoljava rast do proizvoljne veličine. Prijelazi stanja dodatno specificiraju dodaje li se simbol na stog, ili se skida simbol sa vrha stoga.

Turingov stroj: Također sličan konačnom automatu, osim što se ulaz nalazi na "traci" izvršavanja koju Turingov stroj može čitati, na koju može pisati, te pomicati svoju "glavu" za čitanje i pisanje naprijed i nazad. Traci je dozvoljen rast do proizvoljne veličine. Turingov je stroj sposoban obaviti složene izračune koji mogu proizvoljno dugo trajati. Ovo je možda najvažniji model računanja u računarstvu, jer simulira računanje u odsutnosti predefiniranih ograničenja resursa.

Višetračni Turingov stroj: U ovom slučaju može postojati više od jedne trake, čak štoviše - više od jedne glave po traci. Iznenađujuće je da bilo koje računanje koje može obaviti ovaj stroj također može obaviti i obični Turingov stroj, iako bi mu za to trebalo znatno više vremena odnosno veće zauzeće trake.

Moć automata

Imajući na umu ove računske modele, mogu se odrediti njihove granice. To jest, koje klase formalnih jezika oni prihvaćaju?

Moć konačnih automata

Računalni znanstvenici zovu bilo koji jezik kojeg prihvaća konačni automat regularni jezik. Zbog ograničenja o konačnom broju stanja u konačnom automatu, može se lako vidjeti da je za naći neregularni jezik potrebno konstruirati jezik koji bi zahtijevao beskonačan broj stanja.

Takav jezik je skup svih stringova koji se sastoje od slova 'a' i 'b' koji sadržavaju jednak broj slova 'a' i 'b'. Da bi se vidjelo da ovaj jezik ne može prepoznati konačni automat, neka se prvo pretpostavi da takav automat [math]\displaystyle{ M }[/math] postoji. [math]\displaystyle{ M }[/math] mora imati neki broj stanja [math]\displaystyle{ n }[/math]. Neka se sad razmotri string [math]\displaystyle{ x }[/math] koji se sastoji od [math]\displaystyle{ (n+1) }[/math] slova 'a' nakon kojih slijedi [math]\displaystyle{ (n+1) }[/math] slova 'b' po Dirichletovom principu. Nazovimo ovo stanje [math]\displaystyle{ S }[/math], i neka je [math]\displaystyle{ d }[/math] broj slova 'a' koje stroj čita kako bi došao od prvog pojavljivanja stanja [math]\displaystyle{ S }[/math] do nekog sljedećeg pojavljivanja tokom čitanja slijeda slova 'a'. Znamo da se, za drugog pojavljivanja stanja [math]\displaystyle{ S }[/math], može dodati dodatnih [math]\displaystyle{ d }[/math] (gdje je [math]\displaystyle{ d \gt 0 }[/math]) slova 'a' pri čemu će se opet biti u stanju [math]\displaystyle{ S }[/math]. Ovo znači da string od [math]\displaystyle{ (n+d+1) }[/math] slova 'a' mora završiti u istom stanju kao i string od [math]\displaystyle{ (n+1) }[/math] slova 'a'. Ovo implicira da ako stroj prihvaća string [math]\displaystyle{ x }[/math], tada također mora prihvaćati string od [math]\displaystyle{ (n+d+1) }[/math] slova 'a' nakon kojih slijedi [math]\displaystyle{ (n+1) }[/math] slova 'b', koji nije u jeziku stringova koji sadrže jednak broj slova 'a' i 'b'.

Iz ovoga slijedi da taj jezik ne može ispravno prihvatiti nijedan konačni automat, te on stoga nije regularni jezik. Općenitiji oblik ovoga rezultata se zove svojstvo napuhavanja za regularne jezike, i može biti korišteno za pokazivanje da široka klasa jezika ne može prihvaćena konačnim automatima.

Moć potisnih automata

Računalni znanstvenici definiraju jezik kojeg može prihvatiti potisni automat kao kontekstno neovisni jezik, koji može biti specificiran kontekstno neovisnom gramatikom. Jezik koji se sastoji od jednakog broja slova 'a' i 'b', za kojeg je pokazano da je neregularan, može odlučiti potisni automat. Također, općenito, potisni se automat može ponašati kao i obični konačni automat, tako da može odlučiti svaki regularni jezik. Ovaj model računanja je strogo jači od konačnih automata.

Međutim, ispostavlja se da postoje jezici koje ni potisni automati ne mogu odlučiti. Rezultat je sličan onome za regularne jezike, i ovdje neće biti u detalje raščlanjen. Također postoji svojstvo napuhavanja za kontekstno neovisne jezike. Primjer takvog jezika je skup prostih brojeva.

Moć Turingovih strojeva

Turingovi strojevi mogu odlučiti bilo koji kontekstno neovisni jezik, pored jezika neodlučivih konačnim automatima, kao što je jezik prostih brojeva. Stoga je to strogo moćniji model računanja.

Budući da Turingovi strojevi imaju mogućnost "spremanja" svoje ulazne trake, moguće je za Turingov stroj da radi dugo vremena na način koji nije moguć u ostalim, prethodno opisanim modelima računanja. Moguće je konstruirati Turingov stroj koji nikad neće stati za neke ulaze. Kaže se da Turingov stroj odlučuje jezik ako će s vremenom stati na sve ulaze i dati odgovor. Jezik koji tako može biti odlučen se zove rekurzivni jezik. Možemo nadalje opisati Turingove strojeve koji će s vremenom stati i dati odgovor za svaki ulaz u jeziku, ali koji mogu nikada ne stati za ulazne stringove koji nisu u jeziku. Takvi Turingovi strojevi mogu reći je li dani string u jeziku, ali se nikad sa sigurnošću ne može reći da dani string nije u jeziku, jer stroj može nikada ne stati u tom slučaju. Jezik koji prihvaća takav Turingov stroj se zove rekurzivno prebrojiv jezik.

Ispostavlja se da je Turingov stroj izuzetno moćan model automata. Na opće iznenađenje, svi pokušaji izmjene definicije Turingovog stroja u svrhu stvaranja moćnijeg stroja nisu polučili uspjeh. Na primjer, dodavanje dodatne trake Turingovom stroju, i na taj mu način dajući dvodimenzionalnu (ili tri ili bilo koji drugi broj traka, odnosno dimenzija) površinu na kojoj može raditi može biti simulirano Turingovim strojem sa osnovnom, jednodimenzionalnom trakom. Ovi modeli stoga nisu moćniji. Ustvari, posljedica Church-Turingove teze jest da ne postoji razumni model računanja koji može odlučiti jezike koje ne može odlučiti Turingov stroj.

Pitanje koje se postavlja jest: postoje li jezici koji su nerekurzivni, a i rekurzivno prebrojivi? Također, nadalje, postoje li jezici koji nisu ni rekurzivno prebrojivi?

Problem zaustavljanja

Podrobniji članak o temi: Problem zaustavljanja

Problem zaustavljanja je jedan od najpoznatijih problema u računarstvu, jer ima duboke implikacije u teoriji izračunljivosti i na način na koji se računala koriste u svakodnevnom životu. Problem se može iskazati na sljedeći način:

Za dani opis Turingovog stroja i njegov početni ulaz, odredi staje li (odnosno završava) program, prilikom izvršavanja za taj ulaz. Alternativa je da nikad ne staje, zauvijek se izvršujući.

Ovdje se ne postavlja jednostavno pitanje o prostom broju ili palindromu, već općenitije - pita se Turingov stroj da odgovori na pitanje o drugom Turingovom stroju. Može se pokazati (vidi glavni članak: Problem zaustavljanja) da nije moguće konstruirati Turingov stroj koji općenito može odgovoriti na ovo pitanje.

Drugim riječima, jedini općenit način za znati hoće li dani program stati za pojedini ulaz u svim slučajevima jest izvršiti ga i vidjeti staje li. Ako staje, tada se zna da staje. U drugu ruku, ako ne staje, tada se nikad ne može znati hoće li s vremenom stati. Jezik koji se sastoji od svih opisa Turingovih strojeva uparnih sa svim mogućim ulazima za koje Turingovi strojevi s vremenom staju nije rekurzivan. Problem zaustavljanja se stoga zove neizračunljiv ili neodlučiv.

Proširenje problema zaustavljanja se zove Riceov teorem, koji iskazuje da je općenito neodlučivo posjeduje li dani jezik neko specifično netrivijalno svojstvo.

Iznad rekurzivnih jezika

Problem je zaustavljanja lako riješiti ukoliko se dopusti Turingovom stroju koji odlučuje da se zauvijek izvršava kad mu je dan ulaz koji predstavljanja Turingov stroj koji sam ne staje. Jezik zaustavljanja je stoga rekurzivno prebrojiv. Međutim, moguće je konstruirati i jezike koji nisu rekurzivno prebrojivi.

Jednostavan je primjer takvog jezika komplement jezika zaustavljanja, to jest jezik koji se sastoji od svih Turingovih strojeva uparenih sa ulaznim stringovima pri čemu Turingov stroj ne staje za svoj ulaz. Da bi se vidjelo da ovaj jezik nije rekurzivno prebrojiv, neka se zamisli konstrukcija Turingovog stroja [math]\displaystyle{ M }[/math] koji može dati definitivan odgovor za sve takve Turingove strojeve, ali i da može nikad ne stati za Turingov stroj koji sam nikad ne staje. Tad se može konstruirati drugi Turingov stroj, [math]\displaystyle{ M' }[/math], koji može simulirati djelovanje ovog stroja, te također i izravno simulirati izvršavanje stroja danog kao ulaz, na način da preklapa izvršavanje ovih dvaju prgrama. Budući da će izravna simulacija s vremenom stati ako program koji se simulira s vremenom staje, i jer će po pretpostavci simulacija [math]\displaystyle{ M }[/math] s vremenom stati ako ulazni program nikad ne staje, zna se da će u [math]\displaystyle{ M' }[/math] s vremenom jedna od paralelno izvršavajućih inačica stati. [math]\displaystyle{ M' }[/math] stoga odlučuje problem zaustavljanja. Prethodno je pokazano, međutim, da je problem zaustavljanja neodlučiv. Ovdje se dolazi do protuslovlja, te je stoga pokazano da je pretpostavka da [math]\displaystyle{ M }[/math] postoji pogrešna. Komplement jezika zaustavljanja nije rekurzivno prebrojiv.

Modeli zasnovani na konkurentnosti

Razvijeni su brojni računski modeli zasnovani na konkurentosti, uključujući paralelni stroj s izravnim pristupom te Petrijeve mreže. Ovi modeli konkurentnog računanja još uvijek ne implementiraju neku matematičku funkciju koja ne može biti implementirana Turingovim strojevima.

Nerazumni modeli računanja

Church-Turingova teza konjekturira da ne postoji razuman model računanja koji može izračunati više matematičkih funkcija od Turingovog stroja. U ovoj će se sekciji istražiti neki od "nerazumnih" ideja za računske modele koji narušavaju ovu konjekturu. Računalni su znanstvenici zamislili mnoge inačice hiperračunala.

Beskonačno izvršavanje

Neka se pretpostavi postojanje stroja u kojem svaki korak računanja zahtijeva polovicu vremena prethodnog koraka. Ako se količina vremena potrebna za prvi korak normalizira na jediničnu vremensku jedinicu, izvršavanje bi zahtijevalo

[math]\displaystyle{ 1 + {1 \over 2} + {1 \over 4} + \cdots }[/math]

vremena. Ovaj beskonačni red konvergira ka 2 vremenske jedinice, što znači da ovaj Turingov stroj može izvršiti beskonačno izvršavanje u 2 vremenske jedinice. Ovaj je stroj u stanju odlučiti izravnim simuliranjem izvršavanja stroja u pitanju.

Strojevi proročišta

Podrobniji članak o temi: Stroj proročište

Takozvani strojevi proročišta imaju pristup različitim "proročištima" koji pružaju rješenja na pojedine neodlučive probleme. Na primjer, Turingov stroj može imati "proročište za zaustavljanje" koje odmah odgovara staje li ikada dani Turingov stroj za dani ulaz. Ovi su strojevi središnja tema proučavajna u teoriji rekurzije

Granice hiperračunanja

Čak i ovi strojevi, koji naizgled predstavljaju zamišljene granice automata, imaju svoja ograničenja. Iako svaki od njih može riješiti problem zaustavljanja za Turingov stroj, oni ne mogu riješiti svoje vlastite inačice problema zaustavljanja. Na primjer, stroj proročište ne može odgovoriti na pitanje staje li ikada dani stroj proročište.

Povijest teorije izračunljivosti

Lambda račun, važna preteča formalne teorije izračunljivosti, su razvili Alonzo Church i Stephen Cole Kleene. Alan Turing je najčešće smatran ocem suvremenog računarstva, te je postavio mnoge temelje teorija izračunljivosti i složenosti, uključujući prvi opis Turingovog stroja (u [1], 1936.) kao i mnoge rane rezultate od velike važnosti.

Vidi još

Izvori

Michael Sipser (1997). Introduction to the Theory of Computation. PWS Publishing. ISBN 0-534-94728-X Drugi dio: Computability Theory, poglavlja 3–6, str. 123–222.

Christos Papadimitriou (1993). Computational Complexity (1st edition ed.). Addison Wesley. ISBN 0-201-53082-1 Poglavlje 3: Computability, str. 57–70.

Nedovršeni članak Teorija izračunljivosti (računarstvo) koji govori o računarstvu treba dopuniti. Dopunite ga prema pravilima uređivanja Hrvatske internetske enciklopedije.