Appunti di Algoritmi e Principi dell'informatica

Teoria del calcolo 3

N N}∣ N⟹ ∣{f : → ≥ ∣{f : → {0; 1}}∣ = = 2P(N) 0La gran parte delle funzioni (problemi) non è calcolabile algoritmicamente, non èperò una grave perdita, l’insieme dei problemi definibili probabilmente coincidecon l’insieme dei problemi risolvibili.

Quali sono i problemi risolvibili?Costruiamo un programma che ci dica se un dato programma andrà o meno in loop:{1 se (x) =⊥f y N N N N,= ∈ : × →g(y, x) y, x g0 se (x) =⊥fy ∀x ∈ {0, 1}OSS: è una funzione totale, cioè è associato univocamenteg DN 2perciò è definita su tuttoNB: NON è la MTU!!g(y, x)Esiste una MT per ? NOgdim tramite tecnica diagonale (e per assurdo) della non esistenza di una MT per :g∃Supponiamo che MT che calcoli , allora significa che è calcolabile.g(y, x) gLemma: introduciamo una nuova funzione{1, se = 0g(x, x)=h(x) ⊥, altrimentiè per

assurdo calcolabile perché per assurdo lo è (che termina sempre perché è totale), allora esiste il numero di Gödel corrispondente, lo chiamiamo x0. Quindi h(f(x0))

Calcoliamo ora: h(x0) = 1, f(x0) = 0 ⊥ se allora, ma allora e di conseguenza h(x0) = ⊥, f(x0) = 1 ⊥ se allora, ma allora e di conseguenza h(x0) = ⊥

Cioè ho dimostrato che non è calcolabile quindi di conseguenza non lo è nemmeno g.

sottoproblema non risolvibile ⟹ problema non risolvibile

Nota: non è un se e solo se!

OSS: se una funzione è totale non è detto che sia calcolabile e, viceversa, se una funzione è parziale non è detto che non sia calcolabile.

Teoria del calcolo 4

Costruiamo un'altra funzione indecidibile:

{ N1, se (x) = ⊥, ∀x ∈ f y=k(y) 0, altrimenti

dim per assurdo, tramite tecnica diagonale,

dell'indecibilità di :k

Supponiamo per assurdo che sia calcolabile.k(y)

Notiamo che è totale.k(y) =

Definiamo un'altra funzione: , con = indice della -esima MT che

eg(x) w w x calcola una funzione totale ( di Gödel)

Dato che è calcolabile, allora anche lo è. Come?

k g= 0, = 0

Inizializziamo w t=

Calcoliamo k(w){0 ⟹ ++w1 ⟹ (se = ⟹ + +, altrimenti restituisco x t t x)NB: è strettamente monotona perciò se cresce, anche cresce

g w g(w)non è una funzione totale

g -1

Calcoliamo ora g{∅, se parzialefW-1 (w) =g altrimenti

x, = (x) + 1

Definiamo ora un'altra funzione: h(x) fg(x) è totale (perché è totale) e calcolabile

h fg(x)

Indichiamo con l'indice della MT che calcola , cioè

w h0-1 -1= ⟹ (w ) =∅ ⟹ (w ) =h f g g x0 0 0w 0 )

Calcoliamo ora :h(x0 □) = + 1 = + 1 = ) + 1 assurdo

h(x f f h(x0 0) wg(x 00 N N: →Notazione: una funzione è calcolabile se

E solo se esiste una MT che laf N∈ =calcola, ovvero esiste un valore tale che .y f fYTeoria del calcolo 5Decidibilità e semidecidibilitàN: → {0; 1}Consideriamo funzioni del tipo , cioèf{1, se ∈x S(x) = Funzione caratteristica dic Ss 0, se ∈/x SNB: è totalecsUn insieme viene detto DECIDIBILE o ricorsivo se e solo se la sua funzioneScaratteristica è calcolabile.cSL’insieme viene detto SEMIDECIDIBILE o ricorsivamente enumerabile se e soloSse ∅ N}= ∪ = = {g (y) ∣ ∈ è una funzione totale e calcolabile.S S I yg SS = {g (0), (1), ...}Nota: la seconda condizione significa S gS STEOREMASe è decidibile allora è anche semidecidibile.A) S N¬S = −è decidibile se e solo se stesso e il suo complemento ( ) sonoB) S S Ssemidecidibili.dim :A ∅=Se è semidecidibile per definizione.S ∃k ∈ (k) = 1Altrimenti , cioèS cSAllora costruisco una nuova funzione:{ se (x)

1. Dato l'insieme S, se ∈x, cioè se x ∈ S, allora S = gS; altrimenti, k. È totale e calcolabile.
2. L'immagine di φ è quindi semidefinibile per definizione.
3. SSdim : B ⟶ decidibile semidecidibile da dimS S A.
4. Teoria del calcolo 6{0, ∈x S ⟹ (x) ⟹ (x) = decidibile è calcolabile.
5. c ¬ SS 1, ∈/x S è calcolabile.
6. Siano e e semidecidibili: S ⟶ = {g(0), (1), ...} è semidecidibile.
7. S ⟶ = {g(0), (1), ...} è semidecidibile.
8. g ¬S ¬S ∅∪ ¬S = ∩ ¬S =.
9. Perciò, e per definizione S S.
10. Allora costruisco una nuova enumerazione: {g(0), (0), (1), (1), ...}, in questa enumerazione potrò trovare x.
11. Alcuni enunciati con importanti risvolti pratici:

Ricorda: stiamo lavorando solo con i numeri naturali

1. Dato l'insieme S, se ∈x, cioè se x ∈ S, allora S è totale.
2. Se S è totale e calcolabile, allora f è semidecidibile.
3. Se f non è semidecidibile, allora S non è totale e calcolabile.

è possibile definire un formalismo che identifichi tutte e sole le funzioni totali e calcolabili.

Note: gli FSA definiscono funzioni totali ma non tutte le MT definiscono tutte le funzioni calcolabili, ma anche quelle non totali.

Il linguaggio C permette di programmare qualsiasi algoritmo, ma anche quelli che non terminano.

NB: in matematica spesso si trasformano le funzioni parziali in funzioni totali, in informatica questa trasformazione può spesso portare a perdere la calcolabilità.

2) è semidecidibile se e solo se:

S = {x ∣ =⊥}, con calcolabile e parziale: S D h S h(x)hdetto dominio o controimmagine N}= {g(y) ∣ ∈ S I g S ygTeoria del calcolo 7Alcuni autori, al posto di definire questo enunciato tramite questi due punti, preferiscono utilizzare la funzione semi-caratteristica:

è semidecidibile se e solo se la sua funzione semicaratteristica è calcolabile:

S {1, se ∈x S′ (x) = funzione semicaratteristica cS ⊥

se ∈/x S3) Esistono insiemi semidecidibili che non sono decidibili= {x∣f (x) =⊥} è semidecidibile perché dominio di funzione enumerabile,k x= = (x)cioè conK D h(x) fh x {1, se (x) =⊥f x=Però sappiamo anche che non è calcolabile, quindick 0, se (x) =⊥fxnon è decidibile.KPossiamo trarre comeconclusione questocontenimento insiemisticostretto

Nota: Gli insiemi ricorsivisono chiusi rispetto alcomplemento a differenzadei semidecidibili che non losono

Teorema di Kleene del punto fissoSia una funzione totale e calcolabile; è sempre possibile trovare un numerot =naturale tale chep f fp t(p)La funzione è detta punto fisso di .f tpNote: =p t(p) = , hanno semplicemente la stessaM M fp t(p)Teoria del calcolo 8dim: N∈Sia uDefiniamo una MT tale che sul valore di ingresso calcola:x= (u)z fu(x)fzFissato , possiamo costruire la MT e poi possiamo cercare il suo indiceu g(u)E: →uper ogni possibile usando la

solita enumerazioneu E MT g(u)∀uè totale ( posso trovare una MT) e calcolabileg(u)Allora definiamo la seguente funzione:{ (x), =⊥f f (u) uf(x) = ufg(u) ⊥, (u) =⊥fuSe la funzione , dell’enunciato del teorema, è totale e computabile allora anchet ∘la composizione lo èf g (x) =Sia l’indice della MT che calcola cioèv t(g(.)) f t(g(x))vUsiamo al posto della nella costruzione precedente:v u □(x) = (x) = (x)f f ffg(v) t(g(v))v(v)Teorema di Rice N⊆Sia un insieme di funzioni calcolabili, l’insieme degli indici di MT cheF S= {i ∣ ∈ }calcolano funzioni di , cioè , è decidibile se e solo se èF S f F Fi∅= ∪banale, cioè se e solo se è l’insieme di tutte le funzioni calcolabili.F Fdim per assurdo: ∅= ∩Supponiamo, per assurdo, che sia decidibile, non è l’insieme diS F Ftutte le funzioni calcolabili.(x)Prendiamo che è calcolabile.cS

∈ ∈ ∈ ∈(1) (2)/Possiamo trovare α tale che β e γ tale che δ. La funzione ε è: cS{ se ∈/i, f F′ (x) =(3) totale (per definizione) e calcolabile cS se ∈j, f F′ (x)Teoria del calcolo 9′ ′ (x)Applichiamo il teorema di Kleene: esiste un punto fisso di φ, cioè x cS=(4) f F′ ′ (x )′x c S ′ ′(x ) = ∈(3) (4)/Supponiamo che α, allora dalla β segue che γ, ma dalla contraddizione f f f F f F′ ′x i i x′ ′(x ) = ∈(3)Supponiamo allora che α, allora dalla β segue che γ, ma c j f F′ (x)S □= ∈ ⟹ ∈(4) (2)dalla γ si ha δ e dalla contraddizione/ /f f f F f F′ ′x j j xConseguenze del teorema d