Una teoría es decidible si existe un algoritmo que, dado cualquier enunciado en el lenguaje de la teoría, determina en tiempo finito si ese enunciado es consecuencia de la teoría (es decir, si pertenece al conjunto de teoremas de la teoría).

Principio

Efectividad de la teoremacidad: la decidibilidad exige que el conjunto de fórmulas demostrables desde la teoría sea un conjunto decidible (computable), de modo que la teoremacidad sea comprobable mecánicamente y no meramente recursivamente enumerable o semidecidible.

Demostración

Ejemplo: la aritmética de Presburger (la teoría de los enteros con suma) es decidible; la teoría de cuerpos real cerrados es decidible porque la eliminación de cuantificadores reduce las fórmulas a enunciados sin cuantificadores que pueden comprobarse algorítmicamente; muchas teorías con eliminación de cuantificadores o fuerte control de cuantificadores son decidibles.

Aplicación incorrecta

Suponer que la decidibilidad implica factibilidad práctica: una teoría decidible puede tener una complejidad computacional extremadamente alta que hace inviable la búsqueda de pruebas; o asumir que la decidibilidad se conserva al ampliar la lengua o los axiomas sin comprobar los efectos sobre la computabilidad.

Consecuencia

La decidibilidad proporciona un procedimiento efectivo para determinar la teoremacidad, lo que posibilita razonamiento automatizado, clasificación algorítmica de fórmulas y verificación reproducible de propiedades; también se relaciona con la teoría de la complejidad para caracterizar la viabilidad práctica.

Inversión

Una teoría indecidible carece de algoritmo que decida la teoremacidad: ejemplos son sistemas aritméticos suficientemente expresivos, lo que impone límites intrínsecos a la automatización.

Límite

La decidibilidad depende de la elección del lenguaje, la firma y los axiomas; una teoría puede ser decidible en una lengua pero indecidible tras añadir símbolos o axiomas. Hay que distinguir decidibilidad, semidecidibilidad (enumerabilidad recursiva) y completitud, que es una noción separada.

Tensión semántica

Tensión entre decidibilidad, completitud y axiomatizabilidad: la completitud trata sobre valores de verdad de fórmulas, la axiomatizabilidad sobre la enumerabilidad recursiva de los axiomas; la decidibilidad exige un procedimiento efectivo para el conjunto completo de consecuencias y se sitúa en la intersección entre expresividad lógica y limitaciones de computabilidad.

Síntesis

Una teoría decidible es aquella cuyas consecuencias lógicas pueden determinarse mecánicamente y con fiabilidad: convierte la teoremacidad en un hecho algorítmico en lugar de una posibilidad teórica, permitiendo verificación automática y cálculo concreto en aplicaciones model-teóricas y algebraicas.