Decidibilità

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

Decidibilità in teoria della computabilità

[modifica | modifica wikitesto]
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.

Decidibilità in logica matematica

[modifica | modifica wikitesto]

Decidibilità di enunciati in una teoria del primo ordine

[modifica | modifica wikitesto]

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.

Decidibilità di una teoria del primo ordine

[modifica | modifica wikitesto]

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.

Collegamenti esterni

[modifica | modifica wikitesto]
Controllo di autoritàLCCN (ENsh85036191 · GND (DE4152398-2 · BNF (FRcb119818468 (data) · J9U (ENHE987007545768505171