Computabilità e irrisolvibilità

Recensioni dei lettori

Il libro di Martin Davis “Computabilità e irrisolvibilità” fornisce una trattazione formale e rigorosa della teoria della computabilità e delle sue implicazioni in matematica e informatica. Sebbene sia stato apprezzato per la sua profondità e completezza, molti lettori hanno notato la sua notazione impegnativa e la mancanza di esempi concreti, che lo rendono meno accessibile a chi non ha una solida preparazione matematica.

⬤ Trattamento completo e rigoroso della computabilità e della teoria delle funzioni ricorsive.
⬤ Struttura ben organizzata; i teoremi sono interconnessi in modo efficace.
⬤ Contenuto prezioso sulle questioni profonde della calcolabilità e del decimo problema di Hilbert.
⬤ Ristampa a prezzi accessibili da Dover.

⬤ Stile molto formale che può risultare difficile per i lettori non esperti di matematica.
⬤ Mancano esempi concreti per illustrare i concetti.
⬤ Le prove possono risultare noiose e possono saltare i passaggi necessari per la comprensione.
⬤ Alcune sezioni sono state criticate per essere asciutte o prive di vita.

(basato su 12 recensioni dei lettori)

Titolo originale:

Computability and Unsolvability

Contenuto del libro:

In questo testo classico, il dottor Davis fornisce una chiara introduzione alla computabilità, a un livello universitario avanzato, che soddisfa le esigenze di specialisti e non.

Nella prima parte (capitoli 1-5), il professor Davis delinea la teoria generale della computabilità, trattando argomenti quali le funzioni computabili, le operazioni sulle funzioni computabili, le funzioni ricorsive, le macchine di Turing, i problemi decisionali autoapplicati e irrisolvibili. L'autore è stato attento, soprattutto nei primi sette capitoli, a non presupporre una particolare preparazione matematica da parte del lettore.

La seconda parte (capitoli 6-8) comprende una trattazione concisa delle applicazioni della teoria generale, con materiale su problemi combinatori, equazioni diofantee (compreso il decimo problema di Hilbert) e logica matematica. Gli ultimi tre capitoli (Parte 3) presentano un ulteriore sviluppo della teoria generale, che comprende la gerarchia di Kleene, le funzioni computabili e la classificazione dei problemi decisionali irrisolvibili.

Quando fu pubblicata per la prima volta nel 1958, quest'opera introdusse molta terminologia che da allora è diventata standard nell'informatica teorica. In effetti, la statura del libro è tale che molti informatici lo considerano la loro introduzione teorica all'argomento. Questa nuova edizione Dover rende disponibile questo testo pionieristico e ampiamente ammirato in un formato economico.

Per l'edizione Dover, il dottor Davis ha fornito una nuova Prefazione e un'Appendice, Il decimo problema di Hilbert è irrisolvibile, un importante articolo da lui pubblicato su The American Mathematical Monthly nel 1973, che è stato premiato dall'American Mathematical Society e dalla Mathematical Association of America. Queste aggiunte accrescono ulteriormente il valore e l'utilità di un'esposizione insolitamente chiara e stimolante (Centre National de la Recherche Scientifique, Parigi), ora disponibile per la prima volta in brossura.