|
|
|
Logica e Informatica:Quello che i calcolatori possono e non possono fare.
Scopo del corso:Introdurre e discutere alcune relazioni (sia storiche che concettuali) tra logica matematica e informatica. In particolare tratteremo delle limitazioni dei processi di calcolo:
- esistono problemi che non possono essere risolti con alcun calcolatore?
- esistono problemi che, pur risolubili in teoria, richiederebbero per essere risolti più risorse di quelle disponibili nell'universo?
Se rimane tempo, si accennerà anche ai cosiddetti teoremi limitativi della logica matematica (teoremi di Gödel, Church, Tarski).
Libri di testo e altro materiale didattico.
Programma preliminare
Procedimenti effettivi.
Formalismi per la calcolabilità: macchine di Turing; funzioni calcolabili secondo Kleene-Gödel; cenni ad altri formalismi.
La tesi di Church.
Esistenza di funzioni non calcolabili: il problema della fermata.
Riduzioni tra problemi. Problemi completi.
Problemi decidibili e semidecidibili.
Complessità di calcolo delle funzioni: passi di calcolo, spazio di lavoro.
Classi di complessità nel tempo e nello spazio.
Le classi PTIME e NPTIME.
Riduzioni polinomiali; problemi completi.
Il problema se PTIME = NPTIME.
I seguenti argomenti saranno trattati se vi sarà tempo e interesse:
Sistemi formali al primo ordine. Modelli. Completezza.
Aritmetica.
Cenni ai teoremi limitativi: teoremi di Gödel, Church e Tarski.
Prerequisiti:
Aritmetica elementare. Concetto di funzione. Concetto di cardinalità di un insieme.
Concetto intuitivo di algoritmo. Utile una piccola esperienza di programmazione.
Capacità richieste: Buona capacità di astrazione; manipolazione simbolica; mancanza di vertigini.