Computabilità di Turing: Teoria e applicazioni

Recensioni dei lettori

Il libro è un'esplorazione completa e stimolante della computabilità di Turing, con una forte narrazione storica e la competenza dell'autore evidente in ogni sua parte. Si rivolge in particolare agli studenti che cercano una comprensione più approfondita della teoria della computabilità.

⬤ stimolante e completo
⬤ contesto storico dettagliato
⬤ ben scritto e coinvolgente
⬤ adatto agli studenti che vogliono approfondire la loro comprensione
⬤ l'autore dimostra una chiara competenza nel campo.

Alcuni lettori potrebbero trovarlo impegnativo se non hanno familiarità con il campo, in quanto sembra essere rivolto a coloro che hanno una conoscenza preliminare della teoria della computabilità.

(basato su 2 recensioni dei lettori)

Titolo originale:

Turing Computability: Theory and Applications

Contenuto del libro:

Il famoso articolo di Turing del 1936 introdusse una definizione formale di macchina di calcolo, una macchina di Turing. Questo modello ha portato sia allo sviluppo di computer veri e propri sia alla teoria della computabilità, lo studio di ciò che le macchine possono o non possono calcolare. Questo libro presenta la teoria classica della computabilità da Turing e Post ai risultati e ai metodi attuali, e il loro utilizzo nello studio del contenuto informativo delle strutture algebriche, dei modelli e della loro relazione con l'aritmetica di Peano. L'autore presenta l'argomento come un'arte da praticare, e un'arte nel senso estetico della bellezza intrinseca che tutti i matematici riconoscono nella loro materia.

La Parte I fornisce uno sviluppo approfondito dei fondamenti della computabilità, dalla definizione di macchina di Turing fino agli argomenti di priorità delle lesioni finite. Gli argomenti chiave includono la computabilità relativa e gli insiemi computabilmente enumerabili, quelli che possono essere efficacemente elencati ma non necessariamente efficacemente decisi, come i teoremi dell'aritmetica di Peano. La seconda parte comprende lo studio degli insiemi aperti e chiusi computabili dei reali e i teoremi di base e non base per gli insiemi effettivamente chiusi. La Parte III tratta i gradi minimi di Turing. La Parte IV è un'introduzione ai giochi e al loro utilizzo per la dimostrazione di teoremi. Infine, la Parte V offre una breve storia della teoria della computabilità.

L'autore ha affinato i contenuti nel corso di decenni in base al feedback di studenti, docenti e ricercatori di tutto il mondo. La maggior parte dei capitoli include esercizi e il materiale è accuratamente strutturato in base all'importanza e alla difficoltà. Il libro è adatto a studenti universitari e laureati di livello avanzato in informatica e matematica e a ricercatori impegnati nella computabilità e nella logica matematica.