Cosa è la macchina di Turing?

Risponde Pierluigi Crescenzi del Dipartimento di Matematica e Informatica ‘Ulisse Dini’

Una macchina di Turing è un dispositivo che può trovarsi in un certo numero di stati, ha a disposizione un foglio a quadretti grande a piacere e, in ogni istante, si trova posizionato su un quadretto specifico, in cui c’è scritto un simbolo. Sulla base dello stato in cui si trova e del simbolo letto nel quadretto al momento considerato, la macchina decide eventualmente di sostituire tale simbolo con un altro simbolo, di spostare la sua attenzione su un altro quadretto (adiacente a quello al momento considerato) e di cambiare il proprio stato. La specifica di un tale dispositivo si ispira al modo naturale degli esseri umani di eseguire dei calcoli (si pensi, per esempio, all’operazione di somma di due numeri interi, così come ci viene normalmente insegnata alla scuola elementare).

Pur nella sua semplicità, una macchina di Turing è capace di fare le somme, le moltiplicazioni e l’elevamento a potenza. In altre parole, la macchina di Turing,  è in grado di fare della matematica ragionevolmente complicata e, pertanto, di risolvere problemi anche molto complicati.

Turing ne capì appieno le potenzialità al punto da introdurre il concetto di macchina di Turing universale, che oggi chiameremmo sistema operativo (come, ad esempio, Linux e MacOS X). Tale macchina è in grado di leggere una qualunque altra macchina di Turing e simularne l’esecuzione con input una qualunque sequenza finita di simboli. Essa si può considerare, a tutti gli effetti, la madre del software dei nostri odierni computer, siano essi desktop, laptop, tablet o smartphone. Gli enormi sviluppi tecnologici che hanno fatto seguito, senza modificare troppo l’impianto dato da Turing, hanno principalmente consentito la progettazione e lo sviluppo di computer che entrassero nelle nostre borse e perfino nelle nostre tasche.

 

Hai ancora domande su questo argomento? Scrivi a chiediloaunifi@unifi.it