calcolabilita' e complessita
TRANSCRIPT
![Page 1: Calcolabilita' e Complessita](https://reader034.vdocumenti.com/reader034/viewer/2022042518/5575c010d8b42a312a8b4901/html5/thumbnails/1.jpg)
Calcolabilita e Complessita
Andrea Asperti
Department of Computer Science, University of BolognaMura Anteo Zamboni 7, 40127, Bologna, ITALY
Andrea Asperti Universita di Bologna - Dipartimento di Scienze dell’Informazione 1
![Page 2: Calcolabilita' e Complessita](https://reader034.vdocumenti.com/reader034/viewer/2022042518/5575c010d8b42a312a8b4901/html5/thumbnails/2.jpg)
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
Andrea Asperti Universita di Bologna - Dipartimento di Scienze dell’Informazione 2
![Page 3: Calcolabilita' e Complessita](https://reader034.vdocumenti.com/reader034/viewer/2022042518/5575c010d8b42a312a8b4901/html5/thumbnails/3.jpg)
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
Andrea Asperti Universita di Bologna - Dipartimento di Scienze dell’Informazione 3
![Page 4: Calcolabilita' e Complessita](https://reader034.vdocumenti.com/reader034/viewer/2022042518/5575c010d8b42a312a8b4901/html5/thumbnails/4.jpg)
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
Andrea Asperti Universita di Bologna - Dipartimento di Scienze dell’Informazione 4
![Page 5: Calcolabilita' e Complessita](https://reader034.vdocumenti.com/reader034/viewer/2022042518/5575c010d8b42a312a8b4901/html5/thumbnails/5.jpg)
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)
Andrea Asperti Universita di Bologna - Dipartimento di Scienze dell’Informazione 5
![Page 6: Calcolabilita' e Complessita](https://reader034.vdocumenti.com/reader034/viewer/2022042518/5575c010d8b42a312a8b4901/html5/thumbnails/6.jpg)
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 ?
Andrea Asperti Universita di Bologna - Dipartimento di Scienze dell’Informazione 6
![Page 7: Calcolabilita' e Complessita](https://reader034.vdocumenti.com/reader034/viewer/2022042518/5575c010d8b42a312a8b4901/html5/thumbnails/7.jpg)
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.
Andrea Asperti Universita di Bologna - Dipartimento di Scienze dell’Informazione 7
![Page 8: Calcolabilita' e Complessita](https://reader034.vdocumenti.com/reader034/viewer/2022042518/5575c010d8b42a312a8b4901/html5/thumbnails/8.jpg)
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.
Andrea Asperti Universita di Bologna - Dipartimento di Scienze dell’Informazione 8
![Page 9: Calcolabilita' e Complessita](https://reader034.vdocumenti.com/reader034/viewer/2022042518/5575c010d8b42a312a8b4901/html5/thumbnails/9.jpg)
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
Andrea Asperti Universita di Bologna - Dipartimento di Scienze dell’Informazione 9
![Page 10: Calcolabilita' e Complessita](https://reader034.vdocumenti.com/reader034/viewer/2022042518/5575c010d8b42a312a8b4901/html5/thumbnails/10.jpg)
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
Andrea Asperti Universita di Bologna - Dipartimento di Scienze dell’Informazione 10
![Page 11: Calcolabilita' e Complessita](https://reader034.vdocumenti.com/reader034/viewer/2022042518/5575c010d8b42a312a8b4901/html5/thumbnails/11.jpg)
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.
Andrea Asperti Universita di Bologna - Dipartimento di Scienze dell’Informazione 11
![Page 12: Calcolabilita' e Complessita](https://reader034.vdocumenti.com/reader034/viewer/2022042518/5575c010d8b42a312a8b4901/html5/thumbnails/12.jpg)
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.
Andrea Asperti Universita di Bologna - Dipartimento di Scienze dell’Informazione 12
![Page 13: Calcolabilita' e Complessita](https://reader034.vdocumenti.com/reader034/viewer/2022042518/5575c010d8b42a312a8b4901/html5/thumbnails/13.jpg)
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.
Andrea Asperti Universita di Bologna - Dipartimento di Scienze dell’Informazione 13
![Page 14: Calcolabilita' e Complessita](https://reader034.vdocumenti.com/reader034/viewer/2022042518/5575c010d8b42a312a8b4901/html5/thumbnails/14.jpg)
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)}
Andrea Asperti Universita di Bologna - Dipartimento di Scienze dell’Informazione 14
![Page 15: Calcolabilita' e Complessita](https://reader034.vdocumenti.com/reader034/viewer/2022042518/5575c010d8b42a312a8b4901/html5/thumbnails/15.jpg)
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.
Andrea Asperti Universita di Bologna - Dipartimento di Scienze dell’Informazione 15
![Page 16: Calcolabilita' e Complessita](https://reader034.vdocumenti.com/reader034/viewer/2022042518/5575c010d8b42a312a8b4901/html5/thumbnails/16.jpg)
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).
Andrea Asperti Universita di Bologna - Dipartimento di Scienze dell’Informazione 16
![Page 17: Calcolabilita' e Complessita](https://reader034.vdocumenti.com/reader034/viewer/2022042518/5575c010d8b42a312a8b4901/html5/thumbnails/17.jpg)
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
Andrea Asperti Universita di Bologna - Dipartimento di Scienze dell’Informazione 17
![Page 18: Calcolabilita' e Complessita](https://reader034.vdocumenti.com/reader034/viewer/2022042518/5575c010d8b42a312a8b4901/html5/thumbnails/18.jpg)
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
Andrea Asperti Universita di Bologna - Dipartimento di Scienze dell’Informazione 18
![Page 19: Calcolabilita' e Complessita](https://reader034.vdocumenti.com/reader034/viewer/2022042518/5575c010d8b42a312a8b4901/html5/thumbnails/19.jpg)
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
Andrea Asperti Universita di Bologna - Dipartimento di Scienze dell’Informazione 19
![Page 20: Calcolabilita' e Complessita](https://reader034.vdocumenti.com/reader034/viewer/2022042518/5575c010d8b42a312a8b4901/html5/thumbnails/20.jpg)
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.
Andrea Asperti Universita di Bologna - Dipartimento di Scienze dell’Informazione 20
![Page 21: Calcolabilita' e Complessita](https://reader034.vdocumenti.com/reader034/viewer/2022042518/5575c010d8b42a312a8b4901/html5/thumbnails/21.jpg)
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
Andrea Asperti Universita di Bologna - Dipartimento di Scienze dell’Informazione 21
![Page 22: Calcolabilita' e Complessita](https://reader034.vdocumenti.com/reader034/viewer/2022042518/5575c010d8b42a312a8b4901/html5/thumbnails/22.jpg)
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
Andrea Asperti Universita di Bologna - Dipartimento di Scienze dell’Informazione 22
![Page 23: Calcolabilita' e Complessita](https://reader034.vdocumenti.com/reader034/viewer/2022042518/5575c010d8b42a312a8b4901/html5/thumbnails/23.jpg)
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)))
Andrea Asperti Universita di Bologna - Dipartimento di Scienze dell’Informazione 23
![Page 24: Calcolabilita' e Complessita](https://reader034.vdocumenti.com/reader034/viewer/2022042518/5575c010d8b42a312a8b4901/html5/thumbnails/24.jpg)
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)
Andrea Asperti Universita di Bologna - Dipartimento di Scienze dell’Informazione 24
![Page 25: Calcolabilita' e Complessita](https://reader034.vdocumenti.com/reader034/viewer/2022042518/5575c010d8b42a312a8b4901/html5/thumbnails/25.jpg)
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)
Andrea Asperti Universita di Bologna - Dipartimento di Scienze dell’Informazione 25
![Page 26: Calcolabilita' e Complessita](https://reader034.vdocumenti.com/reader034/viewer/2022042518/5575c010d8b42a312a8b4901/html5/thumbnails/26.jpg)
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))}
Andrea Asperti Universita di Bologna - Dipartimento di Scienze dell’Informazione 26
![Page 27: Calcolabilita' e Complessita](https://reader034.vdocumenti.com/reader034/viewer/2022042518/5575c010d8b42a312a8b4901/html5/thumbnails/27.jpg)
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)
Andrea Asperti Universita di Bologna - Dipartimento di Scienze dell’Informazione 27
![Page 28: Calcolabilita' e Complessita](https://reader034.vdocumenti.com/reader034/viewer/2022042518/5575c010d8b42a312a8b4901/html5/thumbnails/28.jpg)
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.
Andrea Asperti Universita di Bologna - Dipartimento di Scienze dell’Informazione 28
![Page 29: Calcolabilita' e Complessita](https://reader034.vdocumenti.com/reader034/viewer/2022042518/5575c010d8b42a312a8b4901/html5/thumbnails/29.jpg)
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))
Andrea Asperti Universita di Bologna - Dipartimento di Scienze dell’Informazione 29
![Page 30: Calcolabilita' e Complessita](https://reader034.vdocumenti.com/reader034/viewer/2022042518/5575c010d8b42a312a8b4901/html5/thumbnails/30.jpg)
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))
Andrea Asperti Universita di Bologna - Dipartimento di Scienze dell’Informazione 30
![Page 31: Calcolabilita' e Complessita](https://reader034.vdocumenti.com/reader034/viewer/2022042518/5575c010d8b42a312a8b4901/html5/thumbnails/31.jpg)
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.
Andrea Asperti Universita di Bologna - Dipartimento di Scienze dell’Informazione 31
![Page 32: Calcolabilita' e Complessita](https://reader034.vdocumenti.com/reader034/viewer/2022042518/5575c010d8b42a312a8b4901/html5/thumbnails/32.jpg)
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))
Andrea Asperti Universita di Bologna - Dipartimento di Scienze dell’Informazione 32
![Page 33: Calcolabilita' e Complessita](https://reader034.vdocumenti.com/reader034/viewer/2022042518/5575c010d8b42a312a8b4901/html5/thumbnails/33.jpg)
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
Andrea Asperti Universita di Bologna - Dipartimento di Scienze dell’Informazione 33
![Page 34: Calcolabilita' e Complessita](https://reader034.vdocumenti.com/reader034/viewer/2022042518/5575c010d8b42a312a8b4901/html5/thumbnails/34.jpg)
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))
Andrea Asperti Universita di Bologna - Dipartimento di Scienze dell’Informazione 34
![Page 35: Calcolabilita' e Complessita](https://reader034.vdocumenti.com/reader034/viewer/2022042518/5575c010d8b42a312a8b4901/html5/thumbnails/35.jpg)
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)).
Andrea Asperti Universita di Bologna - Dipartimento di Scienze dell’Informazione 35
![Page 36: Calcolabilita' e Complessita](https://reader034.vdocumenti.com/reader034/viewer/2022042518/5575c010d8b42a312a8b4901/html5/thumbnails/36.jpg)
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.
Andrea Asperti Universita di Bologna - Dipartimento di Scienze dell’Informazione 36
![Page 37: Calcolabilita' e Complessita](https://reader034.vdocumenti.com/reader034/viewer/2022042518/5575c010d8b42a312a8b4901/html5/thumbnails/37.jpg)
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.
Andrea Asperti Universita di Bologna - Dipartimento di Scienze dell’Informazione 37
![Page 38: Calcolabilita' e Complessita](https://reader034.vdocumenti.com/reader034/viewer/2022042518/5575c010d8b42a312a8b4901/html5/thumbnails/38.jpg)
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
Andrea Asperti Universita di Bologna - Dipartimento di Scienze dell’Informazione 38
![Page 39: Calcolabilita' e Complessita](https://reader034.vdocumenti.com/reader034/viewer/2022042518/5575c010d8b42a312a8b4901/html5/thumbnails/39.jpg)
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.
Andrea Asperti Universita di Bologna - Dipartimento di Scienze dell’Informazione 39
![Page 40: Calcolabilita' e Complessita](https://reader034.vdocumenti.com/reader034/viewer/2022042518/5575c010d8b42a312a8b4901/html5/thumbnails/40.jpg)
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).
Andrea Asperti Universita di Bologna - Dipartimento di Scienze dell’Informazione 40
![Page 41: Calcolabilita' e Complessita](https://reader034.vdocumenti.com/reader034/viewer/2022042518/5575c010d8b42a312a8b4901/html5/thumbnails/41.jpg)
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).
Andrea Asperti Universita di Bologna - Dipartimento di Scienze dell’Informazione 41
![Page 42: Calcolabilita' e Complessita](https://reader034.vdocumenti.com/reader034/viewer/2022042518/5575c010d8b42a312a8b4901/html5/thumbnails/42.jpg)
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
Andrea Asperti Universita di Bologna - Dipartimento di Scienze dell’Informazione 42
![Page 43: Calcolabilita' e Complessita](https://reader034.vdocumenti.com/reader034/viewer/2022042518/5575c010d8b42a312a8b4901/html5/thumbnails/43.jpg)
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
Andrea Asperti Universita di Bologna - Dipartimento di Scienze dell’Informazione 43
![Page 44: Calcolabilita' e Complessita](https://reader034.vdocumenti.com/reader034/viewer/2022042518/5575c010d8b42a312a8b4901/html5/thumbnails/44.jpg)
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
Andrea Asperti Universita di Bologna - Dipartimento di Scienze dell’Informazione 44
![Page 45: Calcolabilita' e Complessita](https://reader034.vdocumenti.com/reader034/viewer/2022042518/5575c010d8b42a312a8b4901/html5/thumbnails/45.jpg)
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).
Andrea Asperti Universita di Bologna - Dipartimento di Scienze dell’Informazione 45
![Page 46: Calcolabilita' e Complessita](https://reader034.vdocumenti.com/reader034/viewer/2022042518/5575c010d8b42a312a8b4901/html5/thumbnails/46.jpg)
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
Andrea Asperti Universita di Bologna - Dipartimento di Scienze dell’Informazione 46
![Page 47: Calcolabilita' e Complessita](https://reader034.vdocumenti.com/reader034/viewer/2022042518/5575c010d8b42a312a8b4901/html5/thumbnails/47.jpg)
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.
Andrea Asperti Universita di Bologna - Dipartimento di Scienze dell’Informazione 47
![Page 48: Calcolabilita' e Complessita](https://reader034.vdocumenti.com/reader034/viewer/2022042518/5575c010d8b42a312a8b4901/html5/thumbnails/48.jpg)
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.
Andrea Asperti Universita di Bologna - Dipartimento di Scienze dell’Informazione 48
![Page 49: Calcolabilita' e Complessita](https://reader034.vdocumenti.com/reader034/viewer/2022042518/5575c010d8b42a312a8b4901/html5/thumbnails/49.jpg)
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
Andrea Asperti Universita di Bologna - Dipartimento di Scienze dell’Informazione 49
![Page 50: Calcolabilita' e Complessita](https://reader034.vdocumenti.com/reader034/viewer/2022042518/5575c010d8b42a312a8b4901/html5/thumbnails/50.jpg)
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?
Andrea Asperti Universita di Bologna - Dipartimento di Scienze dell’Informazione 50
![Page 51: Calcolabilita' e Complessita](https://reader034.vdocumenti.com/reader034/viewer/2022042518/5575c010d8b42a312a8b4901/html5/thumbnails/51.jpg)
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.
Andrea Asperti Universita di Bologna - Dipartimento di Scienze dell’Informazione 51
![Page 52: Calcolabilita' e Complessita](https://reader034.vdocumenti.com/reader034/viewer/2022042518/5575c010d8b42a312a8b4901/html5/thumbnails/52.jpg)
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.
Andrea Asperti Universita di Bologna - Dipartimento di Scienze dell’Informazione 52
![Page 53: Calcolabilita' e Complessita](https://reader034.vdocumenti.com/reader034/viewer/2022042518/5575c010d8b42a312a8b4901/html5/thumbnails/53.jpg)
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.
Andrea Asperti Universita di Bologna - Dipartimento di Scienze dell’Informazione 53
![Page 54: Calcolabilita' e Complessita](https://reader034.vdocumenti.com/reader034/viewer/2022042518/5575c010d8b42a312a8b4901/html5/thumbnails/54.jpg)
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
Andrea Asperti Universita di Bologna - Dipartimento di Scienze dell’Informazione 54
![Page 55: Calcolabilita' e Complessita](https://reader034.vdocumenti.com/reader034/viewer/2022042518/5575c010d8b42a312a8b4901/html5/thumbnails/55.jpg)
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.
Andrea Asperti Universita di Bologna - Dipartimento di Scienze dell’Informazione 55
![Page 56: Calcolabilita' e Complessita](https://reader034.vdocumenti.com/reader034/viewer/2022042518/5575c010d8b42a312a8b4901/html5/thumbnails/56.jpg)
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
Andrea Asperti Universita di Bologna - Dipartimento di Scienze dell’Informazione 56
![Page 57: Calcolabilita' e Complessita](https://reader034.vdocumenti.com/reader034/viewer/2022042518/5575c010d8b42a312a8b4901/html5/thumbnails/57.jpg)
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.
Andrea Asperti Universita di Bologna - Dipartimento di Scienze dell’Informazione 57
![Page 58: Calcolabilita' e Complessita](https://reader034.vdocumenti.com/reader034/viewer/2022042518/5575c010d8b42a312a8b4901/html5/thumbnails/58.jpg)
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 Σ∗
Andrea Asperti Universita di Bologna - Dipartimento di Scienze dell’Informazione 58
![Page 59: Calcolabilita' e Complessita](https://reader034.vdocumenti.com/reader034/viewer/2022042518/5575c010d8b42a312a8b4901/html5/thumbnails/59.jpg)
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
Andrea Asperti Universita di Bologna - Dipartimento di Scienze dell’Informazione 59
![Page 60: Calcolabilita' e Complessita](https://reader034.vdocumenti.com/reader034/viewer/2022042518/5575c010d8b42a312a8b4901/html5/thumbnails/60.jpg)
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.
Andrea Asperti Universita di Bologna - Dipartimento di Scienze dell’Informazione 60
![Page 61: Calcolabilita' e Complessita](https://reader034.vdocumenti.com/reader034/viewer/2022042518/5575c010d8b42a312a8b4901/html5/thumbnails/61.jpg)
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
Andrea Asperti Universita di Bologna - Dipartimento di Scienze dell’Informazione 61
![Page 62: Calcolabilita' e Complessita](https://reader034.vdocumenti.com/reader034/viewer/2022042518/5575c010d8b42a312a8b4901/html5/thumbnails/62.jpg)
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.
Andrea Asperti Universita di Bologna - Dipartimento di Scienze dell’Informazione 62
![Page 63: Calcolabilita' e Complessita](https://reader034.vdocumenti.com/reader034/viewer/2022042518/5575c010d8b42a312a8b4901/html5/thumbnails/63.jpg)
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 ϕ ≤ ψ.
Andrea Asperti Universita di Bologna - Dipartimento di Scienze dell’Informazione 63
![Page 64: Calcolabilita' e Complessita](https://reader034.vdocumenti.com/reader034/viewer/2022042518/5575c010d8b42a312a8b4901/html5/thumbnails/64.jpg)
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
Andrea Asperti Universita di Bologna - Dipartimento di Scienze dell’Informazione 64
![Page 65: Calcolabilita' e Complessita](https://reader034.vdocumenti.com/reader034/viewer/2022042518/5575c010d8b42a312a8b4901/html5/thumbnails/65.jpg)
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.
Andrea Asperti Universita di Bologna - Dipartimento di Scienze dell’Informazione 65
![Page 66: Calcolabilita' e Complessita](https://reader034.vdocumenti.com/reader034/viewer/2022042518/5575c010d8b42a312a8b4901/html5/thumbnails/66.jpg)
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
Andrea Asperti Universita di Bologna - Dipartimento di Scienze dell’Informazione 66
![Page 67: Calcolabilita' e Complessita](https://reader034.vdocumenti.com/reader034/viewer/2022042518/5575c010d8b42a312a8b4901/html5/thumbnails/67.jpg)
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))
Andrea Asperti Universita di Bologna - Dipartimento di Scienze dell’Informazione 67
![Page 68: Calcolabilita' e Complessita](https://reader034.vdocumenti.com/reader034/viewer/2022042518/5575c010d8b42a312a8b4901/html5/thumbnails/68.jpg)
Funzioni non calcolabili - Lezione 9
I Notazione
I Terminazione
I Totalita
I Equivalenza
I Tre funzioni “simili”
Andrea Asperti Universita di Bologna - Dipartimento di Scienze dell’Informazione 68
![Page 69: Calcolabilita' e Complessita](https://reader034.vdocumenti.com/reader034/viewer/2022042518/5575c010d8b42a312a8b4901/html5/thumbnails/69.jpg)
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)
Andrea Asperti Universita di Bologna - Dipartimento di Scienze dell’Informazione 69
![Page 70: Calcolabilita' e Complessita](https://reader034.vdocumenti.com/reader034/viewer/2022042518/5575c010d8b42a312a8b4901/html5/thumbnails/70.jpg)
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!
Andrea Asperti Universita di Bologna - Dipartimento di Scienze dell’Informazione 70
![Page 71: Calcolabilita' e Complessita](https://reader034.vdocumenti.com/reader034/viewer/2022042518/5575c010d8b42a312a8b4901/html5/thumbnails/71.jpg)
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 .
Andrea Asperti Universita di Bologna - Dipartimento di Scienze dell’Informazione 71
![Page 72: Calcolabilita' e Complessita](https://reader034.vdocumenti.com/reader034/viewer/2022042518/5575c010d8b42a312a8b4901/html5/thumbnails/72.jpg)
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.
Andrea Asperti Universita di Bologna - Dipartimento di Scienze dell’Informazione 72
![Page 73: Calcolabilita' e Complessita](https://reader034.vdocumenti.com/reader034/viewer/2022042518/5575c010d8b42a312a8b4901/html5/thumbnails/73.jpg)
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
Andrea Asperti Universita di Bologna - Dipartimento di Scienze dell’Informazione 73
![Page 74: Calcolabilita' e Complessita](https://reader034.vdocumenti.com/reader034/viewer/2022042518/5575c010d8b42a312a8b4901/html5/thumbnails/74.jpg)
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 .
Andrea Asperti Universita di Bologna - Dipartimento di Scienze dell’Informazione 74
![Page 75: Calcolabilita' e Complessita](https://reader034.vdocumenti.com/reader034/viewer/2022042518/5575c010d8b42a312a8b4901/html5/thumbnails/75.jpg)
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
Andrea Asperti Universita di Bologna - Dipartimento di Scienze dell’Informazione 75
![Page 76: Calcolabilita' e Complessita](https://reader034.vdocumenti.com/reader034/viewer/2022042518/5575c010d8b42a312a8b4901/html5/thumbnails/76.jpg)
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.
Andrea Asperti Universita di Bologna - Dipartimento di Scienze dell’Informazione 76
![Page 77: Calcolabilita' e Complessita](https://reader034.vdocumenti.com/reader034/viewer/2022042518/5575c010d8b42a312a8b4901/html5/thumbnails/77.jpg)
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
Andrea Asperti Universita di Bologna - Dipartimento di Scienze dell’Informazione 77
![Page 78: Calcolabilita' e Complessita](https://reader034.vdocumenti.com/reader034/viewer/2022042518/5575c010d8b42a312a8b4901/html5/thumbnails/78.jpg)
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) ↓}
Andrea Asperti Universita di Bologna - Dipartimento di Scienze dell’Informazione 78
![Page 79: Calcolabilita' e Complessita](https://reader034.vdocumenti.com/reader034/viewer/2022042518/5575c010d8b42a312a8b4901/html5/thumbnails/79.jpg)
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).
Andrea Asperti Universita di Bologna - Dipartimento di Scienze dell’Informazione 79
![Page 80: Calcolabilita' e Complessita](https://reader034.vdocumenti.com/reader034/viewer/2022042518/5575c010d8b42a312a8b4901/html5/thumbnails/80.jpg)
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)
Andrea Asperti Universita di Bologna - Dipartimento di Scienze dell’Informazione 80
![Page 81: Calcolabilita' e Complessita](https://reader034.vdocumenti.com/reader034/viewer/2022042518/5575c010d8b42a312a8b4901/html5/thumbnails/81.jpg)
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).
Andrea Asperti Universita di Bologna - Dipartimento di Scienze dell’Informazione 81
![Page 82: Calcolabilita' e Complessita](https://reader034.vdocumenti.com/reader034/viewer/2022042518/5575c010d8b42a312a8b4901/html5/thumbnails/82.jpg)
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.
Andrea Asperti Universita di Bologna - Dipartimento di Scienze dell’Informazione 82
![Page 83: Calcolabilita' e Complessita](https://reader034.vdocumenti.com/reader034/viewer/2022042518/5575c010d8b42a312a8b4901/html5/thumbnails/83.jpg)
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.
Andrea Asperti Universita di Bologna - Dipartimento di Scienze dell’Informazione 83
![Page 84: Calcolabilita' e Complessita](https://reader034.vdocumenti.com/reader034/viewer/2022042518/5575c010d8b42a312a8b4901/html5/thumbnails/84.jpg)
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).
Andrea Asperti Universita di Bologna - Dipartimento di Scienze dell’Informazione 84
![Page 85: Calcolabilita' e Complessita](https://reader034.vdocumenti.com/reader034/viewer/2022042518/5575c010d8b42a312a8b4901/html5/thumbnails/85.jpg)
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}
Andrea Asperti Universita di Bologna - Dipartimento di Scienze dell’Informazione 85
![Page 86: Calcolabilita' e Complessita](https://reader034.vdocumenti.com/reader034/viewer/2022042518/5575c010d8b42a312a8b4901/html5/thumbnails/86.jpg)
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)}
Andrea Asperti Universita di Bologna - Dipartimento di Scienze dell’Informazione 86
![Page 87: Calcolabilita' e Complessita](https://reader034.vdocumenti.com/reader034/viewer/2022042518/5575c010d8b42a312a8b4901/html5/thumbnails/87.jpg)
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).
Andrea Asperti Universita di Bologna - Dipartimento di Scienze dell’Informazione 87
![Page 88: Calcolabilita' e Complessita](https://reader034.vdocumenti.com/reader034/viewer/2022042518/5575c010d8b42a312a8b4901/html5/thumbnails/88.jpg)
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)
Andrea Asperti Universita di Bologna - Dipartimento di Scienze dell’Informazione 88
![Page 89: Calcolabilita' e Complessita](https://reader034.vdocumenti.com/reader034/viewer/2022042518/5575c010d8b42a312a8b4901/html5/thumbnails/89.jpg)
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.
Andrea Asperti Universita di Bologna - Dipartimento di Scienze dell’Informazione 89
![Page 90: Calcolabilita' e Complessita](https://reader034.vdocumenti.com/reader034/viewer/2022042518/5575c010d8b42a312a8b4901/html5/thumbnails/90.jpg)
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)
Andrea Asperti Universita di Bologna - Dipartimento di Scienze dell’Informazione 90
![Page 91: Calcolabilita' e Complessita](https://reader034.vdocumenti.com/reader034/viewer/2022042518/5575c010d8b42a312a8b4901/html5/thumbnails/91.jpg)
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
Andrea Asperti Universita di Bologna - Dipartimento di Scienze dell’Informazione 91
![Page 92: Calcolabilita' e Complessita](https://reader034.vdocumenti.com/reader034/viewer/2022042518/5575c010d8b42a312a8b4901/html5/thumbnails/92.jpg)
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
Andrea Asperti Universita di Bologna - Dipartimento di Scienze dell’Informazione 92
![Page 93: Calcolabilita' e Complessita](https://reader034.vdocumenti.com/reader034/viewer/2022042518/5575c010d8b42a312a8b4901/html5/thumbnails/93.jpg)
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 .
Andrea Asperti Universita di Bologna - Dipartimento di Scienze dell’Informazione 93
![Page 94: Calcolabilita' e Complessita](https://reader034.vdocumenti.com/reader034/viewer/2022042518/5575c010d8b42a312a8b4901/html5/thumbnails/94.jpg)
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).
Andrea Asperti Universita di Bologna - Dipartimento di Scienze dell’Informazione 94
![Page 95: Calcolabilita' e Complessita](https://reader034.vdocumenti.com/reader034/viewer/2022042518/5575c010d8b42a312a8b4901/html5/thumbnails/95.jpg)
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.
Andrea Asperti Universita di Bologna - Dipartimento di Scienze dell’Informazione 95
![Page 96: Calcolabilita' e Complessita](https://reader034.vdocumenti.com/reader034/viewer/2022042518/5575c010d8b42a312a8b4901/html5/thumbnails/96.jpg)
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.
Andrea Asperti Universita di Bologna - Dipartimento di Scienze dell’Informazione 96
![Page 97: Calcolabilita' e Complessita](https://reader034.vdocumenti.com/reader034/viewer/2022042518/5575c010d8b42a312a8b4901/html5/thumbnails/97.jpg)
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.
Andrea Asperti Universita di Bologna - Dipartimento di Scienze dell’Informazione 97
![Page 98: Calcolabilita' e Complessita](https://reader034.vdocumenti.com/reader034/viewer/2022042518/5575c010d8b42a312a8b4901/html5/thumbnails/98.jpg)
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= ∅}.
Andrea Asperti Universita di Bologna - Dipartimento di Scienze dell’Informazione 98
![Page 99: Calcolabilita' e Complessita](https://reader034.vdocumenti.com/reader034/viewer/2022042518/5575c010d8b42a312a8b4901/html5/thumbnails/99.jpg)
Il teorema del punto fisso di Kleene - Lezione 14
I primo teorema di ricorsione
I secondo teorema di ricorsione
I applicazioni
Andrea Asperti Universita di Bologna - Dipartimento di Scienze dell’Informazione 99
![Page 100: Calcolabilita' e Complessita](https://reader034.vdocumenti.com/reader034/viewer/2022042518/5575c010d8b42a312a8b4901/html5/thumbnails/100.jpg)
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
![Page 101: Calcolabilita' e Complessita](https://reader034.vdocumenti.com/reader034/viewer/2022042518/5575c010d8b42a312a8b4901/html5/thumbnails/101.jpg)
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)
Andrea Asperti Universita di Bologna - Dipartimento di Scienze dell’Informazione 101
![Page 102: Calcolabilita' e Complessita](https://reader034.vdocumenti.com/reader034/viewer/2022042518/5575c010d8b42a312a8b4901/html5/thumbnails/102.jpg)
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.
Andrea Asperti Universita di Bologna - Dipartimento di Scienze dell’Informazione 102
![Page 103: Calcolabilita' e Complessita](https://reader034.vdocumenti.com/reader034/viewer/2022042518/5575c010d8b42a312a8b4901/html5/thumbnails/103.jpg)
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.
Andrea Asperti Universita di Bologna - Dipartimento di Scienze dell’Informazione 103
![Page 104: Calcolabilita' e Complessita](https://reader034.vdocumenti.com/reader034/viewer/2022042518/5575c010d8b42a312a8b4901/html5/thumbnails/104.jpg)
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
Andrea Asperti Universita di Bologna - Dipartimento di Scienze dell’Informazione 104
![Page 105: Calcolabilita' e Complessita](https://reader034.vdocumenti.com/reader034/viewer/2022042518/5575c010d8b42a312a8b4901/html5/thumbnails/105.jpg)
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.)
Andrea Asperti Universita di Bologna - Dipartimento di Scienze dell’Informazione 105
![Page 106: Calcolabilita' e Complessita](https://reader034.vdocumenti.com/reader034/viewer/2022042518/5575c010d8b42a312a8b4901/html5/thumbnails/106.jpg)
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 .
Andrea Asperti Universita di Bologna - Dipartimento di Scienze dell’Informazione 106
![Page 107: Calcolabilita' e Complessita](https://reader034.vdocumenti.com/reader034/viewer/2022042518/5575c010d8b42a312a8b4901/html5/thumbnails/107.jpg)
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.
Andrea Asperti Universita di Bologna - Dipartimento di Scienze dell’Informazione 107
![Page 108: Calcolabilita' e Complessita](https://reader034.vdocumenti.com/reader034/viewer/2022042518/5575c010d8b42a312a8b4901/html5/thumbnails/108.jpg)
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.
Andrea Asperti Universita di Bologna - Dipartimento di Scienze dell’Informazione 108
![Page 109: Calcolabilita' e Complessita](https://reader034.vdocumenti.com/reader034/viewer/2022042518/5575c010d8b42a312a8b4901/html5/thumbnails/109.jpg)
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 .
Andrea Asperti Universita di Bologna - Dipartimento di Scienze dell’Informazione 109
![Page 110: Calcolabilita' e Complessita](https://reader034.vdocumenti.com/reader034/viewer/2022042518/5575c010d8b42a312a8b4901/html5/thumbnails/110.jpg)
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.
Andrea Asperti Universita di Bologna - Dipartimento di Scienze dell’Informazione 110
![Page 111: Calcolabilita' e Complessita](https://reader034.vdocumenti.com/reader034/viewer/2022042518/5575c010d8b42a312a8b4901/html5/thumbnails/111.jpg)
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.
Andrea Asperti Universita di Bologna - Dipartimento di Scienze dell’Informazione 111
![Page 112: Calcolabilita' e Complessita](https://reader034.vdocumenti.com/reader034/viewer/2022042518/5575c010d8b42a312a8b4901/html5/thumbnails/112.jpg)
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?
Andrea Asperti Universita di Bologna - Dipartimento di Scienze dell’Informazione 112
![Page 113: Calcolabilita' e Complessita](https://reader034.vdocumenti.com/reader034/viewer/2022042518/5575c010d8b42a312a8b4901/html5/thumbnails/113.jpg)
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.
Andrea Asperti Universita di Bologna - Dipartimento di Scienze dell’Informazione 113
![Page 114: Calcolabilita' e Complessita](https://reader034.vdocumenti.com/reader034/viewer/2022042518/5575c010d8b42a312a8b4901/html5/thumbnails/114.jpg)
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.
Andrea Asperti Universita di Bologna - Dipartimento di Scienze dell’Informazione 114
![Page 115: Calcolabilita' e Complessita](https://reader034.vdocumenti.com/reader034/viewer/2022042518/5575c010d8b42a312a8b4901/html5/thumbnails/115.jpg)
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
Andrea Asperti Universita di Bologna - Dipartimento di Scienze dell’Informazione 115
![Page 116: Calcolabilita' e Complessita](https://reader034.vdocumenti.com/reader034/viewer/2022042518/5575c010d8b42a312a8b4901/html5/thumbnails/116.jpg)
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.
Andrea Asperti Universita di Bologna - Dipartimento di Scienze dell’Informazione 116
![Page 117: Calcolabilita' e Complessita](https://reader034.vdocumenti.com/reader034/viewer/2022042518/5575c010d8b42a312a8b4901/html5/thumbnails/117.jpg)
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
Andrea Asperti Universita di Bologna - Dipartimento di Scienze dell’Informazione 117
![Page 118: Calcolabilita' e Complessita](https://reader034.vdocumenti.com/reader034/viewer/2022042518/5575c010d8b42a312a8b4901/html5/thumbnails/118.jpg)
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
Andrea Asperti Universita di Bologna - Dipartimento di Scienze dell’Informazione 118
![Page 119: Calcolabilita' e Complessita](https://reader034.vdocumenti.com/reader034/viewer/2022042518/5575c010d8b42a312a8b4901/html5/thumbnails/119.jpg)
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
Andrea Asperti Universita di Bologna - Dipartimento di Scienze dell’Informazione 119
![Page 120: Calcolabilita' e Complessita](https://reader034.vdocumenti.com/reader034/viewer/2022042518/5575c010d8b42a312a8b4901/html5/thumbnails/120.jpg)
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 .
Andrea Asperti Universita di Bologna - Dipartimento di Scienze dell’Informazione 120
![Page 121: Calcolabilita' e Complessita](https://reader034.vdocumenti.com/reader034/viewer/2022042518/5575c010d8b42a312a8b4901/html5/thumbnails/121.jpg)
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)
Andrea Asperti Universita di Bologna - Dipartimento di Scienze dell’Informazione 121
![Page 122: Calcolabilita' e Complessita](https://reader034.vdocumenti.com/reader034/viewer/2022042518/5575c010d8b42a312a8b4901/html5/thumbnails/122.jpg)
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.
Andrea Asperti Universita di Bologna - Dipartimento di Scienze dell’Informazione 122
![Page 123: Calcolabilita' e Complessita](https://reader034.vdocumenti.com/reader034/viewer/2022042518/5575c010d8b42a312a8b4901/html5/thumbnails/123.jpg)
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.
Andrea Asperti Universita di Bologna - Dipartimento di Scienze dell’Informazione 123
![Page 124: Calcolabilita' e Complessita](https://reader034.vdocumenti.com/reader034/viewer/2022042518/5575c010d8b42a312a8b4901/html5/thumbnails/124.jpg)
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.
Andrea Asperti Universita di Bologna - Dipartimento di Scienze dell’Informazione 124
![Page 125: Calcolabilita' e Complessita](https://reader034.vdocumenti.com/reader034/viewer/2022042518/5575c010d8b42a312a8b4901/html5/thumbnails/125.jpg)
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.
Andrea Asperti Universita di Bologna - Dipartimento di Scienze dell’Informazione 125
![Page 126: Calcolabilita' e Complessita](https://reader034.vdocumenti.com/reader034/viewer/2022042518/5575c010d8b42a312a8b4901/html5/thumbnails/126.jpg)
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
Andrea Asperti Universita di Bologna - Dipartimento di Scienze dell’Informazione 126
![Page 127: Calcolabilita' e Complessita](https://reader034.vdocumenti.com/reader034/viewer/2022042518/5575c010d8b42a312a8b4901/html5/thumbnails/127.jpg)
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.
Andrea Asperti Universita di Bologna - Dipartimento di Scienze dell’Informazione 127
![Page 128: Calcolabilita' e Complessita](https://reader034.vdocumenti.com/reader034/viewer/2022042518/5575c010d8b42a312a8b4901/html5/thumbnails/128.jpg)
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.
Andrea Asperti Universita di Bologna - Dipartimento di Scienze dell’Informazione 128
![Page 129: Calcolabilita' e Complessita](https://reader034.vdocumenti.com/reader034/viewer/2022042518/5575c010d8b42a312a8b4901/html5/thumbnails/129.jpg)
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?
Andrea Asperti Universita di Bologna - Dipartimento di Scienze dell’Informazione 129
![Page 130: Calcolabilita' e Complessita](https://reader034.vdocumenti.com/reader034/viewer/2022042518/5575c010d8b42a312a8b4901/html5/thumbnails/130.jpg)
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(β → α)
Andrea Asperti Universita di Bologna - Dipartimento di Scienze dell’Informazione 130
![Page 131: Calcolabilita' e Complessita](https://reader034.vdocumenti.com/reader034/viewer/2022042518/5575c010d8b42a312a8b4901/html5/thumbnails/131.jpg)
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
Andrea Asperti Universita di Bologna - Dipartimento di Scienze dell’Informazione 131
![Page 132: Calcolabilita' e Complessita](https://reader034.vdocumenti.com/reader034/viewer/2022042518/5575c010d8b42a312a8b4901/html5/thumbnails/132.jpg)
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.
Andrea Asperti Universita di Bologna - Dipartimento di Scienze dell’Informazione 132
![Page 133: Calcolabilita' e Complessita](https://reader034.vdocumenti.com/reader034/viewer/2022042518/5575c010d8b42a312a8b4901/html5/thumbnails/133.jpg)
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.
Andrea Asperti Universita di Bologna - Dipartimento di Scienze dell’Informazione 133
![Page 134: Calcolabilita' e Complessita](https://reader034.vdocumenti.com/reader034/viewer/2022042518/5575c010d8b42a312a8b4901/html5/thumbnails/134.jpg)
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 .
Andrea Asperti Universita di Bologna - Dipartimento di Scienze dell’Informazione 134
![Page 135: Calcolabilita' e Complessita](https://reader034.vdocumenti.com/reader034/viewer/2022042518/5575c010d8b42a312a8b4901/html5/thumbnails/135.jpg)
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.
Andrea Asperti Universita di Bologna - Dipartimento di Scienze dell’Informazione 135
![Page 136: Calcolabilita' e Complessita](https://reader034.vdocumenti.com/reader034/viewer/2022042518/5575c010d8b42a312a8b4901/html5/thumbnails/136.jpg)
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 . . .
Andrea Asperti Universita di Bologna - Dipartimento di Scienze dell’Informazione 136
![Page 137: Calcolabilita' e Complessita](https://reader034.vdocumenti.com/reader034/viewer/2022042518/5575c010d8b42a312a8b4901/html5/thumbnails/137.jpg)
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.
Andrea Asperti Universita di Bologna - Dipartimento di Scienze dell’Informazione 137
![Page 138: Calcolabilita' e Complessita](https://reader034.vdocumenti.com/reader034/viewer/2022042518/5575c010d8b42a312a8b4901/html5/thumbnails/138.jpg)
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
Andrea Asperti Universita di Bologna - Dipartimento di Scienze dell’Informazione 138