Macchina di Turing

In informatica, una macchina di Turing (o più brevemente MdT) è una macchina ideale che manipola i dati contenuti su un nastro di lunghezza potenzialmente infinita, secondo un insieme prefissato di regole ben definite^[1]. In altre parole, si tratta di un modello astratto che definisce una macchina in grado di eseguire algoritmi e dotata di un nastro potenzialmente infinito su cui può leggere e/o scrivere dei simboli.

Introdotta nel 1936 da Alan Turing^[2] come modello di calcolo per dare risposta all'Entscheidungsproblem (problema di decisione)^[3] proposto da Hilbert nel suo programma di fondazione formalista della matematica, è un potente strumento teorico che viene largamente usato nella teoria della calcolabilità e nello studio della complessità degli algoritmi, in quanto è di notevole aiuto agli studiosi nel comprendere i limiti del calcolo meccanico; la sua importanza è tale che oggi, per definire in modo formalmente preciso la nozione di algoritmo, si tende a ricondurlo alle elaborazioni effettuabili con macchine di Turing.

^ macchina di Turing in "Enciclopedia della Scienza e della Tecnica", su www.treccani.it. URL consultato il 19 luglio 2022.
^ Douglas R. Hofstadter, Alan Turing : the enigma, Centenary ed, Princeton University Press, 2012, ISBN 978-1-4008-4497-5, OCLC 795331143. URL consultato il 19 luglio 2022.
^ Go¨del, Turing, CRC Press, 14 ottobre 2011, pp. 23–53, ISBN 978-0-203-16957-5. URL consultato il 19 luglio 2022.

[1] Turing in "Enciclopedia della Scienza e della Tecnica", su www.treccani.it. URL consultato il 19 luglio 2022.

[2] Douglas R. Hofstadter, Alan Turing : the enigma, Centenary ed, Princeton University Press, 2012, ISBN 978-1-4008-4497-5, OCLC 795331143. URL consultato il 19 luglio 2022.

[3] Go¨del, Turing, CRC Press, 14 ottobre 2011, pp. 23–53, ISBN 978-0-203-16957-5. URL consultato il 19 luglio 2022.

[1]

[2]

[3]