Strings vs Natural Numbers

Strings vs Natural Numbers

Una delle differenze tra il modello computazionale delle Macchine di Turing e quello delle Funzioni Parziali Ricorsive (vedi [SMb], dove sono chiamate μ-ricorsive) e' che nel primo modello vengono manipolate stringhe di simboli, mentre nel secondo numeri naturali.

Quindi, mentre domini e codomini delle funzioni parziali ricorsive 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 ∪ {errore}

tale che, per ogni y appartenente ad X,

 decod(cod(y)) = y

Notare che in [CB] la funzione di codifica e' definita su A^* e non su A⁺. Noi utilizziamo questa definizione per semplicita' poiche' praticamente non cambia nulla.

Poiche' i numeri naturali (che indichiamo con N) 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 Funzioni Parziali Ricorsive esiste pero' solo dal punto di vista espressivo, e non sostanziale. E' infatti una differenza inessenziale dal punto di vista della teoria della computazione.

Abbiamo gia' avuto occasione di vedere nella sezione 1.3.4 del testo di Ausiello come, utilizzando la Definizione 1.50, sia possibile definire un isomorfismo tra A⁺ (con A qualsiasi diverso dal vuoto) ed N.
Questo 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 Funzioni Parziali Ricorsive) a studiare solamente le funzioni che hanno come dominio e codominio l'insieme dei numeri naturali.
L'esistenza di tale isomorfismo permette inoltre di osservare che, se un insieme X ha una funzione di codifica su A⁺ per un qualche A (con relativa funzione di decodifica), allora per X esistera' pure una funzione di codifica (e decodifica) su {0,1}⁺ (poiche' i naturali si codificano facilmente su {0,1}⁺.

Per poter considerare solo funzioni sui naturali in teoria della ricorsivita' e per avere la possibilita' di codificare qualsiasi insieme su {0,1}⁺ (sempre che esista una codifica su un qualche A⁺ per tale insieme), non e' strettamente indispensabile avere un isomorfismo tra A⁺ ed N. Sarebbe sufficiente avere una funzione iniettiva tra A⁺ ed N.

Vediamo come definire una simpatica funzione iniettiva tra i numeri naturali e l'insieme delle stringhe su un qualsiasi alfabeto di cardinalita' almeno 1.
Questa funzione utilizza l'isomorfismo definito da Cantor tra le coppie di numeri naturali ed i numeri naturali (che quindi dimostra che NxN ha la stessa cardinalita' di N).

L'isomorfismo di Cantor tra le coppie di numeri naturali ed i numeri naturali si definisce nel modo seguente.

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.
L'isomorfismo di Cantor e' ovviamente una funzione calcolabile (l'algoritmo che, presa la coppia (n,m), restituisce la sua rappresentazione come numero naturale 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).

Vediamo ora come utilizzare l'isomorfismo di Cantor per definire una funzione iniettiva tra A⁺ ed N.
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. 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 associare in modo iniettivo un numero alla 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 0 rappresenta il carattere a, e' il numero 54. La nostra rappresentazione della stringa "agaa" sara' quindi la rappresentazione della coppia (54,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

l'isomorfismo di Cantor tra coppie di naturali a naturali, la nostra funzione iniettiva tra A⁺ ed N

F: A⁺ -> N

sara' definita come segue:

F(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 F tra stringhe e numeri naturali definita in questo modo sia invertibile sull'immagine di F. Perche'?
Inoltre, per semplicita', non abbiamo preso in considerazione la stringa vuota. Abbiamo considerato A⁺ e non A^*. Perche?

Ovviamente quella proposta e' solo una tra le tante possibilita' di associare stringhe finite con numeri naturali in modo iniettivo.
Una di queste sembrerebbe quella di vedere una stringa come la rappresentazione posizionale in base B di un numero naturale, dove B e' la cardinalita' dell'alfabeto. L'associazione tra stringhe e numeri naturali cosi' definita non sarebbe pero' iniettiva. Perche'?

Spesso una qualsiasi funzione iniettiva viene chiamata "codifica".

La cosa simpatica e' che si possono codificare con numeri naturali (tramite una funzione iniettiva, o addirittura un isomorfismo, come osservato all'inizio di queste note) anche le macchine di Turing, o le Funzioni Parziali Ricorsive. Il che implica che e' possibile codificare algoritmi con numeri naturali.
In che modo? Semplice. Una funzione parziale ricorsiva non e' forse rappresentata dalla stringa di caratteri corrispondente alle equazioni che la definiscono? Se quindi vediamo una funzione parziale ricorsiva 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.