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 ispitivan jest 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 nefizikalnim, 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.