Insieme ricorsivamente enumerabile

Nella teoria della calcolabilità esistono due definizioni di insieme ricorsivamente enumerabile (spesso abbreviato in insieme r.e.) o insieme semi-decidibile. Intuitivamente, un insieme numerabile $S$ si dice r.e. se esiste un algoritmo (o equivalentemente una funzione ricorsiva totale) che:

• preso un certo input, se l'input appartiene a $S,$ allora esso termina (o "è definita" nel caso delle funzioni ricorsive).

Oppure, equivalentemente,

• genera in output tutti e soli gli elementi di $S$.

La prima definizione è quella che più strettamente si riferisce al nome "insieme semi-decidibile", mentre la seconda al nome "ricorsivamente enumerabile" (la funzione ricorsiva infatti è detta in quel caso funzione enumeratrice).

La classe degli insiemi ricorsivamente enumerabili è un sovrainsieme stretto degli insiemi ricorsivi.

Definizioni formali

Le due seguenti definizioni degli insiemi r.e. sono date riferendosi solo all'insieme dei naturali e a funzioni dai naturali ai naturali; tuttavia tramite opportune funzioni di decodifica è possibile ricondurre a questi casi tutti gli altri insiemi numerabili.

Esistenza funzione enumeratrice

Un insieme numerabile $S$ si dice ricorsivamente enumerabile se esiste una funzione calcolabile $f$ tale che $S$ è l'immagine di $f$:

$\mathrm {Im} (f)=S.$

In questo caso la funzione $f,$ per ogni controimmagine che prende in input, restituisce in output un elemento di $S,$ come per associare a ogni "posizione" (i naturali in input) nell'enumerazione l'elemento (di $S$) che sta in quella posizione. Per questo si dice che la funzione $f$ enumera $S.$ Da notare che sono ammesse ripetizioni nell'enumerazione, cioè un elemento di $S$ può trovarsi in più posizioni.

Insieme semi-decidibile

Un insieme numerabile $S$ si dice ricorsivamente enumerabile se è semidecidibile, cioè se la sua funzione semicaratteristica

$\mathbf {1} _{S}(x)=1{\text{ se e solo se }}x\in S$

è calcolabile. In altre parole, se $S$ è un sottoinsieme della controimmagine di $\mathbf {1} _{S}$:

$S\subseteq \mathrm {Controim} (\mathbf {1} _{S})$

e $\mathbf {1} _{S}$ restituisce 1 tutte e sole le volte in cui l'input appartiene ad $S$. Secondo la tesi di Church-Turing, il concetto di funzione calcolabile è definito in modo equivalente da vari modelli di calcolo, tra cui le macchine di Turing. Perciò, è frequente trovare una formulazione alternativa di questa stessa definizione, che sostituisce al concetto di funzione calcolabile quello di macchina di Turing:

Un insieme numerabile $S$ si dice ricorsivamente enumerabile sse esiste una macchina di Turing tale che, se prende in input un elemento di $S$, allora termina.

Dimostrazione dell'equivalenza delle due definizioni

Mostriamo che le due definizioni sono equivalenti mostrando che la prima implica la seconda, e che la seconda implica la prima.

Dobbiamo dimostrare che $x\in \mathrm {Im} (f){\text{ se e solo se }}\mathbf {1} _{S}(x)=1.$

Partiamo dalla definizione di insieme ricorsivamente enumerabile:

$\mathrm {Im} (f)=S,$

è quindi possibile scrivere un programma $P$ che ci dica se un elemento $x\in S$ simile al seguente:

    begin
      input(x)
      while (F(i) != x)
             i = i + 1
      output(1)
    end.

La funzione calcolata dal programma è:

$\varphi _{P}(x)=1{\text{ se e solo se }}x\in S,$

quindi $S$ è un sottoinsieme della controimmagine di $\varphi _{P}$:

$S\subseteq \mathrm {Controim} (\varphi _{P})$

se e solo se

$\mathrm {Im} (f)\subseteq \mathrm {Controim} (\varphi _{P})$

dunque, dato che $\varphi _{P}=\mathbf {1} _{S},$

$x\in \mathrm {Im} (f){\text{ se e solo se }}\varphi _{P}(x)=1{\text{ se e solo se }}\mathbf {1} _{S}(x)=1$

dimostrando così l'uguaglianza tra le due definizioni.

La cardinalità della classe degli insiemi r.e.

È piuttosto banale dimostrare che la cardinalità della classe degli insiemi r.e. è numerabile, dato che si può stabilire una corrispondenza biunivoca dalla suddetta classe all'insieme delle macchine di Turing, nonostante possano esistere diverse MdT che accettano il medesimo insieme. Ciò è possibile perché, per definizione, ogni insieme r.e. è accettato da almeno una macchina di Turing, e inoltre l'insieme delle MdT è ricorsivo, dato che esiste una MdT in grado di stabilire sempre se un numero binario rappresenta una macchina di Turing valida. Dunque, a fortiori, l'insieme delle MdT è numerabile, e di conseguenza lo è anche la classe degli insiemi r.e.

Proprietà degli insiemi r.e.

Unione e intersezione

Se gli insiemi $A$ e $B$ sono r.e., allora anche $A\cap B$ e $A\cup B$ sono ricorsivamente enumerabili.

Insieme complemento

Se l'insieme $S$ è r.e. e l'insieme complemento ${\overline {S}}=\mathbb {N} -S$ (stiamo considerando $\mathbb {N}$ come universo) è anch'esso r.e., allora $S$ è ricorsivo. Formalmente:

$(S\in RE)\land ({\overline {S}}\in RE)\Rightarrow \;S\in R.$

Interpretazione: osserviamo che per un insieme ricorsivo $I$, dato un qualunque numero naturale $x$, siamo in grado di rispondere in un tempo finito sull'appartenenza di $x$ all'insieme, sia nel caso in cui $x\in I$, sia nel caso in cui $x\notin I$.

Nel caso di un insieme ricorsivamente enumerabile, siamo invece in grado di rispondere in un tempo finito, solo nel caso in cui $x\in I$, mentre negli altri casi potremo dover calcolare all'infinito.

Il complemento ${\overline {I}}$ di un insieme $I$, contiene tutti gli elementi che non sono contenuti in $I$, quindi se fossimo in grado di accorgerci in un tempo finito quando un qualunque elemento $x$ appartiene a ${\overline {I}}$ (è il caso in cui ${\overline {I}}$ è ricorsivamente enumerabile), vorrebbe dire che siamo in grado di accorgerci in un tempo finito di quando un elemento generico $x$ non appartiene a $I$. Per cui $I$ e ${\overline {I}}$ non sono solo r.e., ma anche ricorsivi.

Corollario: Se $S$ è r.e. ma non ricorsivo, allora il suo complemento ${\overline {S}}$ non è r.e., cioè formalmente:

$(S\in RE)\land (S\notin R)\Rightarrow \;{\overline {S}}\notin RE.$

Esempi di insiemi r.e.

Premessa: ricordiamo che ogni volta che utilizziamo la funzione $\varphi$, ci riferiamo a un'enumerazione delle funzioni ricorsive in cui la funzione $\varphi _{i}$ corrisponde alla $i+1$-esima funzione ricorsiva. Cioè detta $f$ la $i+1$-esima funzione ricorsiva, abbiamo:

$\varphi _{i}(y)=f(y).$

Gli insiemi

• ${\mathit {K}}=\lbrace x|\varphi _{x}(x){\text{ è definita}}\rbrace ;$
• ${\mathit {K'}}=\lbrace \left\langle x,y\right\rangle |\varphi _{x}(y){\text{ è definita}}\rbrace$ (problema della fermata);
• $\lbrace x|\varphi _{x}(c){\text{ è definita}}\rbrace$, dove $c$ è una qualunque costante;
• $\lbrace \left\langle x,y,z\right\rangle |\varphi _{x}(y)=z\rbrace$ (indecidibilità del valore di una funzione);

non sono ricorsivi ma r.e.

Limitazioni: insiemi non r.e.

Premessa: ricordiamo che ogni volta che utilizziamo la funzione $\varphi$, ci riferiamo a un'enumerazione delle funzioni ricorsive in cui la funzione $\varphi _{i}$ corrisponde alla $i+1$-esima funzione ricorsiva. Cioè detta $f$ la $i+1$-esima funzione ricorsiva, abbiamo:

$\varphi _{i}(y)=f(y).$

Insieme delle funzioni ricorsive totali

L'insieme ${\mathit {Tot}}=\lbrace x|\varphi _{x}{\text{ è totale}}\rbrace$ non è r.e. Questo insieme corrisponde al problema di stabilire se un dato programma rappresenta un algoritmo (cioè se esista o meno un input sul quale il programma non termina). Si differenzia dal problema della fermata per il fatto che l'input su cui far girare il programma non è definito a priori.

Dimostrazione:

1. Per ipotesi supponiamo che ${\mathit {Tot}}$ sia ricorsivamente enumerabile.
2. Dall'ipotesi precedente segue che per la prima definizione che abbiamo dato di r.e., poiché ${\mathit {Tot}}$ non è vuoto (esiste almeno una funzione ricorsiva totale), esiste una funzione ricorsiva totale ${\mathit {enum}}$ che lo enumera:

   $enum\colon \mathbb {N} \mapsto {\mathit {Tot}}$, con $\mathrm {Im} (enum)={\mathit {Tot}}.$

3. Allora definiamo una funzione totale $g$, in questo modo:

   $g(x)=\varphi _{enum(x)}(x)+1,$

   $g$ è totale perché $\varphi _{enum(x)}$ è a sua volta una funzione totale, dato che ${\mathit {enum}}(x)$ restituisce solo indici di funzioni totali, cioè ${\mathit {enum}}(x)\in {\mathit {Tot}}$ per definizione (punto 2).

4. Chiamiamo ${\mathit {\bar {i}}}$ l'indice della funzione $g$ nell'enumerazione delle funzioni ricorsive che abbiamo specificato nella premessa: $g=\varphi _{\bar {i}}.$
5. Poiché $g$ è totale, il suo indice deve appartenere all'insieme ${\mathit {Tot}}$ (${\mathit {\bar {i}}}\in {\mathit {Tot}}$).
6. Inoltre, poiché ${\mathit {enum}}$ enumera l'insieme ${\mathit {Tot}}$ di cui ${\mathit {\bar {i}}}$ fa parte, deve esistere un ${\mathit {\bar {x}}}$ tale che $enum({\bar {x}})={\bar {i}}.$
7. Come abbiamo detto al punto 4, $g=\varphi _{\bar {i}}$, quindi applicando ${\bar {x}}$ come parametro abbiamo $g({\bar {x}})=\varphi _{\bar {i}}({\bar {x}}).$
8. Inoltre partendo dalla definizione del punto 3, $g(x)=\varphi _{enum(x)}(x)+1$, e applicando ${\bar {x}}$ come parametro, otteniamo $g({\bar {x}})=\varphi _{enum({\bar {x}})}({\bar {x}})+1=\varphi _{\bar {i}}({\bar {x}})+1$, che è in palese contraddizione col punto 7.
9. Quindi dalla ipotesi che ${\mathit {Tot}}$ sia r.e. segue l'assurdo, cioè segue che sia il punto 7 sia il punto 8, che sono in contraddizione, sono veri. Per cui ${\mathit {Tot}}$ non è r.e.

Insieme delle funzioni ricorsive non totali

L'insieme ${\overline {\mathit {Tot}}}=\lbrace n|\varphi _{n}{\text{ non è totale}}\rbrace$ non è r.e. Questo insieme corrisponde al complemento dell'insieme ${\mathit {Tot}}$, e rappresenta l'insieme delle funzioni il cui valore non è definito per almeno un valore dell'argomento.

Dimostrazione: Supponiamo per assurdo che ${\overline {\mathit {Tot}}}$ sia ricorsivamente enumerabile. Per la seconda definizione di r.e., la sua funzione semicaratteristica

$\mathbf {1} _{\overline {\mathit {Tot}}}(n)=1{\text{ se e solo se }}n\in {\overline {\mathit {Tot}}}$

è calcolabile. Definiamo $cost_{x,y}()=\varphi _{x}(y)$ come la funzione identicamente uguale a $\varphi _{x}(y)$ e definiamo la seguente funzione:

$g(x,y)={\begin{cases}1,&{\text{se }}\varphi _{x}(y){\text{ è definita}},\\0,&{\text{se }}\mathbf {1} _{\overline {\mathit {Tot}}}(i)=1,{\text{ con }}\varphi _{i}=cost_{x,y}.\end{cases}}$

Dato che $cost_{x,y}$ è una funzione ricorsiva, l'indice $i$ tale che $\varphi _{i}=cost_{x,y}$ è calcolabile.

La funzione $g$ è ben definita ed è calcolabile, perché ci sono solo due possibilità incompatibili:

• Se $\varphi _{x}(y)$ è definita, allora $g(x,y)=1$; inoltre, $cost_{x,y}=\varphi _{i}$ è totale, dunque $i\notin {\overline {\mathit {Tot}}}$, da cui segue che $\mathbf {1} _{\overline {\mathit {Tot}}}(i)\neq 1,$ quindi $g(x,y)\neq 0$.
• Se $\varphi _{x}(y)$ non è definita, allora non lo è nemmeno $cost_{x,y}()$, quindi $cost_{x,y}=\varphi _{i}$ non è totale, ossia $i\in {\overline {\mathit {Tot}}}$, da cui segue che $\mathbf {1} _{\overline {\mathit {Tot}}}(i)=1,$ e siccome la funzione semicaratteristica di ${\overline {\mathit {Tot}}}$ è calcolabile, allora $g(x,y)=0.$ Infine, il fatto che $\varphi _{x}(y)$ non sia definita implica che $g(x,y)\neq 1$.

Segue che $g$ è la funzione caratteristica dell'insieme $K'$, e siccome $g$ è calcolabile allora $K'$ è un insieme ricorsivo, ovvero il problema della fermata è decidibile, in contraddizione con il teorema di Turing.

Complemento di K

L'insieme ${\overline {K}}=\lbrace y|\varphi _{y}(y){\text{ non è definita}}\rbrace$ non è r.e.

Dimostrazione: si vede facilmente dal fatto che $K$ è r.e. ma non ricorsivo, e applicando il corollario della proprietà sull'insieme complemento.

Procedure elencative e insiemi r.e.

In generale diciamo insieme ricorsivamente enumerabile un'entità $S$ individuata esplicitamente da una procedura elencativa $P_{S}$ e dal relativo elenco potenziale $E_{S}$; si dice anche che gli identificatori che compaiono in $E_{S}$ rappresentano gli elementi che appartengono a $S$. Per esprimere il fatto che $x$ denota un elemento di $S$ si scrive $x\in S$.

Questa definizione non esclude che $F_{S}$ presenti identificatori ripetuti; si può avere anche una procedura $P_{S}$ che emette stringhe che vengono replicate illimitatamente; in particolare si può incontrare una procedura che elenca solo un numero finito di tipi di stringhe ripetendone illimitatamente uno o più tipi.

Ogni insieme ricorsivamente enumerabile può essere individuato da diverse procedure elencative. Tra queste se ne può trovare una non ripetitiva. In caso contrario, di fronte a una procedura $P$ che si dimostra o si sospetta essere ripetitiva se ne può costruire una $P'$ equivalente non ripetitiva: si tratta di ampliare la $P$ con un meccanismo che controlla se ogni nuovo identificatore di elemento generato coincide o meno con un identificatore già emesso e nel primo caso evita di emetterlo.

Osserviamo che la nuova procedura non ripetitiva $P'$ risulta più complicata della $P$ e potrebbe essere molto meno efficiente. Quindi le procedure ripetitive di concezione semplice possono presentare interesse.

Disponendo di una procedura elencativa non ripetitiva si possono riscontrare diversi comportamenti.

1. Si dimostra che genera un elenco illimitato di elementi: in tal caso si individua un insieme numerabile.
2. Si dimostra che genera un elenco limitato di elementi. Si possono allora incontrare due comportamenti: (2a) si individua un elenco esplicito di elementi; (2b) con le risorse impiegate non si riesce a determinare effettivamente l'elenco esplicito completo degli elementi.
3. Non si riesce a decidere se l'elenco che la procedura va generando sarà illimitato o meno e con le risorse impiegate fino a un certo punto si dispone di un elenco parziale di elementi.

Idealmente si distinguono le procedure elencative (eventualmente non ripetitive) in grado di generare elenchi illimitati da quelle in grado di generare elenchi finiti. Volendo limitarsi alle informazioni che possono essere effettivamente acquisite, si deve invece tenere presente la possibilità di una procedura elencativa $P$ che, dopo l'eventuale generazione di un certo numero finito di identificatori, proseguendo nella sua evoluzione per un certo numero di passi non effettua alcun'emissione. In tale circostanza chi attende di conoscere la sua emissione viene lasciato nel dubbio sul comportamento della procedura:

1. dopo un'ulteriore attesa la $P$ emetterà altri identificatori e si arresterà;
2. si avrà il chiarimento del fatto che la procedura procederà a un'emissione illimitata che porterà a un insieme finito (2a) o numerabile (2b);
3. essa continuerà a comportarsi in modo che non si sappiano prevedere gli sviluppi successivi.

Le distinzioni precedenti non si possono considerare mere sottigliezze senza conseguenze. In effetti si dimostra che risulta impossibile fare nette distinzioni fra le procedure elencative, quando queste vengono considerate nella loro globalità. Più precisamente si dimostra impossibile costruire un meccanismo o definire una procedura che consenta di stabilire la classe di comportamento alla quale appartiene una generica procedura elencativa. Questo è un risultato che pone dei limiti molto seri alla portata dei metodi computazionali e della matematica e dovrebbe essere sempre tenuto ben presente.

Diciamo insieme contabile un insieme ricorsivamente enumerabile che si rivela essere finito o numerabile. Solo le procedure per le quali si trovano i comportamenti precedentemente individuati da 1. e 2. individuano insiemi che si possono considerare contabili.

Bibliografia

• Giorgio Ausiello, Fabrizio d'Amore, Giorgio Gambosi; FrancoAngeli Editore: Linguaggi, Modelli, Complessità (2003) (ISBN 88-464-4470-1)
• Brainerd, W.S., Landweber, L.H. (1974), Theory of Computation, Wiley, ISBN 0-471-09585-0