Da Gödel a Turing: limiti della dimostrabilità e della calcolabilità
Giorno 26 marzo 9 aprile 2024, con inizio alle ore 14:30, presso l'Aula T del DFA, il Prof. Domenico Cantone (DMI UniCT) terrà un seminario dal titolo Da Gödel a Turing: limiti della dimostrabilità e della calcolabilità.
Il seminario è proposto dal Prof. Giuseppe Falci nell'ambito delle attività del National Quantum Science and Technology Institute (NQSTI).
Tutte le persone interessate sono invitate a partecipare.
Abstract. Il programma di Hilbert, elaborato nei primi anni venti del XX secolo in risposta alla crisi dei fondamenti della matematica causata da antinomie e paradossi emersi all'inizio dello stesso secolo, mirava a fornire una base rigorosa per la matematica mediante sistemi assiomatici la cui consistenza fosse dimostrabile internamente. Dopo averne delineato i principi fondamentali, vengono presentati i celebri teoremi di incompletezza di Gödel, i quali impongono forti limiti alla realizzabilità del programma stesso. Infatti, in ogni sistema assiomatico sufficientemente complesso, esistono proposizioni che non possono essere né dimostrate né refutate all'interno del sistema stesso (primo teorema di incompletezza). Inoltre, se il sistema è consistente, non è possibile dimostrare la sua consistenza all'interno del sistema stesso (secondo teorema di incompletezza). La seconda parte del seminario affronterà il problema della decisione per la logica del primo ordine, formulato da Hilbert e Ackermann nel 1928. In particolare, dopo aver illustrato la formalizzazione del concetto di algoritmo, elaborata da Alan Turing nel 1936 tramite le sue celebri "macchine", sarà esaminata l'indecidibilità del "Problema della Fermata" (Halting Problem), che riguarda la possibilità di determinare se una macchina di Turing, dato un input finito, terminerà la sua esecuzione o continuerà all’infinito. Dall'indecidibilità del "Problema della Fermata" segue direttamente l'indecidibilità della logica del primo ordine, in quanto il funzionamento delle macchine di Turing può essere formalizzato all'interno della logica del primo ordine.
Bio. Domenico Cantone è dal 1990 professore ordinario di Informatica, prima all'Università di L'Aquila e dal 1991 all'Università di Catania, dove si è laureato in Matematica nel 1982. Sotto la supervisione di Jacob T. Schwartz, ha conseguito presso la New York University il Master of Science (nel 1985) e il Ph.D. in Computer Science (nel 1987). È (co)autore di 4 monografie e di oltre 250 tra articoli su riviste internazionali e su atti di conferenze internazionali e nazionali. I suoi principali campi di interesse includono: teoria computabile degli insiemi, logica computazionale e deduzione automatica, problema dello string matching, teoria delle scelte sociali e, più recentemente, algoritmi quantistici.
Images credits: Diego Queiroz - Own work, CC BY-SA 3.0, https://commons.wikimedia.org/w/index.php?curid=9860332 ; Turing machine, by Tom Dunne, 2002.