Lezione 28, mercoledì 13 dicembre 2017 // Macchina di Turing

Nella lezione di oggi continuerò la spiegazione del concetto di Macchina di Turing, iniziata ieri. 

Mostrerò poi come ogni macchina di Turing si identifica con il suo programma: ossia, due Macchine di Turing che hanno uguale programma sono uguali.

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

Infine, mostrerò come ogni Macchina di Turing possa essere concepita come un concetto matematico e possa essere codificata. 

Lezione 27, martedì 12 dicembre 2017 // Macchina di Turing

In questa lezione spiegherò il concetto di Macchina di Turing, e in particolare:

•  il "nastro” di una Macchina di Turing ,
• il “puntatore” di una Macchina di Turing,
• gli “stati” di una Macchinadi Turing  (un insieme finito, che contiene almeno lo stato iniziale e lo stato finale),
• le “azioni” che la Macchina di Turing sa compiere,
• la forma delle “istruzioni” per  una Macchina di Turing,
• il “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),
• la “configurazione” di una Macchina di Turing,
• la “computazione” di una Macchina di Turing.

Lezione 26, lunedì 11 dicembre 2017 // Codificazione

Spiegherò 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,  spiegherò 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.

Infine, darò una breve sintesi degli altri temi del capitolo 7 (Algebra di Boole, Connettivi n-ari).

Lezione 25, mercoledì 6 dicembre 2017 // Successioni finite di bit, rappresentazione dei numeri mediante successioni finite di bit

Nella lezione odierna inizierò  la trattazione della risposta alla domanda "perché tante cose, tantissime cose,  possono essere codificate mediante  successioni finite di bit ("digitalizzate")?"

Spiegherò 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).

Mostrerò poi 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.

Lezione 24, martedì 5 dicembre 2017 // Funzioni, insiemi equipotenti, infinito.

Nella lezione di oggi tratterò  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 "insiemi 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 Cantor 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.