Oggi, come già anticipato, introduco il concetto di riducibilità per poi arrivare a definire la classe di funzioni rec e a formalizzare la differenza tra la classe degli insiemi ricorsivi R e quella degli insiemi ricorsivamente enumerabili RE.
Intuitivamente già sappiamo che un insieme in R è decidibile: ovvero esiste una funzione caratteristica calcolabile totale per quell’insieme. Abbiamo dunque la garanzia che dopo un numero non limitato, ma finito di passi otterremo una risposta dall’algoritmo che calcola la funzione caratteristica stessa. Mentre nel caso degli insiemi semi-decidibili in RE, potremmo incappare in una computazione non terminante durante il calcolo della semi-caratteristica ed impiegare un tempo infinito per decidere l’appartenenza di un elemento all’insieme.
Per raggiungere questi scopi introduciamo alcuni concetti di riducibilità per poi applicarli a R e RE.
Riducibilità
Una riduzione è una particolare funzione f che trasforma un problema (ovvero un insieme o una classe) A in un altro problema B, in modo da mantenerne inalterata la caratteristica principale.
Definizione di riduzione
Definizione: A si riduce a B secondo la riduzione f, in simboli \(A \leq_f B\)
, tutte e sole le volte che:
$$a \in A \iff f(a) \in B \text{, ovvero } f(A) \subseteq B \wedge f(\bar A) \subseteq \bar B$$
Proprietà: \(A \leq_f B \iff \bar A \leq_f \bar B\)
.
Dimostrazione: si ha che
\(x \in \bar A \iff x \notin A \iff f(x) \notin B
\iff f(x) \in \bar B\)
.
□
Piú in generale, si definisce una relazione di riduzioni \((\leq_F )\)
dove F è una particolare classe di funzioni. Allora sciveremo
Relazione di riduzione che classifica due classi
Definizione di relazione di riduzione: siano \(\mathcal{D}, \mathcal{E}\)
due classi di problemi con \(\mathcal{D} \subseteq \mathcal{E} (\subseteq \mathcal{H})\)
. Una relazione di riduzione \(\leq_F\)
classifica \(\mathcal{D} \text{ ed } \mathcal{E} \iff \forall \text{ problema } A,B,C\)
:
$$ \begin{align} &A \leq_F A &(\textit{Riflessiva}) \\ &A \leq_F B, B \leq_F C \implies A \leq_F C &(\textit{Transitiva}) \\ &A \leq_F B, B \in \mathcal{D} \implies A \in \mathcal{D} &(\mathcal{D} \textit{ ideale}) \\ &A \leq_F B, B \in \mathcal{E} \implies A \in \mathcal{E} &(\mathcal{E} \textit{ ideale}) \end{align} $$
Lemma riduzione con classe di funzioni: una relazione di riduzione \((\leq_F )\)
classifica \(\mathcal{D}, \mathcal{E} . \mathcal{D} \subseteq \mathcal{E}\)
sse:
$$ \begin{align} &id \in F &(\textit{F ha identit\`{a}}) \\ &f,g \in F \implies f \circ g \in F &(\textit{F chiusa per composizione}) \\ &f \in F, B \in \mathcal{D} \implies \{x | f(x) \in B\} \in \mathcal{D} & 3\\ &f \in F, B \in \mathcal{E} \implies \{x | f(x) \in B\} \in \mathcal{E} & 4 \end{align} $$
La relazione di riduzione \((\leq_F )\)
è un pre-ordine parziale cioè un
ordinamento parziale riflessivo e transitivo, ma non anti-simmetrico.
Definizione di grado, arduo e completo
Se \((\leq_F )\)
classifica
\(\mathcal{D} \text{ ed } \mathcal{E}, \forall A,B,H\)
problemi:
Nella definizione (9) si dice anche che \(\{B|A \equiv_F B\}\)
è il
grado di A.
Diremo semplicemente \(\mathcal{E}\textit{-arduo}\)
o
\(\mathcal{E}\textit{-completo}\)
quando la classe di riduzioni F sia
fissata; talvolta ometteremo anche \(\mathcal{E}\)
,
se chiaro dal contesto.
Proprietà completezza
Se un problema è completo per una classe E e appartiene ad una sotto- classe D, allora le due classi coincidono.
Proprietà: se \(\leq_F\)
ed \(\mathcal{E}\)
, \(\mathcal{D} \subseteq \mathcal{E}\)
e C è completo per \(\mathcal{E}\)
se e solamente se \(\mathcal{D} = \mathcal{E}\)
.
Dimostrazione: (se) \(\mathcal{D} = \mathcal{E}\)
è ovvio che
\(C \in \mathcal{D}\)
.
(solo se) Sia \(C \in \mathcal{D} \text{ e } A \in \mathcal{E}\)
.
Per completezza \(A \leq_F C \text{ e } A \in \mathcal{D}\)
per la
condizione (iii) di \(\leq_F\)
che classifica D ed E.
Quindi \(\mathcal{D} \subseteq \mathcal{E}\)
e la tesi.
□
Proprietà: se A è completo per \(\mathcal{E}, A \leq_F B, B \in \mathcal{E}\)
allora B è completo per \(\mathcal{E}\)
Dimostrazione: \(\forall D \in \mathcal{E}, D \leq_F A\)
per
completezza, ma classifica \(\mathcal{D} \text{ ed } \mathcal{E}\)
e
allora \(D \leq_F A, A \leq_F B \implies D \leq_F B\)
e quindi B è
arduo e poichè appartiene a \(\mathcal{E}\)
, è completo.
□
Classe rec
Da qui in avanti “rec” sarà il nome dell’insieme delle funzioni calcolabili totali:
Definizione:
$$rec = \{ \varphi_x | \forall y \in \mathbb{N} . \varphi_x(y) \downarrow\}$$
Adesso che abbiamo sia la definizione generale di riduzione e le sue proprietà,
che la definzione di rec, possiamo ottenere le interessanti relazioni di
riduzione \(\leq_{rec}\)
.
Definizione: A è riducibile a B (\(A \leq_{rec} B\)
) se e solamente se esiste una funzione calcolabile totale \(f:\mathbb{N} \mapsto \mathbb{N}\)
tale che:
$$x \in A \iff f(x) \in B$$
Vediamo ora che queste relazioni di riduzione conservano la ricorsività e la ricorsiva enumerabilità. Ricordiamo che R è la classe degli insiemi ricorsivi e che RE è la classe degli insiemi ricorsivamente enumerabili.
Teorema: la relazione di riduzione \(\leq_{rec}\)
classifica R e RE.
Dimostrazione: sappiamo già che \(R \subseteq RE\)
(vedi gerarchia) e
questo ci permette di soddisfare le ipotesi del lemma riduzione con classe di
funzioni, perché:
- andiamo a vedere se in rec c’è una funzione identità e le funzioni ricorsive primitive ce l’hanno, a maggior ragione ce l’hanno le funzioni µ-ricorsive (considerando solo quelle totali) che sono un sovrainsieme delle funzioni ricorsive primitive.
- la composizione di funzioni totali conserva la totalità
- bisogna verificare che
\(f \in rec, B \in R \implies \{x | f(x) \in B\} \in R\)
cioè che presa una funzione calcolabile totale da rec, applicata ad un problema B preso da R ci lascia in R, quindi si va a vedere la funzione caratterisitica dell’insieme \(I = \{x | f(x) \in B\}\)
che è esattamente \(\chi_I = \chi_B \circ f\)
. Essendo entrambe calcolabili totali anche la loro composizione lo è, quindi \(I \in R\)
- bisogna verificare che
\(f \in rec, B \in RE \implies \{x | f(x) \in B\} \in RE\)
, quindi, analogamente al punto precedente, andiamo ad analizzare la semi-caratteristica di B e notiamo che è sempre una composizione di funzioni totali. □
A questo punto se trovassimo un problema che sia \(\leq_{rec}\textit{-completo}\)
per R, potremo vedere quali problemi sono decidibili e quali no.
Se ne trovassimo uno \(\leq_{rec}\textit{-completo}\)
per RE sepremmo
quali sono al più semi-decidibili e quali nemmeno semi-decidibili.
Osservazione: nel caso in cui \(A \leq_{rec} B\)
- \(A \notin R \implies B \notin R\)
- \(A \notin RE \implies B \notin RE\)
- \(B \in R \implies A \in R\)
- \(B \in RE \implies A \in RE\)
K è RE-completo
Torniamo a ragionare sull’insieme degli indici delle funzioni che convergono se
applicate al loro stesso indice, ovvero
\(K = \{x | \varphi_x(x) \downarrow\}\)
.
Proprietà 1: \(\bar K \nleq_{rec} K\)
Dimostrazione: sappiamo che K è ricorsivamente enumerabile (semi-decidibile),
ma non ricorsivo (decidibile). Se per assurdo \(\bar K\)
si riducesse a
K allora per la proprietà delle riduzioni, anche \(\bar K\)
sarebbe
ricorsivamente enumerabile, ma abbiamo già dimostrato che ciò provoca una
contraddizione:
per la proprietà 3 degli insiemi \(\bar K\)
sarebbe anche ricorsivo e
quindi sarebbe ricorsivo anche K.
□
Proprietà 2: \(K \nleq_{rec} \bar K\)
Dimostrazione: per la proprietà delle riduzioni \(A \leq_{rec} B
\iff \bar A \leq_{rec} \bar B\)
, se per assurdo fosse vero
che \(K \leq_{rec} \bar K\)
dovrebbe essere anche vero che
\(\bar K \leq_{rec} K\)
che è appena stato dimostrato falso.
□
Teorema: K è RE-completo, o più precisamente \(\leq_{rec}\textit{-completo}\)
per RE. In altri termini \(A\in RE \implies A \leq_{rec} K\)
.
Dimostrazione: per definizione A è il dominio di una funzione calcolabile ψ,
cioè \(A = \{x | \psi(x) \downarrow \}\)
.
A partire da ψ si definisca una funzione ψ’ a due variabili di cui ignora la
seconda, cioè sia ψ’(x, y) = ψ(x), che è a sua volta una funzione calcolabile
e quindi avrà un indice, diciamo i; in simboli \(\psi' = \varphi_i\)
.
Allora, per il teorema del parametro
\(\psi'(x, y) = \varphi_i(x, y) = \varphi_{s(i,x)}(y)\)
, con s
calcolabile, iniettiva e totale.
Posso riscrivere la definizione di A come segue:
quindi \(x \in A \iff f(x) \in K \text{, con } f(x) = \lambda x.s(i,x)\)
,
che è totale, calcolabile e iniettiva perchè la s(i, x) lo è: prendiamo i tale
che \(\psi'(x, y) = \varphi_i(x, y) = \varphi_{s(i,x)}(y) \implies
f = \lambda x. s(i, x)\)
.
□
Osservazione:
- \(K \leq_{rec} I \implies I \notin R\)
- \(\bar K \leq_{rec} I \implies I \notin RE\)
- \(I \leq_{rec} K \implies I \in RE\)
Domani dovrei finire con le riduzioni e concludere la prima parte sulla calcolabilità per addentrarmi nello studio della complessità.