Iscriviti alla Newsletter!
Logica da Zero a Gödel di Francesco Berto e Fallacie di ragionamento
La computabilità: Algoritmi, Logica, Calcolatori è un’introduzione alla teoria della computabilità. Non si tratta di un testo particolarmente tecnico e può essere compreso anche da chi non ha quasi nessuna cognizione pregressa sull’argomento. In particolare non sono richieste particolari competenze matematiche o logico-formali. Anche se probabilmente il libro può suscitare approvazione e interesse soprattutto per gli interessati alla logica filosofica, esso può essere di utilità anche a studenti di matematica del triennio piuttosto che a studenti del liceo particolarmente agguerriti.
Il testo è diviso in sette capitoli. Il primo capitolo, Algoritmi introduce la nozione centrale di algoritmo, la loro possibile rappresentazione grafica mediante i diagrammi di flusso e i loro possibili risultati, tra cui anche la possibilità che essi non ne producano affatto. Il secondo capitolo, Funzioni matematiche e algoritmi è il primo passo verso la costruzione della teoria della computabilità in matematica. Infatti, gli algoritmi sono concettualmente vicini ai sistemi di logica, grazie ai quali possiamo effettuare dimostrazioni rigorose. Sono a tal punto vicini che i due campi si intersecano. Per mostrare in che modo questo avvenga, gli autori forniscono una serie di utili spiegazioni circa la natura delle funzioni, alla loro calcolabilità effettiva (o non calcolabilità) e nell’ultimo paragrafo anticipano alcuni risultati sull’indecidibilità (cioè problemi matematici che non ammettono una risposta positiva da parte di alcun algoritmo). Il capitolo terzo, Le macchine di Turing, è una trattazione di un certo dettaglio delle macchine di Turing, una macchina astratta che, appositamente programmata, è in grado di svolgere algoritmi. In particolare la macchina di Turing può essere utilizzata per spiegare in che consista la computabilità effettiva. Esse, dunque, possono essere impiegate per il calcolo di funzioni aritmetiche. Nella parte finale del capitolo si considera anche il problema della fermata. Il capitolo quarto, Funzioni ricorsive, è dedicato alla spiegazione di un tipo particolare di funzioni, le funzioni ricorsive. Si scoprirà che di esse ci sono diversi tipi. Per cui nel capitolo quinto Tesi di Church e problemi indecidibili si considera la tesi di Church, la sua disamina e la sua analisi circa la connessione con le macchine di Turing. Il penultimo capitolo, il sesto, La computabilità e i fondamenti della matematica, considera il versante puramente logico e considera i teoremi di indecidibilità di Gödel e la loro connessione con i risultati di Church. In fine, Computabilità informatica e studio della mente fornisce una panoramica generalissima sull’informatica, come disciplina applicativa della teoria della computabilità. Inoltre, sempre in questo ultimo capitolo, si considera stringatamente, il legame tra alcune discipline della scienza cognitiva, in particolare tra la filosofia della mente, l’intelligenza artificiale e la neuroscienza.