Sito Visitato 498739 volte Pagina Visitata 271 volte Sei in : Etantonio/IT/Universita/1anno/FondamentiInformatica/ModelliCalcolo/Turing/     

Macchina di Turing che ricerca un numero su di un nastro illimitato

Stato iniziale :       la testina di lettura e scrittura può essere posizionata su di una cella qualsiasi del nastro.

Stato finale    :      la testina di lettura e scrittura è posizionata sulla cifra meno significativa del n° .

Descrizione algoritmo :       dato che il nastro è illimitato, la ricerca del n° non può avvenire solo in un verso in quanto se                                        questo è errato, non si raggiunge mai il n° stesso. La ricerca avviene alternando i 2 passi :

                                               a) ricerca del n° a sx con riscrittura delle X presenti e scrittura di una X al posto del 1° blank                                                          che segue le X.

                                               b) ricerca del n° a dx con riscrittura delle X presenti e scrittura di una X al posto del 1° blank                                                         che segue le X.

                                               Quando il n° viene individuato, vengono cancellate tutte le X inserite sul nastro e ci si                                                    posiziona sulla cifra meno significativa del n°.

Matrice funzionale

 

b

X

" a Î A

descrizione

qo

X q1 sx

X q0 dx

a q2 sx

inserimento di una X a dx al posto del 1° blank

q1

X q0 dx

X q1 sx

a q3 dx

inserimento di una X a sx al posto del 1° blank

q2

b q2 dx

b q2 sx

a q4 dx

cancella le X a sx e si posiziona sulla cifra più significativa

q3

b q3 sx

b q3 dx

a q4 dx

cancella le X a dx e si posiziona sul blank successivo alla cifra meno significativa

q4

b q5 sx

 

a q4 dx

si posiziona sulla cifra meno significativa

q5

       

Esempio di computazione della stringa

b

1

2

b

b

b

b

b     bbbbbbb

 

b

b

b

1

2

b

b

                                                                                                                                                                           

b

1

2

b

q0

b

b

b

 

b

b

q0

b

1

2

b

b

1

2

q1

b

X

b

b

 

b

q1

b

X

1

2

b

b

1

2

X

q0

X

b

b

 

b

X

q0

X

1

2

b

b

1

2

X

X

q0

b

b

 

b

X

X

q0

1

2

b

b

1

2

X

q1

X

X

b

 

b

X

q2

X

1

2

b

b

1

2

q1

X

X

X

b

 

b

q2

X

b

1

2

b

b

1

q1

2

X

X

X

b

 

q2

b

b

b

1

2

b

b

1

2

q3

X

X

X

b

 

b

q2

b

b

1

2

b

b

1

2

b

q3

X

X

b

 

b

b

q2

b

1

2

b

b

1

2

b

b

q3

X

b

 

b

b

b

q2

1

2

b

b

1

2

b

b

b

q3

b

 

b

b

b

1

q4

2

b

b

1

2

b

b

q3

b

b

 

b

b

b

1

2

q4

b

b

1

2

b

q3

b

b

b

 

b

b

b

1

q5

2

b

b

1

2

q3

b

b

b

b

               

b

1

q3

2

b

b

b

b

               

b

1

2

q4

b

b

b

b

               

b

1

q5

2

b

b

b

b