La teoría de
la computación es una rama de la matemática y la computación que centra su
interés en las limitaciones y capacidades fundamentales de las computadoras.
Específicamente esta teoría busca modelos matemáticos que formalizan el
concepto de hacer un cómputo (cuenta o cálculo) y la clasificación de
problemas.
Teoría de
autómatas
Esta teoría
provee modelos matemáticos que formalizan el concepto de computadora o
algoritmo de manera suficientemente simplificada y general para que se puedan
analizar sus capacidades y limitaciones. Algunos de estos modelos juegan un
papel central en varias aplicaciones de las ciencias de la computación,
incluyendo procesamiento de texto, compiladores, diseño de hardware e inteligencia
artificial.
Teoría de la
computabilidad
Esta teoría
explora los límites de la posibilidad de solucionar problemas mediante
algoritmos. Gran parte de las ciencias computacionales están dedicadas a
resolver problemas de forma algorítmica, de manera que el descubrimiento de
problemas imposibles es una gran sorpresa. La teoría de la computabilidad es
útil para no tratar de resolver algoritmicamente estos problemas, ahorrando así
tiempo y esfuerzo.
Los
problemas se clasifican en esta teoría de acuerdo a su grado de imposibilidad:
Los
computables son aquellos para los cuales sí existe un algoritmo que siempre los
resuelve cuando hay una solución y además es capaz de distinguir los casos que
no la tienen. También se les conoce como decidibles, resolubles o recursivos.
Los
semicomputables son aquellos para los cuales hay un algoritmo que es capaz
encontrar una solución si es que existe, pero ningún algoritmo que determine
cuando la solución no existe (en cuyo caso el algoritmo para encontrar la
solución entraría a un bucle infinito). El ejemplo clásico por excelencia es el
problema de la parada. A estos problemas también se les conoce como listables,
recursivamente enumerables o reconocibles, porque si se enlistan todos los
casos posibles del problema, es posible reconocer a aquellos que sí tienen
solución.
Los
incomputables son aquellos para los cuales no hay ningún algoritmo que los
pueda resolver, no importando que tengan o no solución. El ejemplo clásico por
excelencia es el problema de la implicación lógica, que consiste en determinar
cuándo una proposición lógica es un teorema; para este problema no hay ningún
algoritmo que en todos los casos pueda distinguir si una proposición o su
negación es un teorema.
Teoría de la
complejidad computacional
Aun cuando
un problema sea computable, puede que no sea posible resolverlo en la práctica
si se requiere mucha memoria o tiempo de ejecución. La teoría de la complejidad
computacional estudia las necesidades de memoria, tiempo y otros recursos
computacionales para resolver problemas; de esta manera es posible explicar por
qué unos problemas son más difíciles de resolver que otros. Uno de los mayores
logros de esta rama es la clasificación de problemas, similar a la tabla
periódica, de acuerdo a su dificultad. En esta clasificación los problemas se
separan por clases de complejidad.
No hay comentarios:
Publicar un comentario