COMPUTABILITA' E COMPLESSITA'

Modulo COMPUTABILITA'

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

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]

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

3. Descrivere la tecnica della diagonalizzazione,