Alla base di tutto #4
Si cercherà adesso di spiegare, semplificando di molto, il complicato funzionamento della macchina di Turing.
La macchina di Turing è composta da un nastro di lunghezza infinita e una testina:
-Il nastro costituisce la "memoria" delle operazioni compiute ed è diviso in celle. Queste possono ospitare un unico simbolo, che deve appartenere a un alfabeto prestabilito dal programmatore, oppure possono essere vuote. L'alfabeto può essere, per esempio, quello binario costituito, quindi, solo da "0" e "1", oppure quello delle lettere italiane (a,b,c...)
-La testina collega l'organo di controllo al nastro, lungo cui può muoversi e può scrivere o cancellare il simbolo nella casella nella quale si trova. La testina per ogni movimento si trova in uno stato preciso (A,B,C...) appartenente a un insieme finito di stati Q, a seconda del quale cambia l'operazione che deve svolgere. Una volta terminato il comando, questa si muove a destra o a sinistra della casella.
Si riporta un'immagine per meglio visualizzarne il funzionamento
Ogni operazione viene, quindi, determinata da cinque parametri:
1. L'attuale stato della macchina
2. Il simbolo contenuto nella cella correntemente in corso di lettura
3. Il simbolo da scrivere nella medesima cella se non avviene alcuna modifica del dato
4. Lo stato della macchina a seguito delle precedenti operazioni (2 e 3)
5. La direzione di scorrimento del nastro (avanti o indietro).
Per maggior chiarezza si invita a guardare questi due brevi video:
https://www.youtube.com/watch?v=w28bwuYseNk
https://www.youtube.com/watch?v=ThWwEcJWiAE
Bibliografia:
(La macchina di Turing):la macchina di Turing, http://arjelle.altervista.org/Tesine/Matteo/turingmacchina.htm
Commenti
Posta un commento