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.




mercoledì 23 dicembre 2015

Parti omesse nei capitoli 6 e 7 // Tipologia dl domande sul capitolo 6 e sul capitolo 7

Sono state omesse le seguenti parti del libro nel capitolo 6 e nel capitolo 7 (e pertanto su tali parti non ci saranno domande obbligatorie nelle prove di esame):

6.3.2..3 Intersezione di un insieme non vuoto di insiemi
6.3.2.4. Riunione su un insieme
6.3.3.2 Le definizioni induttive
6.4.3. Principio di estensionalità per le funzioni
6.4.4. Proprietà e relazioni su insiemi
6.4.5.Relazioni d'ordine e insiemi ordinati

l'intero 7.2. Algebra di Boole

l'intero 7.3. I possibili connettivi proposizionali e la loro definibilità .


Tipologia di domande sul capitolo 6 (si veda anche le domande presenti nel capitolo 10):

a) come le  principali relazioni tra classi (inclusione, condivisione di elementi, ...) vengono lette in logica classica,
b) il principio di estensionalità
c) il principio di comprensione,
c) l'antinomia di Russell
d) le principali operazioni sugli insiemi
e) saper indicare gli elementi dell'intersezione, della unione e del prodotto cartesiano di due insiemi dati, e della potenza di un insieme dato
f) i numeri naturali e la loro definizione induttiva
g) grafo e rango di una funzione
h) funzione totale, invettiva, suriettiva; corrispondenza biunivoca
i) insiemi equipotenti; esistenza di insiemi infiniti non equipotenti (teorema di Cantor) .

Tipologia di domande sul capitolo 7 (si veda anche le domande presenti nel capitolo 10):
a) successioni finite di bit
b) teorema che permette la rappresentazione dei numeri naturale in una base qualunque maggiore o uguale a 2;
c) saper rappresentare un numero in base due;
d) saper dire quale numero naturale è rappresentato da una data successione finita di bit;
e) cos'è una codificazione
f) come si codificano gli alfabeti
g) come si codificano le successioni finite di numeri naturali
h) come si codificano i test.







Lezione 29 e lezione 30 (21 e 22 dicembre): La Macchina di Turing

In queste due lezioni ho continuato la spiegazione del concetto di macchina di Turing: il puntatore della macchina, gli stati della macchina (un insieme finito, che contiene almeno lo stato iniziale e lo stato finale), le azioni che la macchina sa compiere, istruzione per una macchina di Turing, programma di una macchina di Turing (un insieme finito di istruzioni tale che almeno una istruzione comincia con lo stato iniziale, almeno una istruzione termina con lo stato finale e ogni stato compare in almeno una istruzione), configurazione di una macchina di Turing, computazione di una macchina di Turing.

Ho spiegato che ogni macchina di Turing si identifica con il suo programma: ossia, due Macchine di Turing che hanno uguale programma sono uguali.


Ho spiegato anche cosa vuol dire che una funzione numerica è calcolata da macchina di Turing.

venerdì 18 dicembre 2015

Lezione 28 (15 dicembre 2015): La codificazione. La Macchina di Turing


Ho spiegato in questa lezione il concetto di "codificazione" : una codificazione degli oggetti di un insieme X è una funzione da X all'insieme dei numeri naturali la quale è totale, iniettavi, calcolabile e ha una funzione inversa che è essa stessa calcolabile.

Successivamente,  ho spiegato perché ogni testo può essere codificato mediante un numero che poi viene rappresentato in base 2 come successione finita di bit. In sintesi:
- un testo è una successione finita di caratteri, costruito utilizzando un "alfabeto" finito (i caratteri che corrispondono ai tasti di una tastiera) e questo "alfabeto" può essere codificato (ad esempio, attraverso i codici ASCII),
- pertanto un testo (codificato l'alfabeto) diviene una successione finita di numeri naturali,
- per un importante teorema matematico, è possibile dare una codificazione delle successioni finite di numeri naturali (ossia è possibile rappresentare mediante un numero una qualunque successione di numeri naturali, in maniera reversibile),
- dunque, il testo - divenuto successione finita di numeri naturali - è codificato mediante un numero naturale che poi viene rappresentato in base 2 come una successione finita di bit ("digitalizzazione").

Lo stesso procedimento può essere fatto anche per i suoni e le immagini.


Nella parte finale della lezione ho iniziato a spiegare il concetto di Macchina di Turing, e in particolare il concetto di "nastro di una macchina di Turing" (vedi il testo).

Lezione 26 e lezione 27 (lunedì 14 dicembre 2015): Funzioni. Insiemi equipotenti. Infinito. Le successioni finite di bit.

Ho trattato, nelle due lezioni ì, i seguenti temi:
- la nozione di funzione entro la concezione classica degli insiemi, e le nozioni di "rango di una funzione" (un sottoinsieme del condominio, costituite dai valori assegnati dalla funzione quando è applicata agli elementi del dominio) e di "grafo di una funzione" (un sottoinsieme del prodotto cartesiano del dominio e del condominio, una sorta di "tabella" della funzione);


-  le proprietà che può avere una funzione, e in particolare le nozioni di "funzione totale", "funzione iniettiva", "funzione suriettiva" e "funzione biettiva" (o "corrispondenza biunivoca"); si tratta di nozioni che hanno una notevole importanza nel nostro trattare con le classi e gli insiemi;

la nozione di "insieme equipotenti" (due insiemi sono equipotenti  quando esiste tra loro una corrispondenza biunivoca, ossia intuitivamente quando "hanno lo stesso "numero di elementi"), e il grande risultato ottenuto da Canto con la scoperta che "ci sono insieme infiniti non equipotenti" ossia che si può considerare una "gradazione" degli insieme infiniti così come c'è una "gradazione" degli insieme finiti.

La dimostrazione di Cantor mostra in particolare che non ci può essere alcuna corrispondenza biunivoca (biezione) tra un insieme X e la sua potenza (l'insieme delle parti di X). Dunque, se X è un insieme infinito, la potenza di X è un insieme infinito di infinità maggiore di quella di X, e la potenza della potenza di X ha un'infinità maggiore di quella della potenza di X, ecc.

Si tratta di un risultato di grande importanza per la cultura in generale, oltre che per la matematica e la logica.

Successivamente, ho cominciato la trattazione della risposta alla domanda "perché tante cose, tantissime cose,  possono essere codificate mediante  successioni finite di bit ("digitalizzate")?"

Ho spiegato il concetto di "successione finita di bit" (le successioni finite di bit di lunghezza k sono 2 elevato a k, sono la potenza k-esima di 2).

Ho poi mostrato perché (per quale importante teorema matematico) i numeri naturali possono essere rappresentati mediante successioni finite di bit. è importante conoscere l'enunciato di quel teorema che permette anche la rappresentazione a noi familiare dei numeri naturali mediante successioni finite di numeri minori di 10. è importante saper rappresentare un numero (noni troppo grande!) mediante una successione finita di bit, e saper dire quale numero è rappresentato da una data successione finita di bit.