decisióne (matematica)

problema della decisione, relativo all'individuazione degli algoritmi o delle procedure che consentano di dare in modo effettivo delle risposte, affermative o negative, a ognuno dei quesiti appartenenti a una determinata classe di domande. Per esempio, in una teoria formalizzata T, il problema della decisione consiste nel trovare una procedura che permetta di stabilire per una qualsivoglia espressione di T se essa sia o non sia un teorema della teoria stessa. Quando è possibile dare una procedura di decisione si dice che il problema della decisione ha soluzione positiva, mentre quando è possibile dimostrare che non esiste tale procedura si dice che il problema della decisione ha soluzione negativa. Nei primi decenni di questo secolo lo studio dei linguaggi formalizzati è stato incentrato su questo problema soprattutto nella direzione di individuare soluzioni positive. Tali ricerche erano caratterizzate dalla convinzione che prima o poi si sarebbe potuto dare una risposta positiva anche alle formulazioni più generali del problema. Vennero così scoperte procedure di decisione per il calcolo degli enunciati, per quello dei predicati monadici e per teorie matematiche particolari, ma per la maggior parte delle teorie più interessanti (per esempio, la teoria dei numeri) il problema sembrava al di là di ogni possibile soluzione. Poiché la questione veniva aggredita utilizzando il linguaggio comune per la parte metateorica, si poteva ritenere che questo fatto fosse l'elemento determinante di tale scacco. Bisognava allora eliminare il linguaggio comune mediante la precisazione del concetto di algoritmo e di procedura di decisione. K. Gödel, nel 1931, non solo mostrò che la teoria dei numeri era indecidibile, ma per far questo introdusse dei metodi (aritmetizzazione della sintassi) che costituiscono tutt'oggi la base di ogni indagine in merito al problema. Il risultato più generale fu però conseguito da A. Church nel 1936, il quale dimostrò un teorema secondo il quale per il calcolo dei predicati in generale non è possibile dare un metodo di decisione. Dopo questo risultato le ricerche si incanalarono in due filoni. Da una parte si cercò di risolvere il problema della decisione per casi speciali, cioè, sia per particolari classi di espressioni del calcolo dei predicati, sia per particolari teorie o particolari branche della matematica; dall'altra si cercò di ridurre il problema generale della decisione per il calcolo dei predicati a quello per determinate classi di espressioni, dette tipi di riduzione, caratterizzate da prefissi di struttura determinata e sempre più semplici.