COMPUTABILITA'

INF/01 - 6 CFU - 2° semestre

Docente titolare dell'insegnamento

DOMENICO CANTONE


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


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]


Altro materiale didattico

I lucidi delle lezioni e delle esercitazioni sono messi a disposizione degli studenti sul sito http://www.dmi.unict.it/~cantone/HomeComputabilita-17/itComputabilita.html



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.


PROVE IN ITINERE

L’esame finale può essere completato mediante due prove in itinere. La prima prova in itinere verterà sulla prima parte del corso e sarà offerta durante la seconda parte del periodo didattico in data concordata con gli studenti. La seconda prova in itinere verterà sulla seconda parte del corso e sarà offerta in occasione del primo appello di esami.

Le prove in itinere consistono in domande aperte che possono riguardare sia argomenti di natura teorica che soluzioni di problemi analoghi a quelli trattati nel corso


PROVE DI FINE CORSO

La prova scritta finale è costituita, di norma, da quattro domande aperte che possono riguardare sia argomenti di natura teorica che soluzioni di problemi analoghi a quelli trattati nel corso


ESEMPI DI DOMANDE E/O ESERCIZI FREQUENTI

http://www.dmi.unict.it/~cantone/ESAMI/ESAMI_COMPUTABILITA/Cmp-sample-2016.pdf




Apri in formato Pdf English version