Usuari:Mcapdevila/Teoria de la computació

La teoria de la computació és una ciència, en particular una branca de la matemàtica i de la computació que centra el seu interès en l'estudi i definició formal dels còmputs. Rep el nom de còmput l'obtenció d'una solució o resultat (generalment en el sentit matemàtic/aritmètic del terme), a partir de certs dades o entrades utilitzant per a això un procés o algorisme.

Branques

La teoria de la computació té diverses branques pròpies, entre elles:

• La Teoria dels llenguatges i gramàtiques formals, que és l'estudi i processament de llenguatges artificials, a través de la utilització de models simplificats de còmput, com són les autòmats finits i els autòmats amb pila.
• La complexitat, o l'estudi de la quantitat de temps i d'espai en memòria que pren l'execució d'un còmput donat.
• La Teoria de la computabilitat, o l'estudi i determinació de la classe de problemes que poden ser resolts en una màquina de Turing.

Teoria d'autòmats

Article principal: Teoria d'autòmats

Aquesta teoria proveeix models matemàtics que formalitzen el concepte de ordinador o algorisme de manera prou simplificada i general perquè es puguin analitzar les seves capacitats i limitacions. Alguns d'aquests models tenen un paper central en diverses aplicacions de les ciències de la computació, incloent processament de text, compilador és, disseny de maquinari i intel·ligència artificial.

Els tres principals models són els autòmats finits , autòmats amb pila i màquines de Turing , cadascun amb les seves variants deterministes i no deterministes. Els autòmats finits són bons models d'ordinadors que tenen una quantitat limitada de memòria, els autòmats amb pila modelen els que tenen gran quantitat de memòria però que només poden manipular a manera d'pila (l'última dada emmagatzemat és el següent llegit), i les màquines de Turing modelen les computadores que tenen una gran quantitat de memòria emmagatzemada en una cinta. Aquests autòmats estan estretament relacionats amb la teoria de llenguatges formals, cada autòmat és equivalent a una gramàtica formal, el que permet reinterpretar la jerarquia de Chomsky en termes d'autòmats.

Existeixen molts altres tipus d'autòmats com les màquines d'accés aleatori, autòmats cel·lulars, màquines àbac i les màquines d'estat abstracte, però en tots els casos s'ha mostrat que aquests models no són més generals que la màquina de Turing, ja que la màquina de Turing té la capacitat de simular cada un d'aquests autòmats. Això dóna lloc a que es pensi en la màquina de Turing com el model universal d'ordinador.

Teoria de la computabilitat

Article principal: Teoria de la computabilitat

Aquesta teoria explora els límits de la possibilitat de solucionar problemes mitjançant algorismes. Gran part de les ciències computacionals estan dedicades a resoldre problemes de forma algorítmica, de manera que el descobriment de problemes impossibles és una gran sorpresa. La teoria de la computabilitat és útil per no tractar de resoldre algorítmicament aquests problemes, estalviant així temps i esforç.

Els problemes es classifiquen en aquesta teoria d'acord al seu grau d'impossibilitat :

• Els computables són aquells per als quals sí que existeix un algorisme que sempre els resol quan hi ha una solució ia més és capes de distingir els casos que no en tenen. També se'ls coneix com decidibles , resolubles o recursius .
• Els semicomputables són aquells per als quals hi ha un algorisme que és capaç trobar una solució si és que existeix, però cap algorisme que determini quan la solució no existeix (en aquest cas l'algorisme per trobar la solució entraria a un bucle infinit). L'exemple clàssic per excel·lència és el problema de la parada. A aquests problemes també se'ls coneix com listables , recursivament enumerables o recognoscibles , perquè si s'enlistan tots els casos possibles del problema, és possible reconèixer a aquells que sí que tenen solució.
• Els incomputabilitat són aquells per als quals no hi ha cap algorisme que els pugui resoldre, no important que tinguin o no solució. L'exemple clàssic per excel·lència és el problema de la implicació lògica, que consisteix a determinar quan una proposició lògica és un teorema; per aquest problema no hi ha cap algorisme que en tots els casos pugui distingir si una proposició o la seva negació és un teorema.

Hi ha una versió més general d'aquesta classificació, on els problemes incomputabilitat se subdivideixen al seu torn en problemes més difícils que altres. L'eina principal per aconseguir aquestes classificacions és el concepte de reducibilitat : Un problema $A$ es redueix al problema $B$ si sota la suposició que se sap resoldre el problema $B$ és possible resoldre el problema $A$, això es denota per $A\leq _{t}B$, i informalment vol dir que el problema $A$ no és més difícil de resoldre que el problema $B$. Per exemple, sota la suposició que una persona sap sumar, és molt fàcil ensenyar a multiplicar fent sumes repetides, de manera de multiplicar es redueix a sumar.

Teoria de la complexitat computacional

Article principal: Complexitat computacional

Tot i que un problema sigui computable, potser no sigui possible resoldre en la pràctica si es requereix molta memòria o temps d'execució. La teoria de la complexitat computacional estudia les necessitats de memòria, temps i altres recursos computacionals per resoldre problemes, d'aquesta manera és possible explicar perquè uns problemes són més difícils de resoldre que altres. Un dels majors èxits d'aquesta branca és un la classificació de problemes, anàleg a la taula periòdica, d'acord amb la seva dificultat, en aquesta classificació els problemes se separen per classes de complexitat.

Aquesta teoria té aplicació en gairebé totes les àrees de coneixement on es vulgui resoldre un problema computacionalment, perquè els investigadors no només volen utilitzar un mètode per resoldre un problema, sinó utilitzar el més ràpid. La teoria de la complexitat computacional també té aplicacions en àrees com la criptografia, on s'espera que desxifrar un codi secret sigui un problema molt difícil a menys que es tingui la contrasenya, en aquest cas el problema es torna fàcil.

Altres subbranques

• Models de còmput Estudia abstraccions de fer un còmput. Aquí s'inclouen els clàssics models de la teoria d'autòmats més d'altres models com funcions recursives, càlcul lambda i fins i tot llenguatges de programació.
• Teoria algorísmica de la informació Centra la seva atenció en la complexitat per descriure algorismes una seqüència de dades (cadena); aquí la complexitat està mesura per la longitud de la seva descripció més petita .
• Especificació i verificació formal Busca metodologies per garantir que un problema estigui correctament modelatge i sistemes formals per a validar la correcció de la solució algorísmica.
• La Teoria de l'aprenentatge computacional cerca algorismes que facin que els ordinadors modifiquin els seus comportaments de manera autònoma amb base en dades empíriques, i concretament en exemples i contraexemples. A aquest tipus d'aprenentatge se l'anomena aprenentatge supervisat. De forma anàloga a la teoria de la complexitat computacional, en aquesta teoria les funcions es classifiquen pel seu grau de dificultat de ser apreses.
• Teoria de tipus Cerca la classificació d'enunciats d'acord amb els tipus de valors que calculen utilitzant eines de teoria de llenguatges formals.

Història

Vegeu també: Entscheidungsproblem i Tesi de Church-Turing

La teoria de la computació comença pròpiament a principis del segle XX, poc abans que les computadores electròniques fossin inventades. En aquesta època diversos matemàtics es preguntaven si existia un mètode universal per resoldre tots els problemes matemàtics. Per a això havien de desenvolupar la noció precisa de mètode per resoldre problemes, és a dir, la definició formal d'algorisme.

Alguns d'aquests models formals van ser proposats per precursors com Alonzo Church (càlcul lambda), Kurt Gödel (funcions recursives) i Alan Turing ( màquina de Turing). Aquests models són equivalents en el sentit que poden simular els mateixos algorismes, encara que ho facin de maneres diferents. Entre els models de còmput més recents hi ha els llenguatges de programació, que també han resultat ser equivalents als models anteriors, això és una forta evidència de la conjectura de Church-Turing, que tot algorisme hagut i per haver es pot simular en una màquina de Turing, o equivalent, usant funcions recursives. El 2007 Nachum Dershowitz i Yuri Gurevich van publicar una demostració d'aquesta conjectura basant-se en certa axiomatització d'algorismes.

Un dels primers resultats d'aquesta teoria va ser l'existència de problemes impossibles de resoldre algorítmicament, i el problema de la parada el més famós d'ells. Per a aquests problemes no existeix ni existirà cap algorisme que els pugui resoldre, no important la quantitat de temps o memòria es disposi en un ordinador. Així mateix, amb l'arribada de les computadores modernes es va constatar que alguns problemes resolubles en teoria eren impossibles en la pràctica, ja que aquestes solucions necessitaven quantitats irrealistes de temps o memòria per poder-se trobar.

Des d'èpoques antigues, els còmputs han existit i s'han efectuat de manera mental o assistida per rudiments com comptes, llapis i paper, o taules.

Els antecedents de la computació mecànica, poden traçar fins a èpoques antigues, amb el desenvolupament d'artefactes per assistir el procés dels càlculs matemàtics mentals, per exemple el àbac, el regle de càlcul o el quipu.

Encara que potser sigui més propícia com a exemple precursor, la cèlebre calculadora grega d'Antikythera, utilitzada segons els experts per assistir en càlculs astronòmics, i considerada per molts com la primera ordinador. Un altre exemple precursor són les màquines sumador de Blaise Pascal. Aparells que demostren una notable perícia dels seus creadors en el coneixement sobre la forma d'elaborar els càlculs desitjats, al grau de poder representar en la forma de mecanismes més o menys elaborats.

No obstant això, la teoria de la computació com a ciència comença pròpiament a principis del segle XX, poc abans que les computadores electròniques fossin inventades.

En aquest època diversos matemàtics es preguntaven quina mena de problemes de la matemàtica, podien resoldre per "mètodes simples" i quines no. I per això havien en principi desenvolupar una definició de "mètode per resoldre problemes", és a dir, necessitaven el desenvolupament d'una noció formal (matemàtica) del que és un càlcul/algorisme i l'aritmètica lògica.

Durant el segle XIX i XX diversos corrents filosòfiques van aplanar el camí de la computació a partir de les definicions de sistemes formals. Destacant Kurt Gödel i Bertrand Russell entre d'altres.

Diverses definicions i models formals del que és un càlcul van ser proposats per precursors del domini com Alan Turing i Alonzo Church, entre aquests models hi ha la màquina de Turing, les funcions recursives, i el càlcul Lambda. Tots els quals s'ha demostrat posteriorment que són equivalents en expressivitat computacional, és a dir, tots poden representar la mateixa classe de còmputs o algorismes, encara que ho facin de maneres diferents.

S'assumeix normalment que les computadores electròniques són també equivalents en capacitat de còmput a qualsevol d'aquests tres models esmentats anteriorment, però no hi ha una prova formal d'això, per aquesta raó a aquest presumpció raonable es coneix com la conjectura de Church-Turing.

D'aquí la rellevància de l'estudi de les màquines de Turing, ja que gràcies a aquest conjectura àmpliament acceptada com a veritable, tot problema de còmput que sigui resoluble en una màquina de Turing, es considera que també ho serà en un ordinador, i viceversa.

És meritori el fet que gràcies a l'equivalència de màquines de Turing i ordinadors, s'hagi determinat que hi ha càlculs que no poden ser resolts en un temps raonable en cap ordinador imaginable, o fins i tot, que no poden resoldre's en l'absolut, per exemple el problema de correspondència de Post o el problema de predir si una màquina de Turing qualsevol va a arribar a un estat final (conegut com el problema de l'Haltingen en anglès, o problema de la parada ).

Altres temes d'interès de la teoria de la computació, són la quantitat de temps o la quantitat de memòria necessària per realitzar un càlcul donat. S'ha determinat que existeixen còmputs sismes, però que necessiten quantitats irreals de temps o memòria per poder efectuar-se. És summament important per als especialistes del domini conèixer la complexitat computacional d'un algorisme, ja que aquesta determinarà l'aplicabilitat del mateix.

Un altre interès d'aquesta ciència, són els models reduïts de còmput, que són en realitat casos particulars d'una màquina de Turing. Com ho són les màquines d'estat finit esbossades primer per Warren McCulloch i Walter Pitts a 1943, i els autòmats amb pila.