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

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

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

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

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

Indecidibilidad: no existe ningún algoritmo que siempre termine y decida correctamente la pertenencia para toda entrada del dominio del problema.

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

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

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.