Autore: Elia Argentieri
Ultima modifica: 6 mag 2022 18:07
Redazione: 27 gen 2022 23:28
Sorgente di questa pagina
Tempo di lettura: 9 minuti

Oggi dimostriamo alcuni importanti risultati della teoria della calcolabilità. In questa lezione iniziamo a mettere insieme i pezzi: già conosciamo gli insiemi R, RE, rec, e il paradigmatico insieme K (che è parente stretto di K₀, l’insieme che formalizza il problema della fermata).

Con lo scopo di dimostrare che non esistono algoritmi in grado di decidere (e nemmeno di semi-decidere) se una funzione è totale o parziale (sbattendo violentemente contro il problema della fermata), andiamo ad introdurre un altro insieme molto importante, ovvero l’insieme TOT di tutti e soli gli indici dei programmi che calcolano funzioni calcolabili totali.

Insieme TOT

Ricordando che $rec = \{ \varphi_x | \forall y \in \mathbb{N} . \varphi_x(y) \downarrow\}$ , andiamo a definire un nuovo insieme:

Definizione:
$$TOT = \{x | \varphi_x \in rec\}$$

Attenzione a non confondere rec con TOT: sebbene entrambi abbiano a che fare con funzioni calcolabili totali, rec è un insieme di funzioni, mentre TOT è un insieme di indici (di programmi o macchine). In questa serie avevo già esplicato la differenza tra indici e funzioni.

L’obiettivo è quello di dimostrare che TOT è indecidibile, cioè non è né ricorsivo (decidibile), né ricorsivamente calcolabile (semi-decidibile).
Prima di addentrarci nella dimostrazione, vediamo una definizione che ci tornerà utile.

Insieme di indici che rappresentano le funzioni

Definizione: A è un insieme di indici che rappresentano le funzioni (i.i.r.f.) se e solamente se:
$$\forall x,y . x \in A \wedge \varphi_x = \varphi_y \implies y \in A$$

Con questa definizione possiamo definire l’insieme A di tutti e soli gli indici dei programmi che calcolano una particolare funzione φ.

Attenzione a non confondere A con $A_x$ che era stato definito nel teorema del padding lemma. Confrontiamo A e $A_x$ , che avevamo definito così: $\forall y \in A_x . \varphi_y = \varphi_x$ .

Esempi di insiemi di indici che rappresentano le funzioni:

l’insieme vuoto (il quantificatore universale sull’insieme vuoto è sempre vero)
l’insieme $\mathbb{N}$ (contiene tutte le funzioni calcolabili)
l’insieme degli indici delle funzioni il cui dominio è un singolo elemento, ovvero $I = \{i | \#dom(\varphi_i) = 1\} = \{i|\exists n. dom(\varphi_i) = \{n\}\}$

TOT non è ricorsivo (decidibile)

Ricordando che K non è ricorsivo, mostriamo che K si riduce a TOT secondo $\leq_{rec}$ , provando la non ricorsività di TOT:

$$K = \{x | \varphi_x(x) \downarrow\} \leq_{rec} \{x | \varphi_x \in rec\} = TOT$$

$K = \{x | \varphi_x(x) \downarrow\} \leq_{rec} \{x | \varphi_x \in rec\} = TOT$

Definiamo questa funzione calcolabile parziale: $\psi(x, y) = \begin{cases}1 & \text{se } x \in K \\ \text{indefinita}&\text{altrimenti} \end{cases}$

La funzione ψ appena definita, è calcolabile parziale perché il programma $P_x$ calcola $\varphi_x(x)$ e se questa converge restituisce 1 per ogni y.
Per il teorema del parametro s-m-n esiste f calcolabile totale iniettiva tale che $\varphi_{f(x)}(y) = \psi(x,y)$ . Ricordiamo come costruire la funzione f: scegliamo i tale che $\psi(x,y) = \varphi_i(x,y) = \varphi_{s(i,x)}(y) \implies f = \lambda x.s(i,x)$ .

Dobbiamo dimostrare che la riduzione funziona e possiamo farlo prendendo la definizione di riduzione e applicandola: $x \in K \iff f(x) \in TOT$ , che possiamo dimostrare separando nei due casi:

$x \in K \implies \varphi_{f(x)} = \psi(x,y) = \lambda y. 1 \implies \varphi_{f(x)} \text{ totale} \implies f(x) \in TOT$ cioè la funzione f applicata ad $x \in K$ restituisce l’indice di una funzione totale e quindi anche $f(x) \in TOT$ .
$x \notin K \implies \varphi_{f(x)} = \lambda y. \text{ indefinito} \implies \varphi_{f(x)} \text{ parziale} \implies f(x) \notin TOT$ cioè la funzione f applicata ad $x \notin K$ restituisce l’indice di una funzione parziale e quindi anche $f(x) \notin TOT$ .

Siccome $K \leq_{rec} TOT$ e sappiamo che K non è ricorsivo, allora possiamo concludere che TOT non è ricorsivo. □

TOT non è nemmeno semi-decidibile

Mostriamo che TOT non è ricorsivamente enumerabile tramite la riduzione $\bar K \leq_{rec} TOT$ (ricordiamo che $\bar K$ non è ricorsivamente enumerabile).

Per le proprietà delle riduzioni $\bar K \leq_{rec} TOT \iff K \leq_{rec} \overline{TOT}$ . Cioè possiamo mostrare che TOT non è ricorsivamente enumerabile se e solo se K si riduce a non TOT.

Prendiamo in considerazione la funzione calcolabile: $\psi(x, y) = \begin{cases} \text{indefinita} & \text{se } x \in K \\ 1 & \text{altrimenti} \end{cases}$

$x \in K \implies \varphi_{f(x)} = \psi(x,y) = \lambda y. \text{indefinita} \implies \varphi_{f(x)} \text{ parziale} \implies f(x) \in \overline{TOT}$
$x \notin K \implies \varphi_{f(x)} = \psi(x,y) = \lambda y. 1 \implies \varphi_{f(x)} \text{ totale} \implies f(x) \notin \overline{TOT}$

Quindi $\bar K \leq_{rec} TOT$ e TOT non è ricorsivamente enumerabile. □

Teorema di Rice

Il teorema di Rice afferma che non è decidibile il problema di decidere quali funzioni calcolabili soddisfino una data proprietà non banale della funzione stessa. Le proprietà banali in questo contesto sono quelle che non discriminano tra le funzioni calcolabili, cioè che valgono per tutte o per nessuna.

Teorema “pre-Rice”

Teorema: sia A un insieme di indici che rappresentano le funzioni tale che $\emptyset \neq A \neq \mathbb{N}$ .
Allora $K \leq_{rec} A$ oppure $K \leq_{rec} \bar A$ .

Dimostrazione: iniziamo col dimostrare che $K \leq_{rec} A$ ovvero $x \in K \iff f(x) \in A \text{ con } f \in rec$ .

Prendi un indice $i_0 \in \bar A$ associato ad una funzione $\varphi_{i_0}(y)$ che sia ovunque indefinita.
Poichè $A \neq \emptyset$ posso prendere un altro indice $i_1 \in A$ (stavolta appartiene all’insieme A) con associata la funzione $\varphi_{i_1}(y)$ .
Notiamo che $\varphi_{i_0} \neq \varphi_{i_1}$ perché A è un i.i.r.f. (insieme di indici che rappresentano le funzioni) e un i.i.r.f. contine tutti gli indici di $\varphi_{i_1}(y)$
Definiamo la seguente funzione calcolabile:
$$\psi(x,y) = \begin{cases} \varphi_{i_1}(y)& \text{se }x \in K\\ \text{indefinita} = \varphi_{i_0}(y) & \text{altrimenti} \end{cases}$$
Applichiamo il teorema s-m-n per determinare una funzione calcolabile totale iniettiva tale per cui $\psi(x,y) = \varphi_{f(x)}(y)$ .
Prendiamo in esame il caso in cui $x \in K$ e quindi $\varphi_{f(x)}(y) = \varphi_{i_1}(y)$ : notiamo che siccome $i_1 \in A$ e A è un i.i.r.f. allora anche $f(x) \in A$ .
Il caso complementare è analogo: se $x \notin K$ e quindi $\varphi_{f(x)}(y) = \varphi_{i_0}(y)$ allora dato che $i_0 \in \bar A$ e A è un i.i.r.f. allora $f(x) \notin A$ .
Abbiamo dimostrato che:
- $x \in K \implies \varphi_{f(x)} = \varphi_{i_1} \implies f(x) \in A$
- $x \notin K \implies \varphi_{f(x)} = \varphi_{i_0} \implies f(x) \in \bar A$

Quindi $x \in K \iff f(x) \in A$ cioè $K \leq_{rec} A$ .

La dimostrazione di $K \leq_{rec} \bar A$ si ottiene analogamente capovolgendo la definizione della funzione $\psi$ , come segue:

$$\omega(x,y) = \begin{cases} \text{indefinita} = \varphi_{i_0}(y)& \text{se }x \in K\\ \varphi_{i_1}(y) & \text{altrimenti} \end{cases}$$

$\omega(x,y) = \begin{cases} \text{indefinita} = \varphi_{i_0}(y)& \text{se }x \in K\\ \varphi_{i_1}(y) & \text{altrimenti} \end{cases}$

$\omega(x,y) = \varphi_{g(x)}(y)$
$x \in K \implies \varphi_{g(x)} = \varphi_{i_0} \implies f(x) \in \bar A$
$x \notin K \implies \varphi_{g(x)} = \varphi_{i_1} \implies f(x) \notin \bar A$ □

Teorema di Rice

Teorema: sia $\mathcal{A}$ una classe di funzioni calcolabili. L’insieme $A = \{n | \varphi_n \in \mathcal{A}\}$ è ricorsivo se e solo se $A = \emptyset \vee A = \mathbb{N}$ .

Dimostrazione: notiamo che $A$ (sintassi) è un insieme di indici, mentre $\mathcal{A}$ (semantica) è una classe di funzioni. Notiamo anche che se $A = \mathbb{N}$ allora $\mathcal{A}$ è la classe di tutte le funzioni calcolabili.

Esaminiamo ogni caso:

se $\mathcal{A} = \emptyset$ allora $A$ è ovviamente ricorsivo ($\chi_A$ totale perché restituisce sempre 0)
se $\mathcal{A}$ è la classe di tutte le funzioni calcolabili allora $A$ è ancora ricorsivo ($\chi_A$ totale perché restituisce sempre 1)
in tutti gli altri casi basta applicare il teorema precedente (“pre-Rice”) perché $A$ è un insieme di indici che rappresentano le funzioni □

Questo importante risultato negativo, ci impedisce, come già anticipato, di costruire algoritmi che provano altri algoritmi perchè si incappa nel problema della fermata. Il “trucco” usato dagli informatici per aggirare questo problema è, per esempio, quello adottato dagli analizzatori statici, che approssimano il comportamento che avrà il programma a tempo di esecuzione. In questo modo vengono accettati solo i programmi che passano certi requisiti, scartando tutti i programmi scorretti, ma anche alcuni che in realtà sono corretti, così da far passare solo quelli di cui si ha certezza che vadano bene. In un certo senso “abbiamo falsi positivi, ma nessun falso negativo”.

Altri teoremi

Teorema: $K$ non è un i.i.r.f.

Dimostrazione: bisogna mostrare che non è vero che $\forall x \in K \implies \varphi_x = \varphi_y \implies y \in K$ .

Definiamo la funzione $\psi(x, y) = \begin{cases}42 & \text{se } x = y \\ \text{indefinita}&\text{altrimenti}\end{cases}$
Per la tesi di Church Turing e per il teorema del parametro si ha che $\psi(x,y) = \varphi_i(x,y) = \varphi_{s(i,x)}(y) = \varphi_{f(x)}(y)$ .
Per il teorema di ricorsione $\exists f(x) . \varphi_{f(x)}(y) = \varphi_x(y)$ con x punto fisso per f(x).
Notiamo che $\psi(p,p) = \varphi_p(p) = 42 \implies p \in K$ .
Per il teorema del padding lemma $\exists q \neq p | \varphi_q = \varphi_p$ .
Tuttavia $\psi(p,q) = \varphi_p(q) = \varphi_q(q)$ è indefinita e q non appartiene a K. Di conseguenza K non è un i.i.r.f. □

Insieme K₁

Definizione: L’insieme $K_1 = \{x | dom(\varphi_x) \neq \emptyset \}$ è l’insieme degli indici delle funzioni che hanno dominio non vuoto, cioè che sono definite in almeno un punto.

Teorema: l’insieme $K_1$ non è ricorsivo.

Dimostrazione: l’insieme $K_1$ non è vuoto (banalmente esistono funzioni che hanno il dominio non vuoto) e non è $\mathbb{N}$ (non contiene la funzione ovunque non definita che ha dominio vuoto). Per il teorema di Rice, l’insieme $K_1$ non è ricorsivo. □

Teorema: l’insieme $K_1$ è ricorsivamente enumerabile.

Dimostrazione: se $K_1$ è ricorsivamente enumerabile allora deve esistere una funzione semi-caratteristica calcolabile tale che: $\chi_{K_1} = \begin{cases}1&\text{se }dom(\varphi_x) \neq \emptyset\\ \text{indefinita}&\text{altrimenti}\end{cases}$ . Siccome posso immaginare un algoritmo che prova sistematicamente tutti gli input della funzione $\varphi_x$ e che restituisce 1 se la funzione è definita in quel punto e che continua indefinitivamente all’infinito se il punto non esiste, allora per la tesi di Church Turing la semi-caratteristica esiste calcolabile e K₁ è ricorsivamente enumerabile. □

K ≡ K₀ ≡ K₁

Possiamo dimostrare che $K = \{ x ∣ \varphi_x(x) \downarrow\} \equiv_{rec} K_0 = \{(x,y) | \varphi_y(x) \downarrow\} \equiv_{rec} K_1 = \{x | dom(\varphi_x) \neq \emptyset \}$ , cioè i tre insiemi si riducono l’uno all’altro e sono RE-completi.