Calcolabilita' e Complessita

Calcolabilita e Complessita

Andrea Asperti

Department of Computer Science, University of BolognaMura Anteo Zamboni 7, 40127, Bologna, ITALY

[email protected]

Andrea Asperti Universita di Bologna - Dipartimento di Scienze dell’Informazione 1

Content

A:CalcolabilitaNumerabilita e diagonalizzazioneRicorsione PrimitivaLe Macchine di Turing e la Tesi di ChurchEnumerazioni accettabiliFunzioni non calcolabiliInsiemi ricorsivi e ricorsivamente enumerabiliI teoremi di Rice e Rice-ShapiroIl teorema del punto fisso di KleeneRiducibilitaCalcolabilita e completezzaLa gerarchia aritmetica


Obiettivi del corso

Fornire una introduzione alla teoria della calcolabilita e della complessita, alfine di chiarire i seguenti concetti:

I Capire quali problemi possono essere risolti in modo algoritimico

I Studiare e confrontate diversi meccanismi e costrutti computazionali

I Fornire una definizione precisa della nozioni di calcolabilita e di decidibilita

I Fornire metodi e strumenti per capire se un problema e o meno decidibile

I Comprendere le implicazioni logiche (Teorema di Incompletezza di Godel)

I Fornire una nozione di costo computazionale

I Classificare i problemi in base alla loro efficienza

I Studiare la relazione tra calcolo deterministico e nondeterministico

I Studiare la relazione tra risorse differenti (tempo e spazio)

I Discutere i principali problemi aperti di teoria della complessita


Approfondimenti bibliografici

Calcolabilita

I S. Barry Cooper, Computability Theory, Chapman & Hall, 2004.

I N. J. Cutland. Computability: An Introduction to Recursive Function Theory.Cambridge University Press, Cambridge, UK, 1986.

I P. G. Odifreddi. Classical Recursion Theory: the Theory of Functions and Setsof Natural Numbers, volume 125 of Studies in Logic and the Foundations ofMathematics. Elsevier, 1997.

I H. Rogers. Theory of Recursive Functions and Effective Computability. MITpress, 1987.

Complessita

I Ding-Zhu Du and Ker-I Ko, Theory of Computational Complexity, John Wiley& Sons, 2000

I Christos H. Papadimitriou, Computational Complexity, Addison Wesley, 1994


Numerabilita e diagonalizzazione - Lezioni 1 e 2

I Enumerare, contare, calcolare

I Quali insiemi sono enumerabili?

I Dovetailing

I Alfabeti, stringhe, linguaggi

I Diagonalizzazione - Teorema di Cantor

I Diagonalizzazione e paradossi (Russel, Berry)


Numerabilita

Un insieme A si dice numerabile se esiste una funzione suriettiva f dall’insiemedei numeri naturali N in A.f e detta funzione di enumerazione.

I N e numerabile

I Ogni sottoinsieme di un insieme numerabile e ancora numerabile.

Che possiamo dire dei soprainsiemi di N ?


Aggiungere un elemento

LemmaSia A numerabile. Allora {∗} ⊕ A e ancora numerabile.

Sia f : N → A la funzione di enumerazione di A. definiamo g : N → {∗} ⊕ Anel modo seguente:

g(x) =

{g(0) = ∗g(x + 1) = f (x)

Chiaramente g e suriettiva.

Corollario: Sia A numerabile e D finito. Allora D ⊕ A e ancora numerabile.


Aggiungere una quantita numerabile di elementi

LemmaL’unione di due insiemi numerabili A e B e ancora numerabile.

Siano f e g le due funzioni di enumerazione di A e B. A⊕ B e alloraenumerato dalla seguente funzione h:

h(x) =

{h(2x) = f (x)

h(2x + 1) = g(x)

Corollario: Un unione finita di insiemi numerabili e numerabile.

Corollario: Se D e finito e A e numerabile allora D × A e numerabile.


Muoversi tra due infiniti: dovetailing

Cerchiamo una funzione biunivoca da N ×N in N .

Un modo alternativo di descrivere il problema consiste nella definizione di unapolitica di visita delle coppie 〈i , j〉 del piano in modo tale che ogni coppia vengaispezionata una ed una sola volta al passo k. k e la codifica della coppia 〈i , j〉.

0 1 2 3 4 · · · i

0 0 1 3 6 10↙ ↙ ↙ ↙

1 2 4 7 11↙ ↙ ↙

2 5 8 12↙ ↙

3 9 13↙

4 14...j


Codifica delle coppie del piano

La somma delle componenti i ed j per i punti su di una stessa diagonale ecostante e pari al numero di diagonali gia interamente percorse. Il numero dipunti del piano gia visitati in queste diagonali e

i+j∑k=0

k =(i + j)(i + j + 1)

2

Per visitare l’elemento < i , j > dovro ancora percorrere j passi lungo l’ultimadiagonale, per cui

〈i , j〉 = j +

i+j∑k=0

k =(i + j)2 + i + 3j

2


Corollari

LemmaIl prodotto cartesiano di due insiemi numerabili e numerabile.

LemmaL’unione di un insieme numerabile di insiemi numerabili e ancora numerabile.

Sia A un insieme numerabile e sia f la sua funzione di enumerazione.{Ba|a ∈ A} una collezione di insiemi numerabili, ciascuno enumerato da unafunzione ga. La funzione h : N ×N →

⋃a∈A Ba definita da

h(n,m) = gf (n)(m)

e suriettiva.


Sequenze ordinate, stringhe, linguaggi

LemmaSe A numerabile, anche

⋃i∈N Ai e numerabile.

Osservazione: Nel caso in cui A sia finito, l’insieme⋃

i∈N Ai non e altro chel’insieme di tutte le stringhe definibili sull’alfabeto A. Dunque ogni linguaggio,inteso come sottoinsime di stringhe definite su di un dato alfabeto, e semprenumerabile.

Corollario: L’insieme delle parti finite di un insieme numerabile e numerabile.


Il teorema di Cantor

Cantor

Dato un insieme arbitrario A, non puo esistere una funzione suriettiva da A inP(A).

Supponiamo che esista una funzione suriettiva g : A→ P(A). Consideriamo ilseguente insieme:

∆ = {a ∈ A | a 6∈ g(a)}∆ ⊆ A e siccome abbiamo supposto che g sia suriettiva deve esistere δ tale cheg(δ) = ∆. Abbiamo allora:

δ ∈ ∆ ⇔ δ 6∈ g(δ) per definizione di ∆⇔ δ 6∈ ∆ per definizione di δ

Siccome questo e assurdo, g non puo essere suriettiva.


Il paradosso di Russel

Russel

Sia U = {x |x 6∈ x}. AlloraU ∈ U ⇔ U 6∈ U

Principio di comprensione

P(t)⇔ t ∈ {x |P(x)}


Il problema della definibilita

Le funzioni definibili da N in N sono una quantita numerabile. Fissiamo unqualche enumerazione fi .Definiamo una funzione g nel modo seguente:

g(x) = fx (x) + 1

g e ben definita, dunque dovrebbe comparire nel nostro elenco di funzionidefinibili. Supponiamo che g = fk . Abbiamo allora:

fk (k) = g(k) = fk (k) + 1

La nozione di definibilita e dunque sempre relativa (dipendente dal linguaggio)e incompleta; comunque essa venga fissata esistono “buone definizioni” definiteche sfuggono alla definizione adottata.


Il paradosso di Berry

Berry

“Sia n il piu piccolo intero positivo non definibile con meno di 100 caratteri”.

I i numeri definibili con meno di 100 caratteri sono una quantita finita,dunque esistono (inifiniti) numeri che soddisfano la proprieta suddetta, etra questi deve ne deve esistere uno minino.

I tale numero e dunque univocamente determinato dalla definizione diBerry.

I ma la definizione di Berry e piu breve di 100 caratteri: contraddizione.

La “definizione” di Berry non e ben posta (la nozione di definibilita non e bendefinita).


Ricorsione primitiva - Lezioni 3, 4, 5

I funzioni ricorsive

I ricorsione primitiva

I somme e prodotti limitati

I predicati ricorsivi

I minimizzazione limitata

I ricorsione multipla

I ricorsione primitiva vs. iterazione

I la funzione di Ackermann

I ricorsione di ordine superiore

I incompletezza algoritmica dei formalismi totali


Ricorsione

La definizione di una funzione f si dice ricorsiva se il valore di f su alcuniargomenti dipende dal valore di f su altri argomenti, solitamente piu “semplici”rispetto ad una opportuna metrica da definire.

{fatt(0) = 1

fatt(n + 1) = (n + 1) ∗ fatt(n)

fibo(0) = 1

fibo(1) = 1

fibo(n + 2) = fibo(n) + fibo(n + 1)

Fattoriale Fibonacci


Ricorsione primitiva - funzioni iniziali

Le seguenti funzioni sono funzioni iniziali del linguaggio primitivo ricorsivo L:

1. le funzioni costanti

ckm(x1, x2, . . . , xk ) = m con m ∈ N

2. le proiezioni (identita generalizzate)

πki (x1, x2, . . . , xk ) = xi per qualche 1 ≤ i ≤ k

3. la funzione successores(x) = x + 1


Ricorsione primitiva - schemi composizionali

I ComposizioneSe h : N n → N e g1, g2, . . . , gn : N k → N appartengono ad L, anche laseguente funzione f : N k → N ∈ L:

f (~x) = h (g1(~x), g2(~x), . . . , gn(~x))

con ~x = (x1, x2, . . . , xk )

I Ricorsione primitivaSe g : N k → N , h : N k+2 → N ∈ L, anche la seguente funzionef : N k+1 → N ∈ L:

f :

{f (0, ~x) = g(~x)

f (y + 1, ~x) = h (y , f (y , ~x), ~x)

con ~x = (x1, x2, . . . , xk )

Una funzione f e primitiva ricorsiva se e solo se esiste una sequenza di funzionif1, f2, . . . , fn = f tale che ogni fi o e una funzione base oppure e ottenuta dafunzioni fj con j < i mediante composizione o ricorsione primitiva.


un esempio

codice esecuzione

f1(x) = x

f2(x) = x + 1

f3(x , y , z) = y

f4(x , y , z) = f2(f3(x , y , z))

f5(y , x) =

{f5(0, x) = f1(x)

f5(y + 1, x) = f4(y , f5(y , x), x)

f ≡ f6(x) = f5(f1(x), f1(x))

f (2) = f6(2)

= f5(f1(2), f1(2))

= f5(f1(2), 2)

= f5(2, 2)

= f4(1, f5(1, 2), 2)

= f4(1, f4(0, f5(0, 2), 2), 2)

= f4(1, f4(0, f1(2), 2), 2)

= f4(1, f4(0, 2, 2), 2)

= f4(1, f2(f3(0, 2, 2)), 2)

= f4(1, f2(2), 2)

= f4(1, 3, 2)

= f2(f3(1, 3, 2))

= f2(3)

= 4


Abusi notazionali (inlining)

f1(x) = x

f2(x) = x + 1

f3(x , y , z) = y

f4(x , y , z) = f2(f3(x , y , z)) = y + 1

f5(y , x) =

{f5(0, x) = f1(x) = x

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

f ≡ f6(x) = f5(f1(x), f1(x)) = f5(x , x)

Abuseremo la notazione per ragioni di leggibilita


Alcune funzioni primitive ricorsive

Moltiplicazione Predecessore

mult(0, x) = 0mult(y + 1, x) = add(x , mult(y , x))

pred(0) = 0pred(y + 1) = y

Zero Fattoriale

zero(0) = 1zero(y + 1) = 0

fatt(0) = 1fatt(y + 1) = mult(s(y), fatt(y))

Sottrazione Confronto

sub(0,m) = msub(n + 1,m) = pred(sub(n,m))

eq(n,m) = zero(add(sub(n,m), sub(m, n)))


Somme e prodotti limitati

σf (z , ~x) ≡∑y≤z

f (y , ~x) :

{σf (0, ~x) = f (0, ~x)

σf (z + 1, ~x) = σf (z , ~x) + f (z + 1, ~x)

πf (z , ~x) ≡∏y≤z

f (y , ~x) :

{πf (0, ~x) = f (0, ~x)

πf (z + 1, ~x) = πf (z , ~x) ∗ f (z + 1, ~x)


Predicati primitivi ricorsivi

Un predicato P e primitivo ricorsivo se e solo se lo e la sua funzionecaratteristica cP. Es: zero e eq.

LemmaI predicati primitivi ricorsivi sono chiusi rispetto ai connettivi logici.

c¬P (~x) = 1− cP (~x) ≡ sub(cP (~x), 1)

cP∧Q (~x) = cP (~x) ∗ cQ (~x) ≡ mult(cP (~x), cQ (~x))

LemmaI predicati primitivi ricorsivi sono chiusi rispetto alla quantificazione limitata.Ovvero, se P(z , ~x) e un predicato primitivo ricorsivo lo sono anche ∀z≤y P(z , ~x)e ∃z≤y P(z , ~x).

c∀z≤y P(z,~x) ≡∏z≤y

cP (z , ~x)


Applicazioni

Divisibilita

divide(x , y) ⇐⇒ ∃n≤yeq(mult(n, x), y)

Primalita

prime(x) ⇐⇒ x ≥ 2 ∧ ∀y≤x (divide(y , x)⇒ y = 1 ∨ y = x)

Posso calcolare l’n-esimo numero primo?

{Pr(0) = 2

Pr(n + 1) = min{p|prime(p) ∧ (p > Pr(n))}


Minimizzazione limitata

Per minimizzazione (µ-ricorsione) si intende la ricerca del minimo interopositivo µy P(y) che soddifa il predicato P.La minimizzazione si dice limitata se viene fornito un bound alla ricerca.

LemmaLe funzioni primitive ricorsive sono chiuse rispetto alla minimizzazione limitata.

Dobbiamo dimostrare che se R(y , ~x) e un predicato primitivo ricorsivo, allora loe anche µy<z R(y , ~x).Consideriamo il predicato primitivo ricorsivo

h(y , ~x) = ∀w≤y¬R(w , ~x)

Supponiamo che y0 = µy<z R(y , ~x). Allora per ogni valore di y < y0 la funzioneh(y , ~x) assume valore 1 e per ogni valore y0 ≤ y < z la funzione h(y , ~x)assume valore 0.Dunque, y0 e pari al numero di interi inferiori a z per cui h(y , ~x) assume valore1, ovvero:

µy<z R(y , ~x) = y0 = Σy<z∀w≤y¬R(w , ~x)


Coppie e proiezioni

Le funzioni di codifica e decodifica delle coppie sono primitive ricorsive:

< i , j >= j +

i+j∑k=0

k =(i + j)2 + i + 3j

2

fst(p) = µx≤p∃y≤p < x , y >= p

snd(p) = µy≤p∃x≤p < x , y >= p

Mediante l’uso di coppie posso restituire in output agglomerati di risultati,cosa che permette di simulare la ricorsione multipla.


Fibonacci

La seguente definizione non e primitiva ricorsiva:fibo(0) = 1

fibo(1) = 1

fibo(n + 2) = fibo(n) + fibo(n + 1)

Idea: definire una funzione ausiliaria fibo’ che, su input x restituisca in outputla coppia dei valori < fibo(x), fibo(x + 1) >:

fibo’(0) = < 1, 1 >fibo’(x + 1) = < fibo(x + 1), fibo(x + 2) >

= < snd(fibo’(x)), fst(fibo’(x)) + snd(fibo’(x)) >

La funzione fibo’ e primitiva ricorsiva, e dunque lo e anche fibonacci:

fibo(n) = fst(fibo’(n))


Ricorsione multipla

Si dice storia di f (y , ~x) la funzione f (y , ~x) cosı definita:

f (y , ~x) = < f (0, ~x), f (1, ~x), . . . , f (y , ~x) >y+1

≡ << f (0, ~x), f (1, ~x) >, . . . >, f (y , ~x)>2>2 . . . >2︸︷︷︸y

La storia di f permette di definire il seguente schema di ricorsione multipla:{f (0, ~x) = g(~x)

f (y + 1, ~x) = h(y , f (y , ~x), ~x)

Problema: f e primitiva ricorsiva?

Si, infatti la storia di f e esprimibile mediante ricorsione primitiva:{f (0, ~x) = f (0, ~x) = g(~x)

f (y + 1, ~x) =< f (y , ~x), f (y + 1, ~x) >=< f (y , ~x), h(y , f (y , ~x), ~x) >

Si noti che la definizione precedente non dipende da f ma solo da g e h. Infine:{f (0, ~x) = f (0, ~x))

f (y + 1, ~x) = snd(f (y + 1, ~x))


Ricorsione di coda

Una funzione si dice in forma ricorsiva di coda se la chiamata ricorsiva el’ultima operazione eseguita dalla funzione chiamante.

Teorema

Ogni funzione primitiva ricorsiva puo essere espressa in forma ricorsiva (nonnecessariamente primitiva) di coda.


Ricorsione di coda - dimostrazione

Data la funzione primitiva ricorsiva f si consideri la funzione ricorsiva di coda f’{f (0, ~x) = g(~x)

f (y + 1, ~x) = h (y , f (y , ~x), ~x)

{f ′(0, ~x , i , acc) = acc

f ′(y + 1, ~x , i , acc) = f ′(y , ~x , i + 1, h(i , acc, ~x))

Dimostriamo per induzione su y che, per ogni i

f ′(y , ~x , i , f (i , ~x)) = f (i + y , ~x)

Se y = 0,f ′(0, ~x , i , f (i , ~x)) = f (i , ~x) = f (i + 0, ~x)

Nel caso y + 1, abbiamo

f ′(y + 1, ~x , i , f (i , ~x)) = f ′(y , ~x , i + 1, h(i , f (i , ~x), ~x))= f ′(y , ~x , i + 1, f (i + 1, ~x))= f (i + 1 + y , ~x) per ipotesi induttiva= f (i + y + 1, ~x)

In particolare, f (y , ~x) = f ′(y , ~x , 0, g(~x))


Ricorsione di coda e iterazione

L’interesse delle funzioni ricorsive di coda consiste nel fatto che possono esserericondotte banalmente a meccanismi di tipo iterativo.Ad esempio, la precedente funzione f puo essere calcolata dal seguentealgoritmo ricorsivo:

f(y,x1,...,xn):=

begin

var acc = g(x1,...,xn);

for i := 0 to y

acc := h(i,acc,x1,...,xn)

return acc

end

E possibile dimostrare il seguente risultato:

Teorema

Le funzioni primitive ricorsive sono tutte e solo quelle for-calcolabili, cioe es-primibili in un qualunque linguaggio imperativo utilizzando come unici costruttidi controllo di flusso l’if-then-else, il for e la chiamata di funzione non ricorsiva


Schema di iterazione

Le considerazioni precedenti suggeriscono che sia possibile indebolire lo schemadi ricorsione primitiva, riducendolo alla mera possibilita di iterare unadeterminata funzione h: {

f (0, ~x) = g(~x)

f (y + 1, ~x) = h(f (y , ~x))

Si noti che h non dipende ne da y ne da ~x .In particolare:

f (y , ~x) = hy (g(~x))


Iterazione + coppie

Teorema

Iterazione + Coppie = Ricorsione Primitiva.

Consideriamno per semplicita il caso di una funzione primitiva ricorsiva f con vettore diargomenti ~x vuoto: {

f (0) = a

f (y + 1) = h(y , f (y))

Si consideri la funzione ausiliaria f ′(y) =< y , f (y) > e si osservi che

f ′(y + 1) = < y + 1, f (y + 1) >= < y + 1, h(y , f (y)) >= < fst(f ′(y)) + 1, h(fst(f ′(y)), snd(f ′(y))) >

Postonext(p) =< fst(p) + 1, h(fst(p), snd(p)) >

la funzione f ′ puo essere definita iterando next nel modo seguente:{f ′(0) =< 0, a >

f ′(y + 1) = next(f ′(y))

Infine, f (y) = snd(f ′(y)).


Funzionali di ricorsione e iterazione

Una funzione definita mediante uno schema ricorsivo primitivo o iterativo eunivocamente determinata dalle sue componenti g e h. Questo suggerisce laseguente notazione compatta

f = Rec g h per f =

{f (0, ~x) = g(~x)

f (y + 1, ~x) = h(y , f (y , ~x), ~x)

f = Ite g h per f =

{f (0, ~x) = g(~x)

f (y + 1, ~x) = h(f (y , ~x))

Rec e Ite sono esempi significativi di funzionali, ovvero funzioni di ordinesuperiore che operaro su altre funzioni.


La funzione di Ackermann

ack(0, 0, y) = yack(0, x + 1, y) = ack(0, x , y) + 1

ack(1, 0, y) = 0ack(z + 2, 0, y) = 1

ack(z + 1, x + 1, y) = ack(z , ack(z + 1, x , y), y)

Funzione di Ackermann

La funzione di Ackermann e ben definita, implementabile, e terminante;tuttavia non e esprimibile nel formalismo primitivo ricorsivo.


Istanze della funzione di Ackermann

Consideriamo le istanze parziali

ackz,y x = ack(z , x , y)

In base alle prime due equazioni

ack0,y (x) = x + y

In base all’ultima equazione abbiamo inoltre che

ackz+1,y (x) = ackz,y (ackz+1,y (x − 1))= ackz,y (ackz,y (ackz+1,y (x − 2)))= ackz,y (ackz,y (. . . ackz,y (ackz+1,y (0)) . . . ))︸︷︷︸

x volte

Dunque il risultato di ackz+1,y (x) si ottiene iterando x volte la funzione dellivello sottostante ackz,y a partire dal valore base ackz+1,y (0). Le equazione 3 e4 fissano rispettivamente tale valore base a 0 per z = 1 e a 1 per z ≥ 2.Dunque

ack1,y = Ite 0 ack0,y

ackz+2,y = Ite 1 ackz+1,y


Crescita della funzione di Ackermann

Esplicitando i primi livelli della funzione abbiamo:

ack(0, x , y) = x + yack(1, x , y) = x ∗ yack(2, x , y) = y x

ack(3, x , y) = y y...y}

x volte

La funzione di Ackermann cresce dunque molto velocemente; ad esempio

ack(3, x , y) = 327 > 1014

La complessita della funzione di Ackermann trascende il potere espressivo dellinguaggio primitivo ricorsivo.


Iterare un iteratore

Postonext f = Ite 1 f

abbiamoackz+2,y = next ackz+1,y

e in generale(∗) ackz+1,y = Ite ack1,y next z

Se per calcolare Ackermann e sufficiente iterare, perche non e primitivaricorsiva?

Perche (*) richiede di iterare un funzionale (funzione di ordine superiore).


Un linguaggio di ordine superiore: Il sistema T di Godel

TIPI: B,N ,T1 × T2,T1 → T2

TERMINI:

variabili : x , y , z , . . . ;

costanti : 0, S , True, False, Fst, Snd, If, Rec.

coppie < M,N >

applicazione (M N)

astrazione λx : T .M


Regole di tipizzazione per T (costanti)

0 : NS : N → NTrue : BFalse : BFst : T1 × T2 → T1

Snd : T1 × T2 → T2

If : T → T → B → TRec : T → (N → T → T )→ N → T


Regole di tipizzazione per T (termini strutturati)

Predicato di buona tipizzazione

Γ ` M : T

leggi: il termine M ha tipo T nel contesto Γ.Il contesto e un insieme di dichiarazioni di tipo della forma x : Tx .Ogni variabile libera in M deve essere dichiarata nel contesto.

coppiaΓ ` M : T1 Γ ` N : T2

Γ `< M,N > : T1 × T2

applicazioneΓ ` M : T1 → T2 Γ ` N : T1

Γ ` (M N) : T2

astrazioneΓ, x : T1 ` M : T2

Γ ` λx : T1.M : T1 → T2


Regole di riduzione per T

(Fst) (Fst < M,N >)→ M(Snd) (Snd < M,N >)→ N(β) (λx : T .M N)→ M[N/x ](If true) (If M N true)→ M(If false) (If M N false)→ N(Rec O) (Rec M N O)→ M(Rec S) (Rec M N (S P))→ (N P (Rec M N P))

Remark: il tipo e invariante per riduzione (subject reduction).


Gerarchie di Linguaggi Totali

Funzioni dimostrabilmente totali

nell’aritmetica del second’ordine

Sistema F

Sistema T

Funzioni dimostrabilmente totali

nell’aritmetica del prim’ordine

Primitive

Ricorsive


Il problema dell’Interprete

Sia data una enumerazione effettiva (e.g. lessicografica) Pn dei programmi dellinguaggio L, e sia ϕn la funzione calcolata dal programma Pn.

Un interprete per L e una funzione che preso in input l’indice n di unprogramma ed un input m simula il comportamento di Pn su tale input, cioeuna funzione I tale che

I (n,m) = ϕn(m)

Se la numerazione dei programmi e effettiva, I e intuitivamente calcolabile.

Ci chiediamo se l’interprete per L puo essere scritto in L, cioe se esiste u taleche I = ϕu.


Incompletezza algoritmica dei Formalismi Totali

Supponiamo che esista u tale che I (n,m) = ϕu(n,m) = ϕn(m).Consideriamo la funzione

f (x) = ϕu(x , x) + 1 = ϕx (x) + 1

Se il linguaggio L e chiuso per composizione f ∈ L, e dunque deve esistere unprogramma i tale che ϕi = f .Ma allora

ϕi (i) = f (i) = ϕi (i) + 1

che e assurdo.

Teorema

Nessun formalismo totale e in grado di esprimere il proprio interprete.


Le Macchine di Turing e la Tesi di Church - Lezioni 6, 7

I Costrutti computazionali potenzialmente divergenti

I La tesi di Church

I Le Macchine di Turing

I La Macchina universale


Alcuni importanti costrutti potenzialmente divergenti

I goto

I cicli while

I minimizzazione (µ-ricorsione illimitata)

I ricorsione generale

I costrutti autoreferenziali (auto-applicazione, auto-interpretazione)

I . . .

I linguaggi parziali ammettono tipicamente la definizione del loro propriointerprete.

Abbiamo una gerarchia infinita di linguaggi parziali con potere espressivocrescente?


Sulla auto-applicazione

L’auto applicazione induce divergenza. Posto

f x = x x

la computazione di f f non termina.

L’auto applicazione permette di simulare la ricorsione.Supponiamo di voler definire una funzione ricorsiva f tale che

f x = M[f , x ]

Consideriamo la funzione ausiliaria

h y x = M[y y , x ]

dove le occorrenze di f in M sono state rimpiazzate dalla auto applicazione y y .Posto f = h h abbiamo

f x = h h x = M[h h, x ] = M[f , x ]

Remark: L’auto applicazione e il tipico esempio di costrutto mal tipato.


Modelli di calcolo

I (Term) rewriting systems (Thue 1914, Post 1920)

I Combinatory Logic (Schonfinkel, Curry 1924)

I Funzioni definite da equazioni ricorsive (Herbrand 1931, Godel 1934,Kleene 1936)

I λ-calcolo (Church 1936)

I Turing machines (Turing 1936)

I Funzioni µ-ricorsive (Kleene 1938)

I Markov algorithms (Markov 1954)

I Register machines (Shepherdson, Sturgis 1963)

I . . .

Tutti questi modelli (e molti altri) sono computazionalmente equivalenti.Le funzioni esprimibili in questi modelli sono dette funzioni calcolabili.


La tesi di Church

Church

Le funzioni calcolabili sono esattamente quelle intuitivamente calcolabili medi-ante una procedura effettiva di calcolo.

”Tarski has stressed in his lecture (and I think justly) the greatimportance of the concept of general recursiveness (or Turing’scomputability). It seems to me that this importance is largely due tothe fact that with this concept one has for the first time succeededin giving an absolute notion to an interesting epistemological notion,i.e., one not depending on the formalism chosen.” (Godel 1946)

Remark: La tesi di Church non puo essere dimostrata.


La Macchina di Turing

b b b bb

q

00 0 1 1

Hardware

I un nastro di memoria illimitato, diviso in celle di dimensione fissata.Ogni cella puo contenere un carattere di un alfabeto dato, compreso uncarattere b (bianco) di inizializzaizone.

I una testina di lettura mobile.

I un automa a stati finiti.

Operazioni elementari

I leggere e scrivere il carattere individuato dalla testina

I spostare la testina di una posizione verso destra o verso sinistra

I modificare lo stato interno dell’automa


La Macchina di Turing: definizione formale

Una Macchina di Turing (one-tape, deterministica) e una tupla〈Q, Γ, b,Σ, δ, q0,F 〉 dove

I Q e un insieme finito di stati

I Γ e l’alfabeto finito del nastro

I b ∈ Γ e il carattere bianco

I Σ ⊆ Γ \ {b} e l’insieme dei caratteri di input/output

I q0 ∈ Q e lo stato iniziale

I F ⊆ Q e l’insieme degli stati finali (o di accettazione)

I δ : Q \ F × Γ→ Q × Γ× {L,R} e la funzione di transizione.

L (left) e R (right) denotano le possibili mosse della testina.

Remark: la funzione di transizione ha un grafo finito. Ogni elemento del grafoe una quintupla (q, a, q′, a′,M) tale che δ(q, a) = (q′, a′,M). L’insieme finitodelle quintuple puo essere visto come l’insieme delle istruzioni della macchina(programma), e la determina univocamente.


Convenzioni di input-output

input

I si suppone che il nastro sia inizializzato con la stringa di input (uncarattere per ogni cella)

I la testina e posizionata sul primo carattere dell’input.

I tutte le altre celle del nastro sono inizializzate col carattere speciale b.

output

I nel momento in cui la macchina si arresta l’output e la piu lunga stringadi caratteri in Γ (in particolare, senza b) alla destra della testina


Configurazioni istantanee

Una configurazione e una descrizione dello stato della computazione ad un datoistante della computazione. Questa e definita come una tripla

σ, q, τ

dove q e lo stato dell’automa e σ e τ sono due stringhe di caratteri chedescrivono la porzione non (definitivamente) bianca del nastro alla sinistra ealla destra della testina. Il carattere in lettura e il primo carattere di τ .

La computazione avviene per passi discreti: una transizione tra dueconfigurazioni e una relazione ` governata dalla funzione di transizione.

σ, q, aτ ` σa′, q′, τ se δ(q, a) = (q′, a′,R)σc, q, aτ ` σ, q′, ca′τ se δ(q, a) = (q′, a′, L)

Nelle regole precedenti si suppone che il nastro possa essere esteso “ondemand” con caratteri bianchi qualora se ne abbia necessita.


Computazioni

La relazione `∗ denota la chiusura transitiva e riflessiva della relazione `.

Una funzione f : Σ∗ → Σ∗ e calcolata da una macchina di Turing M se perogni α esiste qf ∈ F tale che

ε, q0, α `∗ σ, qf , τ

e f (α) e il piu lungo prefisso di τ appartenente a Σ∗


L’essenza della Macchina di Turing

Agente di calcolo con potenzialita finite, che procede per passi discreti.Ad ogni passo posso

I prendere visione di una porzione finita dello spazio (discretizzato)circostante (compreso un eventuale stato interno)

I modificare una porzione finita di tale spazio,

I spostarmi di una distanza finita in tale spazio


La Macchina di Turing Universale

Esiste una MdT Universale che prende in input la sequenza di quintuple di unamacchina M, un input m e simula il comportamento di M su input m.

I divido il nastro in una parte superiore ed una inferiore. La parte superiore e utilizzata per memorizzare lequintuple della MdT da simulare M, quella inferiore e il nastro di lavoro, su cui viene inizialmente copiato ildato di input m;

I lo stato interno comprende tre “registri” speciali Q, A e S utilizzati per memorizzare rispettivamente lo

stato della macchina M, il carattere di lettura/scrittura e lo shift (R/L) della testina; inizialmente Q = qM0 ,

I letto il carattere a sul nastro inferiore, rimpiazzo a con un carattere speciale ] per ricordare la posizionedella testina e memorizzo a nel registro A;

I procedo dunque a cercare nella parte superiore del nastro una quintupla relativa ai valori correnti di Q e A;quando la trovo, rimpiazzo i contenuti dei registri con il valore del nuovo stato q′, del carattere da scriverea′ e della mossa da eseguire s; se q′ e finale la computazione si arresta;

I torno quindi a cercare il carattere ] sul nastro iferiore, lo rimpiazzo con il contentenuto di A, eseguo lamossa S e ricomincio il ciclo;

Se leggo l’insieme delle quintuple come la codifica numerica (indice) di M, laMdT Universale e un interprete nel senso precedentemente esposto.

La Macchina Universale permette di eseguire tutti i programmi con un unicohardware: e a tutti gli effetti l’antesignano del moderno elaboratore elettronico.


Numerazioni di Godel - Lezione 8

I Numerazioni accettabili

I Proprieta utm e smn

I Riducibilita di enumerazioni

I Il teorema di equivalenza di Roger

I Il predicato T di Kleene


Numerazioni accettabili

Sia data una enumerazione ϕki delle funzioni parziali calcolabili a k argomenti.

Se la numerazione e effettiva, ci aspettiamo che esista un interprete:

Proprieta utm (Universal Turing Machine)

Esiste un indice u tale che per ogni x , y

ϕu(x , y) = ϕx (y)

Inoltre ci aspettiamo che esista un modo effettivo per determinare i codici deiprogrammi ottenuti per valutazione parziale di programmi dati:

Proprieta smn

Per ogni funzione parziale calcolabile f m+n esiste una funzione totale calcolabilesm

n tale che, per ogni ~xm, ~yn

ϕsmn (~xm)(~yn) = f (~xm, ~yn)

Una enumerazione che gode delle proprieta utm e smn e detta accettabile.


Riducibilita di enumerazioni

Siano date due funzioni di enumerazione ϕ,ψ : N → A.

1. ψ e riducibile a ϕ (in simboli: ψ ≤ ϕ) se esiste una funzione totalecalcolabile f tale che, per ogni numero naturale n, ψn = ϕf (n)

2. ψ e equivalente a ϕ (in simboli: ψ ≡ ϕ) se ψ ≤ ϕ e ϕ ≤ ψ.


Il teorema di equivalenza di Roger

Roger

Tutte le enumerazioni accettabili di funzioni parziali ricorsive sono equivalentitra loro.

In particolare e possibile dimostrare che, supposto ϕ accettabile,

I ψ ≤ ϕ⇔ ψ soddisfa la proprieta utm

I ϕ ≤ ψ ⇔ ψ soddisfa la proprieta smn

_<ϕ ψ

ψ ≅ ϕ

_< ψ ϕ

smn

utm


Dimostrazione del teorema di Roger

Sia u l’indice di un interprete per ϕ.

I ψ ≤ ϕ⇔ ψ soddisfa la proprieta utm:

⇒ Se esiste f t.c. tale che ψn = ϕf (n), allora la funzioneϕu(f (n),m) e calcolabile e deve essere enumerata da ψ.L’indice di tale funzione soddisfa utm.

⇐ Preso u′ tale che ψu′(x , y) = ψx (y), per smn esiste s t.c.tale che ϕs(x)(y) = ψu′(x , y) = ψx (y).

I ϕ ≤ ψ ⇔ ψ soddisfa la proprieta smn

⇒ Sia f t.c. tale che ϕn = ψf (n). Data una funzionecalcolabile g(n,m) esiste s t.c. tale cheϕs(n)(m) = g(n,m); allora f ◦ s soddisfa smn per ψ.

⇐ Si consideri la funzione t.c. ϕu(x , y) = ϕx (y); la funziones tale che ψs(x)(y) = ϕu(x , y) riduce ϕ a ψ.

Fissare una particolare enumerazione non e piu rilevanteche fissare un sistema di riferimento sul piano cartesiano.


Il predicato T di Kleene

Il predicato T di Kleene

Esiste un predicato T (i , n, k, t) tale che

1. ϕi (n) = k ⇔ ∃t ≥ k,T (i , n, k, t)

2. la funzione caratteristica di T e calcolabile

T e il predicato (intuitivamente calcolabile) che afferma che la computazionedel programma di indice i su input n termina con risorse fissate (e.g. tempo ospazio) t e fornisce come risultato k. Si suppone che le risorse necessarie aprodurre k siano almeno pari a k (fissando opportunamente l’unita di misura).

Si osservi che anche la funzione caratteristica del predicato

T 3(i , n, t) = ∃k,T (i , n, k, t) ≡ ∃k ≤ t,T (i , n, k, t)

e ancora calcolabile, ovvero

E possibile decidere se una computazione si arresta in un tempo dato


La forma normale di Kleene

Il predicato T di Kleene fornisce una visione piu fine della nozione di interprete,in cui si evidenzia la nozione di costo computazionale.

In particolare

Teorema della forma normale di Kleene

Per ogni i , nϕi (n) = fst(µ〈k,t〉T (i , n, k, t))


Funzioni non calcolabili - Lezione 9

I Notazione

I Terminazione

I Totalita

I Equivalenza

I Tre funzioni “simili”


Un po’ di notazione

Sia ϕi una enumerazione accettabile delle funzioni parziali calcolabili.

Useremo la notazione ϕi (n)↓ per indicare che la funzione e definita (converge)per input n, e ϕi (n)↑ quando e indefinita (o diverge) per tale input.

Definiamo dominio (dom) di ϕi il suo insieme di convergenza, ossia

dom(ϕi ) = {n|ϕi (n)↓}

Il codominio (cod) di ϕi e l’insieme dei possibili output:

cod(ϕi ) = {m|∃n, ϕi (n) = m}

Le funzioni parziali sono ordinate parzialmente rispetto all’inclusioneinsiemistica dei loro grafi:

ϕi ⊆ ϕj ⇔ ∀n ∈ dom(ϕi ), ϕi (n) = ϕj (n)


Il problema della terminazione

Il test di terminazione e cosi definito:

h(i , x) =

{1 se ϕi (x)↓0 se ϕi (x)↑

Consideriamo ora la funzione f , definita come segue:

f (x) =

{1 se h(x , x) = 0⇔ ϕx (x)↑↑ se h(x , x) = 1⇔ ϕx (x)↓

Se h e calcolabile lo e anche f . Dovrebbe dunque esistere m tale che f = ϕm.Supposto f = ϕm, ci chiediamo quanto vale ϕm(m):

ϕm(m) =

{1 se h(m,m) = 0⇔ ϕm(m)↑↑ se h(m,m) = 1⇔ ϕm(m)↓

il che e assurdo. Questo dimostra che

il test di terminazione non e una funzione calcolabile!


Il problema della totalita

total(i) =

{1 se ϕi e totale

0 altrimenti

Consideriamo una funzione ausiliaria definita nel modo seguente:

f (x , y) =

{0 se ϕx (x)↓↑ altrimenti

La funzione f e calcolabile.Per il teorema s.m.n. esiste h totale calcolabile tale che

ϕh(x)(y) = f (x , y) =

{0 se ϕx (x)↓↑ altrimenti

Avremmo allora

total(h(x)) =

{1 se ϕx (x)↓0 se ϕx (x)↑

Sappiamo che total ◦ h non e calcolabile, e dunque non lo e neppure total .


Il problema della equivalenza estensionale di programmi

eq(i , j) =

{1 se ϕi ≈ ϕj

0 altrimenti

Consideriamo la funzione costante 0, e sia m un indice per essa.Consideriamo la funzione h della sezione precedente:

ϕh(x)(y) =

{0 se ϕx (x) ↓↑ se ϕx (x) ↑

Poniamo

f (x) = eq(h(x),m) =

{1 se ϕx (x) ↓0 altrimenti

f non e calcolabile e dunque neppure eq.


Tre funzioni simili

g(i) ≡

{1 se ∃n, ϕi (n)↓0 altrimenti

g ′(i) ≡

{1 se ∃n, ϕi (n)↓↑ altrimenti

g ′′(i) ≡

{minimo n, ϕi (n)↓ se ∃n, ϕi (n)↓↑ altrimenti


La funzione g

Consideriamo la solita funzione calcolabile h:

ϕh(x)(y) =

{0 se ϕx (x) ↓↑ se ϕx (x) ↑

f (x) = g(h(x)) =

{1 se ϕx (x) ↓0 altrimenti

f non e calcolabile e dunque neppure g .


La funzione g ′

g ′(i) ≡

{1 se ∃n, ϕi (n)↓↑ altrimenti

Accortezza: muoversi con una tecnica di dovetaling tra i due infiniti deipossibili valori di input e del tempo di esecuzione.

Sia t(i , n, s) la funzione caratteristica del predicato (ternario) T di kleene.

g ′(i) = µ〈n, s〉.t(i , n, s) = 1; return 1


La funzione g ′′

g ′′(i) ≡

{minimo n, ϕi (n)↓ se ∃n, ϕi (n)↓↑ altrimenti

Consideriamo la seguente funzione h totale calcolabile

ϕh(i)(y) = f (i , y) =

{0 se y > 0 ∨ ϕi (i)↓↑ altrimenti

ϕh(i)(0) ↓ se e solo se ϕi (i) ↓. Inoltre ϕh(i)(1) ↓. Dunque

g ′′(h(i)) ≡

{0 ϕi (i)↓1 altrimenti

Se g ′′ fosse calcolabile risolveremmo il problema della terminazione diagonale.


Insiemi ricorsivi e r.e. - Lezioni 10,11

I Insiemi ricorsivi

I Insiemi ricorsivamente enumerabili (r.e)

I Enumerabilita crescente

I Caratterizzazioni equivalenti

I Il Teorema di proiezione

I Proprieta di chiusura


Insiemi ricorsivi

Un insieme si dice ricorsivo (o decidibile) se la sua funzione caratteristica ecalcolabile.

Esempi

1. l’insieme vuoto e l’insieme N di tutti i numeri naturali

2. ogni insieme finito

3. l’insieme dei numeri pari

4. l’insieme dei numeri primi

5. tutti gl insiemi definiti da predicati primitivi ricorsivi

Non ogni insieme e ricorsivo(contro) Esempio:

K = {x |ϕx (x) ↓}


Prorieta di chiusura degli insiemi ricorsivi

LemmaGli insiemi ricorsivi sono chiusi rispetto alle operazioni di unione, intersezione ecomplementazione.

Siano A e B insiemi ricorsivi, e siano ca e cB le loro funzioni caratteristiche.Allora:

I cA(n) = 1− cA(n)

I cA∧B (n) = min{cA(n), cB (n)}I cA∨B (n) = max{cA(n), cB (n)}

Gli insiemi ricorsivi, ordinati rispetto alla relazione di inclusione insiemistica,formano quindi un reticolo booleano (Algebra di Boole).


Insiemi ricorsivamente enumerabili

Un insieme si dice ricorsivamente enumerabile (r.e.) se e vuoto oppure e ilcodominio di una funzione totale calcolabile (detta funzione di enumerazione).

LemmaOgni insieme ricorsivo e anche r.e.

Sia A ricorsivo e sia cA la sua funzione caratteristica.Il caso in cui A e finito e banale.Supponiamo A infinito:{

f (0) = µy , cA(y) = 1

f (x + 1) = µy , cA(y) = 1 ∧ y > f (x)


Enumerabilita crescente

LemmaUn insieme A a ricorsivo se e solo se puo essere enumerato in modo crescente.

⇒ si veda la prova del lemma precedente⇐ Se A e finito l’asserto e ovvio. Possiamo dunque suppore A infinito; sia f lafunzione di enumerazione. Definiamo la seguente funzione:

cA(x) = f (µy f (y) ≥ x) = x

(scandisco tutti i dati enumerati da f finche non ne trovo uno non inferioreall’input x : a questo punto arresto la ricerca e verifico se il dato coincide conl’input cercato).

Il fatto (non ovvio) che cA e totale e una conseguenza del fatto che A e infinitoe dunque cod(f ) contiene valori arbitrariamente grandi (superiori ad ogni x).


Teorema di complementazione

Teorema

Un insieme A e ricorsivo se e solo se sia A che A sono r.e.

⇒ ovvio.⇐: Supponiamo che A e A siano rispettivamente enumerati da f e g . Poniamo{

h(2x) = f (x)

h(2x + 1) = g(x)

h e suriettiva su N. Sia pari(n) la funzione caratteristica dell’insieme deinumeri pari.

cA(n) = pari(µy(h(y) = n)

cA e calcolabile e totale.


Caratterizzazioni equivalenti degli insiemi r.e.

Teorema

Sia A un insieme di numeri naturali. Le seguenti affermazioni sono equivalenti:

1. A = ∅ ∨ ∃f : A = cod(f ), f totale calcolabile

2. ∃g : A = dom(g), g parziale calcolabile

3. ∃h : A = cod(h), h parziale calcolabile

I 1⇒ 2 Il caso A = ∅ e ovvio. Sia A = cod(f ) per f tot. calc., poniamo

g(x) = µy(f (y) = x)

Chiaramente g e calcolabile e g(x)↓ se e solo se x ∈ cod(f ).

I 2⇒ 3 Sia A = dom(g); basta considerare

h(x) = x + 0 ∗ g(x)

I 3⇒ 1 Sia A = cod(h), per h parziale calcolabile.Il caso A = ∅ e triviale. Posto a ∈ A e h = ϕi consideriamo

f (〈x , k, s〉) =

{k se T (i , x , k, s) = 1

a altrimenti

dove T e il predicato di kleene. f e totale e calcolabile e cod(f ) = A.


Semidecidibilita

A decidibile A semidecidibile

f (x) =

{1 se x ∈ A

0 se x 6∈ Af (x) =

{↓ se x ∈ A

↑ se x 6∈ A

per f calcolabile

Esistono insiemi semidecidibili (r.e) ma non decidibili (ricorsivi):

Teorema

L’insieme K = {x |ϕx (x) ↓} e r.e.

La funzione k(x) = ϕx (x) e calcolabile e K = dom(k).


Enumerazione degli insiemi r.e.

Possiamo definire una enumerazione W : N → RE dell’insieme RE di tutti gliinsiemi r.e. ponendo

Wi = dom(ϕi )

Si noti che

K = {x |ϕx (x) ↓} = {x |x ∈ dom(ϕx )} = {x |x ∈Wx}


Il teorema di proiezione

Teorema di proiezione

Un insieme A e r.e. se e solo se esiste un insieme B ricorsivo tale che

A = {m|∃n, 〈n,m〉 ∈ B}

I ⇐ Sia cB la funzione caratterisitca di B. Allora A = dom(f ) dove

f (m) = µn, cB (〈n,m〉) = 1

I ⇒ Sia A = dom(ϕi ). Dunque m ∈ A se e solo se ϕi (m) ↓, se e solo se∃n,T (i , n,m), dove T e il predicato ternario di Kleene.

Basta dunque porreB = {〈n,m〉|T (i , n,m)}


Proprieta di chiusura degli insiemi r.e.

Teorema

Gli insiemi r.e. sono chiusi rispetto a unione e intersezione, ma non rispetto allacomplementazione.

unione Sia A = cod(f ′) e B = cod(g ′) con f’ e g’ parziali calc.A ∨ B = cod(h′) dove{

h′(2x) = f ′(x)

h′(2x + 1) = g ′(x)

intersezione Sia A = dom(f ) e B = dom(g) per f , g parziali calc.A ∧ B = dom(h) per h(x) = f (x) ∗ g(x).

complementazione K non e r.e. (altrimenti K sarebbe ricorsivo).

Corollario Esistono insiemi che non sono ne ricorsivi ne ricorsivamenteenumerabili (e.g. K).


Proprieta di chiusura rispetto a funzioni

Teorema

Siano A,B ⊆ N e f : N → N1. se A e ricorsivo e f e totale calcolabile, allora f −1(A) e ricorsivo

2. se A e r.e. e f e calcolabile, allora f −1(A) e r.e

3. se A e r.e. e f e calcolabile, allora f (A) e r.e

1. cf−1(A) = cA ◦ f

2. se A = dom(g), allora f −1(A) = dom(g ◦ f )

3. se A = cod(g), allora f (A) = cod(f ◦ g)


Unioni e interesezioni infinite

Lemma1) una unione r.e. di insiemi r.e. e ancora r.e.2) una interesezione r.e. di insiemi r.e. non e necessarimente r.e.

1) per ogni x⋃

i∈Wx

Wi e r.e. 2) esiste x⋂

i∈Wx

Wi non e r.e.

1) Per dovetailing.2) Per smn esiste h totale calcolabile tale che

Wh(i) = {x |¬T (x , x , i)}

dove T e il predicato di Kleene. Si dimostra facilmente che⋂i∈N

Wh(i) = K

Poiche⋂

i∈N Wh(i) =⋂

i∈cod(h) Wi l’asserto e dimostrato.

Remark: gli insiemi Wh(i) sono ricorsivi e h puo essere scelta monotona crescente,

quindi una intersezione ricorsiva di insiemi ricorsivi non e in generale r.e.


I teoremi di Rice e Rice-Shapiro - Lezioni 12,13

I Insiemi estensionali

I Il teorema di Rice

I Il teorema di Rice-Shapiro (monotonia)

I Il teorema di Rice-Shapiro (compattezza)


Insiemi estensionali

Un insieme (proprieta) A ⊆ N si dice estensionale (w.r.t ϕ) se per ogni i , j

i ∈ A ∧ ϕi ≡ ϕj ⇒ j ∈ A

Ovvero, se cA e la funzione caratteristica di A,

ϕi ≡ ϕj ⇒ cA(i) = cA(j)

Una proprieta estensionale di (indici di) programmi e una proprieta relativa allafunzione calcolata (estensione) e non alla forma o al modo (intensione) in cuiquesta viene calcolata.

P(i) estensionale P(i) intensionale

ϕi e totale ∀n∃k,T (i , n, k, i2)ϕi ≡ f ϕi ≡ f ∧ i ≤ 1005 ∈ cod(ϕi ) i ∈ cod(ϕi )dom(ϕi ) e finito |dom(ϕi )| > iϕi (0) ↑ ϕi (i) ↑∃n, ϕi (n)↓ ∧ϕi (n + 1)↓ ϕi ≡ ϕi+1

Remark: Il complementare di un insieme estensionale e estensionale


Il teorema di Rice

Rice 1953

Una proprieta estensionale di programmi e decidibile se e solo se e banale.

Sia c la funzione caratteristica del predicato. Sia m un indice per la funzioneovunque divergente, e sia a tale c(a) 6= c(m). Cerco h calcolabile tale che

φh(x) ≈

{φa if x ∈ K

φm if x 6∈ K


Definizione di h

Consideriamo la funzione

φh(x)(y) = φx (x);φa(y)

dove “;” denota la composizione sequenziale.Per la poprieta smn h e totale e calcolabile.

E banale verificare che

φh(x) ≈

{φa if x ∈ K

φm if x 6∈ K

Dunque, utilizzando l’ipotesi di estensionalita, avremmo

c(h(x)) =

{c(a) if x ∈ K

c(m) if x 6∈ K

che permetterebbe di decidere l’appartenenza a K .


Uso del teorema di Rice

I Uso diretto, per dimostrare che determinate proprieta (essendoestensionali) non sono decidibili.

I Uso indiretto, per dimostrare che determinate proprieta estensionali nonsono neppure semidecidibili (basta dimostrare che il complementare e r.e.)

Esempio:A = { i |ϕi (0) ↓}

A non e banale, e dunque, per Rice, non puo essere ricorsivo (uso diretto);d’altra parte A e r.e., dunque

A = { i |ϕi (0) ↑}

non e neppure r.e. altrimenti sia A che A sarebbero ricorsivi, contraddicendo ilrisultato di Rice (uso indiretto).


Monotonia e compattezza

Sia A un insieme estensionale (rispetto a ϕ) di numeri naturali

I A e detto monotono se per ogni i e j

i ∈ A ∧ ϕi ⊆ ϕj → j ∈ A

I A e detto compatto se per ogni i ∈ A esiste j ∈ A tale che

1. il grafo di ϕj e finito2. ϕj ⊆ ϕi

insieme monotonia compattezza

{ i |ϕi (0) ↓} si si{ i |ϕi e totale} si no{ i |cod(ϕi ) e finito} no si

{ i |dom(ϕi ) e dom(ϕi ) sono infiniti} no no

Remark: se A e A sono entrambi monotoni allora sono banali.


Rice-Shapiro (monotonia)

Rice-Shapiro (monotonia)

Ogni insieme estensionale A ricorsivamente enumerabile e monotono.

Supponiamo che esistano due indici i e j tali che i ∈ A, j 6∈ A and ϕi ≤ ϕj .Consideriamo la funzione

ϕf (x)(y) = ϕi (y)|(ϕx (x);ϕj (y))

dove “|” denota la composizione parallela (l’output e quello del primo threadterminante). E facile vedere che

φf (x) ≈

{φj if x ∈ K

φi if x 6∈ K

(nel caso x ∈ K uso l’ipotesi ϕi ≤ ϕj ). Dunque

f (x) ∈ A⇔ x ∈ K

e K sarebbe r.e., il che e assurdo.


Rice-Shapiro (compattezza)

Rice-Shapiro (compattezza)

Ogni insieme estensionale A ricorsivamente enumerabile e compatto.

Sia A un insieme estensionale ricorsivamente enumerabile. Supponiamo chei ∈ A e che per ogni j tale che ϕj ⊆ ϕi e ϕj e finito si abbia j 6∈ A.Consideriamo la funzione f totale calcolabile definita come segue (per smn)

ϕf (x)(y) =

{↑ if ϕx (x) ↓ in meno di y passi

ϕi (y) otherwise

Se x ∈ K allora ϕf (x) ≈ ϕi e dunque f (x) ∈ A.Se x ∈ K allora la computazione di ϕx (x) terminera in un numero finito t dipassi, e la funzione ϕf (x) convergera solo per valori di input y ≤ t.Dunque f (x) e un indice per una sottofunzione finita di ϕi , e per ipotesif (x) 6∈ A.

In conclusionef (x) ∈ A⇔ x ∈ K

e K sarebbe r.e., il che e assurdo.


Applicazioni di Rice-Shapiro

I teoremi di Rice-Shapiro permettono di dimostrare facilmente che determinatiinsiemi estensionali non sono r.e. Ad esempio:

{ i |ϕi e totale} non e r.e. in quanto non e compatto{ i |cod(ϕi ) e finito} non e r.e. in quanto non e monotono

Warning: Esistono insiemi estensionali monotoni e compatti ma non r.e., adesempio { i |dom(ϕi ) ∩ K 6= ∅}.


Il teorema del punto fisso di Kleene - Lezione 14

I primo teorema di ricorsione

I secondo teorema di ricorsione

I applicazioni


Il teorema del punto fisso di Kleene

Teorema del punto fisso (Kleene)

Per ogni funzione totale calcolabile f esiste m tale che

ϕf (m) ≈ ϕm

Per smn esiste h totale e calcolabile tale che

ϕh(x)(y) = g(x , y) = ϕf (ϕx (x))(y)

Sia p un indice per h e poniamo m = ϕp(p) = h(p) (che e sicuramente definitoin quanto h e totale). Allora, per ogni y

ϕm(y) = ϕh(p)(y) = g(p, y) = ϕf (ϕp (p))(y) = ϕf (m)(y)

L’interprete permette di simulare la ricorsione!

Supponiamo di voler definire una funzione ricorsiva f tale che

f x = M[f , x ]

Per smn esiste g totale calcolabile tale che ϕg(i)(x) = M[ϕi , x ].Allora f = ϕm dove m e il punto fisso di g .Andrea Asperti Universita di Bologna - Dipartimento di Scienze dell’Informazione 100

Il secondo teorema di ricorsione

Secondo Teorema di ricorsione di Kleene

Per ogni funzione binaria totale calcolabile f esiste una funzione calcolabile stale che, per ogni y

ϕf (s(y),y) ≈ ϕs(y)

Per smn esistono r , h totali e calcolabili tale che

ϕϕr(y)(x)(z) = ϕh(x,y)(z) = g(x , y , z) = ϕf (ϕx (x),y)(z)

Posto s(y) = ϕr(y)(r(y)) abbiamo, per ogni z

ϕs(y)(z) = ϕϕr(y)(r(y))(z) = ϕh(r(y),y)(z) = ϕf (ϕr(y)(r(y)),y)(z) = ϕf (s(y),y)(z)


Applicazioni del teorema del punto fisso

L’uso del teorema del punto fisso per simulare ricorsione e particolarmentepulito, in quanto la funzione g e estensionale, nel senso che

ϕi ≡ ϕj ⇒ ϕg(i) ≡ ϕg(j)

Tuttavia il teorema e vero per qualunque trasformazione effettiva.

Ad esempio:

I in ogni enumerazione accettabile di programmi esistono sicuramente dueprogrammi consecutivi con comportamenti identici, ovvero esiste i taleche

ϕi+1 ≡ ϕi

Dimostrazione: si prenda il punto fisso del successore.

I Esiste un programma che “stampa se stesso”, cioe esiste i tale che

ϕi (0) = i

Dimostrazione: Per smn esiste h tale che ϕh(x)(y) = x ; se ne prenda unpunto fisso.


Dimostrazione alternativa del teorema di Rice

Supponiamo per assurdo che A sia ricorsivo, ma non banale.Esistono dunque i e j tali che i ∈ A e j ∈ A.

Considero la seguente funzione:

h(x) =

{ı se x ∈ A

se x ∈ A

Per definizioneh(x) ∈ A⇔ x ∈ A

Inoltre, se A e ricorsivo h e totale calcolabile e per il teorema del punto fisso diKleene, esiste un indice b tale che ϕb = ϕh(b). Avremmo quindi

b ∈ A⇔ h(b) ∈ A⇔ b ∈ A

che e una contraddizione.


Riducibilita - Lezioni 15,16

I La nozione di (m-)riducibilita

I m-completezza

I Insiemi produttivi e creativi

I Il problema di Post

I Insiemi immuni e semplici

I Complessita di Kolmogorov


Definizione di riducibilita

Siano A,B ⊆ N ; A si dice riducibile (m-riducibile) a B (in simboli A ≤m B),se esiste una funzione totale e calcolabile f tale che

x ∈ A⇔ f (x) ∈ B

Due insiemi si dicono equivalenti (m-equivalenti) (in simboli A =m B), seA ≤m B e B ≤m A;

Osservazioni:

I la relazione ≤m e un preordine (i.e. e riflessiva e transitiva)

I la relazione = m e una relazione di equivalenza

I A ≤m B se e solo se A ≤m B

I se A ≤m B e B e ricorsivo (risp. r.e.) allora A e ricorsivo (risp. r.e.)


K0 =m K

Sia K0 = {〈i , n〉 |n ∈Wi}

I K ≤m K0. Siccome

i ∈ K ⇒ i ∈Wi ⇒ 〈i , i〉 ∈ K0

la funzione f (x) = 〈x , x〉 permette di ridurre K a K0.

I K0 ≤m K . Consideriamo la funzione totale calcolabile h per cui

ϕh(i,x)(y) = g(i , x , y) = ϕi (x)

Abbiamo

〈i , n〉 ∈ K0 ⇔ n ∈Wi ⇔ ∀y , ϕh(i,n)(y)↓ ⇔ ϕh(i,n)h(i , n)↓ ⇔ h(i , n) ∈ K

Quindi la funzione h riduce K0 a K .


m-completezza

Un insieme si dice m-completo se e r.e. ed ogni insieme r.e. e riducibile adesso.

LemmaK0 e K sono insiemi completi.

Dato che K0 =m K e sufficiente dimostrare la proprieta per K0.Abbiamo gia dimostrato che se A ≤m K0 allora A e r.e. e dunque esiste i taleche A = Wi . Allora, per ogni n

n ∈ A⇔ n ∈Wi ⇔ 〈i , n〉 ∈ K0

LemmaA e completo se e solo se A =m K.

Se A =m K allora A e r.e. e m-completo perche lo e K .Viceversa se A e m-completo, allora e r.e. e per la completezza di K , A ≤m K ;inoltre, siccome K e r.e. , K ≤m A per la m-completezza di A.


Insiemi produttivi e creativi

Sia A ⊆ N .

1. A si dice produttivo se esiste f totale e calcolabile tale che per ogni i

Wi ⊆ A⇒ f (i) ∈ A\Wi

2. A si dice creativo se e r.e. ed il suo complemento A e produttivo.

Si osservi che un insieme produttivo non puo essere r.e. Infatti, se A = Wi

allora preso Wi ⊆ A avremmo che A\Wi = ∅ e quindi f (i) 6∈ A\Wi .

Teorema

K e creativo (e la funzione di produzione e l’identita).

Sappiamo che K e r.e.; dimostriamo che K e produttivo, ed in particolare che

Wi ⊆ K ⇒ i ∈ K\Wi

I i ∈ K . Infatti, se i ∈ K allora i ∈Wi e siccome Wi ⊆ K avremmo i ∈ Kche e una contraddizione. Dunque i ∈ K .

I i 6∈Wi . Infatti, se i ∈Wi allora i dovrebbe appartenere a K , ma abbiamoappena dimostrato il contrario.


Caratterizzazione della produttivita

Teorema

Sia A ⊆ N . A e produttivo se e solo se K ≤m A.

(⇐) Supponiamo che K ≤m A, e sia g la corrispondente funzione di riduzione.Per smn esiste h totale e calcolabile tale che ϕh(i)(x) = ϕi (g(x)). Dunque

Wh(i) = g−1(Wi )

Posto f (i) = g(h(i)) vogliamo dimostrare che f e una funzione di produzioneper A, ovvero che per ogni i

Wi ⊆ A⇒ f (i) ∈ A\Wi

Se Wi ⊆ A, Wh(i) = g−1(Wi ) ⊆ K e per la produttivita di K , h(i) ∈ K\Wh(i).Ma allora f (i) = g(h(i)) ∈ A\Wi .


Caratterizzazione della produttivita

(⇒) Sia A produttivo, e sia f la funzione di produzione. Consideriamo h t.c.

ϕh(z,y)(n) =

{0 se f (z) = n ∧ y ∈ K

↑ altrimenti

Per il secondo teorema di ricorsione esiste s totale e calcolabile tale che

ϕs(y)(n) = ϕh(s(y),y)(n)

{0 se f (s(y)) = n ∧ y ∈ K

↑ altrimenti

e dunque

Ws(y) =

{{f (s(y))} se y ∈ K

∅ altrimenti

Vogliamo dimostrare che f ◦ s e una funzione di riduzione da K a A:

I Se y ∈ K allora Ws(y) = {f (s(y))}. Se f (s(y)) ∈ A allora Ws(y) ⊆ A equindi per la produttivia di A, f (s(y)) ∈ A\Ws(y), ed in particolare

f (s(y)) 6∈Ws(y) = {f (s(y))} che e assurdo. Dunque f (s(y)) ∈ A.

I Se y 6∈ K , allora Ws(y) = ∅ ⊆ A e dunque, per la produttivita di A,f (s(y)) ∈ A\Ws(y), ed in particolare f (s(y)) ∈ A.


Caratterizzazione della creativita

Teorema

Sia A ⊆ N . A e creativo se e solo se A =m K .

Per definizione, A e creativo se e solo se e r.e. e A e produttivo.Ma A e r.e se e solo se A ≤m K .Inoltre, per il teorema precedente, A e produttivo se e solo se K ≤m A, cheequivale a K ≤m A.


Il problema di Post

Il problema di Post

la riduzione di K ad A e una tecnica generale per dimostrare l’indecidibilita diA? (almeno limitatamente agli insiemi r.e.)

Ovvero,

per ogni A r.e. non ricorsivo vale A =m K?


Insiemi immuni e semplici

LemmaOgni insieme produttivo A contiene un sottoinsieme infinito r.e.

Sia f una funzione di produzione per A. Per smn esiste r totale e calcolabiletale che, per ogni i :

Wr(i) = Wi ∪ {f (i)}Si noti che siccome f (i) 6∈Wi , Wr(i) estende strettamente Wi . Inoltre, seWi ⊆ A anche Wr(i) ⊆ A. Preso dunque m tale che Wm = ∅, l’unione⋃

n∈N

Wrn(m)

e infinita, r.e. e contenuta in A.

Il risultato precedente motiva la seguente definizione: sia A ⊆ N .

I A si dice immune se e infinito e nessun suo sottoinsieme infinito e r.e.

I A si dice semplice se e r.e. e A e immune.


Complessita di Kolmogorov

Andiamo alla ricerca di un insiemi semplice (dunque non creativo).

La complessita di Kolmogorov di un numero n, indicata con k(n) e il piupiccolo indice i tale che ϕi (0) = n.

Intuizione: invece di dare una descrizione esplicita del numero n, si puo fornireuna procedura i che permetta di generarlo.

LemmaPer ogni i , se ϕi (0)↓, k(ϕi (0)) ≤ i .

Ovvio, per la definizione di k.


Numeri random

Un numero n si dice random se n ≤ k(n).Indicheremo con R l’insieme dei numeri random.

Intuizione: un numero random e un numero di cui non e possibile fornire unadescrizione piu succinta: lui stesso e la sua descrizione minima.

LemmaR 6= ∅.Utilizzando il teorema del punto fisso si dimostra l’esistenza di un i tale cheϕi (0) = i + 1. Dunque i + 1 non e random.

LemmaL’insieme R e r.e.

Un numero a non e random se e solo se esiste un indice i < a tale cheϕi (0) = a. Dunque R e codominio della funzione parziale calcolabile

g(i) =

{ϕi (0) se i < ϕi (0)

↑ altrimenti


Un insieme immune

Teorema

L’insieme R dei numeri random e immune.

Sia A un insieme infinito r.e. e sia f una sua funzione di enumerazione.Per smn esiste h totale e calcolabile tale che

ϕh(i)(x) = f (µn.f (n) > i)

Si osservi che la miminimizzazione µn.f (n) > i termina per ogni i in quanto f etotale e cod(f ) = A e infinito. Per definizione, f (µn.f (n) > i) ∈ A, e sesupponiamo A ⊆ R deve trattarsi di un numero random; inoltre

(∗) ϕh(i)(x) = f (µn.f (n) > i) > i

Per il teorema del punto fisso, esiste m tale che ϕm ≈ ϕh(m). Dunque avremmo

I ϕm(0) = ϕh(m)(0) ∈ R, che implica ϕm(0) ≤ k(ϕm(0)); inoltre abbiamodimostrato che k(ϕm(0)) ≤ m, e per transitivia ϕm(0) ≤ m.

I d’altra parte, per (∗), ϕm(0) = ϕh(m)(0) > m, che porta a contraddizione.


Calcolabilita e completezza - Lezioni 17-18

I Aritmetica del prim’ordine

I Insiemi e funzioni aritmetiche

I Indecidibilita della verita aritmetica

I il Teorema di incompletezza di Godel


Aritmetica

Il linguaggio dell’aritmetica e il linguaggio del primo ordine basato sullaseguente segnatura:

0,S ,+, ·,=Indichiamo con n il termine che rappresenta il numero n.

A ⊆ N k si dice aritmetico se esiste una formula aritmetica ψ(x1, . . . , xk ) taleche

(n1, . . . , nk ) ∈ A⇔ N |= ψ[n1/x1, . . . , nk/xk ]

ovvero ψ(x1, . . . , xk ) e vera sui numeri naturali. Diremo in questo caso che ψ e

una descrizione aritmetica di A.

Ad esempio, l’insieme dei numeri primi e aritmetico, in quanto puo esseredescritto dalla seguente formula aritmetica:

ψ(n) = 2 ≤ n ∧ ∀y , 1 < y ∧ y < n⇒ ∀z , y · z 6= n


Insiemi/funzioni aritmetici

Gli insiemi aritmetici sono chiusi rispetto alle operazioni di unione, intersezionee complementazione.

Una funzione f si dice aritmetica se il suo grafo e un insieme aritmetico.

Le seguenti funzioni sono aritmetiche:

f arieta descrizione

0 0 y = 0S 1 y = S(x)+ 2 y = x1 + x2

· 2 y = x1 · x2

πki k y = xk


Chiusura rispetto alla composizione

LemmaLa composizione di funzioni aritmetiche e aritmetica.

Sia f (x) = g(h(x)) e siano ψg (x , y) e ψh(x , y) le descrizioni aritmetiche di g eh.

Definiamoψf (x , z) = ∃y , ψg (x , y) ∧ ψh(y , z)

e facile dimostrare che ψf e una descrizione aritmetica di f .


Chiusura rispetto alla minimizzazione

LemmaUna funzione definita per minimizzazione di una funzione aritmetica e ancoraaritmetica.

Siaf (x) = µy .(g(x , y) = 0)

e supponiamo che ψg sia una descrizione aritmetica di g .

f e descritta dalla seguente formula:

ψf (x , y) = ψg (x , y , 0) ∧ ∀i , i < y → ∃m, (ψg (x , i ,m) ∧m 6= 0)


Le funzioni calcolabili sono aritmetiche

Teorema

Tutte le funzioni calcolabili sono aritmetiche.

Conseguenza del fatto che ogni funzione calcolabile puo essere espressa in unformalismo che contiene somma, prodotto, costanti, proiezioni ed e chiuso percomposizione e ricorsione primitiva.


Gli insiemi r.e. sono aritmetici

Teorema

Ogni insieme ricorsivamente enumerabile e aritmetico.

Se A e r.e. esiste f (parziale) calcolabile tale che A = dom(f ). Sia ψf (x , y)una descrizione aritmetica di f . Allora

n ∈ A⇔ N |= ∃y , ψf (n, y)

e dunque ψA(x) = ∃y , ψf (x , y) e una descrizione aritmetica di A.

corollario L’insieme K e aritmetico.


Indecidibilita della verita aritmetica

Teorema

L’insieme delle formule aritmetiche vere non e ricorsivamente enumerabile.

Sia {ψn}n∈N una enumerazione effettiva delle formule aritmetiche in unavariabile. Consideriamo l’insieme A cosı definito

n ∈ A⇔|= ¬ψn(n)

Se la verita aritmetica fosse semidecidibile, allora A sarebbe r.e.

Dunque A dovrebbe essere aritmetico e dovrebbe esistere una formula ψa percui

n ∈ A⇔|= ψa(n)

Ma per n = a otteniamo una contraddizione.


Incompletezza

Teorema di incompletezza di Godel

Ogni sistema formale aritmetico, se consistente, e incompleto (i.e. esistonoformule aritmetiche valide ma non dimostrabili).

Un sistema formale e definito da un insieme ricorsivo di assiomi e un insieme diregole di inferenza che permettono di dedurre nuovi teoremi a partire dagliassiomi in un numero finito di applicazioni.

Pertanto le formule aritmetiche dimostrabili costituiscono un insiemericorsivamente enumerabile.

Poiche le formule vere non sono r.e. esistono necessariamente delle formulevere ma non dimostrabili.


La gerarchia aritmetica - Lezioni 19,20

I Le classi Σ0n,Π

0n,∆

0n

I Operazioni sui quantificatori

I Insiemi completi

I Il teorema della gerarchia aritmetica


Le classi Σ0n,Π0

n,∆0n

Sia n un numero naturale.

I Σ0n e la classe di tutti gli insiemi A ⊆ N k per cui esiste un insieme

ricorsivo R ⊆ N n+k tale che

A = {x ∈ N k |∃y1∀y2∃y3...Qyn, (x , y1, y2, ..., yn) ∈ R}

dove Q = ∀ per n pari, e Q = ∃ per n dispari.

I Π0n e la classe di tutti gli insiemi A ⊆ N k per cui esiste un insieme

ricorsivo R ⊆ N n+k tale che

A = {x ∈ N k |∀y1∃y2∀y3...Qyn, (x , y1, y2, ..., yn) ∈ R}

dove Q = ∃ per n pari, e Q = ∀ per n dispari.

I ∆0n = Σ0

n ∩ Π0n.

I⋃

n∈N (Σ0n ∪ Π0

n) e detta gerachia aritmetica.


Semplici proprieta della gerarchia aritmetica

Sia n un numero naturale:

I La classe Σ00 = Π0

0 = ∆00 e la classe degli insiemi ricorsivi.

I La classe Σ0n+1 e la classe delle proiezioni di insiemi in Π0

n.

I La classe Π0n e la classe dei complementi di insiemi in Σ0

n.

I In particolare, Σ01 e la classe degli insiemi r.e e Π0

1 e al classe degli insiemico-r.e.

I ∆01 = ∆0

0 e la classe degli insiemi ricorsivi.

I Σ0n ∪ Π0

n ⊆ Σ0n+1 ∩ Π0

n+1 = ∆0n+1

Dimostreremo in seguito che l’ultima inclusione e stretta.


Esempio: il problema dell’equivalenza

Equ = {(i , j) ∈ N | ϕi = ϕj} ∈ Π02

Infatti

(i , j) ∈ Equ ⇔ ∀n((ϕi (n)↓ ∧ ϕj (n)↓ ∧ϕi (n) = ϕj (n)))∨(ϕi (n)↑ ∧ ϕj (n)↑)

⇔ ∀n((∃t1t2k(T (i , n, t1, k) ∧ T (j , n, t2, k))∨∀t1t2k1k2(¬T (i , n, t1, k1) ∧ ¬T (j , n, t2, k2)))

⇔ ∀ns1s2k1k2∃t1t2k((T (i , n, t1, k) ∧ T (j , n, t2, k))∨(¬T (i , n, s1, k1) ∧ ¬T (j , n, s2, k2))

N.B. Sequenze di quantificatori dello stesso tipo collassano in un soloquantificatore.

Poiche la matrice e ricorsiva, questo dimostra che Equ e (al piu) in Π02.

Possiamo dare una classificazione piu stretta?


Forme normali prenesse

Il Teorema di Kuratowski

Ogni formula aritmetica e eqivalente ad una con un prefisso formato da una listaalternata di quantificatori e una matrice ricorsiva.

La prova si basa sulle seguenti trasformazioni (si suppone che x non occorralibera in β):

¬(∃xα)⇔ ∀x¬α ¬(∀xα)⇔ ∃x¬α(∃xα) ∧ β ⇔ ∃x(α ∧ β) (∀xα) ∧ β ⇔ ∀x(α ∧ β)(∃xα) ∨ β ⇔ ∃x(α ∨ β) (∀xα) ∨ β ⇔ ∀x(α ∨ β)

(∃xα)→ β ⇔ ∀x(α→ β) (∀xα)→ β ⇔ ∃x(α→ β)β → (∃xα)⇔ ∃x(β → α) β → ∀xα⇔ ∀x(β → α)


Quantificazione limitata

LemmaDue quantificatori di cui il primo sia limitato possono sempre essere permutati.

∀x≤a∃yR(x , y)⇔ ∃w∀x≤aR(x , nth(x ,w))∃x≤a∀y¬R(x , y)⇔ ∀w∃x≤a¬R(x , nth(x ,w))

dove nth(x ,w) e la funzione ricorsiva che estrae l’ennesimo elemento da unatupla: {

nth(0,w) = w

nth(n + 1, 〈y , z〉) = nth(n, z)

Quindi i quantificatori limitati possono essere spinti verso l’interno e assorbitinella matrice ricorsiva:

∀ e ∃ limitati non influiscono sulla classificazione nella gerarchia aritmetica


La gerarchia aritmetica e gli insiemi aritmetici

Teorema

La gerarchia aritmetica contiene esattamente gli insiemi aritmetici.

Gli insiemi ricorsivi sono aritmetici (in quanto lo sono quelli r.e.). Gli insiemidella gerarchia aritmetica sono costruiti da insiemi ricorsivi utilizzando uninsieme finito di quantificatori, e dunque sono tutti aritmetici.

Viceversa, la descrizione di ogni insieme aritmetico A puo essere trasformata informa normale prenessa, dove la matrice e una proposizione priva diquantificatori in cui compare solo il predicato (decidibile) di uguaglianza, ed edunque ricorsiva. Quindi A appartiene alla gerarchia aritmetica.


Il teorema di enumerazione

Teorema

Per ogni n,m ≥ 1 esiste un insieme Umn ∈ Σ0

n ⊆ Nm+1 che enumera tutti gliinsiemi A ∈ Σ0

n ⊆ Nm, ovvero tale che A(~x)⇔ U(e, ~x) per qualche e.Similmente per Πn

0.

Per induzione su n. Se n = 1

Um1 (i , ~x)⇔ ~x ∈Wi ∈ Σ0

1

enumera tutti gli insiemi r.e.; inoltre

Um1 (i , ~x)⇔ ~x ∈Wi ∈ Π0

1

enumera tutti gli insiemi co-r.e.

Induttivamente, sia data Um+1n ∈ Σ0

n. Posto

Umn+1(e, ~x)⇔ ∀yUm+1

n (e, ~x , y) ∈ Π0n+1

Umn+1 enumera tutte tutti i sottoinsiemi di Nm in Π0

n+1 e Umn+1 quelli in Σ0

n+1.


Completezza nella gerarchia aritmetica

Sia A ⊆ N e sia n ∈ NI A e detto Σ0

n-completo se A ∈ Σ0n e B ≤m A per ogni B ∈ Σ0

n ⊆ NI A e detto Π0

n-completo se A ∈ Π0n e B ≤m A per ogni B ∈ Π0

n ⊆ N

Teorema

Per ogni n, siaK n

0 = {〈i , x〉|U1n (i , x)}

Allora K n0 e Σ0

n-completo (e K n0 e Π0

n-completo).

Sia B ∈ Σ0n ⊆ N . Per il teorema di enumerazione deve esiste e tale che

B(x)⇔ U1n (e, x)⇔ K n

0 (〈e, x〉)

e duque la funzione f (x) = 〈e, x〉 riduce B a K n0 .


Il teorema della gerarchia aritmetica

Teorema della gerarchia

Per ogni n

1. Σ0n \ Π0

n 6= ∅ (e quindi ∆0n ⊂ Σ0

n)

2. Π0n \ Σ0

n 6= ∅ (e quindi ∆0n ⊂ Π0

n)

3. Σ0n ∪ Π0

n ⊂ ∆0n+1

1. supponiamo che Un(i , x) enumeri tutte le relazioni in Σ0n e consideriamo

l’insieme Kn(x) = Un(x , x). Kn ∈ Σ0n; se Kn ∈ Π0

n allora Kn ∈ Σ0n e

dovrebbe esistere e tale che Kn(x) = Un(e, x). Ma allora otterremmo laseguente contraddizione:

Kn(e) = Un(e, e) = Kn(e)

2. se A ∈ Σ0n \ Π0

n, allora A ∈ Π0n \ Σ0

n

3. sia A ∈ Σ0n \ Π0

n e consideriamo l’insieme

Q(x , z) = (A(x) ∧ z = 0) ∨ (A(x) ∧ z = 1)

Chiaramente Q ∈ ∆0n+1. Tuttavia Q 6∈ Π0

n poiche altrimenti lo sarebbeanche A(x) = Q(x , 0) e allo stesso modo Q 6∈ Σ0

n.


La classificazione di alcuni problemi indecidibili

I K1 = {i |Wi 6= ∅} e Σ01-completo

I Fin = {i |Wi e finito} e Σ02-completo

I Inf = {i |Wi e infinito} e Π02-completo

I Tot = {i |Wi = N} e Π02-completo

I Equ = {〈i , j〉 | ϕi = ϕj} e Π02-completo

I Cof = {i |Wi e cofinito} e Σ03-completo

I Rec = {i |Wi e ricorsivo} e Σ03-completo

I Creative = {i |Wi e creativo} e Σ03-completo

I Simple = {i |Wi e semplice} e Π03-completo

I . . .


Prova di completezza per il problema dell’equivalenza

Abbiamo gia dimostrato che Equ ∈ Π02. Dobbiamo dimostrare che ogni A ∈ Π0

2

e riducibile a Equ. Poiche A ∈ Π02 deve esistere B ricorsivo tale che

A = {n | ∀x∃yB(x , y , n)}

Consideriamo la funzione totale calcolabile h tale che

ϕh(n)(x) = g(n, x) = 0 · µy (B(x , y , n))

Sia inoltre m un indice per la funzione costante 0, e confrontiamo h(n) com m:

〈h(n),m〉 ∈ Equ⇔ ϕh(n) = ϕm

⇔ ∀xϕh(n)(x) = 0⇔ ∀x∃yB(x , y , n)⇔ n ∈ A

Dunque la funzione totale calcolabile s(n) = 〈h(n),m〉 riduce A a Equ.


Esempi di problemi completi nella gerarchia aritmetica

∆0

3

∆0

2

0Σ 3

0Σ 1 = r.e.

0Π 1= co−r.e.

0Π 3

∆0

0= = recursive∆

0

1

= mK K 0 K

0Π 2

0Σ 2

= m = m

= m = mFin

Simple Cof Rec Creative

Inf Tot Equ


Calcolabilita' e Complessita

Education

Transcript of Calcolabilita' e Complessita