Cosa diavolo è una Macchina di Turing?

Articolo in lingua original di Steven Reubenstone

Una macchina di Turing è un semplice “computer” in grado di eseguire operazioni matematiche. Ha un nastro che la attraversa e che è diviso in quadrati. Ogni quadrato può contenere un simbolo come un numero o una lettera.

https://miro.medium.com/v2/resize:fit:1100/format:webp/0*OoCWjje-Tuyj6j8J.jpeg

Immaigne presa da wikipedia: https://en.wikipedia.org/wiki/Turing_machine

La macchina ha una “testa” che può leggere i simboli sul nastro e spostarsi a destra o a sinistra. Ha anche una serie di regole che le dicono cosa fare in base al simbolo che sta leggendo e al suo stato attuale.

Ad esempio, supponiamo che la macchina inizi con il numero “5” sul primo quadrato del nastro. La macchina potrebbe avere una regola che dice: “Se vedi un 5, cambialo in un 6 e sposta la testina di un quadrato a destra”. Quindi la macchina cambierebbe il 5 in un 6 e sposterebbe la testina sul quadrato successivo.

Le macchine di Turing sono importanti per l’informatica perché sono alla base dell’informatica moderna. Forniscono un modello di calcolo che può essere utilizzato per analizzare gli algoritmi e determinarne l’efficienza e l’efficacia. Ci aiutano a capire cosa possono o non possono fare i computer e sono la base di molti linguaggi informatici e concetti di programmazione.

L’importanza della macchina di Turing nell’informatica risiede nella sua capacità di eseguire qualsiasi calcolo che sia risolvibile algoritmicamente (ciò significa che possiamo usare una macchina di Turing per valutare se un certo problema può essere risolto con un computer!!!). Questo concetto, noto come tesi di Church-Turing, è il fondamento della teoria della computazione. La macchina di Turing ci aiuta a capire i limiti di ciò che i computer possono o non possono fare.

La macchina di Turing fu proposta per la prima volta dal matematico britannico Alan Turing nel 1936, come modo per definire formalmente il concetto di procedura o algoritmo efficace. Il suo lavoro ha gettato le basi per lo sviluppo dei moderni computer e ha avuto un profondo impatto sul campo dell’informatica. La macchina di Turing è tuttora ampiamente studiata e utilizzata come strumento teorico per comprendere le capacità e i limiti dei computer e degli algoritmi.

Esempio

Vi spiego passo per passo come una macchina di Turing risolve un problema semplice come decidere se una stringa in ingresso è palindroma o meno (una parola palindroma è una parola che si legge allo stesso modo in avanti e al contrario, come “radar”).

La macchina è nel suo stato di partenza e il nastro contiene una stringa di input, ad esempio “radar”
La macchina legge il primo simbolo sul nastro, ovvero la lettera “r” e la confronta con l’ultimo simbolo che è anch’esso una “r”.
Visto che il primo e l’ultimo simbolo corrispondono, la macchina muove il nastro al simbolo a di un simbolo a destra e di uno a sinistra, rispettivamente
La macchina ora legge i simboli successivi sul nastro: “a” e “a”, confrontandoli di nuovo.
La macchina continua il processo di lettura, confrontando e spostando il nastro finché non ne raggiunge il centro
Se tutti i simboli sul nastro da destra a sinistra e da sinistra a destra corrispondono, la macchina entra nello stato di accettazione indicando che l’input è palindromo.
Se ad un qualsiasi punto della stringa i simboli non corrispondono, la macchina entra in stato di rifiuto indicando che l’input non è palindromo.
A questo punto la macchina si ferma

Vale la pena notare che i passaggi sopra descritti sono solo un semplice esempio di come una macchina di Turing potrebbe risolvere un problema; la macchina potrebbe essere programmata per seguire una serie di regole e stati diversi per risolvere problemi più complessi.