In informatica, una macchina di Turing (o più brevemente MdT, in inglese TM, da Turing machine) è un modello matematico computazionale che descrive una macchina astratta[1][2] che manipola (legge e scrive) i dati contenuti su un nastro di lunghezza potenzialmente infinita, secondo un insieme prefissato di regole ben definite. A dispetto della sua apparente semplicità, questo modello è in grado di simulare la logica di qualunque algoritmo eseguibile su un computer reale[3].
Introdotta nel 1936 da Alan Turing[4] come modello di calcolo per dare risposta all'Entscheidungsproblem (problema di decisione)[5] 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.
- ^ Minsky, 1967, p. 107: "In his 1936 paper, A. M. Turing defined the class of abstract machines that now bear his name. A Turing machine is a finite-state machine associated with a special kind of environment -- its tape -- in which it can store (and later recover) sequences of symbols".
- ^ Stone, 1972, p. 8.
- ^ Macchina di Turing, in Enciclopedia della scienza e della tecnica, Roma, Istituto dell'Enciclopedia Italiana, 2007-2008. 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.