COMPUTABILITA'

Anno accademico 2018/2019 - 1° anno - Curriculum APPLICATIVO, Curriculum DIDATTICO e Curriculum TEORICO
Docente: Domenico CANTONE
Crediti: 6
SSD: INF/01 - Informatica
Organizzazione didattica: 150 ore d'impegno totale, 103 di studio individuale, 35 di lezione frontale, 12 di esercitazione
Semestre:

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

 ArgomentiRiferimenti testi
1Funzioni 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 
2Generazione di funzioni URM-calcolabili: Funzioni calcolabili di base. Composizione. Ricorsione. Minimalizzazione.Cap. 2.1-2.5 di 1) e materiale didattico integrativo 
3Tesi 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 
4Sistemi di Post e di MarkovCap. 3.5 di 1) 
5Enumerazione delle funzioni calcolabili: Enumerazione dei programmi URM. Metodo diagonale. Teorema s-m-n.Cap. 4.1-4.4 di 1) e materiale didattico integrativo 
6Programmi universali: Funzioni e programmi universali (e applicazioni). Operazioni effettive su funzioni calcolabili.Cap. 5.1-5.3 di 1) e materiale didattico integrativo 
7Problemi indecidibili in computabilitàCap. 6.1 di 1) e materiale didattico integrativo 
8Problemi indecidibili in altre aree della matematicaCap. 6.2-6.5 di 1) 
9Problemi semi-decidibiliCap. 6.6 di 1) e materiale didattico integrativo 
10Insiemi ricorsivi e insiemi ricorsivamente enumerabili: Teorema di Rice-ShapiroCap. 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