COMPUTABILITA'
Anno accademico 2023/2024 - Docente: Domenico CANTONERisultati di apprendimento attesi
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)
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à.
Modalità di svolgimento dell'insegnamento
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. Filippo Stanco
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
| Argomenti | Riferimenti 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 Markov | Cap. 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 matematica | Cap. 6.2-6.5 di 1) |
| 9 | Problemi semi-decidibili | Cap. 6.6 di 1) e materiale didattico integrativo |
| 10 | Insiemi ricorsivi e insiemi ricorsivamente enumerabili: Teorema di Rice e teorema di Rice-Shapiro | Cap. 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 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.
Esempi di domande e/o esercizi frequenti
http://www.dmi.unict.it/cantone/ESAMI/ESAMI_COMPUTABILITA/Cmp-sample-2016.pdf