Teoria de la computació

De Viquipèdia
Salta a la navegació Salta a la cerca

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[modifica]

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

Teoria d'autòmats[modifica]

Article principal: Teoria d'autòmats

Aquesta teoria proveeix models matemàtics que formalitzen el concepte d'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[modifica]

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 es redueix al problema si sota la suposició que se sap resoldre el problema és possible resoldre el problema , això es denota per , i informalment vol dir que el problema no és més difícil de resoldre que el problema . 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[modifica]

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[modifica]

  • 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[modifica]

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.[1]

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 és 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.

Referències[modifica]

  1. Nachum Dershowitz & Yuri Gurevich. A natural axiomatization of computability and proof of Church's Thesis. 14, 2008 (Bulletin of Symbolic Logic).