Adesso che abbiamo la definizione di macchina di Turing, che ci serve come formalizzazione dell’idea di algoritmo, possiamo andare a capire meglio come funziona.

Ad ogni passo della computazione, una MdT può trovarsi in una certa configurazione. Una configurazione di una MdT è una quadrupla

$$ (q,u,σ,v) \in (Q \cup \\{h\\}) \times \Sigma^\star \times \Sigma \times \Sigma^F $$

dove \(\Sigma^\star\) è il monoide libero generato da \(\Sigma\) e \(\Sigma^F = \Sigma^\star \cdot (\Sigma \setminus \\{\#\\}) \cup \\{\epsilon\\}\) .
Da notare che \(\Sigma^F\) è costituito da tutte le parole generabili da \(\Sigma\) che terminano con un carattere che non è \(\#\) . Questa condizione ci consente di eliminare dalla notazione tutti i \(\#\) che seguono la stringa di input (essendo il nastro della MdT infinito, dovremmo rappresentare infiniti \(\#\) a seguito della stringa di input o output).

Parlare di monoide libero è un modo molto matematicoso per dire che prendiamo i simboli del nostro alfabeto e generiamo tutte le parole possibili usando, in questo caso, l’operazione binaria di giustapposizione (cioè se prendo una “a” e una “z” e le metto l’una accanto all’altra, cioè le giustappongo, formo la parola “az”). \(\Sigma\) è l’insieme, la giustapposizione è l’operazione binaria, \(\epsilon\) (stringa vuota) è l’elemento neutro. Ecco da dove viene il monoide o semigruppo. Il fatto che sia libero dipende dal concetto di base per cui esiste una decomposizione univoca di ogni elemento (possiamo scindere una stringa nelle sue lettere componenti in modo univoco). La base è l’insieme di parole di lunghezza 1.

Chiudendo questa parentesi sull’algebra, possiamo rappresentare una configurazione con una notazione più sintetica: \((q, u\underline{σ}v)\) , dove q è lo stato in cui si trova attualmente la MdT, u è il testo presente sul nastro a sinistra della testina, σ è il simbolo correntemente sotto la testina e v è il resto del nastro a destra della testina. Se non ci interessa la posizione della testina sul nastro, possiamo abbreviare ulteriormente con la notazione \((q, w)\) , indicando con q lo stato e con w il nastro intero.

Esempi di configurazioni:

  • \((q_0, \underline{▷}aba)\)
  • \((q_0, ▷\underline{a}ba)\)

Una MdT procede cambiando configurazione ad ogni passo di computazione. Una computazione è una successione finita di passi di computazione.

$$ \begin{align} &(q,w) \rightarrow (q',w') & \text{Passo di computazione}\\ &(q_0,w) \rightarrow^\star (q',w') & \text{Chiusura riflessiva e transitiva di passi di computazione} \\ &(q_0,w) \rightarrow^n_M (q',w') & \text{la macchina } M \text{ calcola } w' \text{ in } n \text{ passi} \end{align} $$

Una chiusura di un insieme è in generale il più piccolo oggetto che contemporaneamente contiene quello iniziale e soddisfa una data proprietà.
Una chiusura riflessiva e transitiva \(R^\star\) di una relazione \(R\) è la più piccola relazione transitiva e riflessiva tale che \(R \subseteq R^\star\) .
Sia \(R\) una relazione tra due insiemi \(R \subseteq A \times A\) . \(R^\star\) è la chiusura transitiva e riflessiva di \(R \Leftrightarrow aRa \wedge aRb, bRc \Rightarrow aRc \) .

Esempio di computazione di una MdT che stabilisce se una stringa è palindroma:

$$ \begin{align} &(q_0, \underline{▷}aba) \rightarrow (q_0, ▷\underline{a}ba) \rightarrow (q_A, ▷▷\underline{b}a) \rightarrow (q_0, ▷▷b\underline{a}) \rightarrow \\ &(q_A, ▷▷ba\underline{\#}) \rightarrow (q_0, ▷▷b\underline{a}) \rightarrow (q_1, ▷▷\underline{b}) \rightarrow (q_1, ▷\underline{▷}b) \rightarrow \\ &(q_B, ▷▷▷\underline{\#}) \rightarrow (h, ▷▷▷\underline{SI}) \end{align} $$

Il programma cioè la funzione \(\delta\) è troppo complicato da trascrivere e per il momento salto questa parte.

Turing calcolabilità

Un problema si dice Turing calcolabilese e solo se esiste una macchina di Turing in grado di calcolare una soluzione al problema.

Più formalmente siano \(\Sigma, \Sigma_0, \Sigma_1\) alfabeti, sia \(\#,▷ \notin \Sigma_0 \cup \Sigma1\) e \(\Sigma_0 \cup \Sigma_1 \subset \Sigma \) . Sia \(f\) una funzione \(f : \Sigma^\star_0 \mapsto \Sigma^\star_1 \)

Allora \(f\) è Turing calcolabile da una MdT M se e solo se:

$$ \forall w \in \Sigma^\star_0 : f(w) = z \Leftrightarrow (q_0,▷w) \rightarrow^\star_M (h,▷z\#) $$

Cerchiamo di scompattare questo formalismo. Abbiamo la nostra funzione \(f\) . Se diamo in pasto \(w\) a \(f\) otteniamo \(z\) . Questo è vero solo e soltanto se la macchina \(M\) che calcola \(f\) , parte dallo stato iniziale \(q_0\) con a destra della testina \(w\) e termina nello stato di terminazione \(h\) con a destra della testina \(z\) , seguita dal carattere di fine nastro \(\#\) . Le ipotesi che riguardano \(\Sigma_0\) (l’alfabeto di input) e \(\Sigma_1\) (alfabeto di output) servono ad assicurarsi che i caratteri speciali # e ▷, non si trovino sul nastro né all’inizio né alla fine della computazione onde evitare inutili complessità nella scrittura dei programmi per le MdT.

Quindi se trovo la macchina \(M\) posso concludere che \(f\) è Turing calcolabile.


Oggi pomeriggio ho perso un po' di tempo a capire come funziona MathJax ed a integrarlo sul sito, in modo da rendere visibili le formule matematiche che mi servono per questa serie di articoli. Spero di diventare più efficiente nella scrittura per aumentare gli argomenti che aggiungo ogni giorno.

A domani.