Sito Visitato 498379 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
Esempio di computazione della stringa
|