Decidibilità: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
due significati |
|||
Riga 9:
== Decidibilità in logica matematica ==
Nella logica matematica un enunciato rappresentato da una [[formula ben formata]] φ di una [[teoria del primo ordine]] '''T''' si dice '''
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 [[consistenza (logica matematica)|consistenti]]. I [[teoremi di incompletezza di Gödel]] forniscono una procedura con cui data una qualunque teoria '''T''' in grado di [[funzione rappresentabile|rappresentare]] le operazioni di addizione e moltiplicazione sui [[numeri naturali]] è possibile costruire enunciati indecidibili da '''T'''. Le [[formula ben formata|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.
|