Dipartimento di Informatica e Tecnologia
Cos’è una macchina di Turing?
Una macchina di Turing è una macchina ipotetica pensata dal matematico Alan Turing nel 1936. Nonostante la sua semplicità, la macchina può simulare QUALSIASI algoritmo di computer, non importa quanto sia complicato!
Questa è una rappresentazione molto semplice di una macchina di Turing. Consiste in un nastro infinitamente lungo che agisce come la memoria in un tipico computer, o qualsiasi altra forma di immagazzinamento dati. Le caselle sul nastro sono solitamente vuote all’inizio e possono essere scritte con simboli. In questo caso, la macchina può elaborare solo i simboli 0 e 1 e ” ” (vuoto), e quindi si dice che è una macchina di Turing a 3 simboli.
In ogni momento, la macchina ha una testa che è posizionata sopra uno dei quadrati sul nastro. Con questa testa, la macchina può eseguire tre operazioni molto basilari:
- Leggere il simbolo sulla casella sotto la testa.
- Modificare il simbolo scrivendo un nuovo simbolo o cancellandolo.
- Spostare il nastro a sinistra o a destra di una casella in modo che la macchina possa leggere e modificare il simbolo su una casella vicina.
Una semplice dimostrazione
Come esempio banale per dimostrare queste operazioni, proviamo a stampare i simboli “1 1 0” su un nastro inizialmente vuoto:
Primo, scriviamo un 1 sul quadrato sotto la testa:
In seguito, spostiamo il nastro a sinistra di una casella:
Ora, scrivi un 1 sul nuovo quadrato sotto la testa:
Poi spostiamo di nuovo il nastro a sinistra di un quadrato:
Infine, scrivi uno 0 ed è fatta!
Un programma semplice
Con i simboli “1 1 0” stampati sul nastro, cerchiamo di convertire gli 1 in 0 e viceversa. Questo si chiama inversione di bit, poiché gli 1 e gli 0 sono bit in binario. Questo può essere fatto passando le seguenti istruzioni alla macchina di Turing, utilizzando le capacità di lettura della macchina per decidere da sola le operazioni successive. Queste istruzioni costituiscono un semplice programma.
| Simbolo letto | Istruzione di scrittura | Istruzione di spostamento | |
|---|---|---|---|
| Bianco | Nessuno | Nessuno | |
| 0 | Scrivi 1 | Spostare il nastro a destra | |
| 1 | Scrivere 0 | Spostare il nastro a destra |
La macchina leggerà prima il simbolo sotto la testa, scriverà un nuovo simbolo di conseguenza, poi muoverà il nastro a sinistra o a destra come indicato, prima di ripetere nuovamente la sequenza lettura-scrittura-movimento.
Vediamo cosa fa questo programma al nostro nastro dal precedente punto finale delle istruzioni:
Il simbolo corrente sotto la testa è 0, quindi scriviamo un 1 e spostiamo il nastro a destra di una casella.
Il simbolo letto è ora 1, quindi scriviamo uno 0 e spostiamo il nastro a destra di una casella:
Similmente, il simbolo letto è un 1, quindi ripetiamo le stesse istruzioni.
Infine, viene letto un simbolo ‘vuoto’, quindi la macchina non fa nulla a parte leggere continuamente il simbolo vuoto poiché le abbiamo ordinato di ripetere la sequenza lettura-scrittura-movimento senza fermarsi.
In effetti, il programma è incompleto. Come fa la macchina a ripetere la sequenza all’infinito, e come fa la macchina a smettere di eseguire il programma? Il programma glielo dice con il concetto di stato della macchina.
Lo stato della macchina
Per completare il programma, bisogna considerare i cambiamenti di stato durante l’esecuzione del programma sulla macchina. I seguenti cambiamenti, segnati in corsivo, devono essere aggiunti alla nostra tabella che ora può essere chiamata tabella di stato:
| Stato | Simbolo letto | Istruzione di scrittura | Istruzione di spostamento | Stato successivo |
|---|---|---|---|---|
| Stato 0 | Bianco | Nessuno | Nessuno | Stato di arresto |
| 0 | Scrivere 1 | Spostare il nastro a destra | Stato 0 | |
| 1 | Scrivere 0 | Spostare il nastro a destra | Stato 0 |
Allociamo il precedente set di istruzioni ad uno stato macchina, in modo che la macchina esegua quelle istruzioni quando si trova nello stato specificato.
Dopo ogni istruzione, specifichiamo anche uno stato a cui la macchina deve passare. Nell’esempio, la macchina viene reindirizzata al suo stato originale, lo stato 0, per ripetere la sequenza lettura-scrittura-nove, a meno che non venga letto un simbolo vuoto. Quando la macchina legge un simbolo vuoto, la macchina è diretta verso uno stato di stop e il programma termina.
Macchine a stato finito
Anche se sembra stupido farlo, aggiungiamo ora uno stato aggiuntivo al nostro programma che inverte i bit già invertiti “1 1 0” di nuovo da “0 0 1” a “1 1 0”. Qui sotto c’è la tabella aggiornata, con i cambiamenti elencati in corsivo. La macchina di Turing ora si comporta come una macchina a stati finiti con due stati – queste sono chiamate macchine di Turing a tre simboli e due stati.
| Stato | Simbolo letto | Istruzione di scrittura istruzione | Istruzione di spostamento | Stato successivo |
|---|---|---|---|---|
| Stato 0 | Bianco | Scrittura vuoto | Spostare il nastro a sinistra | Stato 1 |
| 0 | Scrivere 1 | Sposta il nastro a destra | Stato 1 | |
| 1 | Scrivi 0 | Sposta il nastro a destra | Stato 0 | |
| Stato 1 | Bianco | Scrivere in bianco | Spostare il nastro a destra | Stop di stato |
| 0 | Scrivere 1 | Spostare il nastro a sinistra | Stato 1 | |
| 1 | Scrivere 0 | Spostare il nastro a sinistra | Stato 1 |
Per l’istruzione di scrittura, “Nessuno” è stato cambiato in “Write blank” per uniformità (in modo che si faccia riferimento solo ai simboli della macchina), e si noti che sono equivalenti.
Invece di una tabella di stato, il programma può anche essere rappresentato con un diagramma di stato:
Da dove il programma era precedentemente, invece di non fare nulla e fermarsi dopo che la macchina incontra un simbolo vuoto, le diamo l’ordine di spostare il nastro a sinistra prima di passare allo stato 1 dove inverte il processo di inversione dei bit.
In seguito, invertiamo nuovamente i bit, questa volta spostando il nastro a sinistra invece che a destra.
Finalmente, viene letto un simbolo vuoto, quindi spostiamo il nastro a destra per tornare al punto di partenza, e fermiamo il programma.
Con l’introduzione di più stati al nostro programma, possiamo istruire la macchina di Turing ad eseguire funzioni più complesse e quindi eseguire qualsiasi algoritmo che un computer moderno può eseguire.
Nella seconda sezione, impariamo a conoscere i LED, i pin GPIO, le resistenze e python, prima di iniziare a costruire la nostra macchina di Turing!