MATEMATICA E INFORMATICAMatematicaAnno accademico 2023/2024

1014144 - COMPUTABILITA'

Docente: Domenico CANTONE

Risultati 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): 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à.

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

 ArgomentiRiferimenti testi
1Funzioni 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
2Generazione di funzioni URM-calcolabili: Funzioni calcolabili di base. Composizione. Ricorsione. Minimalizzazione.Cap. 2.1-2.5 di 1) e materiale didattico integrativo
3Tesi 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
4Sistemi di Post e di MarkovCap. 3.5 di 1)
5Enumerazione delle funzioni calcolabili: Enumerazione dei programmi URM. Metodo diagonale. Teorema s-m-n.Cap. 4.1-4.4 di 1) e materiale didattico integrativo
6Programmi universali: Funzioni e programmi universali (e applicazioni). Operazioni effettive su funzioni calcolabili.Cap. 5.1-5.3 di 1) e materiale didattico integrativo
7Problemi indecidibili in computabilitàCap. 6.1 di 1) e materiale didattico integrativo
8Problemi indecidibili in altre aree della matematicaCap. 6.2-6.5 di 1)
9Problemi semi-decidibiliCap. 6.6 di 1) e materiale didattico integrativo
10Insiemi ricorsivi e insiemi ricorsivamente enumerabili: Teorema di Rice e teorema di Rice-ShapiroCap. 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


English version