indecidibilita

indecidibilita

indecidibilità in logica, termine utilizzato per indicare la non → decidibilità di una data proprietà. In particolare, un insieme è indecidibile se non esiste un algoritmo in grado di stabilire se un dato elemento appartiene o meno a esso. In questo senso il concetto di insieme indecidibile è strettamente collegato alla teoria della → calcolabilità. Una teoria formalizzata in un sistema formale S è indecidibile se lo è l’insieme dei suoi teoremi, se cioè non per ogni formula ben formata a di S esiste un algoritmo di calcolo che riesce a stabilire se a è un teorema oppure no, vale a dire se a è o non è dimostrabile nel sistema formale dato. Esempi di teorie indecidibili sono l’aritmetica formalizzata dagli assiomi di → Peano e la teoria degli insiemi formalizzata secondo gli assiomi di → Zermelo-Fraenkel. È importante distinguere il concetto di teoria indecidibile dalla nozione di formula indecidibile (→ decidibilità). Un esempio di enunciato indecidibile è quello espresso nel decimo problema di Hilbert, relativo alle equazioni diofantee (→ Hilbert, problemi di).