Carocci editore - Computabilità

Password dimenticata?

Registrazione

Computabilità

Enrico Moriconi, Luca Bellotti, Laura Tesconi

Computabilità

Lambda-definibilità, ricorsività, indecidibilità

Edizione: 2001

Collana: Università

ISBN: 9788843019588

  • Pagine: 272
  • Prezzo:20,90 19,85
  • Acquista

In breve

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.

Indice

Prefazione 1. Elementi di lambda-calcolo, di L. Tesconi/Interpretazione informale/Definizione formale/Il Teorema di Church-Rosser/Altri risultati fondamentali/La relazione di β-equivalenza/Estensionalità nel λ-calcolo/Il Teorema di punto fisso/Risultati di λ-definibilità/λ-definibilità delle funzioni ricorsive/Il λ-calcolo tipizzato 2. Elementi di teoria della ricorsività, di L. Bellotti/Commutabilità e ricorsività/Forma normale/Funzioni parziali ricorsive e diagonalizzazione 3. L'incompletezza dell'aritmetica, di E. Moriconi/Introduzione/Gli assiomi dell´aritmetica/Esprimibilità e rappresentabilità formali/L'aritmetizzazione della sintassi o metateoria/Richiamo sul programma di Hilbert/Condizioni di derivabilità/Il primo Teorema di incompletezza/Il secondo Teorema di incompletezza/Il Teorema di Tarsi/Qualche osservazione/Il Teorema di Löb/Il Teorema di Rosser/L'idecidibilità dell'aritmetica.