Macchina Di Turing

Tempo di lettura: 3 minuti

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.

ISCRIVITI AL CANALE YOUTUBE
...

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.

Altre lezioni in: Teoria sugli Algoritmi

Altre lezioni in: informatica

Avatar
Prof. Andrea Pollini
Docente di Ruolo Informatica (A41) Docente Universitario corso di Sistemi Operativi e Architettura degli Elaboratori

Matematico e Informatico. Ammiro il mondo, penso e immagino un futuro di innovazione. Mi adopero per formare alla creatività e all’imprenditorialità le nuove generazioni. Risolvo problemi complessi per le aziende.

comments powered by Disqus