Un problema indecidible es una cuestión que no se puede resolver con el uso de un algoritmo. Este es un tema de interés en matemáticas y programación de computadoras, donde el problema indecidible tiene implicaciones significativas. Los investigadores interesados en las máquinas de Turing, por ejemplo, han abordado la cuestión del problema de la detención, observando cuándo se detienen los programas informáticos en lugar de ejecutarse infinitamente. Al igual que con otros desafíos en matemáticas, una considerable investigación rodea las formas de sortear problemas indecidibles, además de identificar nuevos problemas para una mayor evaluación y estudio.
Este tema involucra problemas de decisión, preguntas con respuesta sí o no. En matemáticas, a menudo se presentan en forma de fórmulas. Un ejemplo simple podría ser «Para cualquier número real, ¿es X uniformemente divisible por Y?» Este es un problema decidible, porque si la computadora recibe algún valor para X o Y, puede usar un algoritmo para responder la pregunta. Es posible que los problemas más complejos no se puedan resolver con un solo algoritmo para todos los valores posibles.
En estos casos, un algoritmo puede ser preciso para algunas respuestas, pero podría ser incapaz de responder por otros valores. Dados algunos valores, el algoritmo podría moverse a través de una serie de pasos para determinar si la respuesta a la pregunta fue sí o no. En otros casos, no podría hacerlo porque carecería de la información necesaria. Este es un problema conocido con algunos problemas relacionados con matrices, análisis complejos y algunas otras funciones.
La identificación de un problema indecidible puede ocurrir en el contexto de la investigación en matemáticas y ciencias de la computación. Una vez que se cree que un problema es indecidible, los investigadores pueden aplicar una variedad de tácticas para refutar esta teoría. Esto puede incluir el desarrollo de algoritmos que funcionen para algunos valores, discutir los detalles del problema que hacen que sea imposible tratarlo de manera efectiva con un algoritmo para todos los valores y actividades relacionadas. Las publicaciones sobre matemáticas y ciencias de la computación pueden discutir los últimos avances en este campo con ejemplos de algoritmos que los investigadores han utilizado para explorar los límites de un problema indecidible.
Lejos de ser un tema de interés teórico únicamente, el problema indecidible puede tener importantes implicaciones para el mundo real. Por ejemplo, algunos virus informáticos presentan sistemas con problemas indecidibles. El intento del sistema de resolver el problema puede consumir recursos, lo que hace que el sistema se congele o cree vulnerabilidades en el sistema. De manera similar, los técnicos pueden causar un problema con un sistema presentándole inconscientemente un problema que no puede resolver. Es posible que deban finalizar un programa u operación, lo que podría provocar la pérdida de datos.