Insieme ricorsivo

Da Wikipedia, l'enciclopedia libera.

Nella teoria della calcolabilità un insieme ricorsivo è intuitivamente un insieme di numeri naturali, per cui è possibile costruire un algoritmo che in un tempo finito (ma a priori non predeterminato) sia in grado, dato un qualunque numero naturale, di stabilire se esso appartiene o no all'insieme.

Più formalmente si dice che un insieme è ricorsivo se la sua funzione caratteristica è ricorsiva.

Definizione formale[modifica | modifica wikitesto]

Un insieme S, sottoinsieme dei naturali (S \subseteq \mathbb{N}), si dice ricorsivo se la sua funzione caratteristica

1_S:\mathbb{N} \to \left \{ 0,1 \right \}

con

1_S(x) = 
\left\{\begin{matrix} 
0 &\mbox{se}\ x \in S \\
1 &\mbox{se}\ x \notin S
\end{matrix}\right.

è ricorsiva e totale (la totalità è implicita nella notazione che abbiamo dato, che prevede che qualunque sia l'input, l'output sia sempre 0 oppure 1).

Proprietà[modifica | modifica wikitesto]

Insieme complemento[modifica | modifica wikitesto]

Se un insieme S è ricorsivo, allora anche il suo complemento \bar{S} = \mathbb{N} - S (stiamo considerando \mathbb{N} come universo) è ricorsivo.

Unione ed intersezione[modifica | modifica wikitesto]

Se A e B sono insiemi ricorsivi, allora anche A \cap B e A \cup B sono ricorsivi.

Ricorsivamente enumerabile[modifica | modifica wikitesto]

L'insieme A è ricorsivo se e solo se A e il suo complemento \bar{A} sono entrambi ricorsivamente enumerabili (Teorema di Post).

Immagine funzione ricorsiva totale[modifica | modifica wikitesto]

Se l'insieme A è un insieme ricorsivo, ed è anche il dominio di una funzione f: A \to B funzione ricorsiva e totale, allora anche B è ricorsivo.

Esempi di insiemi ricorsivi[modifica | modifica wikitesto]

Limitazioni: insiemi non ricorsivi[modifica | modifica wikitesto]

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)

Il problema della fermata[modifica | modifica wikitesto]

L'insieme

\mathit{K} = \lbrace \left \langle x, y \right \rangle | \varphi_x(y) \grave{e} \mbox{ definita} \rbrace


non è ricorsivo ma ricorsivamente enumerabile.

Insieme degli insiemi ricorsivi[modifica | modifica wikitesto]

L'insieme che contiene tutti gli insiemi ricorsivi, non è ricorsivo (e non è neanche ricorsivamente enumerabile).

Altri insiemi non ricorsivi[modifica | modifica wikitesto]

Molti dei seguenti sono riconducibili al problema della fermata, cioè per dimostrare che non sono ricorsivi si può usare la tecnica di riduzione all'assurdo, per mostrare che se fossero ricorsivi allora anche l'insieme \mathit{K} che rappresenta il problema della fermata lo sarebbe.

  • \lbrace x | \varphi_x(x) \grave{e} \mbox{ definita} \rbrace
  • \lbrace x | \varphi_x(c) \grave{e} \mbox{ definita} \rbrace, dove c è una qualunque costante
  • \lbrace x | \varphi_x \grave{e} \mbox{ costante} \rbrace (indecidibilità della costanza di una funzione)
  • \lbrace \left \langle x, y, z \right \rangle | \varphi_x(y)=z \rbrace (indecidibilità del valore di una funzione)
  • \lbrace \left \langle x, y \right \rangle | \varphi_x = \varphi_y \rbrace (indecidibilità dell'eguaglianza di due funzioni)
  • se x rappresenta la grammatica libera dal contesto d_x, \lbrace x | d_x \mbox{ } \grave{e} \mbox{ ambigua} \rbrace (problema di decidere se una grammatica libera dal contesto è ambigua)
  • l'insieme delle equazioni diofantee che ammettono radici intere

Voci correlate[modifica | modifica wikitesto]

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