Macchina di Turing: differenze tra le versioni

Versione delle 03:47, 27 giu 2025

Versione delle 11:17, 19 set 2025

Riga 2:

[[File:Model of a Turing machine.jpg|thumb|upright=1.4|Un esempio di macchina di Turing]]

In [[informatica]], una '''macchina di Turing''' (o più brevemente '''MdT''', in [[Lingua inglese|inglese]] '''TM''', da ''Turing machine'') è un [[modello matematico]] computazionale che descrive una [[Automa (informatica)|macchina astratta]]<ref>{{cita|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".</ref><ref>{{cita|Stone, 1972|p. 8}}.</ref> 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<ref>{{Treccani|macchina-di-turing_(Enciclopedia-della-Scienza-e-della-Tecnica)|Macchina di Turing|accesso=2022-07-19}}</ref>.

Introdotta nel [[1936]] da [[Alan Turing]]<ref>{{Cita libro|nome=Douglas R.|cognome=Hofstadter|titolo=Alan Turing : the enigma|url=https://www.worldcat.org/oclc/795331143|accesso=2022-07-19|edizione=Centenary ed|data=2012|editore=Princeton University Press|OCLC=795331143|ISBN=978-1-4008-4497-5}}</ref> come modello di calcolo per dare risposta all'''[[Entscheidungsproblem]]'' (problema di decisione)<ref>{{Cita libro|titolo=Go¨del, Turing|url=http://dx.doi.org/10.1201/b11610-6|accesso=2022-07-19|data=2011-10-14|editore=CRC Press|pp=23-53|ISBN=978-0-203-16957-5}}</ref> proposto da [[David Hilbert|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 [[Algoritmo#Modelli formali|definire in modo formalmente preciso]] la nozione di algoritmo, si tende a ricondurlo alle elaborazioni effettuabili con macchine di Turing.