Insieme ricorsivamente enumerabile

Da Wikipedia, l'enciclopedia libera.

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 ad $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.

Indice

1 Definizioni formali
- 1.1 Esistenza funzione enumeratrice
- 1.2 Insieme semi-decidibile
2 Dimostrazione dell'equivalenza delle due definizioni
3 La cardinalità della classe degli insiemi r.e.
4 Proprietà degli insiemi r.e.
- 4.1 Unione e intersezione
- 4.2 Insieme complemento
5 Esempi di insiemi r.e.
6 Limitazioni: insiemi non r.e.
- 6.1 Insieme delle funzioni ricorsive totali
- 6.2 Complemento di K
7 Procedure elencative e Insiemi r.e.
8 Voci correlate
9 Bibliografia

[modifica] 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.

[modifica] Esistenza funzione enumeratrice

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

i m g (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 ad 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.

[modifica] Insieme semi-decidibile

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

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

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

d e f (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 ad $S$ , non termina.

[modifica] 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.

(da fare)

[modifica] La cardinalità della classe degli insiemi r.e.

(da fare)

[modifica] Proprietà degli insiemi r.e.

[modifica] Unione e intersezione

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

[modifica] 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$ , che 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 ad $\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 ad $I$ . Per cui $I$ ed $\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$ .

[modifica] Esempi di insiemi r.e.

Premessa: ricordiamo che ogni volta che utilizziamo la funzione $\varphi$ , ci riferiamo ad 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.

[modifica] Limitazioni: insiemi non r.e.

$\varphi_i(y) = f(y)$

[modifica] 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:

Per ipotesi supponiamo che $T o t$ sia ricorsivamente enumerabile.
dall'ipotesi precedente segue che per la prima definizione che abbiamo dato di r.e., poiché $T o t$ non è vuoto (esiste almeno una funzione ricorsiva totale), esiste una funzione ricorsiva totale $f e n u m$ che lo enumera:
$fenum:\mathbb{N} \to \mathit{Tot}$ , con $I m m a g i n e (f e n u m) = T o t$
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 $f e n u m (x)$ restituisce solo indici di funzioni totali, cioè $\mathit{fenum}(x) \in \mathit{Tot}$ per definizione (punto 2).
chiamiamo $\mathit{\bar{i}}$ l'indice della funzione $g$ nell'enumerazione delle funzioni ricorsive che abbiamo specificato nella premessa: $g = \varphi_{\bar{i}}$
Poiché $g$ è totale, il suo indice deve appartenere all'insieme $T o t$ ( $\mathit{\bar{i}} \in \mathit{Tot}$ )
inoltre poiché $f e n u m$ enumera l'insieme $T o t$ di cui $\mathit{\bar{i}}$ fa parte, deve esistere un $\mathit{\bar{x}}$ tale che $fenum(\bar{x}) = \bar{i}$
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})$
inoltre partendo dalla definizione del punto 3, $g(x) = \left ( \varphi_{fenum(x)} (x) \right ) +1$ , ed 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.
quindi dalla ipotesi che $T o t$ sia r.e. segue l'assurdo, cioè segue che sia il punto 7 che il punto 8, che sono in contraddizione, sono veri. Per cui Tot non è r.e.

[modifica] 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, ed applicando il corollario della proprietà sull'insieme complemento.

[modifica] 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 ad $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 ad 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.

Si dimostra che genera un elenco illimitato di elementi: in tal caso si individua un insieme numerabile.
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.
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:

(i) dopo una ulteriore attesa la

P

emetterà altri identificatori e si arresterà;

(ii) si avrà il chiarimento del fatto che la procedura procederà ad una emissione illimitata che porterà ad un insieme finito (2a) o numerabile (2b);

(iii) 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.

[modifica] Voci correlate

[modifica] 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 0471095850

Estratto da "http://it.wikipedia.org../../../i/n/s/Insieme_ricorsivamente_enumerabile.html"

Categorie: Teoria degli insiemi | Teoria della computazione

We provide Linux to the World