Stavo cercando un libro per approfondire la conoscenza sulla Macchina di Touring e mi chiedevo se qualcuno mi potesse dare qualche suggerimento
*Turing
Prova a partire dall’articolo originale di Turing. Si chiama ON COMPUTABLE NUMBERS, WITH AN APPLICATION TO THE ENTSCHEIDUNGSPROBLEM, ci sono varie copie in internet, tipo la seguente
Ti consiglio di leggerti le prime sezioni. Poi ad un certo punto diventa molto formale e matematico (quando va a definire la macchina universale di Turing e spiega il linguaggio utilizzato). Quella parte è meno utile.
La parte più importante è capire il ragionamento che ha portato alla definizione della macchina e ai suoi vari componenti.
Poi nel corso degli anni il modello è stato studiato rispetto a varie tipologie di modifiche, ed è stata introdotta la Gerarchia di Chomsky che fondamentalmente va a definire delle macchine meno potenti della macchina di Turing, ed associa ad ogni macchina un particolare tipo di Linguaggio formale.
La cosa figa di questo paper è che non solo introduce un modello teorico, ma cerca di motivare perché tale modello è interessante, e cosa è possibile fare con il modello. In queste neanche 40 pagine, Turing ha catturato in modo estremamente “fisico” il concetto astratto di computazione.
Btw, discussione più relativa ad informatica teorica, quindi sposto.
Side Note: consiglio sempre di andarsi a leggere i paper originale, direttamente dalla “sorgente”. Ogni tanto sono difficili da leggere, ma allo stesso tempo è come se si “parlando” direttamente con la persona in merito (Turing, in questo caso). Questa ricchezza è un po’ persa da trattazioni successiva che, seppur a volte più comprensibili e dunque ncessarie ed utili, perdono la sensazione di star leggendo l’autore originale.
Detto questo, ci sono situazioni in cui gli autori originali sono abbastanza illegibili, ed è quasi necessario andarsi a leggere cose più processate sviluppate dopo. Turing in questo caso è ottimo da leggere perché è sempre stato molto chiaro.
1 Like