## [Decidibilidad](/es/node/59956) Definición Propiedad de un problema de decisión que indica la existencia de un procedimiento efectivo (algorítmico), en el modelo de cómputo elegido, que siempre termina y responde correctamente si una entrada pertenece al lenguaje. ## Principio Principio Un problema es decidible si existe un método mecánico terminante que proporciona una respuesta sí/no para cada instancia; la decidibilidad se conserva bajo operaciones booleanas cuando existen construcciones efectivas para los componentes. ## Demostración Demostración El lenguaje reconocido por un autómata finito determinista es decidible pues el procedimiento de transición procesa la entrada y termina indicando aceptación o rechazo. ## Aplicación incorrecta Aplicación incorrecta Tratar una procedimiento de semi-decisió n (que solo se detiene en instancias positivas) como un procedimiento de decisión completo, o asumir que porque muchos casos prácticos son resolubles existe un algoritmo uniformemente tronante para todos los casos. ## Consecuencia Consecuencia Si un problema es decidible, puede construirse un algoritmo general para clasificar instancias; los complementos, intersecciones y uniones de lenguajes decidibles siguen siendo decidibles mediante construcciones efectivas. ## Inversión Inversión Indecidibilidad: no existe ningún algoritmo que siempre termine y decida correctamente la pertenencia para toda entrada del dominio del problema. ## Límite Límite Se aplica a problemas de decisión codificados en un modelo de cómputo preciso (típicamente máquinas de Turing); no aborda límites de recursos, aproximaciones probabilísticas ni independencia semántica respecto a sistemas axiomáticos. ## Tensión semántica Tensión semántica A menudo se confunde con tratabilidad (decidibilidad en tiempo polinómico) o con completitud sintáctica de una teoría; la decidibilidad solo se refiere a la existencia de un procedimiento terminante y correcto, no a su eficiencia ni a su estatus proof-teórico. ## Síntesis Síntesis La decidibilidad identifica problemas para los que existe un algoritmo efectivo y terminante que decide la pertenencia; distingue la solvencia algorítmica exacta de nociones más débiles como la semi-decidibilidad o las restricciones de complejidad.