2012
2012
Sei collegato come utente non registrato
Riepilogo dell'insegnamento: Computability
| Informazioni generali | |||
| Corso di Laurea | Informatica | Percorso | Computer Science and Technology |
|---|---|---|---|
| CFU | 6 | Università | TRENTO |
| Ore di didattica frontale per CFU | 8 | Settore Scientifico Disciplinare | MAT/01 |
| Commento | Introduce students to computability theory | ||
6 cfu così ripartiti nelle aree:
- 6 CFU nell'area MAT - Crediti di MATEMATICA
Sillabo dell'insegnamento
- MAT - Crediti di MATEMATICA
-
MAT/01 - Logica Matematica
Programming languages and their computational power: Lambda calculus, "for" and "while" languages. -
MAT/01 - Logica Matematica
Classical results: padding lemma, s-m-n theorem, Kleene's normal form, fixed point theorem, Rice's theorem, Rice-Shapiro theorem -
MAT/01 - Logica Matematica
m-reductions -
MAT/01 - Logica Matematica
Enumeration of programs, Universal programs -
MAT/01 - Logica Matematica
Logical characterization of recursive functions: primitive and general recursion. -
MAT/01 - Logica Matematica
Problem classes: decidable, undecidable, semi-decidable; Church's Thesis
(*) Le sottoaree con asterisco sono quelle che il GRIN ritiene essenziali
