Carocci editore - Funzioni, macchine, algoritmi

Password dimenticata?

Registrazione

Funzioni, macchine, algoritmi

Marcello Frixione, Dario Palladino

Funzioni, macchine, algoritmi

Introduzione alla teoria della computabilità

Edizione: 2004

Ristampa: 2^, 2009

Collana: Università

ISBN: 9788843030026

  • Pagine: 432
  • Prezzo:35,90 34,10
  • Acquista

In breve

La teoria della computabilità è un settore della ricerca logico-matematica che studia la nozione di calcolo algoritmico, ossia di calcolo eseguibile in modo meccanico. Essa è nata nel corso degli anni Trenta del Novecento nel contesto delle ricerche sulla logica e sui fondamenti della matematica. Con lo sviluppo dei calcolatori digitali la teoria della computabilità ha poi assunto il ruolo di disciplina dei fondamenti per l´informatica teorica. Attraverso di essa, la sua influenza culturale si è estesa ad ambiti quali l´intelligenza artificiale, le scienze cognitive, la linguistica. Di conseguenza, i risultati di teoria della computabilità si trovano al centro di alcuni dei crocevia più vitali e stimolanti della cultura filosofica e scientifica contemporanea, hanno una vasta portata culturale e sono rilevanti per molte differenti discipline. Questo volume vuole rendere accessibili, con un adeguato livello di approfondimento, i principali risultati della teoria della computabilità ad un pubblico che non disponga necessariamente di una specifica preparazione logico-matematica.

Indice

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 / Indice dei riquadri / Indice analitico.