Teorija računanja

Teorija računanja je grana računarstva koja razmatra mogu li se i s kojom učinkovitošću riješiti problemi koristeći računalo. Polje je podijeljeno u dvije glavne grane: teoriju izračunljivosti i teoriju složenosti, s tim da obje grane barataju formalnim modelima računanja.

Kako bi rigorozno proučavali računanje, računalni znanstvenici barataju matematičkim apstrakcijama računala zvanim modeli računanja. Nekoliko je formulacija u uporabi, ali najčešće ispitivani je Turingov stroj. Turingov se stroj može shvatiti kao osobno računalo opremljeno memorijom beskonačnog kapaciteta, iako može memoriji pristupati u malim diskretnim dijelovima. Računalni znanstvenici proučavaju Turingov stroj jer ga je jednostavno formulirati, jer može biti analiziran i korišten u dokazivanju rezultata, i jer predstavlja ono što mnogi smatraju najmoćnijim mogućim "razumnim" modelom računanja. Iako se zahtijev za memorijom beskonačnog kapaciteta može shvatiti kao nefizikalan, za svaki stvarno riješen problem Turingovim strojem korištena memorija će uvijek biti konačna, pa svaki problem koji riješi Turingov stroj može riješiti i osobno računalo sa dovoljno ugrađene memorije.

Teorija izračunljivosti

Podrobniji članak o temi: Teorija izračunljivosti (računarstvo)

Teorija izračunljivosti se primarno bavi pitanjem je li problem uopće rješiv na računalu. Problem zaustavljanja je jedan od najvažnijih rezultata u teoriji izračunljivosti, jer predstavlja primjer konkretnog problema kojeg je i lako formulirati i nemoguće riješiti koristeći Turingov stroj. Veći je dio teorije izračunljivosti izgrađen oko rezultata problema zaustavljanja.

Teorija je izračunljivosti usko vezana sa granom matematičke logike zvanom teorija rekurzije, koja otklanja ograničenje proučavanja samo modela računanja koji su bliski onim fizikalno ostvarivima. Mnogi matematičari i računski teoretičari koji proučavaju teoriju rekurzije će je naslovljavati kao teoriju izračunljivosti. Ne postoji stvarna razlika između dvaju polja osim u tome ima li sam istraživač koji se bavi poljem ured u odsjeku za računarstvo ili matematiku.

Teorija složenosti

Podrobniji članak o temi: Računska teorija složenosti

Teorija složenosti razmatra ne samo može li se problem uopće riješiti na računalu, već i koliko učinkovito može biti riješen. Dva glavna aspekta su promatrana: vremenska složenost i prostorna složenost, koji respektivno predstavljaju broj koraka potreban da se računanje obavi, te količinu memorije potrebnu za obavljanje računanja.

Kako bi analizirali koliko vremena i prostora dani algoritam zahtijeva, računalni znanstvenici izražavaju vrijeme i prostor zahtijevan za rješavanje problema kao funkciju ulaznog problema. Na primjer, pronalaženje nekog pojedinog broja u dugoj listi brojeva postaje sve teže kako ta lista raste. Ako kažemo da postoji $n$ brojeva u listi, tada, ukoliko lista nije predsortirana ili na neki način indeksirana, moramo ispitati svaki broj kako bismo pronašli broj koji tražimo. Stoga kažemo da, kako bi riješio ovaj problem, računalo mora obaviti broj koraka koji raste linearno u veličini problema.

Kako bi pojednostavili ovaj problem, računalni su znanstvenici prihvatili veliko O notaciju, koja dozvoljava usporedbu funkcija na način koji osigurava da pojedinačni aspekti konstrukcije stroja ne moraju biti razmatrani, već samo asimptotsko ponašanje kako problemi postaju sve veći. Stoga se u prethodnom primjeru može reći da problem zahtijeva $O(n)$ koraka za rješavanje.

Možda najvažniji od svih otvorenih problema u računarstvu jest pitanje mogu li određene široke klase problema označene kao NP biti učinkovito riješene. O ovome se više raspravlja u članku klase složenosti P i NP.

Druge formalne definicije računanja

Osim Turingovog stroja, drugi istovjetni (vidi: Church-Turingova teza) modeli računanja su u uporabi.

lambda račun: Računanje je početni lambda izraz (ili dva ako se želi odvojiti funkcija od njenog ulaza) plus konačni slijed lambda termina, od kojih je svaki deduciran iz prethodnog aplikacijom beta redukcije.

kombinatorna logika: je koncept koji ima mnogo sličnosti sa $\lambda$ -računom, ali postoje i važne razlike (npr. kombinator fiksne točke Y u kombinatornoj logici ima normalnu formu, ali ne i u $\lambda$ -računu). Kombinatorna je logika razvijena sa velikim ambicijama: razumijevanje prirode paradoksa, činjenja osnovna matematike ekonomičnijima (konceptualno), te eliminiranje notacije varijabli (te tako osvjetljavajući njihovu ulogu u matematici).

μ-rekurzivne funkcije: računanje je μ-rekurzivna funkcija, tj. njen definirajući slijed, bilo koja ulazna vrijednost/vrijednosti te slijed rekurzivnih funkcija koje se pojavljuju u definirajućem slijedu sa ulazima i izlazima. Stoga, ako se u definirajućem slijedu rekurzivne funkcije $f(x)$ pojavljuju $g(x)$ i $h(x,y)$ , tada se mogu pojaviti termini oblika 'g(5)=7' ili 'h(3,2)=10'. Svaki unos u ovom slijedu treba biti aplikacija osnovne funkcije ili slijediti iz gornjih unosa koristeći kompoziciju funkcija, primitivnu rekurziju ili μ-rekurziju. Na primjer, ako je $f(x)=h(x,g(x))$ , tada da bi se pojavio 'f(5)=3', gore se moraju pojaviti termini poput 'g(5)=6' i 'h(3,6)=3'. Računanje terminira samo ako konačni termin daje vrijednost rekurzivne funkcije primijenjene na ulaze.

Markovljev algoritam: sustav za prepisivanje stringa koji koristi pravila slična gramatičkim kako bi djelovao nad stringovima simbola.

Registarski stroj: je teoretski zanimljiva idealizacija računala. Postoji više varijanti. U većini od njih, svaki registar može sadržavati prirodni broj (neograničene veličine), dok su same instrukcije jednostavne (obično tek nekolicina njih), pa npr. postoje samo dekrementiranje (kombinirano sa uvjetnim skokom) i inkrementiranje (i zaustavljanje). Nedostatak beskonačne (ili dinamički rastuće) vanjske memorije (poput one u Turingovim strojevima) se može shvatiti kao zamjena njene uloge tehnikama Gödelovog obrojčavanja: činjenica da svaki registar sadrži prirodni broj dopušta mogućnost predstavljanja složenih konstrukata (npr. niza, matrice itd.) odgovarajuće velikim prirodnim brojem - nejednoznačnost i predstavljanja i interpretiranja može biti uspostavljena na osnovama ovih tehnika zasnovanih na teoriji brojeva.

P′′: Poput Turingovih strojeva, P′′ koristi beskonačnu traku simbola (bez slučajnog pristupa) i poprilično minimalistički skup instrukcija. Ali ove su instrukcije vrlo različite, te stoga, za razliku od Turingovih strojeva, P′′ me treba održavati različito stanje, jer svu funkcionalnost "sličnu memoriji" može pružiti samo traka. Umjesto prepisivanja trenutnog simbola, može obaviti inkrementiranje modularnom aritmetikom nad njim. P′′ također posjeduje par instrukcija za ciklus, ispitujući simbol praznine. Unatoč svojoj minimalističkoj prirodi, postao je roditeljski formalni jezik ostvarenog i (za zabavu) korištenog programskog jezika zvanog Brainfuck.

Kao dodatak općenitim računskim modelima, neki jednostavniji računski modeli su korisni za posebne, ograničene primjene. Regularni izrazi, na primjer, se koriste za specificiranje uzoraka stringa u mnogim kontekstima, od programske podrške za uredsku produktivnost pa do programskih jezika. Drugi formalizam matematički istovjetan regularnim izrazima, konačni automati, se koristi u dizajnu elektroničkih krugova i pri rješavanju nekih problema. Kontekstno neovisne gramatike se rabe prilikom specifikacije sintakse programskih jezika. Nedeterministički potisni automati su drugi formalizam istovjetan kontekstno neovisnim gramatikama. Primitivno rekurzivne funkcije su potklasa rekurzivnih funkcija.

Različiti modeli računanja imaju sposobnost obavljanja različitih zadataka. Jedan način mjerenja moći računskog modela jest proučavanje klase formalnih jezika koje model može generirati - ovo vodi ka Chomskyjevoj hijerarhiji jezika.

Daljnje čitanje

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

Eitan Gurari (1989). An Introduction to the Theory of Computation. Computer Science Press. ISBN 0-7167-8182-4 Besplatna je verzija također dostupna na: http://www.cse.ohio-state.edu/~gurari/theory-bk/theory-bk.html

Hein, James L: Theory of Computation. Sudbury, MA: Jones & Bartlett, 1996. ISBN 978-0867204971 Nježni uvod u polje, prikladno za studente računarstva druge godine.
Hopcroft, John E., and Jeffrey D. Ullman: Introduction to Automata Theory, Languages, and Computation. 3rd ed Reading, MA: Addison-Wesley, 2006. ISBN 978-0321455369 Jedna od standardnih referenci u polju.
Taylor, R. Gregory: Models of Computation. New York: Oxford University Press, 1998. Neobično čitljiv udžbenik, prikladan za studente viših godina ili postdiplomske studente.
Hartley Rogers, Jr, Theory of Recursive Functions and Effective Computability, MIT Press, 1987, ISBN 0-262-68052-1
Logika izračunljivost: Teorija interaktivnog računanja. Glavi izvor na webu o ovoj temi.
[1] Dobar udžbenik u PDF formatu Forbesa D. Lewisa, koji pokriva teme formalnih jezika, automata i gramatika. Naglasak je više na predstavljanju pregleda rezultata i njihovim primjenama, radije nego na pružanju dokaza.