Modelli di calcolo e computabilità

A cura di: Alberto Marchetti Spaccamela, Marco Protasi

Modelli di calcolo e computabilità

Pagine: 212

ISBN: 9788820427269

Edizione: 1a edizione 1988

Codice editore: 272.4

Disponibilità: Nulla

Un volume per quanti desiderano conoscere i principali risultati della teoria della calcolabilità e le sue applicazioni all'informatica.

Questa disciplina si propone di ricercare modelli di calcolo sempre più potenti e di caratterizzare l'insieme delle funzioni che risultano calcolabili con i modelli proposti.

L'interesse odierno per lo studio della teoria della calcolabilità è dovuto all'introduzione dei calcolatori elettronici, perché la nozione di calcolabilità individuata coincide con il concetto di calcolo eseguibile da una macchina.

In questo testo si presentano diversi modelli di calcolo, ponendo in rilievo gli aspetti informatici di ciascuno; viene mostrato che tutti i modelli calcolano il medesimo insieme di funzioni e vengono dati esempi di funzioni che non possono essere calcolate da nessuno dei modelli proposti.

Alberto Marchetti Spaccamela è professore straordinario di "Sistemi per l'elaborazione dell'informazione" presso la Facoltà di Scienze dell'Università dell'Aquila. Nato a La Spezia nel 1954, si è laureato in ingegneria elettronica all'Università di Roma e si è specializzato all'Università di California a Berkeley. t autore di numerose pubblicazioni scientifiche nel campo della teoria degli algoritmi e delle sue applicazioni alla progettazione di sistemi informatici. t autore insieme a G. Ausiello e M. Protasi del libro Teoria e progetto di algoritmi fondamentali (Angeli, 1985).

Marco Protasi è professore straordinario di -Teoria e applicazione delle macchine calcolatrici» presso la Facoltà di Scienze dell'Università di Roma "Tor Vergata". Nato a Spoleto nel 1950, si è laureato in matematica presso l'università di Roma. Da molti anni è incaricato di ricerca dell'istituto di analisi dei sistemi e informatica del Cnr. E' autore di molte pubblicazioni scientifiche nel campo della matematica applicata e dell'informatica teorica.

Prefazione
1. Introduzione alla calcolabilità
1.1. Algoritmi e procedure
1.2. Calcolatori numerici
1.3. Cenni storici
1.4. Notazione e prerequisiti matematici
1.5. Proprietà di cardinalità degli insiemi
2. Il mini-Pascal
2.1. Il linguaggio mini-Pascal
2.2. Funzioni calcolabili in mini-Pascal
2.3. Funzioni non calcolabili
2.4. Il problema della fermata
2.5. Esercizi
3. La classe delle funzioni ricorsile parziali
3.1. Le funzioni ricorsive parziali
3.2. Equivalenza tra funzioni ricorsivi parziali e funzioni mP calcolabili
3.3. Una seconda definizione della classe delle funzioni ricorsive parziali
3.4. La funzione di Ackermann e la ricursione multipla
3.5. Esercizi
4. La macchina a registri
4.1. La macchina a registri
4.2. Programmi elementari per macchine a registri
4.3. Macchine a registri e funzioni ricorsivi
4.4. Aritmetizzazione delle macchine a registri
4.5. La macchina a registri universale
4.6. La forma normale di Kieene
4.7. Esercizi
5. La macchina di Turing
5.1. La macchina di Turing e le sue principali proprietà
5.2. Potenza computazionale delle macchine di Turing
5.3. Macchine di Turing non deterministiche
5.4. Macchine di Turing con risorsa limitata
5.5. Esercizi
6. Linguaggi e sistemi di Post
6.1. Grammatiche e sistemi di Post
6.2. Grammatiche ed altri modelli di calcolo
6.3. Problemi indicibili
6.4. Classificazione delle grammatiche
6.5. Esercizi
7. Il lambda calcolo
7.1. Introduzione al • -calcolo
7.2. Le regole del calcolo
7.3. Il calcolo delle funzioni aritmetiche
7.4. Il calcolo delle funzioni ricorsivi
7.5. • -calcolo e linguaggi di programmazione
7.6. Esercizi
8. Calcolabilità indipendente dal modello
8.1. La Tesi di Church
8.2. Proprietà delle enumerazioni di Godei
8.3. Il problema della fermata e altri problemi indecidibili
8.4. Insiemi ricorsivi e ricorsivamente enunciabili
8.5. Il teorema di ricursione
8.6. Riduzioni e gradi di indecidibilità
8.7. Esercizi


Collana: Crai