COMPUTABILITA'
Anno accademico 2019/2020 - 1° annoCrediti: 6
Organizzazione didattica: 150 ore d'impegno totale, 103 di studio individuale, 35 di lezione frontale, 12 di esercitazione
Semestre: 2°
Obiettivi formativi
La computabilità, o calcolabilità, studia le funzioni (e i problemi) che possono essere calcolate (ovvero risolti) mediante un procedimento meccanico, prescindendo dalla quantità, purché finita, di risorse necessarie di spazio/tempo.
L’obiettivo primario è dunque la formalizzazione della nozione di algoritmo, mediante modelli di calcolo effettivi. Come modello di calcolo primario sarà adottato quello delle macchine a registri illimitati (URM: Unlimited Register Machines), ma verranno anche presentati velocemente altri modelli di calcolo, quale quello delle macchine di Turing e quello delle funzioni ricorsive generali. Tali modelli (e anche tutti gli altri sinora proposti) risultano essere equivalenti in termini di potenza, nel senso che una funzione è calcolabile in uno dei modelli se e solo se lo è in tutti gli altri. Ciò fa ritenere che il modello di calcolo delle macchine a registri illimitati catturi perfettamente il concetto astratto di algoritmo (tesi di Church-Turing).
Così come una funzione si dice calcolabile se tutti i suoi valori possono essere calcolati algoritmicamente, un problema o predicato si dirà decidibile se può essere risolto mediante un algoritmo.
Utilizzando una enumerazione effettiva delle macchine URM (ispirata alla codifica di Gödel) ed il metodo diagonale di Cantor, saranno esibiti esempi di funzioni non calcolabili e di predicati indecidibili. Questi ultimi, in particolare, comprendono parecchi problemi riguardanti l’esito dell’esecuzione di programmi di calcolatori.
La nozione di decidibilità sarà generalizzata a quella di semi-decidibilità e saranno fornite tecniche per verificare se un dato predicato è (semi-)decidibile oppure no (tecnica della riduzione, teoremi di Rice e di Rice-Shapiro, teorema s-m-n).
Modalità di svolgimento dell'insegnamento
Lezioni frontali
Prerequisiti richiesti
- Elementi di matematica discreta
- Concetto intuitivo di algoritmo
- Elementi di logica matematica
Frequenza lezioni
Per una piena comprensione degli argomenti del corso e delle tecniche risolutive illustrate, la frequenza delle lezioni è fortemente consigliata.
Contenuti del corso
Funzioni calcolabili: Algoritmi, procedure effettive. Modello URM: Unlimited Register Machines. Funzioni URM-calcolabili. Predicati e problemi decidibili. Calcolabilità su altri domini.
Generazione di funzioni URM-calcolabili: Funzioni calcolabili di base. Composizione. Ricorsione. Minimalizzazione.
Tesi di Church-Turing: Altri approcci alla computabilità. Funzioni ricorsive primitive e ricorsive generali. Macchine di Turing. (Sistemi di Post e di Markov)
Enumerazione delle funzioni calcolabili: Enumerazione dei programmi URM. Metodo diagonale. Teorema s-m-n.
Programmi universali: Funzioni e programmi universali (e applicazioni). Operazioni effettive su funzioni calcolabili.
Decidibilità, indecidibilità e semi-decidibilità: Problemi indecidibili in computabilità e in altre aree della matematica. Teorema di Rice. Problemi semi-decidibili.
Insiemi ricorsivi e insiemi ricorsivamente enumerabili: Teorema di Rice-Shapiro.
Testi di riferimento
1) N.J. Cutland. Computability: an introduction to recursive function theory, Cambridge University Press, Cambridge - UK, 1986. [Testo principale]
2) M.D. Davis, R. Sigal, E.J. Weyuker. Computability, Complexity, and Languages: Fundamentals of Theoretical Computer Science, Academic Press, New York, 1994. [Lettura consigliata]
Programmazione del corso
Argomenti | Riferimenti testi | |
---|---|---|
1 | Funzioni calcolabili: Algoritmi, procedure effettive. Modello URM: Unlimited Register Machines. Funzioni URM-calcolabili. Predicati e problemi decidibili. Calcolabilità su altri domini. | Cap. 1.1-1.5 di 1) e materiale didattico integrativo |
2 | Generazione di funzioni URM-calcolabili: Funzioni calcolabili di base. Composizione. Ricorsione. Minimalizzazione. | Cap. 2.1-2.5 di 1) e materiale didattico integrativo |
3 | Tesi di Church-Turing: Altri approcci alla computabilità. Funzioni ricorsive primitive e ricorsive generali. Macchine di Turing. | Cap. 3.1-3.4, 3.6 e 3.7 di 1) e materiale didattico integrativo |
4 | Sistemi di Post e di Markov | Cap. 3.5 di 1) |
5 | Enumerazione delle funzioni calcolabili: Enumerazione dei programmi URM. Metodo diagonale. Teorema s-m-n. | Cap. 4.1-4.4 di 1) e materiale didattico integrativo |
6 | Programmi universali: Funzioni e programmi universali (e applicazioni). Operazioni effettive su funzioni calcolabili. | Cap. 5.1-5.3 di 1) e materiale didattico integrativo |
7 | Problemi indecidibili in computabilità | Cap. 6.1 di 1) e materiale didattico integrativo |
8 | Problemi indecidibili in altre aree della matematica | Cap. 6.2-6.5 di 1) |
9 | Problemi semi-decidibili | Cap. 6.6 di 1) e materiale didattico integrativo |
10 | Insiemi ricorsivi e insiemi ricorsivamente enumerabili: Teorema di Rice-Shapiro | Cap. 7.1-7.2 di 1) e materiale didattico integrativo |
Verifica dell'apprendimento
Modalità di verifica dell'apprendimento
L’esame finale è essenzialmente scritto. La verbalizzazione sarà preceduta da una breve discussione sul compito scritto e, nei casi dubbi, da una breve verifica orale.
Esempi di domande e/o esercizi frequenti
http://www.dmi.unict.it/~cantone/ESAMI/ESAMI_COMPUTABILITA/Cmp-sample-2016.pdf