“Incompletezza e indecidibilità in matematica e informatica”
Venerdì 11 Febbraio 2022, ore 15:30 - Aula 1AD100 e Zoom - Antonino Salibra
Conferenza “Patavina Mathesis”
Abstract
Nel 1931 il logico austriaco Kurt Gödel pubblicò il suo teorema di incompletezza, uno dei risultati più rilevanti della matematica del ventesimo secolo. Il teorema stabilisce che in ogni sistema formale sufficientemente espressivo esiste una proposizione vera che non può essere dimostrata. Se inoltre il sistema è non contraddittorio, allora la sua propria non contraddittorietà non può essere provata nel sistema stesso. In questo seminario, dopo un breve inquadramento storico della matematica di inizio novecento, presenteremo la dimostrazione più semplice del risultato di Gödel.
Analizzeremo anche alcune conseguenze del teorema di Gödel in matematica ed in informatica, tra cui l’indecidibilità del problema della fermata. Alan Turing infatti provò nel 1936 che non esiste un algoritmo generale per risolvere il problema della fermata per tutte le possibili coppie programma-input.
