Decidibilità: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
m ha spostato Decidibilità (logica matematica) a Decidibilità |
due significati |
||
Riga 1:
Il concetto di ''decidibilità'' si trova in [[logica matematica]] e in [[teoria della computabilità]] con accezioni differenti.
== Decidibilità in teoria della computabilità ==
{{vedi anche|insieme ricorsivo}}
Un enunciato rappresentato da una [[formula ben formata]] φ di una [[teoria del primo ordine]] '''T''' si dice '''indecidibile in T''' se né φ né la sua [[negazione]] ¬φ sono [[Teoria del primo ordine#dimostrazioni formali|dimostrabili]] in '''T'''.▼
Nella teoria della computabilità un sottoinsieme ''A'' dell'insieme '''N''' dei [[numeri naturali]] si dice '''decidibile''' o [[insieme ricorsivo|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 ==
▲
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.
| |||