Teoria de la computació

Teoria de autómatasEditar

Aquesta teoria proveeix models matemàtics que formalitzen el concepte d’ordinador o algoritme 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, compiladors, disseny de maquinari i intel·ligència artificial.

Hi ha 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 cadascun d’aquests autòmats. Això dóna lloc al fet que es pensi en la màquina de Turing com el model universal d’ordinador.

Teoria de la computabilidadEditar

Aquesta teoria explora els límits de la possibilitat de solucionar problemes mitjançant algoritmes. 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í hi ha un algoritme que sempre els resol quan hi ha una solució ia més és capaç de distingir els casos que no la tenen. També se’ls coneix com decidibles, resolubles o recursius.
• Els semicomputables són aquells per als quals hi ha un algoritme que és capaç de trobar una solució si és que existeix, però cap algoritme que determini quan la solució no existeix (en aquest cas l’algoritme 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 reconeixibles, perquè si s’enlistan tots els casos possibles de el problema, és possible reconèixer a aquells que sí que tenen solució.
• Els incomputables són aquells per als quals no hi ha cap algoritme 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 algoritme 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 incomputables 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 {\ displaystyle A}

es redueix a el problema B {\ displaystyle B}

si sota la suposició que se sap resoldre el problema B {\ displaystyle B}

és possible resoldre a el problema a {\ displaystyle a}

; això es denota per A ≤ t B {\ displaystyle A \ leq _ {t} B}

, i informalment vol dir que el problema A {\ displaystyle A}

no és més difícil de resoldre que el problema B {\ displaystyle B}

. Per exemple, sota la suposició que una persona sap sumar, és molt fàcil ensenyar-li a multiplicar fent sumes repetides, de manera que multiplicar es redueix a sumar.

Teoria de la complexitat computacionalEditar

Tot i que un problema sigui computable, potser no sigui possible resoldre-ho 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 per què uns problemes són més difícils de resoldre que altres. Un dels majors èxits d’aquesta branca és la classificació de problemes, similar a la taula periòdica, d’acord a 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 .