Teoria de la computació
branca de les matemàtiques que estudia problemes de decidibilitat / From Wikipedia, the free encyclopedia
La teoria de la computació és una ciència, en particular una branca de la matemàtica i de la computació que tracta de quins problemes es poden resoldre en un model de càlcul, mitjançant un algorisme, de quina manera es poden resoldre de manera eficient o en quin grau (per exemple, les solucions aproximades enfront de les precises). Dit d'una altra manera, dés la branca que estudia problemes de decidibilitat.[1] El camp es divideix en tres grans branques: teoria dels autòmats i llenguatges formals, teoria de la computabilitat i teoria de la complexitat computacional, que es relacionen amb la pregunta: "Quines són les capacitats i limitacions fonamentals dels ordinadors?".[2]
Per tal de dur a terme un estudi rigorós de la computació, els informàtics treballen amb una abstracció matemàtica dels ordinadors anomenada model de computació. Hi ha diversos models en ús, però el més freqüentment examinat és la màquina de Turing.[3] perquè és senzilla de formular, es pot analitzar i utilitzar per demostrar resultats i perquè representa el que molts consideren el model de càlcul "raonable" més potent possible.[4] Podria semblar que la capacitat de memòria potencialment infinita és un atribut irrealitzable, però qualsevol problema resolt per una màquina de Turing sempre requerirà només una quantitat finita de memòria.[5]