Promjene

Prijeđi na navigaciju Prijeđi na pretraživanje
m
bez sažetka
'''Teorija računanja''' je grana [[računarstoračunarstvo|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: [[teorija izračunljivosti (računarstvo)|teoriju izračunljivosti]] i [[računska teorija složenosti|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 [[model računanja|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.
3.196

uređivanja

Navigacijski izbornik