La teoria matematica della calcolabilità è uno dei prodotti più importanti del ventesimo secolo, in quanto costituisce il quadro teorico della scienza dei calcolatori, con quel che ne è seguito e continua a seguirne. Sono quindi da apprezzare gli strumenti che rendono accessibile tale teoria, come quest'opera, una presentazione ben concepita e ben riuscita. La parte principale del libro è un'esposizione della teoria classica, rigorosa e dettagliata sia tecnicamente sia nelle spiegazioni e motivazioni, con esercizi abbordabili di verifica dell'apprendimento.
La teoria classica introduce una definizione matematica dei procedimenti effettivi, chiamati anche informalmente algoritmi; la definizione si presenta in diverse versioni equivalenti, una delle quali è per mezzo delle macchine di Turing ( mt), altre con sistemi di deduzione. La teoria stabilisce quindi una serie di risultati che sono positivi e negativi.
I risultati negativi sono teoremi limitativi su quello che non è calcolabile o non è decidibile, cioè risolubile con una mt. Molti di questi riguardano la nozione stessa di calcolabilità, ad esempio non è decidibile se una macchina qualunque si ferma nei suoi calcoli o no.
Tra i risultati positivi vi sono teoremi che stabiliscono che certi tipi di definizioni danno funzioni calcolabili (soprattutto definizioni autoreferenziali, ad esempio il teorema del punto fisso di Kleene, dimostrato nel testo) e questo permette di studiare una ricca struttura di insiemi numerici definibili, quelli decidibili e quelli detti ricorsivamente enumerabili. Tra questi rientrano gli insiemi che codificano le teorie matematiche, e molte proprietà logiche delle teorie sono riflesse dalle proprietà di questi insiemi. Questa parte tuttavia, come anche lo studio di insiemi definibili più complessi, rientra nella teoria avanzata, che non è trattata in questa introduzione.
Vengono invece affrontati, da una parte, l'aspetto storico dei collegamenti con i fondamenti della matematica e, dall'altra, l'evoluzione e trasformazione della teoria nella visione dell'informatica, dove cambiano i formalismi e si pongono nuovi problemi, come quello della complessità computazionale. Alla fine sono dischiuse alcune prospettive sui collegamenti con la linguistica e con le scienze cognitive; il libro termina con la discussione di possibili recenti modelli alternativi di calcolo, come il calcolo biologico con i processi del Dna e la computazione quantista.
La parte dedicata ai risvolti culturali è un po' sacrificata, forse per problemi di dimensione del volume, mentre i principali destinatari del libro sono proprio coloro che desiderano padroneggiare i concetti della calcolabilità che emergono nei loro diversi campi di interesse: filosofi, psicologi, insegnanti; questi comunque trarranno vantaggio dalla saldezza delle basi formate con questo studio, e i matematici a loro volta dagli orizzonti culturali aperti.
Gli autori delineano anche un uso del libro per corsi universitari, brevi o normali, ma è da temere che le loro buone intenzioni e speranze siano deluse; all'università non si offrono più corsi di base di questo genere, introduttivi ma che approfondiscono un argomento. Non si approfondisce nulla di specifico. Soprattutto, non si approfondiscono i fondamenti delle discipline, alla ricerca come si è dell'immediata spendibilità. Questo libro potrebbe essere un modello di insegnamento alternativo, se e quando si riformerà di nuovo l'istruzione universitaria.
Solo il trattamento della tesi di Church si presta a qualche rilievo. Church è il logico che ha dimostrato l'indecidibilità della logica predicativa e ha inventato il lambda-calcolo, altra versione equivalente della calcolabilità; la sua tesi è l'affermazione proposta nel 1936 che le definizioni matematiche di "calcolabile" erano una versione soddisfacente del concetto intuitivo di "metodo effettivo". Dopo qualche discussione gli specialisti sono stati d'accordo, per motivi ben illustrati nel libro. Dal punto di vista filosofico, la tesi è discussa oggi solo dai fisici, che la interpretano come l'affermazione che ogni processo fisico sia realizzabile da una macchina di Turing. Ma la tesi non fa parte della teoria; sennonché qualcuno continua a far riferimento a essa, col rischio di ingenerare confusione. La tesi è richiamata in due modi, entrambi ingiustificati.
Quando si vuole fornire una versione generalissima di un risultato negativo, ad esempio che non esiste alcun metodo effettivo, in senso intuitivo, per decidere un problema, si dimostra prima che non esiste alcuna macchina di Turing che risolve il problema, quindi si sostituisce "metodo effettivo" a "macchina" di Turing facendo appello alla tesi di Church. Ma non si vede perché si dovrebbero formulare teoremi che riguardano i concetti intuitivi.
Un altro caso è quando non si ha pazienza di indicare tutti i dettagli di un procedimento algoritmico, ma solo le sue linee generali; per un certo tempo si è usato dire (anche in classici come il manuale di Rogers) che tale descrizione era comunque soddisfacente in quanto per la tesi di Church le corrispondeva una definizione precisa. Anche questo "espediente adottato a fini espositivi" è discutibile: sarebbe come se ogni volta che si presenta una dimostrazione matematica, in un libro o in classe, si facesse appello a qualcosa da chiamare ad esempio "tesi di Hilbert", concernente l'equivalenza delle dimostrazioni informali con quelle formalizzate.
Gli autori illustrano chiaramente la distinzione dei due usi, ma li accettano e adottano entrambi; gli esiti sono talvolta inutilmente contorti. Ad esempio a p. 231 spiegano come nel teorema sull'indecidibilità del problema della fermata hanno fatto appello due volte alla tesi, e il primo uso, per mostrare che non esiste una mt che risolve il problema, è inessenziale, mentre il secondo sì - ma solo perché per loro "decidibile" significa "risolubile con un metodo effettivo intuitivo", se il lettore se lo ricorda.
Quando invece sorvolano sulle distinzioni, rischiano anche affermazioni errate, come a p. 16: "La Tesi di Church ha varie importanti conseguenze, in particolare l'esistenza di una mt universale ". La macchina universale si costruisce esplicitamente con tutte le sue istruzioni, lo ha fatto Turing e lo si fa quando la si vuole simulare su un calcolatore.
