Decidibilità

Questa voce o sezione sugli argomenti matematica e teorie dell'informatica non cita le fonti necessarie o quelle presenti sono insufficienti.

---

Puoi migliorare questa voce aggiungendo citazioni da fonti attendibili secondo le linee guida sull'uso delle fonti. Segui i suggerimenti del progetto di riferimento.

Il concetto di decidibilità si trova in logica matematica e in teoria della computabilità con accezioni differenti.

Lo stesso argomento in dettaglio: Insieme ricorsivo.

Nella teoria della computabilità un sottoinsieme A dell'insieme N dei numeri naturali si dice decidibile o ricorsivo se esiste un algoritmo che ricevuto in input un qualsiasi numero naturale termina restituendo in output 0 o 1 a seconda che il numero appartenga o no all'insieme A. Equivalentemente A è decidibile se la sua funzione caratteristica è una funzione ricorsiva.

Nella logica matematica un enunciato rappresentato da una formula ben formata φ di una teoria del primo ordine T si dice decidibile in T se o φ o la sua negazione ¬φ sono dimostrabili in T. In caso contrario (se cioè non sono dimostrabili né φ né ¬φ) l'enunciato si dice indecidibile in T.

Esempi classici di enunciati indecidibili sono dati dal teorema di Goodstein per l'aritmetica di Peano e dall'ipotesi del continuo per la teoria assiomatica degli insiemi. Tali enunciati sono stati dimostrati indecidibili sotto l'ipotesi che le teorie in questione siano consistenti. I teoremi di incompletezza di Gödel forniscono una procedura con cui data una qualunque teoria consistente T in grado di rappresentare le operazioni di addizione e moltiplicazione sui numeri naturali è possibile costruire enunciati indecidibili da T. Le formule associate a tali enunciati tuttavia sono talmente lunghe e complesse che la loro scrittura esplicita nel linguaggio del primo ordine è di fatto impossibile da realizzare sia per un uomo sia per un computer.

Nella logica matematica una teoria individuata da un insieme di formule di un linguaggio si dice decidibile se tale insieme di formule è un insieme ricorsivo, cioè esiste un algoritmo che data una qualsiasi formula può stabilire in tempo finito se questa appartiene alla teoria oppure no.

Un esempio di teoria decidibile è la logica proposizionale (in questo caso l'algoritmo di decisione è quello individuato dalle tavole di verità). Esempi di teorie non decidibili sono l'aritmetica di Peano, l'aritmetica di Robinson e la Teoria degli insiemi di Zermelo - Fraenkel.

• (EN) Decidability, su Enciclopedia Britannica, Encyclopædia Britannica, Inc.
• (EN) Eric W. Weisstein, Decidable, su MathWorld, Wolfram Research.

Portale Informatica

Portale Matematica