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)

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

Oppure, equivalentemente,

• che 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 totale $f$ tale che $S$ è l'immagine $f$:

$img(f) = S$

In questo caso la funzione f, per ogni naturale 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

$f(x) = \left\{\begin{matrix} 1 &\mbox{se}\ x \in S \\ \mbox{non definita}\ &\mbox{se}\ x \notin S \end{matrix}\right.$

è calcolabile. In altre parole se $S$ è il suo dominio di definizione:

$def(f) = 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 se esiste una macchina di Turing che quando prende in input un elemento di $S$ termina, mentre quando prende in input un elemento che non appartiene a $S$, non 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.

Partiamo dalla definizione di insieme ricorsivamente enumerabile:

$img(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) = \left\{\begin{matrix} 1 &\mbox{se}\ x \in S \\ \mbox{non definita/non termina}\ &\mbox{se}\ x \notin S \end{matrix}\right.$

quindi se

$\varphi_P(x) = f(x)$

il dominio di definizione di $f$:

$dom(f)=S$

dimostrando così l'uguaglianza tra le due definizioni.

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 $\bar{S} = \mathbb{N} - S$ (stiamo considerando $\mathbb{N}$ come universo) è anch'esso r.e., allora $S$ è ricorsivo. Formalmente:

$(S \in RE) \land (\bar{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 $\bar{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 $\bar{I}$ (è il caso in cui $\bar{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 $\bar{I}$ non sono solo r.e., ma anche ricorsivi.

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

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

Esempi di insiemi r.e.

Premessa: ricordiamo che ogni volta che utilizziamo la funzione $\varphi$, ci riferiamo a una 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) \grave{e} \mbox{ definita} \rbrace$
• $\mathit{K'} = \lbrace \left \langle x, y \right \rangle | \varphi_x(y) \grave{e} \mbox{ definita} \rbrace$ (problema della fermata)
• $\lbrace x | \varphi_x(c) \grave{e} \mbox{ 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 una 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(x) \mbox{ } \grave{e} \mbox{ totale} \rbrace$ non è r.e.

Dimostrazione per assurdo:

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{fenum}$ che lo enumera:
   $fenum:\mathbb{N} \to \mathit{Tot}$, con $Immagine(fenum) = \mathit{Tot}$
3. allora definiamo una funzione totale $g$, in questo modo:
   $g(x) = \left ( \varphi_{fenum(x)} (x) \right ) +1$
   $g$ è totale perché $\varphi_{fenum(x)}$ è a sua volta una funzione totale, dato che $\mathit{fenum}(x)$ restituisce solo indici di funzioni totali, cioè $\mathit{fenum}(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{fenum}$ enumera l'insieme $\mathit{Tot}$ di cui $\mathit{\bar{i}}$ fa parte, deve esistere un $\mathit{\bar{x}}$ tale che $fenum(\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) = \left ( \varphi_{fenum(x)} (x) \right ) +1$, e applicando $\bar{x}$ come parametro, otteniamo $g(\bar{x}) = \left ( \varphi_{fenum(\bar{x})} (\bar{x}) \right ) +1 = \left ( \varphi_{\bar{i}}(\bar{x}) \right ) +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 Tot non è r.e.

Complemento di K

L'insieme $\bar{K} = \lbrace y | \varphi_y(y) \mbox{ non } \grave{e} \mbox{ 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 una 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 alcuna emissione. In tale circostanza chi attende di conoscere la sua emissione viene lasciato nel dubbio sul comportamento della procedura:

1. dopo una ulteriore attesa la $P$ emetterà altri identificatori e si arresterà;
2.   si avrà il chiarimento del fatto che la procedura procederà a una 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.

Voci correlate

• Tipologia delle elaborazioni e delle procedure
• Insieme numerabile, definizione costruttiva
• Elaborazione con risorse illimitate e infinito potenziale
• Cardinalità e composizione di insiemi numerabili

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

Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica