Partiamo dal principio. Cos’è una macchina di Turing? All’apparenza è una macchina molto semplice composta da una testina che si può spostare a sinistra e a destra su un nastro infinito. Le sue operazioni consistono nel leggere un valore dal nastro (detto simbolo) e, in base a delle regole ben definite (il programma) e a ciò che la testina legge, decidere di scriverne uno nuovo per poi spostarsi a sinistra o a destra sul nastro oppure terminare l’esecuzione.
Dietro queste operazioni “atomiche”, però, si dimostra che la macchina di Turing è in grado di eseguire ogni tipo di algoritmo computabile. In parole povere questo strumento ha un potere computazionale maggiore di quello di un normale computer, in quanto è teoricamente illimitato in occupazione di tempo e memoria.
Ogni implementazione della macchina di Turing risulta allora un’approssimazione di essa stessa, in quanto non si può disporre di nastro e tempo infiniti, ciononostante entro certi limiti le simulazioni di questa macchina astratta forniscono comunque i risultati attesi. Ciò che vi presento è una mia versione della macchina di Turing scritta in Java, con nastro limitato solo dalla dimensione massima della memoria della macchina virtuale.
I pacchetti possono essere scaricati agli indirizzi YATM_v1.0_20111001 e YATM_v1.0_20111001_src (il secondo contiene il sorgente) e ridistribuiti secondo le condizioni della GPLv3. All’interno del pacchetto è presente un programma di esempio che è possibile caricare nella macchina e che stampa sul nastro la frase “Hello World!“. Per il resto basta scrivere un programma adeguato per far fare alla macchina tutto ciò che si desidera. Perché non provare? 🙂
