Funzioni, macchine, algoritmi. Introduzione alla teoria della computabilità

Prefazione/ 1.Il concetto di algoritmo/Che cos´è un algoritmo/Diagrammi di flusso/Algoritmi che non sempre producono risultati/Numeri naturali e codifiche dei dati/Esercizi del capitolo I/Soluzioni degli esercizi/ 2.Funzioni e calcolabilità/Il concetto di funzione/Funzioni e algoritmi, decidibilità e calcolabilità, codifiche/Funzioni parziali e calcolabilità/Esercizi del capitolo 2/Soluzioni degli esercizi/ 3.Insiemi, numeri cardinali e calcolabilità/ Introduzione/Insiemi numerabili e più che numerabili/"Incalcolabilità" della calcolabilità/ Insiemi effettivamente enumerabili/Esercizi del capitolo 3/Soluzioni degli esercizi/ 4.Macchine di Turing/Introduzione/Le macchine di Turing/Macchine di Turing che calcolano funzioni aritmetiche/La MT che calcola la moltiplicazione/ Considerazioni conclusive/Esercizi del capitolo 4/ Soluzioni degli esercizi/ 5.Funzioni ricorsive/Introduzione/Funzioni ricorsive primitive/Limiti della ricorsività primitiva/Le funzioni ricorsive generali/Predicati e insiemi ricorsivi e ricorsivamente enumerabili/ Equivalenza fra ricorsività generale e T-computabilità/Esercizi del capitolo 5/Soluzioni degli esercizi/ 6.Tesi di Church e problemi indecidibili/La Tesi di Church/Macchine universali, problemi indecidibili e semidecidibili/Alcuni ulteriori risultati /Esercizi del capitolo 6/Soluzioni degli esercizi/ 7.Computabilità, logica e fondamenti della matematica/Il contesto storico all´origine della teoria della computabilità/I teoremi di Church e di G%del/ 8.Computabilità e informatica/Programmi memorizzati e macchine di von Neumann/Codici assembler e computabilità/Computabilità e linguaggi di programmazione di alto livello/Esercizi del capitolo 8/Soluzioni degli esercizi/ 9.Computabilità e grammatiche formali/ Premessa/Che cos´è una grammatica formale'/La gerarchia di Chomsky/Alberi di derivazione e grammatiche ambigue/Grammatiche e macchine/ Conclusioni/Esercizi del capitolo 9/Soluzioni degli esercizi/ 10.Computabilità e scienze cognitive/Il ruolo della teoria della computabilità nelle scienze cognitive/I livelli di spiegazione secondo David Marr/ Un superamento della computabilità'/ 11.Limiti di risorse e complessità computazionale/Limiti delle risorse di calcolo: alcuni compiti difficili/Complessità computazionale/ 12.Alla ricerca di una via d´uscita: DNA computing e computazione quantistica/Il DNA computing/Computazione quantistica / Suggerimenti bibliografici / Bibliografia /