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 deve rispettare alcune regole

  • per la maggior parte delle situazioni gli viene fornita una regola di comportamento corrispondente
  • se per una certa situazione manca la regola di comportamento allora si ferma
  • davanti allo stesso simbolo letto ci possono essere comportamenti diversi che dipendono dallo stato
  • lo stato iniziale è fissato (0…)

In pratica

  • 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.
  • Le regole che l’esecutore deve applicare sono scritte in un documento che costituisce a tutti gli effetti l’algoritmo….

Le quintuple

Come rappresentare le istruzioni per la macchina di Turing?

Quadruple

Le regole (le istruzioni…) si possono scrivere, nella forma più semplice, come quadruple

(STATOattuale, CARATTEREinput, STATOfuturo, AZIONE)

dove

STATOattuale

stato attuale dell’esecutore

CARATTEREinput

carattere letto dalla testina

STATOfuturo

prossimo stato dell’esecutore

AZIONE

scrivere un certo carattere oppure spostarsi a destra/sinistra.

Quintuple

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

(STATOattuale, CARATTEREinput, STATOfuturo, CARATTEREoutput, DIREZIONE)

Oppure in notazione funzionale

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

Dati

  • lo stato attuale
  • e il carattere letto dalla testina

allora

  • cambia stato
  • scrivi un certo carattere
  • e sposta la testina.

Osserva

se il carattere attuale deve rimanere inalterato basta riscrivere lo stesso carattere.


I programmi

Come rappresentare i programmi per la macchina di Turing?

Soluzione #1

Un grafo, diagramma di stato, dove

  • i nodi rappresentano gli stati
  • gli archi tra i nodi rappresentano le possibili transizioni di stato e sono etichettati con una tripla
    • il carattere che provoca la transizione
    • il carattere da scrivere
    • la direzione dello spostamento sul nastro.

Esempio

i0201Osserva

  • lo stato iniziale è evidenziato dal colore verde e dall’etichetta 0
  • lo stato finale è evidenziato dal colore rosso e dall’etichetta H
  • per specificare lo spostamento sono necessari 3 caratteri come
    • D N S (Destra, Nullo, Sinistra)
    • R N L (Right, Null, Left)
    • > – < (verso destra, …, verso sinistra).

Soluzione #2

Una tabella delle transizioni di stato che per ogni entrata (stato, carattere) prevede una tripla (stato, carattere, direzione)

carattere1 carattere2 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)

Soluzione #3

Ogni linea del programma contiene una quintupla come sequenza di 5 caratteri concatenati:

SCSCD

Con

  • S: i nomi per lo stato attuale e il prossimo stato sono singoli caratteri
  • C: il carattere letto e il carattere scritto
  • D: un carattere predefinito per lo spostamento a destra/sinistra

Soluzione #4

… sequenza di 5 informazioni separate tramite un carattere predefinito:

StatoAttuale,C,StatoFuturo,C,D

Con

  • StatoAttuale
  • StatoFuturo: il carattere separatore permette di utilizzare stringhe!
  • C
  • D: caratteri singoli…

La macchina ufficiale

Turing Machine Simulator è la macchina ufficiale della Gara Nazionale.

Dopo aver scritto il programma nell’area di testo a destra e aver inserito l’input nella casella di testo in basso è possibile passare all’esecuzione (e al debugging…)

Velocità

Agendo sulla barra di scorrimento si può accelerare o rallentare l’esecuzione del programma

Esegui

Inizia l’esecuzione del programma

Stop

Ferma l’esecuzione del programma

Carica

Carica il programma selezionato nella casella di scelta sopra il pulsante.
La macchina originale si presenta con 4 programmi precaricati

  1. Hello world, scrive CIAO
  2. Exchange A and B, traduce le A in B e le B in A
  3. A^nB^n, controlla se l’input è del tipo AnBn
  4. Universal Turing Machine, …
Notice: This work is licensed under a BY-NC-SA. Permalink: La macchina

Comments are closed.