Teorija izračunljivosti

Za drugu upotrebu, pogledajte stranicu Teorija izračunljivosti (računarstvo).

U teorijskoj računarskoj nauci i matematici, teorija izračunljivosti je grana računarstva koja razmatra mogu li se i s kojom efikasnošću rešiti problemi koristeći računar. Polje je podeljeno u tri glavne grane: teoriju automata i jezike, teoriju izračunljivosti i teoriju kompleksnosti, s tim da sve grane izučavaju formalne modele računanja.

Umetnička reprezentacija Tjuringove mašine. Tjuringove mašine se često koriste kao teoretski modeli u računarstvu.

Kako bi rigorozno proučavali računanje, računarski naučnici koriste matematičke apstrakcije, modele računanja. Nekoliko je formulacija u upotrebi, ali najčešće ispitivana je Turingova mašina. Turingova mašina se može shvatiti kao lični računar opremljen memorijom beskonačnog kapaciteta, iako može memoriji pristupati u malim diskretnim delovima. Informatičari proučavaju Turingovu mašinu jer je ona jednostavna za formulaciju i može biti analizirana i korišćena u dokazivanju rezultata jer predstavlja ono što mnogi smatraju najmoćnijim mogućim „razumnim“ modelom računanja. Iako se zahtev za memorijom beskonačnog kapaciteta može shvatiti kao nefizikalan, za svaki stvarno rešen problem Turingovom mašinom korišćena memorija će uvek biti konačna, pa svaki problem koji reši Turingova mašina može rešiti i personalni računar sa dovoljno ugrađene memorije.

Grane

Teorija izračunljivosti

Teorija izračunljivosti se primarno bavi pitanjem je li problem uopšte rešiv na računaru. Problem zaustavljanja je jedan od najvažnijih rezultata u teoriji izračunljivosti, jer predstavlja primer konkretnog problema kojeg je i lako formulisati i nemoguće rešiti koristeći Turingovu mašinu. Veći je deo teorije izračunljivosti izgrađen oko rezultata problema zaustavljanja.

Još jedan važan korak u teoriji izračunljivosti je bila Rajsova teorema, koji navodi da je za sva netrivijalna svojstva parcijalnih funkcija, neizvesno da li Turingova mašina izračunava parcijalne funkcije sa tim svojstvom.

Teorija izračunljivosti je 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 nazvati teorijom izračunljivosti. Ne postoji stvarna razlika između dvaju polja.

Teorija kompleksnosti

Teorija kompleksnosti razmatra ne samo može li se problem uopšte rešiti na računaru, već i koliko efiksno može biti rešen. Dva glavna aspekta su posmatrana: 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 dati algoritam zahteva, istraživači izražavaju vreme i prostor zahtevan za rešavanje problema kao funkciju ulaznog problema. Na primer, 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 rešio ovaj problem, računar mora obaviti broj koraka koji raste linearno u odnosu na veličinu problema.

Kako bi pojednostavili ovaj problem, istraživači su prihvatili veliku O notaciju, koja dozvoljava poređenje funkcija na način koji osigurava da pojedinačni aspekti konstrukcije mašine ne moraju biti razmatrani, već samo asimptotsko ponašanje kako problemi postaju sve veći. Zato se u prethodnom primeru može reći da problem zahteva n koraka za rešavanje.

Možda najvažniji od svih otvorenih problema u računarstvu jeste pitanje mogu li određene široke klase problema označene kao NP biti efikasno rešene.

Druge formalne definicije računanja

Osim Turingove mašine, koriste se i drugi modeli računanja kao što su: lambda račun, kombinatorska logika, μ-rekurzivna funkcija, Markovljev algoritam, Registarska mašina, P′′,

Lambda račun

Računanje je početni lambda izraz (ili dva ako se želi odvojiti funkcija od njenog ulaza) plus konačni sled lambda termina, od kojih je svaki dedukovan 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 tačke Y u kombinatornoj logici ima normalnu formu, ali ne i u $\lambda$-računu). Kombinatorna je logika razvijena sa velikim ambicijama: razumevanje prirode paradoksa, činjenja osnovna matematike ekonomičnijima (konceptualno), te eliminisanje notacije varijabli (te tako osvetljavajući njihovu ulogu u matematici).

μ-rekurzivne funkcije

računanje je μ-rekurzivna funkcija, tj. njen definirajući sled, bilo koja ulazna vrednost/vrednosti te sled rekurzivnih funkcija koje se pojavljuju u definirajućem sledu sa ulazima i izlazima. Stoga, ako se u definirajućem sledu 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 sledu treba biti aplikacija osnovne funkcije ili slediti iz gornjih unosa koristeći kompoziciju funkcija, primitivnu rekurziju ili μ-rekurziju. Na primer, 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 vrednost rekurzivne funkcije primenjene na ulaze.

Markovljev algoritam

sistem za prepisivanje stringa koji koristi pravila slična gramatičkim kako bi delovao nad stringovima simbola.

Registarska mašina

je teoretski zanimljiva idealizacija računara. Postoji više varijanti. U većini od njih, svaki registar može da sadrži prirodni broj (neograničene veličine), dok su same instrukcije jednostavne (obično tek nekolicina njih), pa npr. postoje samo dekrementiranje (kombinovano sa uslovnim skokom) i inkrementiranje (i zaustavljanje). Nedostatak beskonačne (ili dinamički rastuće) spoljašnje memorije (poput one u Turingovim mašinama) se može švatiti kao zamena njene uloge tehnikama Gedelovog obrojavanja. Činjenica da svaki registar sadrži prirodni broj dopušta mogućnost predstavljanja složenih konstrukata (npr. niza, matrice itd.) odgovarajućim velikim prirodnim brojem - nejednoznačnost i predstavljanja i interpretiranja može biti uspostavljena na osnovama ovih tehnika zasnovanih na teoriji brojeva.

P′′

Poput Turingovih mašina, 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 mašina, za P′′ nije neophodno održavati različito stanje, jer svu funkcionalnost „sličnu memoriji” može pružiti samo traka. Umesto prepisivanja trenutnog simbola, može obaviti inkrementiranje modularnom aritmetikom nad njim. P′′ takođe poseduje par instrukcija za ciklus, ispitujući simbol praznine. Uprkos svojoj minimalističkoj prirodi, postao je roditeljski formalni jezik ostvarenog i (za zabavu) korištenog programskog jezika zvanog Brejnfak.

Kao dopuna opštih računskih modela, neki jednostavniji računski modeli su korisni za posebne, ograničene primene. Regularni izrazi, na primer, se koriste za specificiranje uzoraka stringa u mnogim kontekstima, od programske podrške za kancelarijsku produktivnost pa do programskih jezika. Drugi formalizam matematički istovetan regularnim izrazima, konačni automati, se koristi u dizajnu elektronskih krugova i pri rešavanju nekih problema. Kontekstno nezavisna gramatika se koristi prilikom specifikacije sintakse programskih jezika. Nedeterministički potisni automati su drugi formalizam istovetan kontekstno nezavisnim gramatikama. Primitivno rekurzivne funkcije su potklasa rekurzivnih funkcija.

Različiti modeli računanja imaju sposobnost obavljanja različitih zadataka. Jedan način merenja moći računskog modela jeste proučavanje klase formalnih jezika koje model može generisati - ovo vodi ka Čomskijevoj hijerarhiji jezika.

Literatura

• Davis, Martin (2004). The undecidable: Basic papers on undecidable propositions, unsolvable problems and computable functions (Dover Ed). Dover Publications. ISBN 978-0486432281. 
• Monk, Donald (1976). Mathematical Logic. Springer-Verlag. ISBN 9780387901701. 
• Hodges, Andrew (2012). Alan Turing: The Enigma (The Centenary Edition). Princeton University Press. ISBN 978-0-691-15564-7. 
• Sipser, Michael (2013). Introduction to the Theory of Computation 3rd. Cengage Learning. ISBN 978-1-133-18779-0. „central areas of the theory of computation: automata, computability, and complexity. (Page 1)” 
• Hein, James L. (1996). Theory of Computation. Sudbury, MA: Jones & Bartlett. ISBN 978-0-86720-497-1. .
• Hopcroft, John E., and Jeffrey D. Ullman: Introduction to Automata Theory, Languages, and Computation. 3rd ed Reading, MA:. . Addison-Wesley. 2006. ISBN 978-0-321-45536-9. .
• Taylor, R. Gregory: Models of Computation. New York: Oxford University Press, 1998.
• Hartley Rogers, Jr (1987). Theory of Recursive Functions and Effective Computability. MIT Press. ISBN 978-0-262-68052-3. .
• Linz, P. (2007). An introduction to formal language and automata. Narosa Publishing. ISBN 9788173197819. 
• Sipser, Michael (2013). Introduction to the Theory of Computation (3rd izd.). Cengage Learning. ISBN 978-1-133-18779-0. 
• Gurari, Eitan (1989). An Introduction to the Theory of Computation. Computer Science Press. ISBN 978-0-7167-8182-0. Arhivirano iz originala 7. 1. 2007. g. 
• Hein, James L. (1996). Theory of Computation. Sudbury, MA: Jones & Bartlett. ISBN 978-0-86720-497-1.  A gentle introduction to the field, appropriate for second-year undergraduate computer science students.
• Lewis, F. D. (2007). Essentials of theoretical computer science A textbook covering the topics of formal languages, automata and grammars. The emphasis appears to be on presenting an overview of the results and their applications rather than providing proofs of the results.
• Martin Davis, Ron Sigal, Elaine J. Weyuker. Computability, complexity, and languages: fundamentals of theoretical computer science (2nd изд.). Academic Press. 1994. ISBN 978-0-12-206382-4. . Covers a wider range of topics than most other introductory books, including program semantics and quantification theory. Aimed at graduate students.
• S. Barry Cooper (2004). Computability Theory. Chapman and Hall/CRC. ISBN 978-1-58488-237-4. .
• Carl H. Smith (1994). A recursive introduction to the theory of computation. Springer. ISBN 978-0-387-94332-9. . A shorter textbook suitable for graduate students in Computer Science.
• Epstein, Richard L.; Walter A. Carnielli (2000). Computability: Computable Functions, Logic, and the Foundations of Mathematics, with Computability: A Timeline (2nd ed.). Wadsworth/Thomson Learning. ISBN 978-0-534-54644-1. .

Spoljašnje veze

• Logika izračunljivosti
• Forbes D. Lewis, Theory of computation
• Theory of Computation at MIT
• Theory of Computation at Harvard
• Computability Logic - A theory of interactive computation. The main web source on this subject.