Capitolo 7:

Teoria generale della calcolabilita

1

Differenti nozioni di calcolabilita (che seguono da differenti mod-

elli di calcolo) portano a definire la stessa classe di funzioni.

Le tecniche di simulazione fra modelli introducono i concetti di

configurazione, calcolo e codifica. Possiamo formulare una teoria

astratta della calcolabilita, indipendente dal modello di calcolo

adottato??

Tesi di Church-Turing: ogni funzione calcolabile rispetto ad

una qualunque nozione di algoritmo (Turing, Kleene, λ-calcolo,

Markov, Post) e calcolabile secondo Turing.

2

Quindi si congettura che la classe delle funzioni ricorsive sia la

classe di funzioni piu generale per la quale si possa dare un

metodo di calcolo algoritmico.

Se si accetta tale tesi, si possono utilizzare descrizioni informali di

algoritmi per dimostrare la calcolabilita di funzioni senza esibire

una macchina che le calcola.

3

Una enumerazione delle macchine a registri elementari

Abbiamo visto che ogni funzione calcolata tramite una macchina

a registri elementare e ricorsiva (associando numeri naturali agli

stati della macchina e alle sequenze di stati).

Mostriamo che anche i programmi per macchine a registri el-

ementari possono essere codificati (cioe esiste una aritmetiz-

zazione o godelizzazione). Ricordiamo che ogni programma el-

ementare e formato da un numero finito di istruzioni del tipo:

Ri = Ri+ 1 i ≥ 1, n ≥ 0Ri = Ri

.− 1

IF Ri = 0 GOTO 0

4

Per codificare una istruzione abbiamo bisogno:

Xdel suo posto nella sequenza di istruzioni,

Xdel suo tipo,

Xdei numeri i ed n che essa contiene.

Un modo per codificare queste informazioni e il seguente:

Ri = Ri+ 1 −→ 3 · (i.− 1) + 1

Ri = Ri.− 1 −→ 3 · (i

.− 1) + 2

IF Ri = 0 GOTO n −→ 3 · J(i.− 1, n)

dove J : N× N 7−→ N+ e la biiezione

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

2+ x+ 1

5

Il codice dell’istruzione m-esima e usato come esponente per il

numero primo pm (p1 = 2); se il programma ha k istruzioni il suo

codice sara 2y1 . . . pykk , oppure 〈y1, . . . , yk〉, dove y1, . . . , yk sono i

codici delle istruzioni.

Esempio 1 Codifichiamo il seguente programma:

IF R2 = 0 GOTO 0 → 3 · J(1,0) = 9R2 = R2

.− 1 → 3 · 1 + 2 = 5

R1 = R1 + 1 → 3 · 0 + 1 = 1IF R3 = 0 GOTO 1 → 3 · J(2,1) = 27

e quindi il codice e 29 · 35 · 51 · 727, oppure 〈9,5,1,27〉 .

6

La codifica e la decodifica sono entrambe funzioni biiettive (perche?);ad ogni intero

x = 2y1 . . . pymm dove yi

≥ 0 se 1 ≤ i ≤ m,

> 0 se i = m

corrisponde un programma di m istruzioni, in cui la j-esimaistruzione e ottenuta dividendo yi per 3 ed individuando restoe quoziente.

Esempio 2 Al numero 600 corrisponde il programma:

IF R1 = 0 GOTO 0R1 = R1 + 1R1 = R1

.− 1

quale funzione calcola questo programma?

7

Importante: la codifica di un programma produce interi x =

2y1, . . . , pykk , con y1, . . . , yk > 0. Invece, la decodifica di un numero

naturale puo produrre situazioni in cui all’istruzione j-esima cor-

risponde yj = 0.

Per evitare questo problema, introduciamo l’istruzione NOPE

(con codice 0) che non fa nulla.

Esercizio: quale programma e rappresentato dal numero 29 ·55 ·7 · 1127??

Esercizio: Definire una macchina a registri (non elementare)

che dati in input due naturali x e y, determini l’output che una

macchina a registri elementare con codifica x ha per input y.

8

Una enumerazione delle macchine di Turing

Realizziamo una corrispondenza biunivoca fra macchine di Turing

e numeri naturali. Sia data una macchina M = 〈Γ, 6 b,Q, q0, F, δ〉,la cui funzione di transizione e

δ : (Q− F )× (Γ ∪ {6 b}) 7−→ Q× (Γ ∪ {6 b})× {d, s, i}.

Ogni coppia (q, a) per cui la δ non e definita e codificata come

(q, a,⊥,⊥,⊥). Elenchiamo in ordine lessicografico le quintuple

che costituiscono la funzione di transizione, introducendo un or-

dinamento arbitrario sugli insiemi Q∪ {⊥}, Γ∪ {6 b,⊥}, {d, s, i,⊥}.

Questo ordinamento induce un ordinamento fra le quintuple e,

di conseguenza, sulle sequenze di quintuple e sulle codifiche di

macchine di Turing.

9

Enumerazione delle funzioni ricorsive

I metodi definiti determinano una corrispondenza naturali e mac-chine (di Turing o a registri), ma anche fra funzioni ricorsive enumeri naturali.

Sia E : N 7−→ {M} una biiezione fra i naturali e le descrizionidi macchine di Turing, tale che E(x) = Mx, la (x + 1)-esimamacchina dell’enumerazione. Data una codifica C dei naturali suun opportuno alfabeto (quello di nastro della macchina), defini-amo

ϕx(y) =

z ∈ N se la macchina Mx, inizializzata nella

configurazione iniziale q0C(y),si arresta nella configurazione finale C(y) 6 bqFC(z)

indefinita altrimenti.

10

Si ottiene una enumerazione delle funzioni ricorsive ad un argo-

mento (domanda: quale posto occupa la funzione ϕx in questa

enumerazione? la corrispondenza fra naturali e funzioni ricorsive

a un posto e una biiezione?)

Si puo estendere l’enumerazione a funzioni a piu argomenti at-

traverso una opportuna codifica (definirne una).

Il valore x associato alla funzione ϕx si dice indice della funzione

(calcolata dalla macchina Mx).

Dato che x e il numero naturale che codifica la macchina Mx,

esso e anche chiamato il programma che calcola la funzione ϕx.

11

Proprieta di enumerazioni di funzioni ricorsive

L’enumerazione ci consente di formulare i risultiti della teoria

della ricorsivita in modo indipendente dalla macchina.

Tutta l’informazione relativa ad una particolare classe di mac-

chine o programmi e contenuta negli indici delle funzioni, e da

origine ad una enumerazione (magari diversa dalle precedenti)

che gode sempre delle stesse proprieta generali.

Una dimostrazione fornita assumendo una enumerazione per un

certo modello di calcolo diventa valida per tutte le enumerazioni

associate ad altri modelli di calcolo.

12

Teorema 3 (esistenza della funzione universale) Sia data una

qualsiasi enumerazione delle funzioni ricorsive. Per ogni k ∈ Nesiste z tale che, per ogni x1, . . . , xk:

ϕz(x1, . . . , xk, y) =

ϕy(x1, . . . , xk) se essa e definita,

indefinita altrimenti.

Teorema 4 (s-m-n) Sia data una qualsiasi enumerazione delle

funzioni ricorsive. Per ogni m,n ≥ 1 esiste una funzione ricorsiva

s tale che, per ogni x, y1, . . . , ym, z1, . . . , zn:

ϕx(y1, . . . , ym, z1, . . . , zn) = ϕs(x,y1,...,ym)(z1, . . . , zn)

13

Teorema 5 (forma normale di Kleene) Sia data una qualsiasi

enumerazione delle funzioni ricorsive. Esistono una funzione ri-

corsiva U e un insieme di funzioni ricorsive Tk tali che, per ogni

k ∈ N, tutte le funzioni ricorsive di k argomenti sono esprimibili

come segue:

ϕi(x1, . . . , xk) = U(µt[Tk(i, x1, . . . , xk, t) = 0]).

Il teorema mostra che una funzione ricorsiva e calcolabile at-

traverso il calcolo di due funzioni: la prima (il predicato di

Kleene) verifica che esista una computazione ammissibile; la sec-

onda, che spacchetta il codice della computazione per restituire

il risultato.

14

Funzioni non calcolabili

Abbiamo gia introdotto i concetti di funzione calcolabile, non

calcolabile, di insieme decidibile e semidecidibile.

Possiamo riformulare quanto visto in modo indipendente dal

modello di calcolo, avendo introdotto il concetto di enumer-

azione di funzioni ricorsive.

Teorema 6 Sia data una qualsiasi enumerazione delle funzioni

ricorsive. Non esiste alcuna funzione ricorsiva g tale che per ogni

x e y:

g(x, y) =

1 se ϕx(y) e definita,

0 altrimenti.

15

Teorema 7 Non esiste alcuna funzione ricorsiva g′ tale che per

ogni x:

g′(x) =

1 se ϕx(x) e definita,

0 altrimenti.

Corollario 8 Sia data una qualsiasi enumerazione delle funzioni

ricorsive. Gli insiemi

K = {x|ϕx(x)e definita} e K′ = {〈x, y〉|ϕx(y)e definita}

non sono decidibili.

16

Teorema 9 Sia data una qualsiasi enumerazione delle funzioni

ricorsive. Non esiste una funzione ricorsiva g tale che per ogni x:

g(x) =

1 se ϕx(0) e definita,

0 altrimenti.

Xdecidere se un generico programma si arresta su un generico

input

Xdecidere se un generico programma si arresta avendo come in-

put il proprio codice

Xdecidere se un generico programma si arresta con input prefis-

sato

sono problemi con la stessa difficolta.

17

Applicando le tecniche precedenti, si provano i seguenti risultati:

Teorema 10 Sia data una qualsiasi enumerazione delle funzioni

ricorsive. Non esiste una funzione ricorsiva g tale che per ogni x:

g(x) =

1 se ϕx(0) e costante,

0 altrimenti.

Teorema 11 Sia data una qualsiasi enumerazione delle funzioni

ricorsive. Non esiste una funzione ricorsiva g tale che per ogni

x, y, z:

g(x, y, z) =

1 se ϕx(y) = z,

0 altrimenti.

18

Teorema 12 Sia data una qualsiasi enumerazione delle funzioni

ricorsive. Non esiste una funzione ricorsiva g tale che per ogni

x, y:

g(x, y) =

1 se ϕx = ϕy e definita,

0 altrimenti.

Dimostreremo che ogni proprieta non banale e indecidibile.

Tutte le dimostrazioni precedenti si riconducono alla indecidibilita

del problema della terminazione. Un metodo alternativo con-

siste nell’utilizzare la diagonalizzazione (rifare le dimostrazioni

con questo metodo).

19

Indecidibilita in matematica e informatica

Esistono numerosi problemi indecidibili in diversi settori della

matematica e dell’informatica. Ad esempio, nella teoria dei lin-

guaggi formali:

Xdate due grammatiche context-free G1 e G2, L(G1) = L(G2)?

Xdate due grammatiche context-free G1 e G2, L(G1)∩L(G2) = ∅?

Xdata una grammatica contenstuale G, L(G) e vuoto?

20

Nell’ambito della teoria della programmazione (riferendoci ad un

linguaggio specifico, e non ad un modello di calcolo generico):

Xun programma che contiene una dichiarazione di proceduram

chiamera la procedura stessa?

Xuna variabile di programma assumera un particolare valore du-

rante l’esecuzione del programma?

Xun programma, in presenza di un particolare input, fornisce un

determinato output?

Xdue programmi calcolano la stessa funzione?

21

Xun programma calcola una funzione costante?

Xun programma calcola una funzione totale?

Nel campo della matematica:

Xdata una formula del calcolo dei prodicati, tale formula e un

teorema?

Xdata una formula dell’aritmetica, tale formula e un teorema

della teoria?

22

Esistono casi in cui una funzione e calcolabile, ma non siamo in

grado di conoscere il programma che la calcola. Ad esempio:

g(x) =

1 se nell’espansione di π esistono

almeno x 5 consecutivi,

0 altrimenti

e sicuramente calcolabile, ma non sappiamo quale sia l’algoritmo

corretto per calcolarla.

23

Teoremi di Kleene e Rice

Teorema 13 (ricorsione o di Kleene) Sia data una enumerazione

delle funzioni ricorsive. Se t e una funzione calcolabile totale,

allora esiste e ∈ N tale che:

ϕe = ϕt(e).

Il teorema si dice anche del punto fisso. Dato un insieme S e

una funzione τ : S 7−→ S, si dice punto fisso di τ il valore s ∈ S

tale che τ(s) = s.

Corollario 14 Sia data una enumerazione delle funzioni ricor-

sive. Esiste un indice i tale che, per ogni x ∈ N si ha ϕi(x) = i.

24

Teorema 15 (Rice) Sia data una enumerazione delle funzioni

ricorsive e sia F un insieme di funzioni calcolabili. L’insieme

S = {x|ϕx ∈ F} e decidibile sse F = ∅ oppure F coincide con

l’intera classe delle funzioni calcolabili.

Il teorema sancisce quanto promesso: ogni proprieta non banale

delle funzioni calcolabili e indecidibile; I teoremi precedenti sono

applicazioni del teorema di Rice.

Una conseguenza importante nella teoria della programmazione

e che e impossibile provare proprieta delle funzioni calcolate dai

programmi (costanza, crescenza, correttezza).

25

Insiemi decidibili e semidecidibili

Abbiamo gia introdotto i concetti di insieme decidibile e semide-

cidibile, con riferimento alla T-calcolabilita. Possiamo riformu-

lare quanto visto astraendo dal modello di calcolo.

Definizione 16 Un insieme A ⊆ N e detto ricorsivo se la sua

funzione caratteristica CA:

CA(x) =

1 se x ∈ A,0 altrimenti

e ricorsiva totale.

26

Definizione 17 Un insieme A ⊆ N e detto ricorsivamente enu-

merabile (r.e.) se A = ∅ o se esiste una funzione ricorsiva totale

f : N 7−→ N tale che A = imm(f). In tal caso diciamo che la

funzione f enumera l’insieme A.

Dimostreremo che

la classe degli insiemi ricorsivi (risp., ricorsivamente enumerabili)

coincide con

la classe degli insiemi decidibili (semidecidibili).

27

Esempio 18 Xl’insieme dei numeri pari e ricorsivo?

Xl’insieme dei numeri primi e ricorsivo o r.e.?

Xl’insieme {〈y, t〉|ϕy(y)si arresta in meno di t passi } e ricorsivo?

Xl’insieme K = {y|ϕy(y)e definita} e ricorsivo?

Xl’insieme Z = {〈x, y, z〉|ϕx(y) = z} e ricorsivo?

Xl’insieme T = {x|ϕxe totale} e ricorsivo?

28

Forniamo tre proprieta sugli insiemi ricorsivi:

Teorema 19 Un insieme S ⊆ N e ricorsivo sse e decidibile.

Teorema 20 Se un insieme A e ricorsivo allora l’insieme com-

plemento A = N−A e ricorsivo.

Teorema 21 Se insiemi A e B sono ricorsivi allora gli insiemi

A ∩B e A ∪B sono ricorsivi.

29

Teorema 22 Sia dato un insieme S ⊆ N; sono equivalenti:1. S e ricorsivamente enumerabile;2. S e semidecidibile;3. S e il dominio di una funzione gS parziale calcolabile;4. S e l’immagine di una funzione hS parziale calcolabile.

Conseguenza di questo risultato:(i) gli insiemi ricorsivi sono decidibili, e(ii) la classe degli insiemi decidibili ⊂ quella dei semidecidibiliallora ogni insieme ricorsivo e anche r.e., ed esistono insiemi r.e.,ma non ricorsivi.

Esempio 23 L’insieme K = {x|ϕx(x)e definita} non e ricorsivo,ma e r.e. Infatti K = dom(ψ), dove:

ψ(x) =

1 se ϕx(x) e definita,

indefinita altrimenti.

30

Teorema 24 L’insieme T = {x|ϕxe totale} non e ricorsivamente

enumerabile

Teorema 25 Se insiemi A e B sono ricorsivamente enumerabili

allora gli insiemi A ∩B e A ∪B sono ricorsivamente enumerabili.

Teorema 26 Se un insieme A e ricorsivamente enumerabile e se

l’insieme complemento A = N−A e ricorsivamente enumerabile,

allora A e ricorsivo.

Come conseguenza di questo teorema, se un insieme e r.e., ma

non ricorsivo, allora il suo complemento non e r.e.

Questo significa che il complemento di un insieme r.e., ma non

ricorsivo, ha delle proprieta di indecidibilita maggiori dell’insieme

stesso.31

Esempio 27 L’insieme K = {y|ϕy(y) non e definita} non e r.e.

Infatti K e semidecidibile, e quindi r.e.; ma K non e ricorsivo, e

quindi K non puo essere r.e.

Per verificare se ”x appartiene a K” dobbiamo verificare se esiste

y tale che ϕx(x) si arresta in meno di y passi.

Per verificare se ”x appartiene a K” dobbiamo verificare se

per ogni y,ϕx(x) richiede piu di y passi.

XI predicati ”ϕx(x) richiede meno di y passi” e ”ϕx(x) richiede

piu di y passi” sono entrambi decidibili.

XIl predicato ”esiste y tale che ϕx(x) richiede meno di y passi”

e ricorsivamente enumerabile.

XIl predicato ”per ogni y ϕx(x) richiede piu di y passi” non e r.e.

32

Il fenomeno vale in generale:

Teorema 28 Sia A ⊆ N non vuoto. A e ricorsivamente enumer-

abile sse esiste un insieme ricorsivo B ⊆ N2 tale che x ∈ A sse

∃y[(x, y) ∈ B].

Teorema 29 Sia A ⊆ N. A e il complemento di un insieme

ricorsivamente enumerabile sse esiste un insieme ricorsivo B ⊆ N2

tale che x ∈ A sse ∀y[(x, y) ∈ B].

Gli ultimi due risultati possono essere estesi al caso in cui siano

usati piu quantificatori esistenziali ed universali alternati.

33

Definizione 30 Per ogni insieme A ⊆ N, A ∈ Σk se esiste un

predicato ricorsivo P (x, y1, . . . , yk) tale che

x ∈ A sse ∃y1∀y2 . . . QykP (x, y1, . . . , yk),

dove Q = ∃ per k dispari, Q = ∀ per k pari.

Definizione 31 Per ogni insieme A ⊆ N, A ∈ Πk se esiste un

predicato ricorsivo P (x, y1, . . . , yk) tale che

x ∈ Asse∀y1∃y2 . . . QykP (x, y1, . . . , yk),

dove Q = ∀ per k dispari, Q = ∃ per k pari.

34

Definizione 32 Per ogni insieme A ⊆ N, A ∈ ∆k se A ∈ Σk e

A ∈ Πk.

Dalle definizioni deriva che A ∈ Σn se e solo se A ∈ Πn.

L’insieme delle classi Σk e Πk si chiama gerarchia di Kleene o

aritmetica.

Σ0 e Π0 coincidono con la classe degli insiemi ricorsivi;

Σ1 coincide con la classe degli insiemi r.e.;

Π1 con la classe degli insiemi complemento di insiemi r.e.

35

Due proprieta fondamentali:

(i) ∀i[Σi ( Σi+1] e ∀i[Πi ( Πi+1];

(ii) ∀i[Σi ∪Πi ⊂ Σi+1 ∩Πi+1].

La gerarchia aritmetica e utilizzata per esprimere il livello di inde-

cidibilita di un insieme; ad esempio, l’insieme T = {x|ϕx e totale }coincide con l’insieme {x|∀y∃k[ϕx(y) richiede meno di k passi]};quindi T appartiene a Π2.

36