Macchina di Turing

La macchina di Turing è un modello matematico di un computer ideato dal matematico britannico Alan Turing nel 1936. Si tratta di un dispositivo immaginario composto da una serie di elementi, tra cui una banda infinita divisa in celle, una testina in grado di leggere e scrivere sui simboli presenti sulla banda, e un insieme di regole che governano il comportamento della macchina.

La macchina di Turing è in grado di eseguire una vasta gamma di operazioni, come la lettura e la scrittura di simboli, la spostamento della testina lungo la banda, e l’esecuzione di istruzioni condizionali in base allo stato corrente della macchina. Grazie a queste capacità, le macchine di Turing sono state utilizzate per studiare problemi matematici complessi, come il problema della decisione e la risolubilità degli algoritmi.

Il modello della macchina di Turing è diventato un importante strumento teorico nell’informatica e nella teoria dei calcoli. Esso ha permesso di formalizzare il concetto di algoritmo e di studiare le proprietà delle funzioni computazionali. Inoltre, le macchine di Turing sono state utilizzate per definire la nozione di linguaggio formale e per studiare i problemi di riconoscibilità e accettabilità di questi linguaggi.

Definire una macchina di Turing

Una macchina di Turing è un sistema composto da:

• Una banda infinita divisa in celle, su cui possono essere scritti simboli;
• Una testina in grado di leggere e scrivere sui simboli presenti sulla banda;
• Un insieme di stati, inclusi uno stato di accensione e uno stato di arresto;
• Un insieme di regole di transizione che governano il comportamento della macchina, specificando cosa fare in base allo stato corrente, al simbolo letto dalla testina e alla direzione di movimento della testina.

Una regola di transizione ha la forma:

$(q, s) \rightarrow (q', s', D)$

dove $q$ è lo stato corrente, $s$ è il simbolo letto dalla testina, $q'$ è lo stato successivo, $s'$ è il simbolo da scrivere sulla banda e $D$ indica la direzione di movimento della testina (a sinistra o a destra).

esempio

Immaginiamo di voler creare una macchina di Turing che riconosce le stringhe di simboli “aa” e “bb”.

Le regole di transizione per questa macchina potrebbero essere le seguenti:

• $q_0, a \rightarrow q_1, \emptyset, R$
• $q_1, a \rightarrow q_2, \emptyset, R$
• $q_2, b \rightarrow q_3, \emptyset, R$
• $q_3, b \rightarrow q_4, \emptyset, R$
• $q_4, \emptyset \rightarrow q_5, \emptyset, L$

In questa macchina, partiamo dallo stato $q_0$ e leggiamo il simbolo “a”. Se il simbolo è presente, passiamo allo stato $q_1$ e spostiamo la testina a destra. In $q_1$, leggiamo di nuovo il simbolo “a” e passiamo allo stato $q_2$. In $q_2$, leggiamo il simbolo “b” e passiamo allo stato $q_3$. Infine, in $q_3$ leggiamo il secondo simbolo “b” e passiamo allo stato di arresto $q_4$.

Se la stringa non è “aa” o “bb”, la macchina si ferma in uno stato diverso da quello di arresto. Ad esempio, se la stringa è “ab”, la macchina legge il primo simbolo “a” e passa a $q_1$, ma poi legge il simbolo “b” e si ferma in uno stato diverso da quello di arresto.

Wildcard nella definizione di una macchina di Turing

Le wildcard sono simboli speciali che possono rappresentare qualsiasi simbolo o stato. Nella definizione di una macchina di Turing, le wildcard vengono spesso utilizzate per semplificare la scrittura delle regole di transizione.

Le wildcard possono essere utilizzate per rappresentare stati. Ad esempio, supponiamo di voler creare una macchina di Turing che riconosce tutte le stringhe che contengono almeno un “a”. Invece di scrivere una regola di transizione separata per ogni possibile stato che può apparire prima dell’ultimo “a”, possiamo utilizzare la wildcard "$*$" per rappresentare qualsiasi stato. La regola di transizione potrebbe quindi essere scritta come:

$\text{*}, a \rightarrow q, \emptyset, R$

Esempi di macchina di Turing

Ecco tre esempi semplici di macchine di Turing:

1. Una macchina di Turing che riconosce solo stringhe di 0:

Q0: se si incontra un 0, allora scrivere un 0 e spostarsi a destra
Q0: se si incontra una cella vuota, allora fermarsi

2. Una macchina di Turing che inverte l’ordine dei simboli in una stringa:

Q0: se si incontra un 0 o una cella vuota, allora scrivere un 1 e spostarsi a sinistra
Q1: se si incontra un 1, allora scrivere un 0 e spostarsi a destra
Q1: se si incontra una cella vuota, allora fermarsi

3. Una macchina di Turing che calcola il numero di 1 in una stringa:

Q0: se si incontra un 1 o una cella vuota, allora scrivere un 1 e spostarsi a destra
Q1: se si incontra un 0 o una cella vuota, allora scrivere un 0 e spostarsi a destra
Q1: se si incontra un 1, allora scrivere un 0 e spostarsi a sinistra
Q1: se si incontra una cella vuota, allora fermarsi

In tutti questi esempi, la macchina di Turing parte dalla configurazione iniziale in cui la banda contiene solo la stringa da elaborare e la testina si trova sulla prima cella a sinistra della stringa. La macchina si sposta lungo la banda leggendo i simboli e eseguendo le istruzioni specificate per ogni stato fin quando non incontra una condizione di arresto o fino a quando non ha più simboli da elaborare.

Risorse

simulatore di macchina di turing online: https://morphett.info/turing/turing.html