Primi passi matematici sulla computabilità

Recensioni dei lettori

Attualmente non ci sono recensioni dei lettori. La valutazione si basa su 2 voti.

Titolo originale:

A Mathematical Primer on Computability

Contenuto del libro:

Il libro fornisce un'introduzione autonoma alla teoria della computabilità per studenti avanzati di matematica e informatica. Il materiale tecnico è illustrato con numerosi esempi, problemi con soluzioni complete e una serie di esercizi proposti.

La prima parte è incentrata sulle nozioni e sui risultati fondamentali della computabilità, a partire dai concetti pilastro di modello computazionale (un linguaggio di programmazione astratto di alto livello), funzione computabile, insieme decidibile e elencabile, funzione universale propria, problema della decisione e tecnica di riduzione per trasferire le proprietà di decidibilità e elencabilità. Vengono presentati e illustrati i risultati essenziali, ovvero il Teorema di Rice, il Teorema di Rice-Shapiro, il Teorema di Rice-Shapiro-McNaughton-Myhill, il Teorema di Rogers e il Teorema della ricorsione. Vengono studiati la riducibilità e i gradi molti a uno. È inclusa anche una breve introduzione al calcolo con gli oracoli. Vengono introdotti gli operatori computabili e non computabili, nonché gli operatori monotoni e finitari. Viene discussa la relazione tra di essi, in particolare attraverso il teorema di Myhill-Shepherdson. Viene inoltre presentato il teorema del punto fisso minimo di Kleene. Infine, la Parte I si conclude con un breve cenno al modello computazionale di Turing, alla riducibilità di Turing e ai gradi di Turing.

La seconda parte del libro si concentra sulle applicazioni della computabilità in diverse aree, in particolare nella logica (indecidibilità dell'aritmetica, soddisfabilità nella logica proposizionale, decidibilità nella logica modale), nella geometria euclidea, nei grafi e nella complessità di Kolmogorov. Tuttavia, non è richiesta alcuna conoscenza precedente di questi argomenti. Vengono forniti i dettagli essenziali per la comprensione delle applicazioni.