Home » Archivo » Archvio 2009 » Computabilità e algoritmi (Mod. A) - 2009/2010

Laurea Magistrale

Salta il menu di secondo livello

Computabilità e algoritmi (Mod. A) - 5 CFU - A.A. 2009/2010

Link al sito del corso

Insegnante

Prof. Paolo Baldan

Periodo

I anno - 2 trimestre | 11/01/2010 - 12/03/2010

Curriculum:

Ore: 32 Frontali, 0 Laboratorio, 8 Esercizi

Torna su ▲

Programma del Corso

Il corso svilupperà i seguenti temi:

- Algoritmi ed il concetto di procedimento effettivo. Macchine a registri (URM). Funzioni parziali ricorsive (sostituzione, ricorsione, minimalizzazione). Modelli funzionali. Equivalenze tra modelli di calcolo. Universalità dei modelli di calcolo. Tesi di Church.

- Enumerazione delle funzioni calcolabili. Esistenza di funzioni non calcolabili: il metodo della diagonalizzazione. Il teorema del parametro. Programmi universali.

- Problemi decidibili, indecidibili e semidecidibili. Indecidibilità del problema della fermata. Metodo di riduzione. Esempi di altri problemi indecidibili.

- Insiemi ricorsivi e ricorsivamente enumerabili. Insiemi produttivi, creativi e semplici. Teoremi di Rice e di Rice-Shapiro.

- Funzionali. Definizioni ricorsive. Ordinamenti parziali, funzioni monotone e punti fissi. Funzionali ricorsivi. Relazione tra
continuità e ricorsività. Il teorema di Myhill-Sheperdson. Primo teorema di ricorsione. Secondo teorema di ricorsione.

Prerequisiti: - -

Propedeuticità:

Ausili Didattici:

Testi di Riferimento: Nigel Cutland "Computability. An Introduction to Recursive Function Theory." Cambridge University Press.

Torna su ▲