Insieme ricorsivamente enumerabile

termine
(Reindirizzamento da 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 si dice r.e. se esiste un algoritmo (o equivalentemente una funzione ricorsiva totale) che:

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

Oppure, equivalentemente,

  • genera in output tutti e soli gli elementi di .

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 formaliModifica

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 enumeratriceModifica

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

 

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-decidibileModifica

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

 

è calcolabile. In altre parole, se   è un sottoinsieme della controimmagine di  :

 

e   restituisce 1 tutte e sole le volte in cui l'input appartiene ad  . 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   si dice ricorsivamente enumerabile sse esiste una macchina di Turing tale che, se prende in input un elemento di  , allora termina.

Dimostrazione dell'equivalenza delle due definizioniModifica

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

Dobbiamo dimostrare che  

Partiamo dalla definizione di insieme ricorsivamente enumerabile:

 

è quindi possibile scrivere un programma   che ci dica se un elemento   simile al seguente:

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

La funzione calcolata dal programma è:

 

quindi   è un sottoinsieme della controimmagine di  :

 

sse

 

dunque, dato che  ,

 

dimostrando così l'uguaglianza tra le due definizioni.

La cardinalità della classe degli insiemi r.e.Modifica

È 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.Modifica

Unione e intersezioneModifica

Se gli insiemi   e   sono r.e., allora anche   e   sono ricorsivamente enumerabili.

Insieme complementoModifica

Se l'insieme   è r.e. e l'insieme complemento   (stiamo considerando   come universo) è anch'esso r.e., allora   è ricorsivo. Formalmente:

 .

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

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

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

Corollario:Se   è r.e. ma non ricorsivo, allora il suo complemento   non è r.e., cioè formalmente:

 .

Esempi di insiemi r.e.Modifica

Premessa: ricordiamo che ogni volta che utilizziamo la funzione  , ci riferiamo a un'enumerazione delle funzioni ricorsive in cui la funzione   corrisponde alla  -esima funzione ricorsiva. Cioè detta   la  -esima funzione ricorsiva, abbiamo:

 

Gli insiemi

  •  
  •   (problema della fermata)
  •  , dove   è una qualunque costante
  •   (indecidibilità del valore di una funzione)

non sono ricorsivi ma r.e.

Limitazioni: insiemi non r.e.Modifica

Premessa: ricordiamo che ogni volta che utilizziamo la funzione  , ci riferiamo a un'enumerazione delle funzioni ricorsive in cui la funzione   corrisponde alla  -esima funzione ricorsiva. Cioè detta   la  -esima funzione ricorsiva, abbiamo:

 

Insieme delle funzioni ricorsive totaliModifica

L'insieme   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   sia ricorsivamente enumerabile.
  2. dall'ipotesi precedente segue che per la prima definizione che abbiamo dato di r.e., poiché   non è vuoto (esiste almeno una funzione ricorsiva totale), esiste una funzione ricorsiva totale   che lo enumera:
     , con  
  3. allora definiamo una funzione totale  , in questo modo:
     
      è totale perché   è a sua volta una funzione totale, dato che   restituisce solo indici di funzioni totali, cioè   per definizione (punto 2).
  4. chiamiamo   l'indice della funzione   nell'enumerazione delle funzioni ricorsive che abbiamo specificato nella premessa:  
  5. Poiché   è totale, il suo indice deve appartenere all'insieme   ( )
  6. inoltre, poiché   enumera l'insieme   di cui   fa parte, deve esistere un   tale che  
  7. come abbiamo detto al punto 4,  , quindi applicando   come parametro abbiamo  
  8. inoltre partendo dalla definizione del punto 3,  , e applicando   come parametro, otteniamo  , che è in palese contraddizione col punto 7.
  9. quindi dalla ipotesi che   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   non è r.e.

Complemento di KModifica

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

Procedure elencative e Insiemi r.e.Modifica

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

Questa definizione non esclude che   presenti identificatori ripetuti; si può avere anche una procedura   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   che si dimostra o si sospetta essere ripetitiva se ne può costruire una   equivalente non ripetitiva: si tratta di ampliare la   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   risulta più complicata della   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   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   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.


BibliografiaModifica

  • 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

Voci correlateModifica

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