Propiedad de un problema de decisión que indica que no existe un algoritmo, en el modelo de cómputo elegido, que siempre termine y decida correctamente la pertenencia para cada instancia de entrada.

Principio

La indecidibilidad se demuestra mostrando que cualquier hipotético decididor permitiría resolver un problema ya indecidible o conduciría a una contradicción, mediante reducción, diagonalización o argumentos de invariancia.

Demostración

El problema de la detención (Halting Problem) para máquinas de Turing es indecidible: no existe máquina de Turing que determine, para todo programa y entrada codificados, si el programa se detiene sobre esa entrada.

Aplicación incorrecta

Llamar 'indecidable' a una pregunta abierta cuando se quiere decir 'aún no resuelta', o confundir la indecidibilidad computacional con la independencia respecto a un determinado sistema axiomático.

Consecuencia

Cuando un problema es indecidible no existe un algoritmo general terminante; las aproximaciones prácticas deben basarse en procedimientos de semi-decisió n, instancias restringidas, heurísticas o suposiciones adicionales.

Inversión

Decidibilidad: existencia de un algoritmo que siempre termina y decide correctamente la pertenencia en todas las instancias.

Límite

Se refiere a problemas de decisión bajo un modelo formal de cómputo fijado; no implica que instancias individuales no puedan resolverse ni que no existan métodos parciales útiles.

Tensión semántica

Cercana a la noción de independencia lógica (una afirmación ni demostrable ni refutable a partir de axiomas) pero distinta: la indecidibilidad trata imposibilidad algorítmica, la independencia la capacidad deductiva de una teoría.

Síntesis

La indecidibilidad marca los límites de la solvencia algorítmica: aparece cuando ningún procedimiento uniforme y terminante puede decidir la pertenencia, forzando el uso de métodos más débiles o la reformulación del problema.