Seminario: Da Gödel a Turing: limiti della dimostrabilità e della calcolabilità

Giovedì 30 maggio alle 16:00 in aula magna il prof. Domenico Cantone terrà un seminario dal titolo "Da Gödel a Turing: limiti della dimostrabilità e della calcolabilità". Di seguito l'abstract del seminario:

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.