Problema indecidible

Carta Común · N.º 439181

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…

Leer en Wikipedia