Inačica od 24. travnja 2007. u 11:16 uredi Ivan Štambuk (razgovor \| doprinosi) 3.196 edits m sitno ← Starija izmjena		Inačica od 24. travnja 2007. u 11:17 uredi ukloni ovu izmjenu Ivan Štambuk (razgovor \| doprinosi) 3.196 edits mNema sažetka uređivanja Novija izmjena →
Redak 1: '''Teorija računanja''' je grana [[~~računarsto~~rač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.

Teorija računanja: razlika između inačica