Computabilità. Lambda, definibilità, ricorsività, indecidibilità

Questo libro tratta di alcuni argomenti che sono alla base della moderna indagine logica, di grande interesse sia filosofico che matematico: la definibilità, la computabilità, la decidibilità. L'emergenza, negli anni Trenta del Novecento, del concetto di funzione computabile, o calcolabile, ha inaugurato una nuova area della ricerca logico-matematica i cui sviluppi si sono rivelati di notevole importanza per vari ambiti: dalla filosofia (della mente) all'informatica teorica, dalla linguistica ai fondamenti della matematica. I primi due capitoli presentano due fra le più note e importanti precisazioni formali del concetto di computabilità: la D-definibilità (risalente ad A. Church) e la ricorsività (legata in particolare al nome di S. C. Kleene). La nozione di funzione ricorsiva, tuttavia, aveva già svolto un ruolo cruciale nel procedimento con cui Gödel era pervenuto nel 1931 ai suoi risultati sull'incompletezza dell'aritmetica. A questi risultati e ad alcuni dei loro più importanti sviluppi - come il teorema di Tarski sulla verità e quello di Church sull'indecidibilità dell'aritmetica - è dedicato il terzo e conclusivo capitolo. Il volume può costituire la base per un corso annuale oppure, adeguatamente modulato, per corsi semestrali o seminari di approfondimento. Ma la trattazione estremamente lineare e particolareggiata ne fa una lettura introduttiva utile per chiunque voglia familiarizzarsi con questa importante area della ricerca logica.