Trentesima lezione: Calcolabilità e Trattabilità, riepilogo ed esercizi sul capitolo ottavo

Questo blog si riferisce alla lezione che ho tenuto mercoledì 10 dicembre.

Nella lezione ho spiegato cosa è la Tesi di Church: "Ogni funzione calcolabile è calcolabile da una Macchina di Turing". Ho fatto vedere come l'inverso di questa affermazione ("Ogni funzione calcolabile da una Macchina di Turing è calcolabile") è ovviamente vera, e ho spiegato che la Tesi di Church è ritenuta vera dalla comunità scientifica (ed è alla base dell'informatica) e non ha mai trovato una refutazione (non è mai stata trovata una funzione calcolabile che non possa essere calcolata da una macchina di Turing). Ho spiegato anche perché non possa essere trovata una "dimostrazione" della Tesi di Church: essa richiederebbe di conoscere cosa sia una funzione calcolabile "generica", ma è proprio per capire cosa sia una funzione calcolabile "generica" è stato introdotto il concetto di Macchina di Turing...

Nella lezione ho trattato anche il concetto di funzione "trattabile" : funzione che non solo è calcolabile, ma ha ache almeno un programma che viene eseguito in "tempo polinomiale" (ossia non in "tempo esponenziale").

Ho slegato inoltre il concetto di macchina "deterministica" (una macchina di Turing che non ha due istruzioni diverse con lo stessa condizione) e di macchina "non-deterministica" (una macchina di Turing che ha istruzioni diverse con la stessa condizione).

E ho spiegato cosa siano le classi P e NP (entrambe sono classi di funzioni "trattabili", P è la classe delle funzioni che sono calcolabili in tempo polinomiale con macchina di Turing deterministica, NP è la classe delle funzioni che sono calcolabili in tempo polinomiale con macchina di Turing non-deterministica).

Ho mostrato infine come sia ovvio che P è inclusa in in NP, e ho spiegato che è un problema ancora aperto quello se NP sia inclusa in P. Dunque è aperto il problema "P=NP?".

Ventinovesima lezione: Macchina di Turing

Questo blog si riferisce alla lezione che ho tenuto martedì 9 dicembre.

Nella lezione ho continuato la spiegazione sulla macchina di Turing: 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.

Ventottesima lezione: esercizi e approfondimenti sul capitolo settimo, continuazione della spiegazione della Macchina di Turing

Questo blog si riferisce alla lezione che ho tenuto sabato 6 dicembre.

Nella prima parte della lezione ho fatto un riepilogo del capitolo 7 (trascurando la parte relativa all'algebra booleana e ai connettivi n-ari), e ho svolto alcuni esercizi:
- come scrivere in base 2 (ossia come successione finita di bit) un dato numero naturale; ad esempio "trentanove" in base 2 è la successione finita di bit 100111;
- qual è il numero rappresentato da una data successione finita di bit; ad esempio, la successione finita di bit 111010 è il numero "sessanta".

Nella seconda parte della lezione 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.

Ventisettesima lezione: la codificazione dei testi, la Macchina di Turing

Questo blog si riferisce alla lezione che ho tenuto giovedì 4 dicembre.

Nella prima parte della lezione 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 seconda parte 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).

Ventiseiesima lezione: la gradazione delle infinità, la codificazione

Questo post si riferisce alla lezione che ho tenuto ieri pomeriggio, 3 dicembre.

Nella lezione ho ripreso uno dei temi della lezione di sabato, ossia la scoperta (con un teorema dimostrato da G. Cantor) che ci sono insiemi infiniti non equipollenti, e dunque che ci sono diversi livelli di infinità.  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.

Ho poi spiegato 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.

Domande?

Chiarimenti?