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.
Nessun commento:
Posta un commento