COMPUTABILITA' E COMPLESSITA'

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

Informazioni per studenti con disabilità e/o DSA

A garanzia di pari opportunità e nel rispetto delle leggi vigenti, gli studenti interessati possono chiedere un colloquio personale in modo da programmare eventuali misure compensative e/o dispensative, in base agli obiettivi didattici ed alle specifiche esigenze.

E' possibile rivolgersi anche al docente referente CInAP (Centro per l’integrazione Attiva e Partecipata - Servizi per le Disabilità e/o i DSA) del nostro Dipartimento, prof.ssa Patrizia Daniele.

La frequenza delle lezioni non è obbligatoria, ma per una piena comprensione degli argomenti del corso e delle tecniche risolutive illustrate essa è fortemente consigliata.

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.

A titolo esemplificativo, ecco alcuni esempi di domande d’esame:

1. Si stabilisca se una data funzione sia calcolabile.

2. Si enunci e si dimostri il teorema di parametrizzazione.

3.  Si dimostri l'esistenza di una funzione totale e calcolabile s: N --> N tale che W_{s(n)} ed E_{s(n)} siano uguali ad insiemi dati, per ogni numero naturale n.

4. Si enuncino i teoremi di Rice e di Rice-Shapiro.

5.  Si dimostri il teorema di Rice.

6. Si studi la decidibilità e la parziale decidibilità di un dato predicato e della sua negazione.

7. Si applichi la tecnica della diagonalizzazione per dimostrare l'esistenza di una funzione totale e non calcolabile soddisfacente certi dati vincoli.

8.  Si dimostri che se P(x) è un predicato unario parzialmente decidibile, allora esiste un predicato decidibile R(x,y) tale che P (x) <==> (∃y)R(x,y).

Nota: gli esercizi sopra riportati sono solo esempi; la prova potrà includere anche domande su altri argomenti del programma.