In termini semplici, si può pensare a una macchina di Turing come a una scatola nera che riceve una stringa di caratteri, la elabora in qualche modo e restituisce se accetta o rifiuta l'input.
All'inizio può sembrare strano, ma è comune nei linguaggi di basso livello come C, C++ o persino negli script bash. Quando scriviamo codice in uno di questi linguaggi, spesso restituiamo 0 alla fine del nostro script per indicare un'esecuzione riuscita. Potremmo invece far sì che restituisca un 1 in caso di errore generico.
#include <stdio.h>int main()
{
printf("Hello World!");
return 0;
}
Questi valori possono poi essere controllati dal sistema operativo o da altri programmi. I linguaggi di programmazione consentono anche la restituzione di numeri maggiori di 1 per specificare un particolare tipo di errore, ma l'essenza generale è sempre la stessa. Quanto a cosa significhi per una macchina accettare o rifiutare un determinato input, dipende interamente da chi l'ha progettata.
Dietro il sipario si compone la macchina due componenti fondamentali: un blocco di controllo e un nastro. Il nastro lo è infinito e corrisponde alla memoria del modello. Il blocco di controllo può interagire con il nastro attraverso una testa mobile può leggere e scrivere sul nastro. La testa può muoversi a destra e a sinistra sul nastro. Può andare all'infinito a destra ma non può andare oltre l'elemento iniziale del nastro poiché il nastro si espande indefinitamente solo verso un lato.
Inizialmente il nastro è vuoto, pieno solo di simboli vuoti (⊔). Quando la macchina legge la stringa di input, questa viene posizionata nella parte più a sinistra del nastro. Anche la testa viene spostata nella posizione più a sinistra, consentendo alla macchina di iniziare a leggere la sequenza di input da lì. Il modo in cui legge l'input, se lo sovrascrive e qualsiasi altro dettaglio di implementazione è definito nel blocco di controllo.
Il blocco di controllo è costituito da un insieme di stati interconnessi da una funzione di transizione. Le transizioni definite nella funzione di transizione specificano come spostarsi tra gli stati a seconda di ciò che viene letto dal nastro, nonché cosa scrivere su di esso e come muovere la testina.
Nella transizione di cui sopra, il primo termine si riferisce a ciò che viene letto dal nastro. Seguendo la freccia, sul nastro verrà scritto il termine successivo. Non solo il nastro consente di scrivere su di esso qualsiasi carattere nell'input, ma consente anche l'utilizzo di simboli aggiuntivi presenti solo nel nastro. Dopo la virgola, l'ultimo termine è la direzione in cui muovere la testa: R significa giusto e l significa sinistra.
Il diagramma seguente descrive il funzionamento interno di una macchina di Turing che accetta qualsiasi stringa di almeno 2 lunghezze che inizia e finisce con 0, con una quantità arbitraria di 1 nel mezzo. Le transizioni sono posizionate accanto alle frecce che puntano da uno stato all'altro. Ogni volta che la macchina legge un carattere dal nastro, controllerà tutte le transizioni che lasciano il suo stato attuale. Quindi, passa lungo la freccia contenente quel simbolo allo stato successivo.
La macchina di Turing ha 3 stati speciali: UN di partenzaUN accettazionee un rifiuto stato. Lo stato iniziale è indicato nel diagramma da una freccia che si collega solo ad un'estremità e, come suggerisce il nome, è lo stato in cui si avvia la macchina. I restanti 2 stati sono ugualmente semplici: se la macchina raggiunge lo stato di accettazione, accetta l'input e, se raggiunge lo stato di rifiuto, lo rifiuta. Notare che può anche ripetersi eternamente, senza mai raggiungere nessuno dei due.
Il diagramma utilizzato era quello di una macchina di Turing deterministica. Ciò significa che ogni stato aveva una transizione che lo lasciava per ogni possibile simbolo che avrebbe potuto leggere dal nastro. In una macchina di Turing non deterministica questo non sarebbe il caso. È una delle tante varianti della macchina di Turing. Alcuni possono adottare più di un nastro, altri possono avere una “stampante” collegata, ecc. L'unica cosa da tenere a mente con le variazioni del modello è che sono tutte equivalenti in termini di potenza. Cioè, tutto ciò che qualsiasi variazione della macchina di Turing può calcolare può essere calcolato anche mediante il modello deterministico.
L'immagine sotto è di un semplice modello fisico di una macchina di Turing costruita da Mike Davey. Ha un nastro che può essere spostato a sinistra o a destra da due motori rotanti e al centro si trova un circuito in grado di leggere e scrivere sul nastro, catturando perfettamente il concetto di Turing.
Fonte: towardsdatascience.com
