computacion

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 yesfuerzo.
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 unalgoritmo 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 loscasos 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 hayningún algoritmo que en todos los casos pueda distinguir si una proposición o su negación es un teorema.
Hay una versión más general de esta clasificación, donde los problemas incomputables se subdividen a su vez en problemas más difíciles que otros. La herramienta principal para lograr estas clasificaciones es el concepto de reducibilidad: Un problema se reduce al problema si bajo la suposición de quese sabe resolver el problema es posible resolver al problema ; esto se denota por , e informalmente significa que el problema no es más difícil de resolver que el problema . Por ejemplo, bajo la suposición de que una persona sabe sumar, es muy fácil enseñarle a multiplicar haciendo sumas repetidas, de manera que multiplicar se reduce a sumar.
Teoría de la complejidad computacional[editar]Artículo principal: Complejidad computacional
Véase también: Clase de complejidad
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 explicarpor 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.
Esta teoría tiene aplicación en casi todas las áreas de conocimiento donde se desee resolver un problema computacionalmente, porquelos investigadores no solo desean utilizar un método para resolver un problema, sino utilizar el más rápido. La teoría de la complejidad computacional también tiene aplicaciones en áreas como la criptografía, donde se espera que descifrar un código secreto sea un problema muy difícil a menos que se tenga la contraseña, en cuyo caso el problema se vuelve fácil.
Otras subramas[editar]
Modelos decómputo Estudia abstracciones de hacer un cómputo. Aquí se incluyen los clásicos modelos de la teoría de autómatas además de otros modelos como funciones recursivas, cálculo lambda e inclusive lenguajes de programación.
Teoría algorítmica de la información Centra su atención en la complejidad para describir algoritmicamente una secuencia de datos (cadena); aquí la complejidad está medida por...