Macchina di Turing

La macchina di Turing è il modello astratto di calcolo che Alan Turing descrive nel 1936 nell'articolo On Computable Numbers.

È una macchina immaginaria, pensata per dire con precisione che cosa significa «calcolare seguendo una procedura», e si compone di tre elementi:

• un nastro diviso in caselle, su cui si leggono e si scrivono simboli;
• una testina, che legge una casella alla volta e si sposta a destra o a sinistra;
• una tabella di regole, che per ogni stato e ogni simbolo letto dice che cosa scrivere, dove spostarsi e in quale stato passare.

Il passo decisivo è la macchina universale: una macchina di Turing che legge sul nastro la descrizione di un'altra macchina e ne esegue il lavoro. Ne consegue che un solo apparecchio può svolgere qualunque procedura gli venga descritta, ed è il principio del computer a programma memorizzato. Le tecnologie dell'intelligenza precedenti, come la calcolatrice a ruota a pioli, eseguono invece soltanto le operazioni per cui sono costruite.

Fonte: A. M. Turing, On Computable Numbers, with an Application to the Entscheidungsproblem, Proceedings of the London Mathematical Society, 1936.

Enrico Giubertoni. Licenza CC BY-NC 4.0: puoi citarla, tradurla e adattarla con il nome dell'autore e il link, indicando se l'hai modificata. Per un uso commerciale scrivi a info@enricogiubertoni.com

Hai trovato un'inesattezza o un dato da aggiornare? Scrivi a info@enricogiubertoni.com e aiutaci a rendere questo glossario un posto migliore.