Strings vs Natural Numbers

Strings vs Natural Numbers

Una delle differenze tra il modello computazionale delle Macchine di Turing e quello delle URM e' che nel primo modello vengono manipolate stringhe di simboli, mentre nel secondo numeri naturali.

Quindi, mentre domini e codomini delle funzioni calcolate a URM sono sempre i Numeri Naturali, le macchine di Turing possono calcolare funzioni che hanno come dominio (e codominio) qualsiasi insieme i cui elementi si possano rappresentare come stringhe di caratteri. I domini (e codomini) delle funzioni calcolabili da macchine di Turing sono quindi tutti quegli insiemi per i quali sia possibile definire una funzione di codifica e decodifica (vedi Introduzione [CB]). Brevemente, preso un alfabeto A, una funzione di codifica per un insieme X e' una funzione iniettiva

 cod: X -> A*

Mentre la relativa funzione di decodifica e' una funzione

 decod: A* -> X U {errore}

tale che, per ogni y appartenente ad X,

 decod(cod(y)) = y

Poiche' i numeri naturali si possono codificare con stringhe sull'alfabeto {0,1}, le macchine di Turing possono lavorare anche sui numeri naturali, oltre che su molti altri domini e codomini.
Questa apparente maggiore potenza del modello delle TM rispetto a quello delle URM esiste pero' solo dal punto di vista espressivo, e non sostanziale. E' infatti una differenza inessenziale dal punto di vista della teoria della computazione.

Non e' difficile dimostrare infatti (come vedremo nel seguito), che se un elemento di un insieme e' codificabile come stringa di caratteri e' anche codificabile come numero naturale (considerando cioe' l'insieme N dei numeri naturali al posto di A* nella definizione precedente).
Questo implica che se per un insieme X esiste una funzione di codifica (e decodifica) su stringhe di qualche alfabeto A, esiste anche una funzione di codifica (e decodifica) su stringhe dell'alfabeto {0,1}.
La possibilita' di restringersi a codifiche sui numeri naturali e' il motivo per cui nella Teoria della Calcolabilita' (tradizionalmente chiamata anche Teoria della Ricorsivita', in cui si studiano le funzioni calcolabili in modo effettivo) spesso ci si restringe (come si fa con le URM) a studiare solamente le funzioni che hanno come dominio e codominio l'insieme dei numeri naturali.

Vediamo ora come sia possibile codificare con un numero naturale una qualsiasi stringa (non vuota) su un alfabeto.
Per prima cosa osserviamo che i caratteri di un alfabeto si possono ovviamente rappresentare con dei numeri naturali. Per esempio potremmo decidere di rappresentare i caratteri dell'alfabeto {a,b,g,d} con i numeri naturali 0,1,2 e 3, oppure con i numeri 8,23,15 e 4, o in altro modo.

Dopo di che, mostriamo come codificare una coppia di numeri naturali con un numero naturale. Questo si puo' fare in vari modi, uno di questi e' il metodo di Cantor (che, fornendo una funzione di codifica iniettiva e suriettiva tra NxN ed N - quindi senza utilizzare "error" - permette anche di dimostrare che NxN ha la cardinalita' di N).
Prendiamo una tabella in cui ci siano tutti i numeri naturali sulle righe e tutti i numeri naturali sulle colonne:

      0    1    2   3   4   5   6   7   ........
-------------------------------------------.......
 0 |                             
   |
 1 |  
   |
 2 |  
   |
 3 |  
   |
 4 | 
   |
 5 | 
   |
 6 | 
   |
 7 | 
   |
 . |
 . |
 . |
 .

Ogni casella nella tabella sara' identificata quindi da una coppia di numeri naturali.
Riempiamo ora tutte le caselle della tabella con tutti i numeri naturali, procedendo per diagonali, da destra in alto a sinistra in basso.
La prima diagonale e' fatta da una sola casella, che riempiamo con 0.

      0    1    2   3   4   5   6   7   ........
-------------------------------------------.......
 0 |  0
   |
 1 |
   |
 2 |
   |
 3 |
   |
 4 |
   |
 5 |
   |
 6 |
   |
 7 |
   |
 . |
 . |
 . |
 .

Procediamo poi a riempire la seconda diagonale.

      0    1    2   3   4   5   6   7   ........
-------------------------------------------.......
 0 |  0   1
   |
 1 |  2
   |
 2 |
   |
 3 |
   |
 4 |
   |
 5 |
   |
 6 |
   |
 7 |
   |
 . |
 . |
 . |
 .

Poi la terza diagonale

      0    1    2   3   4   5   6   7   ........
-------------------------------------------.......
 0 |  0    1    3
   |
 1 |  2    4
   |
 2 |  5
   |
 3 |
   |
 4 |
   |
 5 |
   |
 6 |
   |
 7 |
   |
 . |
 . |
 . |
 .

e cosi' via per tutte le diagonali. Consideriamo quindi l'intera tabella infinita come se fosse stata riempita tutta in questo modo.

     
      0    1    2   3   4   5   6   7   ........
-------------------------------------------.......
 0 |  0    1    3   6  10  15  21  28   36   ......
   |
 1 |  2    4    7  11  16  22  29  37   ......
   |
 2 |  5    8   12  17  23  30  38  .....
   |
 3 |  9   13   18  24  31  .....
   |
 4 | 14   19   25  32  .......
   |
 5 | 20   26   33  .......
   |
 6 | 27   34   ......
   |
 7 | 35   ....... 
   |
 . | ......
 . | 
 . |
 .

E' quindi chiaro come tutti i numeri naturali possano venire "sistemati" nelle caselle di tale tabella infinita. Poiche' ogni casella e' individuata da una coppia di numeri naturali e ogni casella contiene un numero naturale diverso da quello di tutte le altre caselle, ecco pronta la nostra codifica iniettiva e suriettiva su N delle coppie di numeri naturali: una coppia (n,m) viene codificata con il numero naturale contenuto nella casella identificata dalla riga n e dalla colonna m.
La nostra codifica e' ovviamente una funzione calcolabile (l'algoritmo che, presa la coppia (n,m), restituisce la sua rappresentazione non e' difficile da costruire, come anche l'algortmo che calcola l'inverso di tale funzione. Si puo' fare come esercizio). La rappresentazione di (3,1) sara' 11. Mentre 26 e' la rappresentazione di (1,5).

Se quindi consideriamo l'alfabeto {a,b,g,d} i cui caratteri decidiamo di rappresentare con i numeri naturali 0,1,2 e 3, come e' possibile rappresentare la stringa "agaa"? Facile, prendiamo i numeri che rappresentano i primi due caratteri: 0 e 2, e rappresentiamo con il metodo di Cantor la coppia (0,2). Tale rappresentazione e' 3. Prendiamo ora il terzo carattere della stringa, a, corrispondente al numero 0 e consideriamo il numero corrispondente alla coppia (3,0), che e' 9. Ora, il numero corrispondente alla coppia (9,0), dove 1 rappresenta il carattere a, e' il numero 44. La nostra rappresentazione della stringa "agaa" sara' quindi la rappresentazione della coppia (44,4) dove 4 e' la lunghezza della nostra stringa.

Se indichiamo quindi con c il numero che rappresenta un carattere c e con

(-,-)': NxN -> N

la funzione che codifica coppie di naturali con il metodo di Cantor, la nostra codifica

cod: A⁺ -> N

sara' formalmente definita come segue:

cod(c₁c₂...c_n) = ((...(..((c₁,c₂)',c₃)'...)',c_n)',n)'

Notare che l'uso finale della lunghezza della stringa serve a far si che la funzione tra stringhe e numeri naturali definita in questo modo sia invertibile. Perche'?
Inoltre, per semplicita', non abbiamo preso in considerazione la stringa vuota. Perche?

Ovviamente quella proposta e' solo una tra le tante possibilita' di codificare stringhe finite con numeri naturali.

La cosa simpatica e' che si possono codificare con numeri naturali anche le macchine di Turing, o le URM. Il che implica che e' possibile codificare algoritmi con numeri naturali.
In che modo? Semplice. Un'istruzione URM non e' forse rappresentata come stringa di caratteri? E cos'e' una URM se non una sequenza di istruzioni?
Se quindi vediamo una URM come sequenza di caratteri, la possiamo facilmente codificare con un numero naturale. Lo stesso discorso si puo' fare con le macchine di Turing, o con altri modelli computazionali.