Decidibile

Decidibile è un termine usato in logica e informatica teorica per descrivere problemi o insiemi per cui esiste un algoritmo che, dato un’istanza qualsiasi, termina sempre con una risposta sì o no. In termini operativi, un linguaggio L su un alfabeto finito è decidibile se esiste una macchina di Turing M tale che, per ogni input w, M si ferma e accetta se w ∈ L e si ferma e rifiuta se w ∉ L.

Dal punto di vista computazionale, un linguaggio può essere anche riconoscibile (ricorsivamente enumerabile, RE) se esiste una macchina di Turing che genera tutte le stringhe di L; potrebbe però non fermarsi per gli input non appartenenti a L. Un linguaggio è decidibile se e solo se è RE e la sua complementare è RE, cioè esistono procedure che decidono sia L sia il complemento.

Esempi e limiti. Alcuni problemi sono decidibili: l’aritmetica di Presburger (numeri naturali con l’addizione), la teoria dei campi reali chiusi (risultato di Tarski) e, in pratica, la satisfiability booleana (SAT) ha procedure decisionali esistenti, anche se con complessità elevata. Altri problemi sono decisamente undecidibili: il problema della fermata (halting problem) e l’aritmetica dei naturali con addizione e moltiplicazione (la teoria di Peano) non hanno alcuna procedura che decida in generale la verità delle formule.

Note di contesto. Il concetto di decidibilità dipende dall’uso di un modello computazionale (ad es. macchine di Turing) e dalla codifica delle istanze; una stessa domanda può essere decidibile o meno a seconda di come viene rappresentata. La decidibilità informa sulle possibilità di automatizzare la risoluzione di problemi e definisce confini fondamentali tra problemi computabili e non computabili.