La macchina

Alan Turing, nel progettare il suo esecutore, pensava alle capacità minime che tutti gli esseri umani possiedono

  • leggere, riconoscere, dei simboli
  • scrivere dei simboli, uno alla volta
  • spostare la propria attenzione al simbolo a destra oppure a sinistra del simbolo appena letto

L’esecutore agisce secondo certe regole

  • per un certo numero di situazioni gli viene fornita una regola di comportamento
  • se si presenta una situazione non prevista allora si ferma
  • in presenza di un certo simbolo ci possono essere comportamenti diversi, dipendono dallo stato
  • in un certo stato ci possono essere comportamenti diversi, dipendono dal simbolo letto
  • lo stato iniziale è unico, la macchina si accende sempre nelle stesse condizioni.

In pratica

  • Lo stato iniziale è 0 (zero)
  • Le azioni di osservazione e di scrittura dei simboli avvengono su un nastro, potenzialmente infinito nei due sensi, tramite una testina.
  • I simboli appartengono a un certo alfabeto prefissato,
  • Sono sufficienti due simboli che, per semplicità, si assume siano 0 e 1 oppure b (blank) e 1, ma si può derogare e usare alfabeti più ampi.
  • Le regole che l’esecutore deve applicare sono scritte in un documento che costituisce a tutti gli effetti l’algoritmo….

Quadruple?

Le regole (le istruzioni…) per l’esecutore si possono scrivere come quadruple

(STATOattuale, CARATTEREinput, STATOfuturo, AZIONE)

dove

  • STATOattuale, lo stato in cui si trova l’esecutore
  • CARATTEREinput, il carattere sotto la testina
  • STATOfuturo, lo stato in cui passa l’esecutore
  • AZIONE
    • la scrittura di un certo carattere
    • lo spostamento della testina verso sinistra
    • lo spostamento della testina verso destra
    • nessuna azione.

Quintuple

Per rendere più semplice la stesura dei programmi si preferisce utilizzare le quintuple, specificando contemporaneamente il carattere da scrivere e la direzione dello spostamento

(STATOattuale, CARATTEREinput, STATOfuturo, CARATTEREoutput, DIREZIONE)

Dati lo stato attuale e il carattere letto dalla testina allora l’esecutore dovrà

  • cambiare stato
  • scrivere un certo carattere (se il carattere attuale deve rimanere inalterato riscrive lo stesso carattere)
  • spostare la testina a sinistra, a destra oppure non spostarla.

Come rappresentare i programmi per la macchina di Turing?
Come scrivere il codice sorgente da dare all’applicazione che lo eseguira?

Soluzione 1

Il programma è costituito da una sequenza di linee e ogni linea contiene 5 caratteri consecutivi

SCSCD

Con

  • S: il nome per lo stato attuale e il nome per il prossimo stato
  • C: il carattere letto e il carattere scritto
  • D: il carattere predefinito per lo spostamento a destra, oppure a sinistra.

Soluzione 2

Se si introduce una sintassi più elaborata, con un carattere predefinito di separazione,

S, C, S, C, D

allora i nomi degli stati possono essere delle stringhe!

StatoAttuale, C, StatoFuturo, C, D

Notazione funzionale

(STATOattuale, CARATTEREinput) => (STATOfuturo, CARATTEREoutput, DIREZIONE)

Tabella delle transizioni di stato

Le quintuple nella notazione funzionale ci suggeriscono una rappresentazione alternativa dell’algoritmo: la tabella delle transizioni di stato.

Per ogni entrata (stato, carattere) prevede una tripla (stato, carattere, direzione)

carattere1carattere2…caratterem
stato1(s11, c11, d11)(s12, c12, d12)…(s1m, c1m, d1m)
stato2(s21, c21, d21)(s22, c22, d22)…(s2m, c2m, d2m)
……………
staton(sn1, cn1, dn1)(sn2, cn2, dn2)…(snm, cnm, dnm)

Diagramma di stato

Le quintuple sono la scelta più ovvia per la scrittura veloce delle istruzioni.

La tabella permette un controllo maggiore quando le istruzioni sono numerose.

Quando l’individuazione dell’algoritmo non è immediata, la stesura delle istruzioni diventa faticosa, lo strumento migliore è il diagramma di stato

  • I cerchi, i nodi, rappresentano gli stati
    • Lo stato iniziale è evidenziato dal colore verde e dall’etichetta 0.
    • Lo stato finale è evidenziato dal colore rosso e dall’etichetta H.
  • Le frecce, gli archi, tra i nodi rappresentano le possibili transizioni di stato
    • Un arco parte dallo stato attuale e conduce al prossimo stato, che può essere anche lo stesso
    • Ogni arco è etichettato con una tripla
      • il carattere che provoca la transizione
      • il carattere da scrivere
      • la direzione dello spostamento sul nastro

I caratteri per lo spostamento potrebbero essere

  • D, N, S (Destra, Nullo, Sinistra)
  • D, F, S (Destra, Fermo, Sinistra)
  • R, N, L (Right, Null, Left)
  • >, –, <

Risorse online

  1. Macchina di Turing, Wikipedia
  2. Turing Machines, Stanford Encyclopedia of Philosophy
  3. Turing Machine, Algebraic.net
  4. Turing Machine, MathWorld

Online (Javascript)

  1. TURING MACHINE SIMULATOR
  2. Cms Turing
  3. La macchina di Alan Turing
  4. Turing Machines implemented in JavaScript

Windows

Lascia un commento