Indecidibili

Indecidibili è il termine usato in logica e teoria della computabilità per riferirsi ai problemi decisionali per i quali non esiste alcun algoritmo capace di fornire la risposta corretta (sì o no) per tutti gli input possible. Un problema è decidibile se esiste una macchina di Turing o un algoritmo che si ferma sempre e determina la risposta; se tale algoritmo non esiste, il problema è indecidibile.

Tra gli esempi più noti vi è il problema di arresto: dato il descrittore di una macchina di Turing e un input, stabilire se la macchina si ferma oppure continuerà all’infinito. Un altro classico è il problema della decidibilità della logica di primo ordine (il cosiddetto Entscheidungsproblem): non esiste un algoritmo generale che decida la validità o la soddisfacibilità delle formule; anche il problema di Hilbert sulle equazioni diofantee è indecidibile, dimostrato dal teorema di Matiyasevich.

La nozione di indecidibilità è strettamente legata alla computabilità teorica. Molti problemi indecidibili sono anche ricorsivamente enumerabili (semi-decidibili), come il problema di arresto, nel quale è possibile generare una procedura che accetta i casi sì ma non necessariamente rifiuta in modo definitivo i casi no. Altri problemi indecidibili non sono nemmeno ricorsivamente enumerabili, riflettendo una varietà di sfumature nel confine tra ciò che è computabile e ciò che non lo è.

L’indecidibilità evidenzia i limiti intrinseci dell’approccio algoritmico alla matematica e all’informatica, costituendo una componente fondamentale della teoria della computabilità e delle basi della logica formale.