Problema indecidible

En teoría de la computabilidad y en teoría de la complejidad computacional, un problema indecidible es un problema de decisión para el cual es imposible construir un algoritmo que siempre conduzca a una respuesta de sí o no correcta. El problema de la parada es un ejemplo: no existe algoritmo que determine de manera correcta si un programa arbitrario se detendrá, una vez sea ejecutado...

Un problema de decisión es cualquier pregunta arbitraria de sí o no en un conjunto infinito de entradas. Por ello es tradicional definir el problema de decisión como equivalente al conjunto de entradas para las que el problema retorna sí. Estas entradas pueden ser números naturales, o bien valores de otro tipo, tales como cadenas de un lenguaje formal.

Mediante alguna codificación, tal como una numeración de Gödel, las cadenas se pueden codificar como números naturales. Así, un problema de decisión informalmente expresado en términos de un lenguaje formal es también equivalente a un conjunto de números naturales. Para mantener simple la definición formal, se expresa en términos de subconjuntos de los números naturales.

Formalmente, un problema de decisión es un subconjunto de los números naturales. El problema informal correspondiente consiste en decidir si un número dado está en el conjunto. A un problema de decisión A, si A es un conjunto recursivo, se le denomina decidible, o efectivamente solucionable. Si A es un conjunto recursivamente enumerable, el problema es parcialmente decidible, semidecidible, solucionable, o demostrable. A problemas parcialmente decidibles y a los no decidibles se les califica de indecidibles.

Para demostrar que un problema es indecidible, generalmente se toma un problema que ya se ha demostrado que lo es y se construye una transformación que lo reduce a una instancia del nuevo problema. Se concluye que no puede existir un algoritmo para decidir sobre el nuevo problema dado que ese algoritmo serviría también para decidir sobre un problema conocido como indecidible.

Existe una infinidad de problemas indecidibles, por lo que cualquier lista de problemas indecidibles es necesariamente incompleta.