macchina di Turing universale

In teoria della computazione, si dice macchina di Turing universale (talvolta abbreviato in MTU) una macchina di Turing capace di simulare le evoluzioni di ogni macchina di Turing. Tale macchina è stata proposta da Turing nel suo fondamentale lavoro del 1936 e gli ha consentito di dare una risposta negativa al problema della decidibilità, il cosiddetto "Entscheidungsproblem", posto da David Hilbert nel 1928. Di questa macchina, come delle macchine di Turing in grado di effettuare elaborazioni particolari, si possono individuare versioni diverse caratterizzate dalla disponibilità di risorse diverse. I moderni interpreti svolgono il ruolo teorizzato dal teorema dell'esistenza della macchina di Turing universale.