Teoría de la computabilidad

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 resolverproblemas 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 algorítmicamente estosproblemas, 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 quesiempre 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 sonaquellos 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 lasolución entraría a unbucle infinito). El ejemplo clásico por excelencia es el problema de la parada. A estos problemas también se les conoce comolistables, recursivamente enumerables o reconocibles,porque si se enlistan todos los casos posibles del problema, es posiblereconocer a aquellos que sí tienen solución.
• Los incomputables son aquellos para los cuales no hay ningún algoritmo que lospueda 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 unteorema; 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.
Hay una versión más general de esta clasificación, donde losproblemas 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...