Macchina Di Turing

La Maccchina di Turing

La macchina di Turing rappresenta un esempio di modello astratto di una macchina in grado di eseguire programmi.La sua importanza è tale in quanto la Macchina di Turing risulta legata al concetto di complessità e di computazionalità. Vediamone le caratteristiche fondamentali

Definizione della Macchina di Turing

Una macchina di Turing è formata da una nastro infinito, da una testina che può leggere e scrivere simboli di un alfabeto $A$ nella posizione in cui si trova, può spostarsi e possiede uno stato interno. Lo stato interno è fondamentale per la macchina in quanto le consente di capire cosa sta facendo in un determinato momento.

Nella definizione dello stato non abbiamo vincoli particolari, potremo assegnare un numero o una etichetta mnemonica, la questione importante è che uno stato rappresenta sempre una delle fasi di lavoro della macchina di Turing.

Ogni mossa della macchina di Turing sarà composta da una terna di azioni $(w,m,newState)$ dove:

  • $w\in A$ è il simbolo da scrivere sul nastro. Si può utilizzare il simbolo $*$ per indicare di scrivere quello che si è letto dal nastro (non modificare il contenuto della cella).
  • $m \in {L,R}$ la direzione in cui la macchina sposta la testina (a volte si aggiunge il simbolo $*$ per indicare, negli stati finali, che la macchina non deve muversi ulteriormente).
  • $newState$ il nuovo stato in cui la Macchina di Turing si deve porre.

Regole della macchina di Turing

Compresa l’importanza dello stato, vediamo ora come sia possibile andare a definire il comportamento di una Macchina di Turing. Questo comportamento è il programma che la macchina descrive e la sua descrizione è fatta utilizzando una tabella che definisce le operazioni da eseguire dove le prima due colonne saranno rispettivamente lo stato corrente della Macchina di Turing e il simbolo letto dal nastro, le altre tre colonne sono esattamente la terna $(w,m,newState)$ descritta prima.

\[ \begin{array}{lllll} state & r & w & m & newState \\ \hline s0 & simboloLetto & simboloDaScrivere & movimentoTestina & nuovoStato \\ \newline … \end{array}\]

Ad ogni step della macchina viene letto il simbolo dal nastro ( $r$) e, considerato lo stato della Macchina di Turing( $state$), viene letta la tabella cercando la corrispondenza nelle prime due colonne e vengono quindi eseguite le operazioni descritte nelle successive tre colonne della riga corrispondente alla regola attivata.

Nel caso in cui si utilizzi anche la notazione con il simbolo $*$ per i simboli letti dal nastro, nel caso vi siano due regole, una con un simbolo dell’alfabeto e una con l’asterisco, prevale la regola con il simbolo dell’alfabeto.

Simulatore per la macchina di Turing

Un ottimo strumento per esercitarsi a scrivere macchine di Turing è il simulatore della Macchina di Turing scritto da Antony Morphett.

Previous
Next