Ecco la tipologia delle domande sul capitolo 8, la cui spiegazione si è conclusa nella lezione di lunedì 11 gennaio e alla prima ora della lezione di martedì 12 gennaio:
Il capitolo 9 è stato trattato solo nella sua parte iniziale. Possibili domande:
- Nastro della macchina di Turing
- Puntatore della macchina di Turing
- Rappresentazione dei numeri sul nastro di una macchina di Turing
- Sati di una macchina di Turing
- Azioni che deve saper fare una macchina di Turing
- Come è fatta un'istruzione di una macchina di Turing
- Cos'è un programma di una macchina di Turing
- Identificazione tra macchina di turing e suo programma.
- Configurazione e di una macchina di Turing
- Computazione di una macchina di Turing
- Calcolo di una funzione numerica da parte di una macchina di Turing
- Funzioni Turing-calcolabili (o ricorsive)
- Tesi di Church e suo commento
- Modificabilità delle macchine di Turing
- Esistenza di funzioni non calcolabili
- Macchina di Turing deterministica e macchina di Turing non-deterministica
- Programmi trattabili (polinomiali)
- Il problema P=NP
- La macchina di Turing è modello della nostra mente?
Il capitolo 9 è stato trattato solo nella sua parte iniziale. Possibili domande:
- Assiomatizzabilità delle proposizioni logiche vere
- Assiomatizzabilità delle verità logiche del primo ordine