COMPUTABILITA'

Anno accademico 2024/2025 - Docente: Vincenzo CUTELLO

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

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.
2	Generazione di funzioni URM-calcolabili: Funzioni calcolabili di base. Composizione. Ricorsione. Minimalizzazione.
3	Tesi di Church-Turing: Altri approcci alla computabilità. Funzioni ricorsive primitive e ricorsive generali. Macchine di Turing.
4	Sistemi di Post e di Markov
5	Enumerazione delle funzioni calcolabili: Enumerazione dei programmi URM. Metodo diagonale. Teorema s-m-n.
6	Programmi universali: Funzioni e programmi universali (e applicazioni). Operazioni effettive su funzioni calcolabili.
7	Problemi indecidibili in computabilità
8	Problemi indecidibili in altre aree della matematica
9	Problemi semi-decidibili
10	Insiemi ricorsivi e insiemi ricorsivamente enumerabili: Teorema di Rice e teorema di Rice-Shapiro

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.

Esempi di domande e/o esercizi frequenti

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

2. Si studi la decidibilità e la parziale decidibilità del seguente predicato unario (predicato dato)

3. Descrivere la tecnica della diagonalizzazione,

Corso di laurea magistrale in

Informatica