## [Indecidibilidad](/es/node/59958) Definición 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 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 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 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 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 Inversión Decidibilidad: existencia de un algoritmo que siempre termina y decide correctamente la pertenencia en todas las instancias. ## Límite 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 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 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.