Computabilità (macchine di Turing, funzioni ricorsive) e complessità (P vs NP).

Le questioni principali che affronteremo sono: 

1. quali funzioni possono essere calcolate da un computer? Quali problemi possono essere risolti?
2. quanto velocemente un computer può risolvere un problema?