Le macchine di Turing.

La quintupla :  < qi, delta, delta i, qj, (SDF) >

La prima lettera è lo stato da qui si analizza la quintupla.

Delta è il valore che si fa leggere alla macchina ( solitamente 0 e 1 )

Delta i è il delta dell’input! Cosa fa sta macchinaccia?  Sta in un punto ( dove sta la testina) ma non si fa i ca… suoi e legge un imput (delta) , leggendolo, cancella lo stato di partenza e ci mette quello nuovo, che sarebbe qj.

(Esempio. Io  guardo canale 5 ( stato iniziale qi) , poi guardo l’orologio ( input) e penso, “cazzarola, inizia Medici in prima linea su rai2!” e cambio canale.

Canale5 (stato iniziale)  “orario” ( input )  cancello lo stato iniziale e metto rai2!

La macchina però ha la testina (di c…) e quindi in base agli iput, può solo fare un passo a destra ( D) , a sinistra ( S) o farsi i ca… suoi ( una volta tanto) e cioè F.

Facciamo un esempio pratico.

.    qi , 1 -> 1, qi, D     questa schifezza si legge = sto in qi, leggo 1 lo sostituisco don 1 e faccio un passo a             destra.

. qi, 0 -> E , q2, D    Sto in q1, leggo 0 e cancello quello che c’era prima ,mettendoci una epsilon , vado in q2 e faccio un posto a destra.

.  q2, 1 -> 0 q2 F   Sto in q2, leggo un uno e lascio un uno, resto in q2 e non mi muovo .

Capiamo. Lo stato qi , q2 e company, sono sul disegno. La D, S e F sono sul nastro. ( praticamente sono gli spostamenti della testina.

Esempio: macchina che sostituisce lo 0 con 1 e viceversa.

 schema macchina di turing

Le istruzioni  di questa macchina sono:

q1,1,0,q1, D    ( la freccina non si mette più)

q1,0,1,q1,D

q1,E,E,q accettazione, F        ( la E sta per epsilon.)

Se ci chiedono di fare la Computazione di un determinato input, si fa così:computazione.

devi immaginarti il nastro con la testina… l’input in questo esempio sarà  1101. Bisogna vedere quella macchina che cosa faràe se l’operazione è accettata o no.