Programma
Mercoledì 15 marzo 2023, ore 16.00–17.30: La crisi dei fondamenti e la nascita dalla logica matematica
(disponibile su youtube.com)
Giovedì 16 marzo 2023, ore 16.00–17.30: Le funzioni calcolabili
(disponibile su youtube.com)
I seminari del 15 e 16 marzo esordiranno con un inquadramento storico sulla crisi dei fondamenti (le geometrie non-euclidee, il successo della geometria iperbolica, i paradossi insiemistici), le proposte di Hilbert e di Brouwer, per esaminare quindi alcune delle questioni poste da Hilbert per il suo programma:
1) Ammesso che il ragionamento matematico sia finito, dimostrare con metodi finiti che la matematica è coerente.
2) Dimostrare che la teoria degli insiemi è coerente.
3) Dimostrare l'ipotesi del continuo.
4) Produrre un algoritmo che decide quali equazioni diofantee hanno soluzioni.
5) Produrre un algoritmo che decide quali affermazioni matematiche sono vere.
Le risposte sono state tutte negative. Percorreremo i risultati di Gödel, di Turing, di Cohen, Scott e Solovay, e di Bowman–Robinson, Matjiase-vic, mostrando in modo esplicito come certe costruzioni matematiche impediscono la realizzazione del programma auspicato da Hilbert, ma al contempo mostrano le basi di quel nuovo panorama matematico che diventerà l'informatica.
A seguire, si affronta la teoria delle funzioni matematiche che gestiscono tutti i risultati elencati: le funzioni calcolabili. Vengono introdotte mediante tre differenti approcci (quello di Gödel, quello di Turing, quello di Bowman–Matjiasevic). Le funzioni calcolabili offrono un banco di prova molto semplice ed elementare per approfondire l'intuizione sulle funzioni in generale; si sfrutta questo e si sviluppano in dettaglio molti esempi di funzioni calcolabili per accquisire dimestichezza con la teoria fondamentale della matematica e giungere al Teorema di Caratteriz-zazione (Ognuna delle tre definizioni determina lo stesso concetto di funzione aritmetica).
Mercoledì 19 aprile 2023, ore 16:00–17.30: I numeri come algoritmi, i numeri come dimostrazioni
Giovedì 20 aprile 2023, ore 16:00–17.30: La potenza dell'aritmetica e del calcolo meccanico
Nei seminari del 19 e 20 aprile si svolgerà un confronto tra i Teoremi di Incompletezza di Gödel e il Teorema della Macchina Universale di Turing. In particolare verranno analizzati i seguenti punti:
- Tutto è numero: gli algoritmi sono numeri, le affermazioni sono numeri.
- Il calcolo della deduzione naturale: come si ragiona in matematica.
- L'espressività dell'aritmetica: quanto è potente la matematica.
- L'espressività del calcolo meccanico: quanto sono potenti i calcolatori.
Bibliografia:
- Elliott Mendelson, Introduzione alla logica matematica, Boringhieri
- Yuri V. Matiyasevich, Hilbert's Tenth Problem, MIT Press
- Alan M. Turing, On Computable Numbers, with an Application to the Entscheidungsproblem, Proc. London Math. Soc. 42 (doi:10.1112/plms/s2-42.1.230)
