Valentina Pirata

SCHEDA – La Macchina di Turing Universale (MTU)
a cura di S. Pinna e M. Giunti (Università di Cagliari)
Una Macchina di Turing (MT) è un sistema ideale di calcolo inventato allo scopo di formalizzare il
concetto intuitivo di algoritmo, termine con cui si intende un qualsiasi processo di trasformazione
simbolica sulla base di regole non ambigue.
Essa è costituita da diverse parti interconnesse: una parte interna (che contiene le regole di
esecuzione e la memoria interna); una parte esterna, costituita da un nastro diviso in celle e
potenzialmente estendibile all’infinito, sopra il quale sono scritti i simboli su cui avviene il calcolo;
una testina leggi/scrivi/muovi, che è un grado di leggere il simbolo contenuto in una cella,
sovrascrivere un altro simbolo e muoversi su di una cella adiacente a quella letta; e infine un’unità
di controllo, cioè un semplice meccanismo input-output che indica alla macchina quali operazioni di
scrittura/movimento svolgere al passaggio presente e quale regola far scattare al passaggio
successivo.
Turing rese evidente che tramite le sue macchine si può, in linea di principio, calcolare qualsiasi
funzione computabile da un uomo con carta e penna. Inoltre – e qui sta il passaggio fondamentale
per comprendere il legame col computer moderno – egli dimostrò l’esistenza di una Macchina di
Turing Universale (MTU), che è in grado di simulare il funzionamento di qualsiasi altra MT, a patto
che le regole proprie di quest’ultima vengano codificate in un linguaggio riconoscibile dalla MTU.
Poiché per ogni funzione computabile esiste una MT in grado di calcolarla, la MTU non è altro che
l’analogo teorico di un computer digitale, il cui hardware è in grado di far girare qualsiasi software,
a patto che il linguaggio di programmazione in cui quest’ultimo è scritto sia riconoscibile da
quell’hardware.

Download Report