Our website is made possible by displaying online advertisements to our visitors.
Please consider supporting us by disabling your ad blocker.
Macchina di Turing
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.
Previous Page Next Page
