Introduzione alle Macchine di Turing | Cerca per titolo, autore, parola chiave | ||||||||
Introduzione alle Macchine di Turing Di Antonio Brogi, Antonio Cisternino e Francesco Romani, Dipartimento di Informatica, Università di Pisa. Nel 1936 il matematico inglese Alan Turing propose l'idea di una macchina immaginaria che fosse capace di eseguire ogni tipo di calcolo su numeri e simboli. In questo ottimo articolo viene spiegato il funzionamento della macchina di Turing: una macchina di Turing è definita da un insieme di regole ( istruzioni ) che definiscono il comportamento della macchina su un nastro di input-output ( lettura e scrittura ). Il nastro può essere immaginato come un nastro di carta di lunghezza infinita, diviso in quadratini dette celle. Ogni cella contiene un simbolo oppure è vuota. La macchina di Turing ha una testina che si sposta lungo il nastro leggendo, scrivendo oppure cancellando simboli nelle celle del nastro. La macchina analizza il nastro, una cella alla volta, iniziando dalla cella che contiene il simbolo più a sinistra nel nastro. Ad ogni passo, la macchina legge un simbolo sul nastro e in accordo al suo stato interno corrente decide il suo prossimo stato interno, e scrive un simbolo sul nastro e decide se spostare o meno la testina a sinistra o a destra di una posizione.
|
|||||||||
Introduzione alle Macchine di Turing | Disclaimer: questo è un link a contenuti ospitati su server esterni. |