Codifica di programmi

Codifica di programmi

Gianluca Gippetto 1

Studente del CdL in InformaticaUniversit degli Studi di Palermo

Anno accademico 2010-11

1Slide basate sul testo: Davis,Sigal,Weyuker Computability, Complexity andLanguagesG.Gippetto (Studente Unipa) Codifica di programmi A.A. 2010-11 1 / 26

Indice

1 Metodi di codificaFunzione coppiaNumeri di Gdel

2 Codifica di programmiCodifica di unistruzioneCodifica di un programma

G.Gippetto (Studente Unipa) Codifica di programmi A.A. 2010-11 2 / 26

La funzione coppia

In matematica, una funzione coppia una funzione biunivoca del tipoN2 N, ossia una funzione che codifica coppie di numeri naturali in unsingolo numero naturale. Noi utilizzeremo la seguente:

DefinizioneChiameremo funzione coppia la seguente

x, y = 2x(2y + 1) 1

Affinch la funzione coppia sia effettivamente un buon metodo di codifica,lequazione

x, y = zdeve ammettere ununica soluzione. Proviamo che cos.


Biunivocit della funzione coppia

Dalla equazione2x(2y + 1) 1 = z

otteniamo la seguente

2y + 1 =z + 1

2x

Dovendo essere il II membro un numero naturale dispari, si deduce che x necessariamente il massimo naturale tale che 2x|z + 1. Dal momento che x univocamente determinato, lo anche y.


Funzioni l ed r per la decodifica

Lequazione x, y = z definisce quindi le due funzioni:

l(z) = x r(z) = y(l da left, sinitra) (r da right, destra)

Poich x, y < z + 1, abbiamo che l(z) z ed r(z) z. Questo cipermette di scrivere:

l(z) = minxz[(y)z (z = x, y)

]r(z) = min

yz[(x)z (z = x, y)

]Le funzioni l ed r sono dunque ricorsive primitive.


Esempio di decodifica

Ricordando che z = x, y = 2x(2y + 1) 1.Sia z = 35. Si ha:

2y + 1 =36

2x

Il massimo naturale x tale che 2x divide 36 2. Da cui:

2y + 1 =36

4= 9 = y = 4

Riassumendo:2, 4 = 35


Riepilogo

Teorema (della funzione coppia)Le funzioni x, y, l(z), r(z) hanno le seguenti propriet:

1 sono ricorsive primitive2 l(x, y) = x3 r(x, y) = y4 l(z), r(z) = z5 l(z), r(z) z


Numeri di Gdel

DefinizioneChiamiamo numero di Gdel della n-upla (a1, . . . , an) il numero

[a1, . . . , an] =ni=1

paii

dove pi denota li-esimo numero primo.

Per esempio:[2, 11, 4, 7, 6] = 22 311 54 77 116

Dimostreremo dopo che [a1, . . . , an] ricorsiva primitiva.


Bont della codifica

Il teorema fondamentale dellaritmetica, il quale afferma che un intero esprimibile in un unico modo come prodotto di numeri primi (a menodellordine dei fattori), ci assicura che la numerazione di Gdel gode dellapropriet di unicit:

[a1, . . . , an] = [b1, . . . , bn] (a1, . . . , an) = (b1, . . . , bn)


Unosservazione sulla codifica

Osserviamo per che, data una sequenza s, ogni altra sequenza t ottenutada s aggiungendovi uno o pi 0 consecutivi alla fine (a destra), ha ilmedesimo numero di Gdel di s:

[a1, . . . , an] = [a1, . . . , an, 0]

poich p0n+1 = 1

Dal momento che

1 = 20 = 20 30 = 20 30 50 = . . .

naturale porre 1 come il numero di Gdel della sequenza vuota dilunghezza 0.

N.B.: non accade la stessa cosa di sopra aggiungendo degli 0 a sinistra!


Ricorsivit primitiva di [a1, . . . , an]

Le funzioni che compaiono nella definizione di [a1, . . . , an] sono:produttoria,elevamento a potenza,successione pi dei numeri primi.

Sappiamo gi che le prime due sono ricorsive primitive, ci rimane dadimostrare che lo anche la successione pi dei numeri primi.


Ricorsivit primitiva di pi (1)

Affinch pi sia ricorsiva primitiva, deve essere una funzione totale, quindidefinita anche per i = 0: porremo p0 = 0.La definizione sar una cosa di questo tipo:{

p0 = 0

pn+1 = mintH[Primo(t) t > pn

]Il problema quello di fissare, per ogni n, un H sicuramente maggiore ouguale di pn+1.



Ci viene in aiuto la tecnica utilizzata da Euclide per dimostrare che esistonoinfiniti numeri primi.

1 Dati i primi n numeri primi, consideriamo il numero:

Qn = p1 . . . pn + 1

2 Qn non divisibile per nessuno dei primi n numeri primi; infatti, per1 i n si ha:

Qnpi

=p1 . . . pn + 1

pi= p1 . . . pi1 pi+1 . . . pn +

1

pi

3 Concludiamo che Qn o primo, oppure divisibile per un numeroprimo maggiore di pn.



Conseguenze del ragionamento precedente:esistono infiniti numeri primi (ci che voleva trovare Euclide);Per ogni n, Qn qn+1 (ci che interessa noi in questo momento).

Qn dunque un buon limite da imporre alla minimalizzazione limitata.E a maggior ragione lo il numero pn! + 1 Qn. Porremo perci:{

p0 = 0

pn+1 = mintpn!+1[Primo(t) t > pn

]Concludiamo che pi ricorsiva primitiva, e di conseguenza ricorsivaprimitiva anche la funzione di Gdel .


Decodifica di un numero di Gdel

Vogliamo definire una funzione che applicata al numero di Gdel x cifornisca li-esimo termine della n-upla codificata da x, cio tale che sex = [a1, . . . , an], allora:

(x)i = ([a1, . . . , an])i = ai

E facile convincersi che (x)i il massimo esponente k tale che pki |x.Possiamo dunque definire (x)i come segue:

(x)i = mintx((pt+1i |x))

La funzione (x)i evidentemente ricorsiva primitiva.


Lunghezza della ennupla codificata

Unaltra cosa che gradiremmo conoscere di un numero di Gdel x lalunghezza della n-upla che codifica.Essa coincide con lindice i del numero primo pi grande che divide x.La funzione cercata pu ottenersi nel modo seguente 2:

Lt(x) = minix

[(x)i 6= 0 (j)x (j i (x)j = 0)

]Essa evidentemente ricorsiva primitiva.

2Lt sta per lenght, lunghezzaG.Gippetto (Studente Unipa) Codifica di programmi A.A. 2010-11 16 / 26

Codifica di programmi

In questa sezione, vedremo come associare a ciascun programma P nellinguaggio S un numero, che indicheremo con #(P ), in modo taleche P pu essere integralmente ricostruito a partire da #(P ).Naturalmente utilizzeremo i metodi di codifica appena visti. Inparticolare, dato un programma P:

codificheremo ogni istruzione di P (singolarmente) utilizzando lafunzione coppia;applicheremo poi alla lista (ordinata) dei codici delle istruzioni cosottenuta, la funzione di Gdel , trovando il codice dellinteroprogramma.


Codifica di unistruzione: elementi in gioco

Quali elementi caratterizzano una istruzione del linguaggio S a parte laposizione che essa occupa allinterno del programma?

1 Il tipo di istruzione (incremento, decremento, . . . )2 La variabile coinvolta3 Leventuale etichetta


Numerazione di variabili ed etichette

Ordiniamo variabili ed etichette come segue:

Y,X1, Z1, X2, Z2, X3, Z3, . . .

A1, B1, C1, D1, E1, A2, B2, C2, . . .

Denoteremo con #(V ) e con #(L) rispettivamente la posizione dellavariabile V e la posizione delletichetta L nellordinamento dato.Riferendoci agli elenchi sopra, avremo per esempio:

#(X2) = 4, #(Z1) = 3

#(C1) = 3, #(A2) = 6


Codifica di unistruzione

Sia I unistruzione. Definiamo:

#(I) = a, b, c

dove:1 Se I ha unetichetta L, allora a = #(L) , altrimenti a = 0.2 Se la variabile V compare in I, allora c = #(V ) 13 Il valore di b varia a seconda del tipo di istruzione:

Tipo istruzione Valore di b

V V 0V V + 1 1V V 1 2if V 6= 0 goto A #(A) + 2


Decodifica di unistruzione

TeoremaPer ogni numero dato q, vi ununica istruzione I tale che #(I) = q.

I tre a, b, c tali che a, b, c = q sono infatti univocamente determinati:a = l(q), b = l(r(q)), c = r(r(q))

Ottenuti a, b, c, basta seguire al contrario le indicazioni della slideprecedente per trovare listruzione I:

1 se a = 0, I non etichettata,altrimenti ha la a-esima etichetta della lista;

2 la variabile V coinvolta la (c+ 1)-esima della lista;3 listruzione sar:

V V se b = 0V V + 1 se b = 1V V 1 se b = 2if V 6= 0 goto A se b > 2 e b 2 = #(A)


Codifica di un programma

Dato un programma P , composto dalla sequenza di istruzioni I1, . . . , In,definiamo #(P ) come il numero di Gdel della sequenza #(I1), . . . ,#(In)diminuito di 1:

#(P ) = [#(I1), . . . ,#(In)] 1Naturalmente, per ricostruire un programma P a partire da #(P ) sarsufficiente:

Trovare x = #(P ) + 1 = [#(I1), . . . ,#(In)]Per j = 1 n:

estrarre il codice della j-esima istruzione del programma: #(Ij) = (x)jdecodificare listruzione Ij


Esempio di codifica di un programma (1)

Si consideri il seguente programma:

[A] X X + 1 (I1)if X 6= 0 goto A (I2)

Abbiamo #(I1) = 1, 1, 1:a = 1, poich letichetta A occupa la prima posizione.b = 1, poich listruzione del tipo V V + 1c = #(X) 1 = 2 1 = 1

Effettuando i calcoli:

1, 1 = 21(2 1 + 1) 1 = 5

1, 5 = 21(2 5 + 1) 1 = 21#(I1) = 21



La seconda istruzione da codificare

if X 6= 0 goto A

Abbiamo #(I2) = 0, 3, 1a = 0, poich listruzione non etichettatab = #(A) + 2 = 3

c = #(X) 1 = 1Effettuando i calcoli:

3, 1 = 23(2 1 + 1) 1 = 23

0, 23 = 20(2 23 + 1) 1 = 46#(I2) = 46



Concludiamo che:

#(P ) = [#(I1),#(I2)] 1= [21, 46] 1= 221 346 1= 18 586 928 403 505 481 978 329 694 207


Zeri e codifica di Gdel

In precedenza, avevamo osservato che, data una sequenza s, ogni altrasequenza t ottenuta da s aggiungendovi uno o pi 0 consecutivi a destra,ha il medesimo numero di Gdel di s.Lambiguit facilmente eliminabile, decretando che nessun programmapu terminare con listruzione Y Y .Tale istruzione appunto quella di codice 0, ottenendosi da 0, 0, 0 = 0

a = 0, poich listruzione non etichettata.b = 0, per il tipo di istruzione.c = #(Y ) 1 = 1 1 = 0.


Metodi di codificaFunzione coppiaNumeri di Gdel

Codifica di programmiCodifica di un'istruzioneCodifica di un programma

Codifica di programmi

Documents

Transcript of Codifica di programmi