giovedì 14 gennaio 2016

Tipologia delle domande sul capitolo 8 e sul capitolo 10.

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:


  • 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







domenica 10 gennaio 2016

Tipologia delle domande sul capitolo 5

Rispondo alla richiesta di scrivere le tipologie delle domande sul capitolo 5, quelle spiegate in una delle lezioni del mese di dicembre. Comunque, le tipologie delle domande (e le risposte a tale domande) si possono trovare anche nel capitolo 10 del volume (II edizione).

1. Cos'è una proposizione del primo ordine.

2. Cos'è una formula del primo ordine (ciò che si ottiene da una proposizione del primo ordine mediante un processo di "astrazione" d ogni contenuto extra-logioco...)

3. Cos'è un sistema di valori per le variabili libere di una formula del primo ordine.

4. Cos'è un modello, e cos'è un contromodello, di una formula del primo ordine.

5. Passare da una proposizione del primo ordine a una formula del primo ordine, e passare da una formula del primo ordine e da un sistema di valori per le sue variabili libere a una proposizione del primo ordine (v. il volume, da pagina 247 a pagina 252) .

6. Cos'è la chiusura esistenziale, e cos'è la chiusura universale, di una formula del primo ordine.

7. Quando una formula del primo ordine è detta soddisfacibile,   o verità logica, o falsificabile, o falsità logica..Qual è la negazione di soddisfacibile, o di verità logica, o di falsificabile , o di falsità logica,

8. Cosa vuol dire che una formula del primo ordine A è conseguenza logica di un insieme  di formule M del primo ordine.

9. Cosa dice il teorema di incompletezza della logica.

10. Cosa dice il teorema di completezza della logica del primo ordine.