Macchina di Turing

Online

Sezione del sito ufficiale
Macchina di Turing, Wikipedia
Turing Machines, Stanford Encyclopedia of Philosophy
Turing Machine, Algebraic.net
Turing Machine, MathWorld

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

(STATO_attuale, CARATTERE_input, STATO_futuro, AZIONE)

dove

STATO_attuale

stato attuale dell'esecutore

CARATTERE_input

carattere letto dalla testina

STATO_futuro

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

(STATO_attuale, CARATTERE_input, STATO_futuro, CARATTERE_output, DIREZIONE)

Oppure in notazione funzionale

(STATO_attuale, CARATTERE_input) => (STATO_futuro, CARATTERE_output, DIREZIONE)

Dati

lo stato attuale
e il carattere letto dalla testina

allora

cambia stato
scrivi un certo carattere
e sposta la testina.

Nota

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

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 #2

... 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...

Soluzione #3

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

	carattere₁	carattere₂	...	carattere_m
stato₁	(s₁₁, c₁₁, d₁₁)	(s₁₂, c₁₂, d₁₂)	...	(s_1m, c_1m, d_1m)
stato₂	(s₂₁, c₂₁, d₂₁)	(s₂₂, c₂₂, d₂₂)	...	(s_2m, c_2m, d_2m)
...	...	...	...	...
stato_n	(s_n1, c_n1, d_n1)	(s_n2, c_n2, d_n2)	...	(s_nm, c_nm, d_nm)

Soluzione #4

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

Osserva che

lo stato iniziale è evidenziato dal colore verde e dall'etichetta 0
lo stato finale è evidenziato dal colore rosso e dall'etichetta H
per lo spostamento sono necessari 3 caratteri significativi come: D N S, R N L oppure > - <.

ESERCIZI

Prova la Macchina di Turing!