COMPUTABILITA'

Conoscenza e capacità di comprensione (knowledge and understanding): saranno acquisite le conoscenze relative alla formalizzazione della nozione di algoritmo, mediante il modello delle macchine a registri illimitati (URM: Unlimited Register Machines), saranno esibiti esempi di funzioni non calcolabili e di predicati indecidibili, 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).

Capacità  di applicare conoscenza e comprensione (applying knowledge and understanding):  saranno acquisite le capacità per costruire funzioni non-calcolabili mediante diagonalizzazione e per verificare se un dato predicato è (semi-)decidibile oppure no.

Autonomia di giudizio (making judgements): lo studente sarà in grado di valutare in maniera informale la (semi-)decidibilità o meno di un assegnato problema computazionale.

Abilità comunicative (communication skills): saranno acquisite le necessarie abilità comunicative ed un'adeguata appropriatezza espressiva nella comunicazione di problematiche inerenti gli studi di computabilità, anche ad interlocutori non esperti.

Capacità  di apprendimento (learning skills): lo studente avrà la capacita di adattare le conoscenze acquisite anche a nuovi contesti, nonché di aggiornarsi attraverso la consultazione delle fonti specialistiche del settore della computabilità.

Lezioni frontali

Qualora l'insegnamento venisse impartito in modalità mista o a distanza potranno essere introdotte le necessarie variazioni rispetto a quanto dichiarato in precedenza, al fine di rispettare il programma previsto e riportato nel syllabus.

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.

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]

L’esame finale è essenzialmente scritto. La verbalizzazione potrà essere preceduta da una breve discussione sul compito scritto e, nei casi dubbi, da una breve verifica orale.

La verifica dell'apprendimento potrà essere effettuata anche per via telematica, qualora le condizioni lo dovessero richiedere.

Per l'attribuzione del voto finale si seguiranno di norma i seguenti criteri:

- non approvato: lo studente non ha ancora acquisito i concetti di base e non riesce a svolgere in modo adeguato gli esercizi.

- 18-23: lo studente dimostra una conoscenza essenziale dei concetti di base; le capacità espositive e di collegamento tra i contenuti sono limitate, ma riesce a risolvere esercizi semplici.

- 24-27: lo studente dimostra una buona conoscenza dei contenuti del corso, sa esporli in modo chiaro e collegarli tra loro; risolve gli esercizi con pochi errori.

- 28-30 e lode: lo studente ha acquisito una conoscenza completa dei contenuti, li espone con chiarezza e spirito critico e risolve gli esercizi in modo accurato e senza errori.

Gli studenti con disabilità e/o DSA dovranno contattare con sufficiente anticipo rispetto alla data dell'esame il docente, il referente CInAP del DMI (prof.ssa Daniele) e il CInAP per comunicare che intendono sostenere l'esame fruendo delle opportune misure compensative.