COMPUTABILITA'

Anno accademico 2015/2016 - 1° anno - Curriculum C
Docente: Domenico CANTONE
Crediti: 6
SSD: INF/01 - Informatica
Organizzazione didattica: 150 ore d'impegno totale, 102 di studio individuale, 48 di lezione frontale
Semestre:

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

Obiettivi:

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).

 

Programma:

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
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 MarkovCap. 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 matematicaCap. 6.2-6.5 di 1) 
9*Problemi semi-decidibiliCap. 6.6 di 1) e materiale didattico integrativo 
10*Insiemi ricorsivi e insiemi ricorsivamente enumerabili: Teorema di Rice-ShapiroCap. 7.1-7.2 di 1) e materiale didattico integrativo 
* Conoscenze minime irrinunciabili per il superamento dell'esame.

N.B. La conoscenza degli argomenti contrassegnati con l'asterisco è condizione necessaria ma non sufficiente per il superamento dell'esame. Rispondere in maniera sufficiente o anche più che sufficiente alle domande su tali argomenti non assicura, pertanto, il superamento dell'esame.

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