Una semplice macchina di Turing per l'addizione

Supponiamo di voler costruire una macchina di Turing in grado di effettuare per esempio la semplice operazione '2+3'. Come procederemo?

Tanto per cominciare, dovremo 'dare in pasto' alla nostra macchina di Turing il suo input, corrispondente ai due addendi che vogliamo sommare. Per farlo, lo stato iniziale del nastro su cui si muove la macchina dovrà in qualche modo 'rappresentare' i due addendi. Immaginiamo dunque che sul nostro nastro tutte le cellette contengano il simbolo '0', tranne due gruppi, uno di due e uno di tre cellette, che contengano '1'. Questi due gruppi di cellette (che devono essere distinti; stabiliamo dunque che siano separati da una celletta che contiene '0') rappresenteranno i nostri due addendi, '2' e '3'. La testina sarà posizionata sulla prima casella che contiene '1', e la macchina si troverà nello stato iniziale. In sostanza, il nastro avrà l'aspetto che vedete nella figura qui sotto:

Evidentemente, vogliamo che la posizione finale del nastro rappresenti il nostro output, il risultato che vogliamo raggiungere. Approfittiamo del fatto che l'operazione di sommare due più tre è abbastanza facile, per capire quale dovrà essere lo stato finale della macchina: la testina dovrà fermarsi quando sul nastro, al posto dei due gruppi, uno di due e uno di tre cellette, che contengono '1' e rappresentano i nostri due addendi, vi sarà un solo gruppo di cinque cellette che contengono '1': questo gruppo rappresenterà il nostro risultato, cioè il numero '5'. Alla fine il nastro dovrà dunque corrispondere a quello rappresentato dalla figura 2:

In sostanza, vogliamo che la macchina faccia qualcosa di simile a quello che fa un bambino quando per capire il risultato dell'operazione '2+3' "mette insieme" un mucchietto contenente due sassolini e un mucchietto contenente tre sassolini, ottenendo alla fine un mucchietto contenente cinque sassolini.

Quali istruzioni, quale 'programma' dobbiamo dare alla macchina per farla passare dallo stato iniziale a quello finale? Il risultato può essere ottenuto attraverso una varietà di strategie diverse (cioè attraverso 'programmi' diversi). Una strategia semplicissima consiste nello sfruttare il fatto che i due gruppi di '1' sono separati da un singolo zero, e che alla partenza la testina è posizionata sul primo '1' del primo gruppo. Possiamo dire alla testina di trasformare in '0' l''1' sul quale si trova, poi di spostarsi a destra fino a quando non incontra uno '0' (che sarà quello che separa i due gruppi di '1'), e di trasformare questo '0' in '1': In sostanza, la macchina 'unisce' i due gruppi di '1', cancellando il primo '1' del primo gruppo in modo da 'compensare' la scrittura di un '1' al posto dello '0' che li separava. Il programma che faremo eseguire alla macchina dovrà avere più o meno la forma seguente:

• scrivi '0' al posto dell''1' che stai leggendo
• spostati a destra finché non incontri uno '0'
• scrivi '1' al posto dello '0' che stai leggendo
• fermati (se siamo tipi ordinati, possiamo far tornare la macchina sul primo '1' del nastro prima di farla fermare – questo, evidentemente, richiederà istruzioni ulteriori)

Per 'scrivere' questo programma in termini più formali e precisi, possiamo pensare a un insieme di regole ciascuna delle quali composta da cinque elementi: 1) l'indicazione dello stato attuale della macchina; 2) il simbolo letto dalla macchina; 3) il simbolo che la macchina scrive al posto di quello letto; 4) il movimento che la testina deve fare; 5) lo stato successivo della macchina. Per capire l'idea, vediamo la forma che il nostro programma potrebbe assumere in questa notazione:

La macchina parte nello stato 'A' (abbiamo usato delle lettere anziché dei numeri per etichettare gli stati della macchina, in modo da non far confusione con gli '0' e gli '1' che la testina può leggere e scrivere). In questo stato legge '1' (dato che questa è la sua situazione di partenza), e lo sostituisce con '0'. Poi si sposta a destra e passa nello stato 'B'. Lo stato 'B' prevede istruzioni diverse a seconda che la macchina legga '0' o '1': se legge '1', vuol dire che sta ancora 'scorrendo' il primo addendo: lascia l''1' al suo posto e si sposta ancora a destra. Se legge '0', vuol dire che ha finito di percorrere il primo addendo, ed è arrivata allo '0' che lo separa dal secondo; trasformando questo '0' in '1' ottiene il risultato di lasciare sul nastro una fila ininterrotta di '1' corrispondente al risultato desiderato.

Descritto a parole, questo meccanismo può certo risultare complicato – ma se lo provate in pratica con davanti carta e penna, o con la macchina di Turing inserita nel CD-ROM sotto forma di applet Java [CD applet macchina di Turing], vedrete che è in fondo semplicissimo. E funziona non solo con '2+3', ma con qualunque somma di due numeri naturali.

Esercizio 1: Quali istruzioni dovremmo aggiungere per far tornare la nostra macchina di Turing, al termine delle sue operazioni, con la testina posizionata sul primo 1 del risultato?

Esercizio 2: La nostra macchina di Turing è molto semplice, ma è basata in fondo sul 'trucco' di sfruttare lo '0' che separa i due addendi, senza considerare affatto il secondo addendo. Provate a costruire una macchina di Turing meno 'pigra', che scriva il risultato senza cancellare i due addendi, sotto forma di un nuovo gruppo di '1' a destra del secondo addendo, e separato da quest'ultimo attraverso uno '0'. In sostanza, lo stato finale del nastro nel nostro esempio della somma '2+3' dovrà essere

...000000011011101111100000.....