Potreste farmi un esempio di macchina di Turing che calcola la somma di due numeri? (esempio che faccia 1+1=2)?

Una macchina di Turing è un modello concettuale di calcolatore. La sua utilità è legata prevalentemente alla teoria della computabilità, infatti attraverso operazioni semplicissime la macchina di Turing sarebbe in grado di poter eseguire ogni possibile algoritmo (tesi di Church-Turing).

Il modello è costituito da un nastro indefinito che può essere letto e scritto, dato un insieme di simboli (senza perdere di generalità possono essere 0 e 1), da una testina che si muove a destra e a sinistra. Il sistema può assumere un predefinito numero di stati, tra cui lo stato finale che indica che l’algoritmo si è concluso in modo corretto.

Il comportamento della macchina è definito attraverso una tabella di istruzioni: per ogni stato e per ogni simbolo letto sono definite le azioni, cioè l’eventuale scrittura, l’eventuale cambio di stato e lo spostamento a destra o a sinistra. Fa parte integrante del modello l’interpretazione dei dati di ingresso e di uscita.

Il caso della somma di due numeri è trattato ad esempio qui.

Supponendo di trattare numeri interi positivi rappresentati dalla sequenza di 1 di lunghezza pari al numero da memorizzare, e supponendo che i due numeri da sommare siano separati da uno zero, la tabella delle istruzioni necessarie per produrre il numero somma è molto semplice ed è riportata qui sotto.

A parole: partendo dall’inizio del nastro bisogna scorrere a destra (S1) fino a trovare un 1; cancellare il primo 1 e scorrere a destra fino a trovare uno 0 (S2); quindi basta riempire lo 0 tra i due numeri con un 1 (END). Ora è memorizzato il numero somma dei due numeri iniziali.

Qui sotto vengono rappresentate le configurazioni del nastro ad ogni passo per il caso della somma 4 + 2.

Il fatto che le istruzioni siano così elementari in alcuni casi complica un po’ gli algoritmi: si pensi ad esempio di dover copiare un numero, sempre memorizzato come sequenza di 1, e scriverlo di seguito al primo numero, separato da uno 0. Per contare gli 1 semplicemente incrementando una variabile (stato) è necessario porre un limite superiore ai numeri da rappresentare.

Per copiare numeri di qualunque lunghezza bisogna copiare una cifra per volta attraverso un ciclo che riporta lo stato ad un valore precedente. La tabella delle istruzioni è descritta qui.

Si vedano anche i seguenti link:

http://en.wikipedia.org/wiki/Turing_machine_examples

http://www.digitanto.it/pages/Multiframe.htm?f=http://www.digitanto.it/Articoli/AppuntiDiInformatica14.htm