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.