Abstract
La "teoria della calcolabilità" di occupa di distinguere ciò che può essere calcolato per via automatica da ciò che invece non può essere calcolato per via automatica. I modelli di Von Neumann, Turing e Church servivano, prima ancora di poter disporre materialmente di strumenti di calcolo automatico, a ragionare sulla possibilità di risolvere (calcolare) automaticamente qualsiasi problema o meno. Con ragionamenti per nulla semplici si arriva così a dimostrare che esistono dei problemi che non possono essere risolti (la cui soluzione non può essere calcolata) attraverso strumenti automatici (come la macchina di Turing, ad esempio).
Quale impatto può avere questa prospettiva teorica novecentesca su un insegnamento elementare della matematica rinnovato? Nelle scuole primarie ancora le ore di matematica ruotano attorno al calcolo, e le operazioni in colonna, che sono uno dei più antichi esempi di algoritmo (si descrivono in un celebre trattato del matematico al-Khwarizmi dal cui nome deriva questo termine) costituiscono ancora per ogni alunno il primo contatto con la matematica, parte della biografia matematica di coloro che trovano in aula i docenti delle scuole secondarie. Nel seminario, con il quale il Seminario Enriques festeggia il giorno de pi greco, si offrono alcuni spunti su tale prospettiva, quale condizione di ogni proposta susseguente di innovazione didattica.
Nel libro Qual è il problema? (per la casa editrice Mimesis) ho affrontato alcuni temi relativi a problemi che invece sono calcolabili. Si potrebbe dire: per chi progetta algoritmi, i problemi non calcolabili non sono affatto interessanti! Piuttosto è interessante, nell'ambito dei problemi calcolabili, distinguere tra problemi facilmente (velocemente) calcolabili e problemi che, pur essendo calcolabili, richiedono tempi enormi (giorni, mesi, anni, milioni di anni, ...). Di questo si occupa l'analisi della complessità computazionale di un problema o di un algoritmo (da qui vengono fuori le classi di complessità P, NP, NP-completi, ...).
Nel seminario, con il quale il Seminario Enriques festeggia il giorno de pi greco, si riprendono queste questioni aggiungendo alcune riflessioni sulla sorprendente circostanza dei problemi non calcolabili.
Link identifier #identifier__85040-1Marco Liverani lavora nel campo della cybersecurity ed è professore incaricato di informatica presso il Dipartimento di Matematica e Fisica dell’Università degli Studi Roma Tre, dove ha insegnato Informatica 1 e ora Algoritmi e strutture di dati e Ottimizzazione combinatoria.
Link identifier #identifier__23163-2Locandina
This post is also available in:
Link identifier #identifier__186056-5
Eng