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.^[1]

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.

Qui ci riferiamo alla versione deterministica a un nastro e con istruzioni a 5 campi che individuiamo semplicemente come macchina U. La macchina opera con un nastro che, quando si vuole che simuli l'evoluzione di una certa macchina di Turing T mentre elabora una certa stringa w, inizialmente viene caricata in una sua prima sezione con una codifica opportuna delle istruzioni della macchina T seguita, dopo un demarcatore particolare bene individuabile, dalla stessa w.

Nell'evoluzione della U si distinguono successivi stadi, ciascuno corrispondente ad un passo dell'evoluzione della macchina T. In ogni stadio la prima sezione del nastro della U non viene mai modificata, mentre la seconda parte deve essere modificata nella nuova stringa per la T. La simulazione di un passo della T viene ottenuta con una prima fase nella quale la testina si muove dalla posizione della seconda sezione, sulla quale si trovava, verso la prima sezione alla ricerca della quintupla che costituisce l'istruzione che la T deve eseguire. Questa ricerca viene effettuata con la U in stati che ricordano quale istruzione si cerca. Trovata l'istruzione si ha una seconda fase della U nella quale la testina torna a destra fino alla posizione nella quale si deve effettuare il passo evolutivo, mentre gli stati ricordano come deve essere eseguito il passo per la T. La terza fase della U riguarda la esecuzione del passo.

Si può quindi capire come con questi stadi evolutivi formati da tre fasi la U possa simulare tutti i passi della T, quale essa sia. Si osserva che la macchina di Turing universale è in grado di simulare anche la propria evoluzione mentre procede a simulare una qualsiasi macchina T. Si osserva anche che l'evoluzione della U è enormemente più faticosa e lenta della evoluzione della macchina T simulata: la generalità della portata della U viene pagata con la sua bassissima efficienza.

È anche chiaro che la macchina di Turing universale ha puramente un ruolo di modello computazionale teorico, utile per le considerazioni generali alle quali può portare e non per la sua capacità di fornire risultati specifici (attraverso manovre estremamente laboriose e in tempi lunghissimi). Si può dire che il primo segmento del nastro della macchina U contiene il particolare "programma" che le consente di simulare la particolare macchina T. La macchina di Turing universale quindi costituisce un modello di computer a programmazione interna.

All'interno dei videogiochi Dwarf Fortress, Minecraft^[2][3] e del gioco di carte Magic the Gathering^[4] è possibile creare una macchina universale di Turing. Tali giochi sono quindi (accidentalmente) Turing completi.

• (EN) Alan Turing, On Computable Numbers, with an application to the Entscheidungsproblem, vol. 42, Proc. London Math. Soc., 1936, pp. 230-265. (accessibile anche on-line)
• Arto Salomaa (1985): Computation and automata, Cambridge University Press

• Macchina di Turing
• Entscheidungsproblem
• Interprete (informatica)
• Turing equivalenza

Portale Informatica

Portale Matematica